Re: RSA questions

-----BEGIN PGP SIGNED MESSAGE-----

>That was the answer I was lookin for. Any more maths available ?
>(formulas!, formulas!) My paranoia hates the ``I believe'' part.

Yeah, I'll try to play with the math this weekend or something;
actually, Charlie Merritt posted some formulas...

>story of the snake biting its tail:if you choose p and q with the
>``nice'' properties you describe, you then restrict yourself to a
>subset of all possible values of p and q, thus shrinking the key space
>search for the possible attacker.

Hm.... I don't think you reduce the keyspace all that much.  The
restriction on e (and d) is they must be relatively prime to phi(n),
and if n = p q = (2p' + 1) (2q' + 1) then phi(n) = 4p'q', in which
case e (and d) can't be 2, 4, p', q', 2p', 2q', 4p', 4q', or 4p'q', a
total of 9 numbers out of the total possible.  I don't remember the
prime number theorem off hand (prime distribution), but for big
numbers the chances of stumbling on the correct d is essentially the
same as just guessing the factors of n in the first place.

There are other RSA artifacts: for example, a message may encrypt to
itself.  But you can minimize this (down to a max of 9 messages if
memory serves) by good choices for p and q.

So, choose good primes :)

Besides, an attacker hopefully won't have any information on the
primes you chose and will be forced to do a brute force search anyway.

Karl L. Barrus
klbarrus@owlnet.ric.ede



-----BEGIN PGP SIGNATURE-----
Version: 2.3a

iQCVAgUBLUA5PIOA7OpLWtYzAQGcgwQAmdiZwjSE3MgjvNF3AJDgSVKRICTNAGsQ
vloBoVNlFxtQVM8eqyxXJQt+5ydJpRIICaCg8lOOCaI3G4Y4xg/F4UGbvk5ev3tN
KohVP2jC33ngHPKQ5IkCuxEmvH0BKHaoTcIEQ4CcMGyxiyPTeixy3FtpZvoKrO2L
FlC55LWRZJI=
=7CZv
-----END PGP SIGNATURE-----

Karl Lui Barrus wrote:
>Hm.... I don't think you reduce the keyspace all that much.  The
>restriction on e (and d) is they must be relatively prime to phi(n),
>and if n = p q = (2p' + 1) (2q' + 1) then phi(n) = 4p'q', in which
>case e (and d) can't be 2, 4, p', q', 2p', 2q', 4p', 4q', or 4p'q', a
>total of 9 numbers out of the total possible.  I don't remember the

Argh, I left out p'q' and 2p'q', which brings the total to 11 unusable
numbers. 

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