5a. RSA Cryptosystem

B’s setup:

• choose two n-digit prime numbers $p,q$ at random
• B’s PK (public key) is pair $(N,e)$ where $N=pq$
• e is a small integer relatively prime to $(p-1)(q-1)$
• Private: computes d st. $ed\equiv 1\mathrm{mod}(p-1)(q-1)$

$(N,e)$ public key $d$ private key - needs to keep $p,q$ private.

A (sender):

• connects message into an integer m
• looks up B’s public key $(N,e)$
• computes $y\equiv m^e\mathrm{mod}N$
• sends encrypted y

B (decrypt): computes $m\equiv y^d\mathrm{mod}N$

Questions we should ask

1. Is this correct? Does $m\equiv y^d\mathrm{mod}N$?
2. Can we do the steps efficiently?
3. Why do we think this is secure?

Question 1: Correctness

Fermat's Little Theorem

If p is prime and $a<p$, then $a^{p-1}\equiv 1\mathrm{mod}p$

Given: $ed\equiv 1\mathrm{mod}(p-1)(q-1)$ Want to show:

$$\begin{array}{c}\begin{array}{r}{y}^d\equiv m(modN)\\ ⟺m^{ed}\equiv m\mathrm{mod}n\\ ⟺m^{ed}-m\equiv 0\mathrm{mod}N\end{array}\end{array}$$

Therefore $m^{ed}-m$ is divisible by N. Therefore $m^{ed}-m$ is divisible by p and Z

$ed=\lambda (p-1)(q-1)+1$ by definition of congruence

Therefore $m^{ed}-m$ is divisible by p and by q.

How do you compute d st. $ed\equiv 1\mathrm{mod}(p-1)(z-1)$ using Extended Euclidean Algorithm?

Bob picks n-digit x at random 
tests if x prime
	if yes, log x
	if no, pick another random until success

1. How likely is it for x to be prime?
2. How do you test it?

For #2, to test if x is prime

• pick a < x at random
• Compute $y=a^{k-1}\mathrm{mod}x$
• if y = 1, true
• if y != 1, false

If x is true, accept (Fermat’s Little Theorem)

There are some composite x’s (not prime numbers) that always pass the test - Charmichael Numbers These can still be tested for

Randomized Algorithm

Why is the system secure?