I will give one worked out example, followed by a partial one. (Recall that textbook RSA encryption is insecure and should not be used. This is just for illustration.)

Say the receiver chooses and . Then and . Take public exponent (one can verify that ). Then because . The receiver publishes the public key .

Say the sender wants to send the message . She would compute or and send the ciphertext 8321 to the receiver.

The receiver can decrypt the ciphertext 8321 by computing or . (Note: these numbers were already too large to be handled by ‘bc’ directly. One can compute the result in several steps, using the fact that . (Why?))

Now I’ll try a smaller example. Choose and , and take . What will the receiver’s public key be? What will it’s private key be?

Say the sender wants to send the message . What will the ciphertext be?

Verify that the receiver can correctly recover the message from the ciphertext.

September 30, 2009 at 12:18 pm |

Prof. Katz is the smaller example to compute on computer or manually? I am asking this, since I am writing a small example program which can be run on SAGE (this is a open source mathematic software which can be programmed with python and provides notebook mode for interactive examples. Sage is providing implementations variying from operations on finite field or elliptic curves and cryptography).

If it is allowed, I can provide a link to my example. Other students can play with it and do their on examples.

September 30, 2009 at 12:28 pm |

They

canbe done manually using ‘bc’ (that’s how I did it) but on an exam I would give smaller numbers.I don’t mind if you use Sage or any other programming language; the main point is to test your understanding.

October 2, 2009 at 7:49 am |

“One can compute the result in several steps, using

the fact that 8321^{13709} mod 17399 = 8321 * (((8321^2 mod 17399)^2 mod 17399)^{23} mod 17399)^{149} mod 17399 . (Why?))”

Because:

13709 = (2*2*23*149) + 1

October 2, 2009 at 2:35 pm |

p = 17, q = 23, e = 3

— N = p*q = 391

— phi(N) = (p-1)*(q-1) = (16)*(22) = 352

(Note that gcd(e,phi(N)) = gcd(3,352) = 1)

— private key = d = e^-1 mod phi(N)

= 3^-1 mod 352

= 235

— public key = (N, e) = (391,3)

m= 257

— c = m^e mod N = 257^3 mod 391 = 110

c = 110

— m = c^d mod N = 110^(235) mod 391 = 257