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