From: Karl Lui Barrus <klbarrus@owlnet.rice.edu>
Date: Thu, 7 Oct 93 12:05:42 PDT
To: cypherpunks@toad.com
Subject: Weak RSA keys?
Message-ID: <9310071903.AA25719@flammulated.owlnet.rice.edu>
MIME-Version: 1.0
Content-Type: text/plain


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@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