Weak RSA keys?

Karl Lui Barrus klbarrus at owlnet.rice.edu
Thu Oct 7 12:05:42 PDT 1993


I don't mean to flame you, but before you rush off and publish your
results somewhere you may want to step back and check over your premise
and the steps it involves a few times.

> The "spare" is 7.  The "spare" runs faster, too.  Go ahead, try it.
> The myth is that "ED = 1 mod (m)".
> The truth is as follows:
>	G = gcd( p-1 , q-1)  in this example G=2
>	F = m/G              in this example F=20
>	ED = 1 mod (F)

Now how exactly do you calculate this "F"?  Does it involve, say,
knowing phi(n), information ONLY available to you if you happen to
know the factorization of n?  In which case the whole thing collapses
anyway?

How can you use this information to decrypt a message?  If I were to
give you the 200 digit product of two primes, could you find the
"spare" key?  

If I get some time I'd like to look over your method to see if it's
really there or an artifact of the numbers you chose.  There is a
"weakness" easily shown in RSA in that for some keys, up to 9 messages
encrypt to themselves!  That is, M^e = M mod n.  Now, if you pick
large primes, these 9 messages will get lost in the 100 trillion
numbers every atom in the universe can have allocated, so it really
isn't a problem.

-- 
Karl L. Barrus: klbarrus at owlnet.rice.edu         
keyID: 5AD633 hash: D1 59 9D 48 72 E9 19 D5  3D F3 93 7E 81 B5 CC 32 

"One man's mnemonic is another man's cryptography" 
  - my compilers prof discussing file naming in public directories





More information about the cypherpunks-legacy mailing list