[cryptography] Why using asymmetric crypto like symmetric crypto isn't secure

James Muir muir.james.a at gmail.com
Sat Nov 3 21:32:21 EDT 2012


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



-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 198 bytes
Desc: OpenPGP digital signature
URL: <http://lists.randombit.net/pipermail/cryptography/attachments/20121103/30dff178/attachment.asc>


More information about the cryptography mailing list