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

Adam Back adam at cypherspace.org
Sun Nov 11 08:13:12 EST 2012


(I copied Hans-Joachim Knobloch onto the thread)

Weiner is talking about small secret exponents (small d), no one does that. 
They choose smallish prime e, with low hamming weight (for
encryption/signature verification efficiency) like 65537 (10001h) and get a
random d, which will by definition be |d| > |n|/4.  (The limit of Weiner's
algorithm).  

(To get both |d| < |n|/4 (susceptible to Weiner attack) and small |e| isnt
possible because you need ed = 1 mod LCM(p-1,q-1); which implies ed = 1 + k
LCM(p-1,q-1).  |LCM(p-1,q-1)| ~= |n| so to get |d| < |n|/4 you minimally
need |e| > 3|n|/4 ie for a 1024 bit modulus, |e| >= 768 bits to get a |d| =
256-bits.

The only people who would ever have ended up vulnerable to Weiner's attack
are those intentionally and aggressively trying to reduce the server
workload by aiming to artificially have very small |d|.

The Knobloch eprint paper says that you cant naively keep the public modulus
secret for small e, if the attacker has a few known plaintext/ciphertext
pairs because c = m^e mod n implies m^e -c = k.n and as k.n can be
factorized to find k.  (p & q will be harder to find so you'll find k first
if it is not also coincidentally itself large and prime, or composite of
large enough primes to not be factorizable; if it doesnt factorize quickly
use another known plaintext/ciphertext pair.

Note they are only saying fixed or small e because their approach requires
to know or guess e in order to compute m^e (if e is small you can try all
possible e).  

I wouldnt think thats the end of it either - more things are clearly
leaking.  eg Even with large, unknown e st |e| = |n| if you had known
plaintext ciphertext pairs with a multiplicative relationship like c1 = m1^e
mod n, and c2 = m2^e mod n and c3 = m3^e mod n where m3 = m1*m2.  Then
c1*c2-c3 = k.n and we're back to the find small factors to find k trick.

Adam

On Sat, Nov 10, 2012 at 10:52:29AM +0800, Sandy Harris wrote:
>On Sat, Nov 3, 2012 at 5:29 PM, Peter Gutmann <pgut001 at cs.auckland.ac.nz> wrote:
>
>>   [...] 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.
>
>Is this a different attack from Weiner's "Cryptanalysis of Short RSA
>Secret Exponents"?
>madchat.awired.net/crypto/codebreakers/ShortSecretExponents.pdf
>
>I thought it had been known for at least a decade that small exponents were
>a bad idea, because of the Weiner paper.
>_______________________________________________
>cryptography mailing list
>cryptography at randombit.net
>http://lists.randombit.net/mailman/listinfo/cryptography



More information about the cryptography mailing list