From: an56238@anon.penet.fi (zaaaaaaaap!)
Date: Thu, 20 Jan 94 09:10:20 PST
To: cypherpunks@toad.com
Subject: RSA: questions
Message-ID: <9401201631.AA13465@anon.penet.fi>
MIME-Version: 1.0
Content-Type: text/plain



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

Karl Lui Barrus writes:
>
>I believe if p and q are well chosen (p-1 and q-1 have large prime
>factors, for example p = 2p'+1 and q=2q'+1 with p' and q' prime) then
>only two values of d will work as the decryption exponent.  This makes
>guessing d as "easy" as guessing either p or q in the first place.
>

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

>For example: p = 11 (p' = 5), q = 23 (q' = 11), n = 253, phi(n) = 220
>I picked e = 7, gcd(e,n) = 1, solve for d = 63
>The message 20 encrypts to 20^7  mod 253 = 136
>I make a brute force search for d by raising C to all possible values
>of d, from 1 to 253, looking for what decrypts to the original message.

I did a brute force search too in my first example. However, this is the
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.
So, to completely answer the question, you need to figure out the
distribution of prime number couples (p,q) that verify:
	p=2p'+1,	p' prime
	q=2q'+1		q' prime, p'!=q'

This way you'll be able to know how much you're shrinking key space.

- -zap


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

iQCUAgUBLT5QWCk+9PttYUp1AQFwHwP3T+DoLsQQf9C/LBWKv62AhGBxFIk/h1Zl
HnCtDwuJvbAG10RJ1Hg4uetdvtqyo+T3vfeFzExsdEBnPljGTNptpnJF5CXqVjB/
lbPAmxrFPUjOnSU0NbJcxfU73QTwq5Ep2Nj3uQu1RAdi0JptZ2wjIGnngrlXqCwT
RlLXRAMVAw==
=XuUd
-----END PGP SIGNATURE-----
-------------------------------------------------------------------------
To find out more about the anon service, send mail to help@anon.penet.fi.
Due to the double-blind, any mail replies to this message will be anonymized,
and an anonymous id will be allocated automatically. You have been warned.
Please report any problems, inappropriate use etc. to admin@anon.penet.fi.