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

RSA Digital Signature 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 signature generation

INPUT: RSA public key (n, e), RSA private key d, message m.

OUTPUT: Signature s.

   1. Compute h = H (m) where H is a hash function.

   2. Compute s = h^d mod n.

   3. Return(s).

Basic RSA signature verification

INPUT: RSA public key (n, e), message m, signature s.

OUTPUT: Acceptance or rejection of the signature.

   1. Compute h = H (m).

   2. Compute h^` = s^e mod n.

   3. If h = h^` then return(“Accept the signature”);

       Else return(“Reject the signature”).

Implementations in Java
Implementations in .NET