14
$\begingroup$

It is often said that RSA encryption of a cryptographic hash with a private key is the same as signing (signature generation). And that verification consists of decryption using a public key.

Is RSA encryption with a private key over a cryptographic hash equivalent to signature generation?

$\endgroup$
20
$\begingroup$

Short answer

No, RSA encryption with a private key is not the same as RSA signature generation. RSA encryption can only be performed with an RSA public key according to the RSA standard.

The terms Raw RSA or textbook RSA are often used to indicate RSA without a padding scheme. Raw RSA simply consists of modular exponentiation. Raw RSA is vulnerable to many cryptographic attacks and is not safe for general use.

Sources of confusion

It is often mentioned that signing is equivalent to RSA encrypting (the hash over) the message using the private key. This is only true if you disregard the required padding mechanism. The RSA padding mechanisms are different for encryption and signing.

Another reason why the two can be confused is that the public key is often identified with the ASN.1 OID for RSA encryption: 1.2.840.113549.1.1.1 or {iso(1) member-body(2) us(840) rsadsi(113549) pkcs(1) pkcs-1(1) rsaEncryption(1)}. This is for instance often the case within X.509 certificates. This OID is however generally used as a generic pointer to the PKCS#1 specifications; the unfortunate name is tied to the history of the X.509 and RSA specifications.

A deeper look into padding schemes

The PKCS#1 RSA Cryptography Specifications clearly define different schemes for RSA encryption and RSA signature generation.

The older PKCS#1 v1.5 standard contains two padding schemes that are often simply referred to as PKCS#1 v1.5. The padding for these encryption and signature schemes are however quite different, which is reflected by their official names RSAES-PKCS1-v1_5 and RSASSA-PKCS1-v1_5.

Fortunately the confusion that arises from two padding schemes with the same name is not present for the newer OAEP encryption - which uses RSAES-OAEP padding - and PSS signature generation schemes - which uses RSASSA-PSS padding. So the name of the padding for encryption and signature generation is different even though they rely on the same mechanism (called a mask generation function or MGF with one implementation: MGF1).

The actual modular exponentiation is mathematically the same for RSA encryption with a public key and RSA signature generation using the private key. This is easily verified by looking at the last part of paragraph 5.2 [emphasis mine]:

The main mathematical operation in each primitive is exponentiation, as in the encryption and decryption primitives of Section 5.1. RSASP1 and RSAVP1 are the same as RSADP and RSAEP except for the names of their input and output arguments; they are distinguished as they are intended for different purposes.

In general, a signature created by performing RSA encryption will fail if the other party correctly implemented the verification method.

However, some software libraries actually perform RSA padding for signature generation if the private key is used for encryption. One possible reason for this is SSL/TLS; versions of TLS up to v1.2 used a "signature" created from an MD5 hash concatenated with a SHA-1 hash. Such a scheme is often not compatible with the signature generation methods provided by RSA implementations, hence they rely on the RSA encryption routine to magically do the right thing.

RSA implementation notes

A lot of implementations do not allow encryption with a private key. Trying to simulate signature generation using private keys is often not possible. Implementations of public key operations often assume a small public exponent. Furthermore, they will generally not apply the Chinese Remainder Theorem that is used to speed up private key operations.

Note that public keys do not require protection against information leakage, while private keys should be kept secure at all times. Hence RSA encryption implementations - when programmed to be used with a public key - may not contain protection against side channel attacks, possibly exposing the private key to an attacker that is able to apply a side channel attack.

$\endgroup$
5
$\begingroup$

It depends on what you mean by RSA. If you mean the plain textbook RSA where $P = C^d \bmod n$ (decryption with private key $d$) and $S = M^d \bmod n$ (signature generation), then yes, they are the same.

However, textbook RSA is inherently unsafe, and for real-life RSA such as RSA-OAEP+ (encryption) or RSA-PSS (signatures) signing is not the same as decryption.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.