RSA Encryption Scheme

RSA, named after its inventors Rivest, Shamir and Adleman, was proposed in 1977 shortly after the discovery of public-key cryptography. 

RSA key pair generation

INPUT: Security parameter l.

OUTPUT: RSA public key (n, e) and private key d.

   1. Randomly select two primes p and q of the same bitlength l/2.

   2. Compute n = pq and φ = ( p − 1)(q − 1).

   3. Select an arbitrary integer e with 1 < e < φ and gcd(e, φ) = 1.

   4. Compute the integer d satisfying 1 < d < φ and ed ≡ 1 (mod φ).

   5. Return(n, e, d)

Basic RSA encryption

INPUT: RSA public key (n, e), plaintext m ∈ [0, n − 1].

OUTPUT: Ciphertext c.

   1. Compute c = m^e mod n.

   2. Return(c)

Basic RSA decryption

INPUT: RSA public key (n, e), RSA private key d, ciphertext c.

OUTPUT: Plaintext m.

   1. Compute m = c^d mod n.

   2. Return(m)

Implementations in Java

Implementations in .NET