Week 2 - RSA

Question 1

What is RSA?

Answer 1

used to generate a public + private key pair

Question 2

what is the first step?

Answer 2

Identify 2 large distinct prime numbers P and Q

Question 3

What is Step 2 (calculate n)?

Answer 3

n = p * q

Question 4

What is Euler’s function ϕ(n), and how is it calculated for RSA?

Answer 4

number of positive integers up to value of n, co prime with n

ϕ(n)=(p−1)(q−1)

Question 5

what is the public key in RSA?

Answer 5

e

e must be < ϕ(n) (euler’s function) and a COPRIME (prime and not a factor)

e is paired with n (e,n) <- public key

Question 6

How is the private key
D calculated in RSA?

Answer 6

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

(d,n) <- private key

Question 7

hat are the RSA encryption and decryption formulas?

Answer 7

Encryption=(plaintext)^e mod n

Decryption= (ciphertext)^d mod (n)
 

Question 8

Toy example

Answer 8

p = 5 q = 11

n = 5 * 11 = 55

ϕ(n)=(5−1)(11−1)
= 4 * 10
= 40

e < 40 & e must be a prime and not be a factor

e = 7

d = 7 ^-1 mod (40)

7 d= 1 mod (40)
d = 23

public key = (7,55)
private key = (23,55)

Encryption (public key)

p = 2

2^7 mod 55 = 18

Decryption (privatekey)

C = 18

18^23 mod 55 = 2