RSA - Algorithm

• Plaintexts are positive integers up to 2^{512}, ie. 512-bit blocks
• Keys are quadruples (p,q,e,d)
• p - 256-bit prime number
  q - 258-bit prime number
  d and e large numbers with (de - 1) divisible by (p-1)(q-1)
• C = E_K(P) = P^e mod pq [Euclid's algorithm]
• P = D_K(C) = C^d mod pq [Fermat test etc.]
• All quantities are readily computed from classic and modern number theory algorithms
• E_K is easily computed from the pair (pq,e)
• No easy way to compute D_K from the pair (pq,e)
• Therefore public key(pq,e)
• private key(pq,d)
• Attack is to factor pq into p and q
• Factorisation cannot be proved as slow, but it certainly not practical for key sizes ~1024 bits as used in PKI