[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
RSA != RSA?
The final fundamental step in generating an RSA key pair is to compute the
decryption key, d, such that
e d === 1 mod (p-1)(q-1)
Or is it? RFC 2437, aka PKCS #1, RSA Labs's own spec for how to do RSA,
says that the modulus should be lcm(p-1,q-1), where lcm is Least Common
Multiple. Say what?!?
The original R/S/A paper in CACM, which is what the IPsec RFCs reference,
says (p-1)(q-1). So does Schneier 2nd edition, a common reference on
such things.
Clearly, any key pair built using the (p-1)(q-1) version will pass any test
based on the lcm version, since (p-1)(q-1) is necessarily an integer
multiple of lcm(p-1,q-1). However, the converse is not true: key pairs
built using the lcm version won't necessarily satisfy the stricter test.
(Unless I have missed something, there is *at best* a 50% chance that an
lcm key pair is also a (p-1)(q-1) key pair, since the lcm is guaranteed to
take out at least one factor of 2.)
I assume, without immediately being able to prove it, that either version
of the decryption key will actually work. This smells like an
optimization that somebody noticed after the original publication.
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.
God knows we have enough difficulties exchanging RSA keys already, since
no two groups seem to agree on a data format for it. But I thought we all
agreed on what an RSA key *is*!
Does anybody know the story behind this discrepancy?
Henry Spencer
henry@spsystems.net
Follow-Ups: