[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: RSA != RSA?
At 14:57 8.2.2001 -0500, you wrote:
>An addendum... I wrote:
>> I assume, without immediately being able to prove it, that either version
>> of the decryption key will actually work...
>
>Sandy Harris of our team promptly came up with a proof. So the added lcm
>is, presumably, an optimization.
It is an optimization (and obvious one).
>The problem naturally is not visible when exchanging *public* keys, since
>d is found only in the private key. It becomes an issue only when a key
>*pair* is being generated on one system for use by another, and the
>receiving system is being cautious and checking the key for consistency.
Then the consistency check should be (mod LCM). The condition
ed = 1 mod LCM(p-1, q-1) is a _necessary_ one for the key pair
(e, d) be "correct" for all possible plaintexts, that is, if it's
not satisfied then M^(ed) != M mod pq for a significant portion
of plaintexts M (at least, for all M which are primitive roots
mod p or those mod q).
So, checking (mod LCM), we check the _necessary_and_sufficient_
condition, can't be better.
>And this is an interoperability booby-trap that ought to be noted
>somewhere. It's a limited one, since it involves the private key, which
>isn't traded around a lot... but we ran into it in exactly that way, an
>interoperability failure. Preferably it should get explicit mention; at
>the very least, the IPsec RFCs should reference PKCS#1 as well as the
>original paper.
Very true.
Alexey
Follow-Ups:
References: