Score:1

Crypto

In RSA, what if we get pInv instead of qInv?

oCriptoPanquer

7/10/24, 2:27 PM

I'm following the discussion in the question about RSA and what if we set $p<q$.

So, what if we mistakenly let $p<q$ and proceed with the private keys creations; that is, we pick up $p, q, e$ and derive from them: $dP,dQ, qInv$ (I'm using the CRT key structure in PKCS#1).

So, by trying to create those private-key elements, and forcing $p<q$, I see that they differ from those created when $p > q$, by the following:

$dP$ and $dQ$ values are swapped;
$qInv$ is calculated as $p^{-1} \bmod q$ instead of $q^{-1} \bmod p$.

My question: if some adversary asks the key owner to sign a chosen message $m$ and the owner:

First comes out with the ciphertext $c_{wrong}$, created from $p<q$;
So, the adversary complains that the signature verification is failing.
Finally, the owner fix .1 and .2 above, and give $c_{correct}$.

Can the adversary gain any advantage from learning $c_{wrong}$ and $c_{correct}$?

111

1 + 1

fgrieu

7/10/24, 2:48 PM

With their private key, the key owner would not _encrypt_. They would _sign_. In asymmetric cryptography, encryption always uses the public key.

Score:2

Crypto

poncho

7/10/24, 2:46 PM

I'm following the discussion in the question about RSA and what if we set $p<q$

Nothing bad will happen - the CRT algorithm we use doesn't actually depend on $p > q$ - it'll work both ways.

The standard algorithm to perform the final CRT step is:

$$m = m_q + q \cdot ((m_p - m_q) \cdot qinv \bmod p)$$

(where $m_p = c^{d_p} \bmod p$ and $m_q = c^{d_q} \bmod q$)

It is easy to see that $0 \le m < pq$ (if $0 \le m_p < p$ and $0 \le m_q < q$) and that $m = m_q \bmod q$ and (given $q \cdot qinv = 1 \bmod p$ ) that $m = m_p \bmod p$.

Because $p, q$ are relatively prime, there is only one such $m$ which meets all three criteria, and hence $m$ must be the proper decryption.

Note that none of the steps used the relative magnitude of $p$ and $q$ - they would all be true for either ordering.

So, the adversary complains that the decryption is failing.

Why would decryption fail?

Can the adversary gain any advantage from learning $c_{wrong}$ and $c_{correct}$?

Those are both valid ciphertexts; RSA (with correct padding) is CCA secure, and so there is no advantage.

The obvious follow-up question would be:

Why then did they specify that p > q in the first place?

Dunno - the question you linked to gives some plausible reasons why it might make an implementation easier.

+ 6

oCriptoPanquer

7/10/24, 3:00 PM

when I said "encrypt", I was thinking in "signing". So, does it make sense to say that the signature verification would fail?

poncho

7/10/24, 3:02 PM

@oCriptoPanquer: why would signature verification fail? You're using a perfectly valid private key.

oCriptoPanquer

7/10/24, 3:05 PM

let's suppose $p⋅=1 \bmod q$ is used instead of $⋅=1 \bmod$ Let's assume a bad implementation of OpenSSL.

poncho

7/10/24, 3:08 PM

@oCriptoPanquer: in that case (assuming deterministic signatures), the private key can easily be recovered. In that case, $m_{correct} = m_{wrong} \pmod q$ but $m_{correct} \ne m_{wrong} \pmod p$, hence computing $\gcd( n, m_{correct} - m_{wrong})$ immediately yields a factor ($q$)

fgrieu

7/10/24, 5:20 PM

@oCriptoPanquer: The only case I know where $p>q$ matters is in implementations that compute $m_p-m_q\bmod p$ as $m_p-m_q+p\bmod p$ and wrongly assume $m_p-m_q+p\ge0$ (where $m_p=c^{d_p}\bmod p$ and $m_q=c^{d_q}\bmod q$). But AFAIK that does not happen with OpenSSL.

oCriptoPanquer

7/10/24, 9:16 PM

I didn't get one detail: even when we have $m_{correct} = m_q + p(m_p - m_q).qInv \bmod p$ and $m_{wrong} = m_p + q(m_q - m_p).pInv \bmod q$, we can say that $m_{correct} = m_{wrong} \bmod q$? (one have *qInv* and the other *pInv*)

Elon Musk

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

EN: In RSA, what if we get pInv instead of qInv?

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.