9.2 RSA-based signatures
An RSA-based signature is generated by applying the private key part of the RSA key pair to the hash value of the message m to be signed. To recap from Chapter 7, Public-Key Cryptography, Alice’s RSA key pair has the public key part PKAlice = (e,n), where n is the product of two large primes p and q, and e is some number that is coprime to φ(n) = (p − 1)(q − 1). Alice’s private key, on the other hand, takes the form SKAlice = d, where d = e−1 mod φ(n).
To encrypt some message m for Alice, Bob must encode m so that it is a number between 1 and n − 1. The cipher is then given by
Alice can decrypt it using her private key d via
In order to sign m, we can simply switch the order of the two operations, and use the private key d for encryption, except that we do not encrypt m itself, but its hash value H(m). To be specific,
Alice sends m along with the signature s = sigAlice(m) to Bob.
In order to verify...
