RSA-Based Signature Algorithms

Question

From Beginning Cryptography with Java - chapter 4, digital signatures:

Signatures are created using the RSA algorithm by applying the RSA algorithm using the private key and then distributing the result as the signature. Because of the way the RSA algorithm works, this means the signature can be decrypted using the public key, giving you the process you see in Figure 4-5. The reason it works so well is that if a signature decrypts successfully with a given public key, then it must have been created with the corresponding private key.

"the signature can be decrypted using the public key"? I thought decryption is done by the private key...?

Answer 1

This is an ill-worded attempt at explaining RSA signatures. The basic operation - modular exponentiation - is the same for all RSA operations. So in that sense you can think of RSA signature verification as "decrypting" with the public key.

However, both the type of key as the message padding are an integral part of RSA operations. They are required to secure RSA operations. RSA padding is different for encryption and signature generation, even if both are informally called PKCS#1 v1.5 padding. The input parameters are generally also different; the signature generation requires the padding to be applied on a specific formatted hash value internally.

Public and private key operations differ in several ways. Both use modular exponentiation. However, private keys require additional protection to make sure that the secret components that make up the private key aren't leaked through side channel attacks. Private key also used a large exponent or multiple values that allow calculations using the Chinese Remainder Theorem (CRT). Saying that signature generation is encryption with the private key is therefore a very dangerous statement; internally they should be quite different operations.

---

I would urge you to simply read the RSA PKCS#1 v2.1 specifications in RFC 3447. They are quite readable, and they make a clear distinction between the various primitives in section 5.2:

The main mathematical operation in each primitive is exponentiation, as in the encryption and decryption primitives of Section 5.1. RSASP1 and RSAVP1 [EDIT: for signature generation / verification] are the same as RSADP and RSAEP [EDIT: for decryption / encryption, in that order] except for the names of their input and output arguments; they are distinguished as they are intended for different purposes.

This was different for PKCS#1 v1.5 and earlier versions of the PKCS#1 standard. The change in wording in PKCS#1 was very deliberate. Unfortunately the confusion remains when it comes to the OID that specifies an RSA public key, even one that is used for signature verification:

{iso(1) member-body(2) us(840) rsadsi(113549) pkcs(1) pkcs-1(1) rsaEncryption(1)}

This is a legacy of the older PKCS#1 version 1 standards, I'm afraid.

---

For more information, also see https://crypto.stackexchange.com/q/15997/1172.

Answer 2

First a quick review of RSA:

RSA encryption

In RSA encryption, you encrypt a plain text M by raising it to a public key e in a publicly known modulus N:

encryption = M^e mod N

To decrypt, you raise the encrypted text to the private key d:

decryption = (M^e)^d = M^ed mod N

The private and public keys are designed so that x^ed = x mod N for (almost) all x.

RSA signature

To sign a message M, you "encrypt" it with your private key d:

signature = M^d mod N

To check whether you have actually signed it, anyone can look up your public key and raise the signature to its power:

signature^e = (M^d)^e = M mod N

If the result is the message M, then the verifier knows that you signed the message.

Conclusion

In effect, in verifying a signature, the verifier is performing the same operation as someone who was decrypting the signature using the public key.