Score:4

Why does OpenSSL RSA signing process need the public exponent?

bz flag

I am trying to fully separate RSA key pairs by breaking down $(N,e)$ for public part and $(N,d)$ for private part. From my understanding of RSA signature process, the message to be signed is digested at first (using e.g., SHA256) and the digest is then encrypted using private key. The receiver of the message then calculates the exact same digest and could verify the source by using a public key to verify, that the signature matches.

If my understanding is correct, the owner of "private" key should only need the $(N,d)$ pair to calculate signature, and the owner of the "public" key should only need the $(N,e)$ pair.

However, when I try to use the EVP API of OpenSSL (3.1.0), the generated signature could not be verified, if the signing process does not know the $(N,d,e)$ triplet. Providing the EVP_PKEY_fromdata with OSSL_PARAM array containing solely the $N$ and $d$ (while $e$ being set to nullptr in the parameter builder) results in a seemingly valid signature, however, the verification process reports error:0200008A:rsa routines::invalid padding.

When I supply valid $e$ to the parameter builder, everything works as intended.

Am I missing something important here? Is my understanding of the signing and verifying process wrong or incomplete?

Score:6
my flag

One option that OpenSSL implements is 'blinding', which it uses to a way to avoid timing attacks.

What it does is, instead of computing $c^d \bmod N$ in the straight-forward fashion, it picks a random value $r$, computes $r^{-1} \bmod N$, and then computes first $m_{blind} = (c \cdot r^{-1})^d \bmod N$, and then $m = m_{blind} \cdot r^e \bmod N$.

Without $e$, the final computation of $m$ doesn't work.

OpenSSL 1.1 allowed you to turn this on/off using the RSA_blinding_on/off APIs. I'm not sure if version OpenSSL version 3 always has it turned on or not.

KennnyCZ avatar
bz flag
I somehow suspected, that it's a countermeasure for side-channel attacks, so your answer makes perfect sense to me. Thank you for your reply, now I see that separating the $(N,d)$ form is not suitable for my purposes.
Score:3
ng flag

I am trying to fully separate RSA key pairs by breaking down (N,e) for public part and (N,d) for private part.

There are performance, security and compatibility drawbacks to putting an RSA private key in the $(N,d)$ form. It's generally best to use the full form $(N,e,d,p,q,d_p,d_q,q_\text{inv})$ standardized as RSAPrivateKey by PKCS#1. If small private key size is paramount, we can use $(p,q,e)$, which is enough to easily compute $N=p\,q\,$, $d=e^{-1}\bmod\operatorname{lcm}(p-1,q-1)\,$, $d_p=e^{-1}\bmod(p-1)\,$, $d_q=e^{-1}\bmod(q-1)\,$, $q_\text{inv}=q^{-1}\bmod p$. While it's possible to factor $N$ from $N,e,d$ and find the smallest $e$ matching $d$, that's relatively complex.

The $p,q,d_p,d_q,q_\text{inv}$ terms exist to allow using the Chinese Remainder Theorem when computing $m\in[0,N)$ from $c$ with $c=m^e\bmod N$, and the private key. It's computed $m_p:=c^{d_p}\bmod p$, $m_q:=c^{d_q}\bmod q$, then $m:=((m_p\,q_\text{inv}-m_q)\bmod p)\,q+m_q$. This allows a large work reduction (by a factor up to nearly 4) compared to $m:=c^d\bmod N$. OpenSSL does that for signature at least when it has the private key in full form. That would also allow parallelization (for a total speedup by a factor up to nearly 8).

Often the absence of error during use of the private key is insured by verifying that $m^e\bmod N=c$. That's especially useful to avoid the Bellcore attack when the above CRT method has been used. However the check still is a good idea even when $N,d$ is used rather than $p,q,d_p,d_q,q_\text{inv}$.

I guess the OpenSSL signing process requires $e$ for said verification. Also, it needs $e$ to convert a private key in short form into the full form, which some code path does. Update: poncho's answer gives a better explanation than my guess: that $e$ is required for side-channel countermeasures.

I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.