03.RSA algorithm

RSA algorithm

Possible application of the Primality Test is used in public-key cryptosystems for example, which is commonly used for secure data transmission. The idea of asymettric encryption is:

1. $P$ (public key) and $S$ (secret key) can be computed efficiently
2. With a $P$ , $S$ :
3. $S$ is not computable from $P$ (without a quantum computer, during the life of this universe)

RSA algorithm steps (simplified, toy example):

1. randomly select two primes $p$ and $q$ of similar size, each with $l+1$ bits ( $l\ge 500$)
2. let $n=p\cdot q$
3. let $e$ an integer co-prime with $(p-1)(q-1)$
4. $d=(\frac{1}{e})mod((p-1)(q-1))$
5. $P=(e,n)$ and $S=(d,n)$
6. let $M=\text{message},C=M^{e}mod(n)\to M=C^{d}mod(n)$