RSA is an example of public key cryptography. It is a widely used system, relying for its security on the difficulty of factoring a large number.

Alice forms her public and private keys as follows:

  • Chooses large primes p and q, then form n=pq.

  • Chooses e coprimeMathworldPlanetmathPlanetmath with ϕ(n)=(p-1)(q-1).

  • Publishes (n,e) as her public key.

  • Computes private key d such that de1mod ϕ(n).

To encrypt a message M (where M<n) the user Bob forms C=Memod n.

To decrypt the message, Alice forms d(C)=Cdmod n.

This recovers message M because:

d(C) =Cdmod n
=(Me+rn)dmod n  for some r
=(M(p-1))t(q-1)Mmod n  for some t
(1+sp)t(q-1)Mmod p  for some s
Mmod p

So d(C)Mmod p and similarly, d(C)Mmod q so by the Chinese remainder theoremMathworldPlanetmathPlanetmathPlanetmath, d(C)Mmod n, and since we know M<n we know that M=d(C).

Title RSA
Canonical name RSA
Date of creation 2013-03-22 15:14:50
Last modified on 2013-03-22 15:14:50
Owner aoh45 (5079)
Last modified by aoh45 (5079)
Numerical id 5
Author aoh45 (5079)
Entry type Definition
Classification msc 94A60
Synonym RSA cryptosystem