Sunday, September 9, 2012

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 = hd 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` = se mod n.
   3. If h = h` then return(“Accept the signature”);
       Else return(“Reject the signature”).

Implementations in Java
Implementations in .NET


  1. Great ! I am thankful to you for posting the detail about this popular algorithm that is used in majority of digital signature scheme. But a non technical person will find it difficult to understand, even you didn't have posted enough detail about each step.
    digital signatures

  2. This is fabulous.Great post!Thank you for sharing.Keep it up!!!

    - digital signature

  3. Hi there! glad to drop by your page and found these very interesting and informative stuff. Thanks for sharing, keep it up!

    - online signature