On 12-11-03 05:29 PM, Jon Callas wrote: >> In the past there have been a few proposals to use asymmetric >> cryptosystems, >> typically RSA, like symmetric ones by keeping the public key secret, >> the idea >> behind this being that if the public key isn't known then there isn't >> anything >> for an attacker to factor or otherwise attack. Turns out that doing this >> isn't secure: >> >> http://eprint.iacr.org/2012/588 >> >> Breaking Public Keys - How to Determine an Unknown RSA Public Modulus >> Hans-Joachim Knobloch >> >> [...] We show that if the RSA cryptosystem is used in such a symmetric >> application, it is possible to determine the public RSA modulus if the >> public exponent is known and short, such as 3 or F4=65537, and two or >> more >> plaintext/ciphertext (or, if RSA is used for signing, signed >> value/signature) pairs are known. > > Great paper, however, the conclusions here and in replies are not quite > right. The paper itself says, > > it is possible to determine the public RSA modulus if the public > exponent is known and short, such as 3 or F4=65537, > > > Which immediately prompts the question of "what if it's long or secret?" > [1] This attack doesn't work on that. > > What it tells you is that if for some strange reason, you are going to > keep the public key secret, you need to make the exponent part of the > secret. That's the real, real lesson here -- an RSA key has an exponent > and a modulus and unless the exponent is secret, the key isn't secret. > And of course secret doesn't mean the usual ones just put in a cabinet.
Thanks for directing the thread back toward reality, Jon :-) I saw the eprint paper last week. It simply notes that if you have two plaintext/ciphertext pairs, (m1,c1), (m2,c2), for textbook RSA (i.e. RSA where you don't pad) and you know the public exponent, then you can compute the RSA modulus from N'=gcd(c1-m1^e, c2-m2^e). If e is small, then N' will be a small multiple of N; you can easily find the small factors of N' and remove them to get N. So, as Jon said, there's no point in hiding your RSA modulus if you are using a small public exponent like e=3, 17 or 2^16+1 and you are doing textbook RSA. However, no one should be doing textbook RSA. If you want to encrypt with RSA, then use RSA-OAEP. In that case, the gcd trick from the paper no longer works because the plaintext is salted -- the random bytes that form the salt aren't easy to obtain from a plaintext/ciphertext pair. It is possible that the modulus might still leak if you can analyze several RSA-OAEP plaintext/ciphertext pairs. That seems like a research type question to me. You could consider the same problem with RSA-PKCS1-v1.5. -James
signature.asc
Description: OpenPGP digital signature
_______________________________________________ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
