# RSA-Based Signature Algorithms

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...?

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.

• Note that private key operations may have different security requirements than public key operations. Using one for another may lead to insecurity with regards to side channel attacks (!). Commented Jun 22, 2014 at 17:28
• I totally second that. When RSA signatures were first described (in the Disco era), the "encryption with the private key" analogy was used, and since then it has been an endless source of confusion. Commented Jun 22, 2014 at 17:51
• @ThomasPornin I feel a bit bad about attacking David though, he's done so much for Bouncy Castle libs :( . It's not personal, just a difference of opinion. Good book otherwise. Commented Jun 22, 2014 at 18:35
• I beg to differ. The book is hard to follow, not so much because of the subject, but because of the style.
– rapt
Commented Jun 23, 2014 at 20:17
• @rapt That's OK, hopefully you do agree on my answer :) Commented Jun 23, 2014 at 20:41

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 = Me mod N

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

decryption = (Me)d = Med mod N

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

## RSA signature

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

signature = Md mod N

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

signaturee = (Md)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.

• That answers my question (i.e. the author used somewhat misleading terms). But for this to work, the verifier first needs to make sure that the signer owns the public key they publish. This is done by proving that the signer is trusted (by someone that the verifier already trusts). If the signer is now trusted, then why does the verifier need to verify that the signer is truly signed on the signer's message?
– rapt
Commented Jun 3, 2014 at 22:04
• The signature is an integrity check, so the person who is verifying the message (called the relying party) is not just checking that the signer is trusted. The relying party is also verifying that the message has not be tampered with en route. In order to establish trust we use methods like web-of-trust or X.509 certificates. Commented Jun 4, 2014 at 6:39