RSA
algorithm, securityAlgorithm
- choose \(p\) and \(q\) primes
Miller-Rabin
- calculate module \(n = pq\)
- choose $e < (p-1)(q-1) such that \(\text{gcd}(e,(p-1)(q-1))=1\)
- calculate \(d=e^{-1} \mod (p-1) (q-1)\)
- \(K^{+} = <e,n>\) — \(K^{-} = <d,n>\)
This algorithm is Generalized Euclid’s Algorithm
Usage
Cypher: \(c = m^{e} \mod n\) Decypher: \(m = c^{d} \mod n\)
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)