Cryptography/RSA

Last updated 3 years ago

Was this helpful?

Fermat's Little Theorem

The theorem states that for any prime p and any number $a \in \{1, ... p-1\}$ we have that $a^{p - 1} \equiv 1 \text{ mod }p.$

RSA starts off with two primes, $p$ and $q.$

We have $N:= pq$ and a number $e$ such that $\text{gcd}(e, (p - 1)(q-1)) = 1.$ Our private key is $d:= e^{-1}(\text{mod} (p - 1)(q - 1))$

E(x) = x^e \text{mod } N

D(x) = y^d \text{mod } N

Last updated 3 years ago

Was this helpful?

The theorem states that for any prime p and any number $a \in \{1, ... p-1\}$ we have that $a^{p - 1} \equiv 1 \text{ mod }p.$

RSA starts off with two primes, $p$ and $q.$

We have $N:= pq$ and a number $e$ such that $\text{gcd}(e, (p - 1)(q-1)) = 1.$ Our private key is $d:= e^{-1}(\text{mod} (p - 1)(q - 1))$

E(x) = x^e \text{mod } N

D(x) = y^d \text{mod } N