4
$\begingroup$

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?

$\endgroup$

2 Answers 2

6
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – KennnyCZ
    Aug 27, 2023 at 9:18
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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