10. (RSA Public Key Cryptosystem) Let us pick two prime numbers p 41,q 67 Then,

Question

10. (RSA Public Key Cryptosystem) Let us pick two prime numbers p 41,q 67 Then, npq 41 67 2747 ?(n)-. (p-1)(q-1)-40 * 66 2640 We pick a small prime number s, with gcd(s, ?(n))-1. s-13. Then, t-s-1 mod ?(n)s 13-1 mod 2640-2437. (This inverse is computed by Euclid's algorithm.) The public keys are (s,n) and the private key (t, n). (a) Suppose a sender wants to send a number x 2169. Compute the encrypted message y. Make sure you perform a mod operation after each multiplication so the intermediate results does not become too large. Use the recursive algorithm Power to compute the exponentiation. (You may use an Excel sheet to generate the data.) Show the computation. (b) Compute the decrypted message z and verify that z x. Show the computation.

Explanation / Answer

Let's define power function first

def power_with_mod(number, exponent, mod):

if exponent == 0:

return 1;

result = power_with_mod(number, exponent/2, mod)

print "power_with_mod(%s, %s, %s) = %s" %(number,exponent/2, mod, result)

if exponent % 2 == 0:

return (result * result) % mod

else:

return (number * result * result) % mod

Here is complete computation with recursive power function

x = 2169

y = power_with_mod(2169, 13, 2747)

power_with_mod(2169, 0, 2747) = 1
power_with_mod(2169, 1, 2747) = 2169
power_with_mod(2169, 3, 2747) = 2560
power_with_mod(2169, 6, 2747) = 2005
y = power_with_mod(2169, 13, 2747) = 223

Decrypt the message

z = power_with_mod(223, 2437, 2747) ## y = 223, t = 2437, n= 2747

power_with_mod(223, 0, 2747) = 1
power_with_mod(223, 1, 2747) = 223
power_with_mod(223, 2, 2747) = 283
power_with_mod(223, 4, 2747) = 426
power_with_mod(223, 9, 2747) = 344
power_with_mod(223, 19, 2747) = 1246
power_with_mod(223, 38, 2747) = 461
power_with_mod(223, 76, 2747) = 1002
power_with_mod(223, 152, 2747) = 1349
power_with_mod(223, 304, 2747) = 1287
power_with_mod(223, 609, 2747) = 426
power_with_mod(223, 1218, 2747) = 174
z = power_with_mod(223, 2437, 2747) = 2169 = x

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

---

---

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