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”).
