On Fri, 10 Jan 2003, The Amazing Dragon wrote:
> They've chosen to include more information than required in the private
> portion, and prevent you from swaping the two keys. These are not
> requirements of RSA though. Simply swap the "D" and "Exponent" portions,
> and the system will decrypt when it suposed to be encrypting and vice
> versa. Note that this new public/private pair is a perfectly valid RSA
> key pair.
Such a pair of keys would be functional but you might lose all security
when you swap the exponents.
For instance, a public exponent (e) is often a small number (for instance
2^16 + 1 is a popular value) and there are known attacks (e.g. Wiener's
attack and its improvement by Bohen and Durfee) against small values of
a private exponent (d).
On Fri, 10 Jan 2003, Jason Coombs wrote:
> Worst-case, if a private key contains only p and q in addition to d then the
> n portion of the public key is known, which leaves only e unknown but e is
> easily derived when p, q, d and n are known and you are in possession of a
> sample of the ciphertext produced using {e,n} -- thus anyone who possesses a
> private key can derive the corresponding public key if the public key is
> ever used to produce ciphertext.
>
> The cryptanalysis would look something like this, based on reversing the key
> generation algorithm:
There is no cryptanalysis. You know p, q (and hence n = pq, and z =
\phi(n) = (p-1)(q-1)), and d. You compute e such that ed = 1 (mod z),
i.e. the modular inverse of d, the same way you would compute d from e
when generating a new key (using Euclid's algorithm). Game over.
The factorization of the modulus (n) must be kept secret by the owner of
the private key. In fact, p, q, or z do not have to be included in the
private key at all to make all the computations; implementors include them
for their own convenience (e.g. faster computation using CRT).
--Pavel Kankovsky aka Peak [ Boycott Microsoft--http://www.vcnet.com/bms ]
"Resistance is futile. Open your source code and prepare for assimilation."
This archive was generated by hypermail 2b30 : Sun Jan 12 2003 - 19:33:03 PST