From: Karl Lui Barrus <klbarrus@owlnet.rice.edu>
Date: Fri, 21 Jan 94 12:38:15 PST
To: cypherpunks@toad.com
Subject: Re: RSA questions
Message-ID: <9401212022.AA11610@stygian.owlnet.rice.edu>
MIME-Version: 1.0
Content-Type: text/plain


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