Question

Below is an example of key generation, encryption, and decryption using RSA. For the examples below, fill in the blanks to indicate what each part is or answer the question.

Public key is (23, 11) What is 23 called? _______________, What is 11 called?_______________

Private key is (23, 13) What is 23 called?_______________, What is 13 called?_______________

23 can be part of the public key because it is very hard to _______________ large prime numbers.

ENCRYPT (m) = m^e mod n What is m? _______________, what is n? _______________ (generic name, not a number)

DECRYPT (c) = c^d mod n What is c? _______________

What does "mod" mean?__________________________________________________________________________________________________________________

Everything in Bold is What I am Lost on? Teacher gave confusing example to solve.

EXAMPLE

An RSA public-key / private-key pair can be generated by the following steps:

1. Generate a pair of large, random primes p and q. NOTE for examples we use small prime numbers due to the size of the number generated.

p=3, q=5

2. Compute the modulus n as n = pq.

n = p*q, 15=3*5

3. Select an odd public exponent e between 3 and n-1 that is relatively prime to p-1 and q-1.

e is between 3 and 14, e is relatively prime to 2 (3-1) and 4 (5-1)

φ(n)=2*4=8

e=7, could also be 9 or 11 or 13

4. Compute the private exponent d from e, p and q. (See below.)

e^-1 = d (mod φ(n))

7^-1 = d (mod 8)

7 * d = 1 (mod 8) What number multiplied by 7 and then divided by 8 equals 1?

Multiples of 8	8	16	24	32	48	56	64	72	80	88	96	104
Multiples of 7	7	14	21	28	35	42	49	56	63	70	77	84	91	98	105

7 * 15 = 1 (mod 8) = 105/8= 13 remainder 1

d = 15

5. Output (n, e) as the public key and (n, d) as the private key.

PUBLIC KEY IS (15, 7) (Modulus, e), PRIVATE KEY IS (15, 15) (Modulus,d)

The encryption operation in the RSA cryptosystem is exponentiation to the e th power modulo n:

Plaintext = 8

ciphertext = ENCRYPT (m) = m^e mod n

c = 8^7 mod 15 = 2,097,152 mod 15 = 2 (ciphertext)

The decryption operation is exponentiation to the dth power modulo n: m = DECRYPT (c) = c^d mod n.

m= 2^15 mod 15 = 32,768 mod 15 = 8 (plaintext)

Answer 1