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?))”

    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.
    Can you please explain?

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: