About RSA

ppk

2021-10-30 2021-10-30 187 words One minute

Contents

choose two primes, $p$ and $q$
calculate $N = p \times q$
calculate $r = φ (N) = φ (p \times q) = (p - 1) (q - 1)$
- $φ$ is the Eular function, $φ (n)$ represents the number of integers prime with $n$
- if $n$ is a prime, then obviously $φ (n) = n - 1$
- $φ (mn) = φ (m) φ (n)$
choose $e$ no more than $N$ and prime with $r$
calculate $d$ such that $e d \equiv 1 mod r$
then $(e, N)$ is public key and $(d, N)$ is private key
don’t forget to destroy $p$ and $q$

Now Alice wants to send some message to Bob.

She needs to transform the message string into a integer $m$ no more then $N$ .

When Bob receive the ciphertext, he needs to decrypt it.

How to show that Bob can get right raw message?

c^{d} \equiv (m^{e})^{d} mod N \equiv m^{e d} mod N \equiv m^{t r + 1} mod N \equiv m \cdot m^{t r} mod N \equiv m \cdot (m^{φ (N)})^{t} mod N \equiv m \cdot 1^{t} mod N \equiv m mod N

The key point is $m^{φ (N)} \equiv 1 mod N$ when $g cd (m, N) = 1$

In fact, we can choose more than two primes at beginning.

For example, choose $n$ primes $p_{1}, p_{2}, \dots, p_{n}$

calculate $N = p_{1} \times p_{2} \times \dots \times p_{n}$

and calculate $r = φ (N) = (p_{1} - 1) (p_{2} - 1) \dots (p_{n} - 1)$

then everything is the same.

The difficulty to crack RSA decides to the difficulty to factoring a big intger.

The big intger is just $N$ and if we can factor it into some primes, then we can calculate $r$ , and get $d$ .

Contents