Textbook RSA examples

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 $p = 137$ and $q = 127$. Then $N=pq=17399$ and $\phi(N)=136 \cdot 126 = 17136$. Take public exponent $e=5$ (one can verify that $gcd(5, 17136)=1$). Then $d=13709$ because $5 \cdot 13709= 1 \bmod 17136$. The receiver publishes the public key $(N=17399, e=5)$.

Say the sender wants to send the message $m=16410$. She would compute $c=m^e \bmod N$ or $16410^5 = 8321 \bmod 17399$ and send the ciphertext 8321 to the receiver.

The receiver can decrypt the ciphertext 8321 by computing $8321^d \bmod N$ or $8321^{13709} = 16410 \bmod 17399$. (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 $8321^{13709} \bmod 17399 = 8321 \cdot (((8321^2 \bmod 17399)^2 \bmod 17399)^{23} \bmod 17399)^{149} \bmod 17399$. (Why?))

Now I’ll try a smaller example. Choose $p=17$ and $q=23$, and take $e=3$. What will the receiver’s public key be? What will it’s private key be?

Say the sender wants to send the message $m = 257$. What will the ciphertext be?

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

5 Responses to “Textbook RSA examples”

1. Anonymous Says:

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.

• jonkatz Says:

They can be 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.

2. Anonymous Says:

“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

3. Anonymous Says:

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

4. Brent Says:

How does that work? You say that d=13709 because 5*13709=1%17136.
But my question is that 1%anything always equals 1.
I am confused because 5*13709 does not equal 1.