RSA

Algorithm

1. choose $‘p‘$ and $‘q‘$ primes
   • Miller-Rabin
2. calculate modulo $‘n=pq‘$
3. choose $‘e<(p-1)(q-1)‘$ such that $‘\text{gcd}(e,(p-1)(q-1))=1‘$
4. calculate $d=e^-1 (p-1) (q-1)$¹
   • private key
5. $‘K^{+}=<e,n>‘$ — $‘K^{-}=<d,n>‘$

Usage

• Cypher: $‘c=m^e\mathrm{mod}n‘$
• Decypher: $‘m=c^d\mathrm{mod}n‘$

$‘\text{textsc}Proof‘$ using Euler’s Theorem², modulo used is $‘n‘$:

while, with $‘ed‘$ the multiplicative inverse of the private key :

we can conclude

Example with Bob and Alice:

• modulus $‘p‘$ and base $‘g‘$ are agreed publicly
• $‘a‘$ private Alice key
• $‘A‘$ public Alice key
  • $‘A=g^a\mathrm{mod}p‘$
• $‘b‘$ private Bob key
• $‘B‘$ public Bob key
  • $‘A=g^b\mathrm{mod}p‘$

Security

• hard - decypher without knowing $‘d‘$
• hard - calculating $‘d‘$ knowing $‘e,n‘$ without knowing $‘p,q‘$
• hard - calculating $‘p,q‘$ knowing $‘n‘$, with $‘n‘$ sufficiently big (at least 1024 bits)

Footnotes

1. The algorithm used is Generalized Euclid’s Algorithm, ↩

2. for $‘p,q‘$ primes: $‘\varphi (n)=\varphi (p\cdot q)=(p-1)\cdot (q-1)‘$ ↩