mlm@nl.cs.cmu.edu (Michael Mauldin) (07/13/87)
In article <15@nl.cs.cmu.edu>, mlm@nl.cs.cmu.edu (Michael Mauldin) writes: > Does choosing E to be a power of 2 work for RSA encryption? > > If E = 2**k, then exp(M,E) mod N is just k squarings of M (mod N). I meant 2**k + 1. Obviously if p & q are odd, then phi(p*q) = (p-1)(q-1) = product of two even numbers has 4 as a factor, and then gcd (2**k, phi(N)) >= 4. If E = 2**k + 1, then exp(M,E) mod N takes k+1 multiplications. Using 2**k + 1, you can even choose a relatively small k to further reduce the number of multiplications. With 100 digit p and q and 200 digit N, using E = 2**32 + 1 reduced encryption time from 169.4 seconds (on a microvax) to 6.8 seconds (25 times faster). The question still is, does this weaken the encryption? Is it easier to break RSA using E = 2**k+1 for relatively small k? Michael L. Mauldin (Fuzzy) Department of Computer Science ARPA: Michael.Mauldin@NL.CS.CMU.EDU Carnegie-Mellon University Phone: (412) 268-3065 Pittsburgh, PA 15213-3890