You have to write a program IN PYTHON language which will trace the execution of

Question

You have to write a program IN PYTHON language which will trace the execution of the RSA cryptosystem on a simple example. Make sure that you take the modulo after every operation i.e. it is not enough just to take the modulo after a long string of operations because the numbers can get so big that you get an overflow error.

(a) Alice choses her two primes to be p = 29 and q = 17 and multiplies them to obtain n = 493. Next, Alice randomly choses e = 15. Alice makes e and n public.

(b) You first need to calculate what Alice’s secret d will be. Your program should compute ?(n) = (p?1)(q ?1), and then your program should find the unique integer d (using brute force search here is OK) such that d is between 1 and n ? 1 and d · e mod ?(n) = 1.

(c) The cleartext message Bob wishes to send to Alice is M = 28. Bob looks up Alice’s public e and n, and then calculates (your program should do this) C = Me mod n. For full credit you should implement the fast divide and conquer modular exponential method discussed in class and the textbook; you will get partial credit if you implement the simple, inefficient and straightforward method for modular exponentiation.

(d) Alice receives the ciphertext C. She will then use her secret d to decipher Bob’s message by calculating (your program should do this) M0 = C d mod n. If you have done this correctly, the decoded message M0 should come out equal to the original message M. Again, for full credit you should implement the fast, divide and conquer modular exponential method.

(e) Your program should print out the following values; p, q, n, ?(n), e, d, M, C, M0 .

(f) Turn in the program listing (a print out of your program) and a print out of your program’s output. Please make sure it is well commented and easy to understand and follow

Explanation / Answer

# Iterative Python3 program

# (x^y)%p
def modularexponential(x, y, p) :
res = 1 # Initialize result

# Update x if it is more
# than or equal to p
x = x % p

while (y > 0) :

# If y is odd, multiply
# x with result
if ((y & 1) == 1) :
res = (res * x) % p

# y must be even now
y = y >> 1 # y = y/2
x = (x * x) % p

return res


# Driver Code
p=int(input('Enter prime p: '))
q=int(input('Enter prime q: '))
n=p*q
phi=(p-1)*(q-1)
e=int(input('Enter e value: '))
i=2;
# To find d value
while (i < n) :
temp=(i*e)%phi
if(temp==1):
d=i;
break;
i=i+1;   

# Message Bob wishes to send to Alice for example M = 28
M=int(input('Enter Message value: '));
C = modularexponential(M, e, n);

#Alice receives the ciphertext C and decrypt the messagee.   
M0=modularexponential(C, d, n)

print("Choosen primes:p=" + str(p) + ", q=" + str(q) );
print("n : " + str(n) );
print("?(n) : " + str(phi))
print("Choosen value e " + str(e) )
print("Calculated value D ",+d);
print("Encrypted Value C ",+C);
print("Decrypted value M0",+M0);

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.