Sunday, September 9, 2012

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 = me 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 = cd mod n.
   2. Return(m)

Implementations in Java
Implementations in .NET

1 comment :

  1. Amazing ! I am so happy that I found this article. You have posted the complete RSA encryption scheme. This article is of great help to me and I will do share it with all my friends too.
    digital certificates