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