-----BEGIN PGP SIGNED MESSAGE----- Considering the general temperature of this list, I'm amazed that I didn't get torched over my algorithm. sigh. The c-punks are all too busy debating operating systems to worry about effiency in their remailers. Unless, of course, Hal's "I don't understand" was from the Moore school? Let's try this again. Let 2*x be the target number of bits in the modulous. Let n be a large random number with x+2 digits. Let n1 be the next multiple of 0x10001. Let t2 be n1 mod 8, t3 be n1 mod 9, t5 be n1 mod 25, t7 be n1 mod 49. Loop: For i = 2 to 7 If n1 = 1 mod i and (n1-1)/i + 1 is not a multiple of {2,3,5,7} If (n1-1)/i + 1 is prime. { Let k = 0's in n1/0x10001. If k is in range, save and exit. } EndIf EndIf Next n1 += 0x10001; EndLoop Recall: x^p = x mod p therefore, x^(p-1) = 1 mod p. So what we need is: (x^e)^d = x^ed = x^(p-1)*i+1 = x mod p. ie: ed = (p-1)*i+1 or: (ed - 1) / i + 1 = p Now 0x10001 inverts easily, it is just n1/0x10001. By keeping track of various quantities, we can eliminate all multiprecision divisions except for the original one needed to get n1 and the t's, and doing increments instead.
Yes, I see that you are right about this. It would be easy to generate e,d pairs and get a d which is significantly short on 1's by 10% or more. I did not quite follow your algorithm to do this (was n the modulus or was it phi, the sum of the modulus' divisors?). The one caveat is that if "high-zero" decryption exponents are widely used, it could conceivably reduce the search space somehow, although I don't see offhand how to exploit this.
Hal
(you may wish to ensure that k is _above_ a certain threshhold...)
I don't either, but if >80% of the digits were 0, I'ld probably start to get nervous. But I don't need a fast-key for my home system, I'm barely handing 10 signatures a day. I only advocate using high 0's when you are in a high usage environment. Nathan -----BEGIN PGP SIGNATURE----- Version: 2.6.2 iQEVAwUBLzA2NnmgMs8UcStNAQEyjQf/aOPBXcN6/M9cmh3aQHXeIr5uY3DEwvRw WHBtWv0dVE1jfSS/4i71apWi2+Gm7iRyLGc/G4Y03RkcqMhePGSHgN6NHEHC3QaR qoKMsa/h6z5nSMd/t8umTiSUJxFX2/1z8k29j7bM5gduUTqHPdFwcVnQnE8Rhy72 hwF+r3g9lFIhavsLFnT7KPeQ1ozVFJ+ItoTDWOOjjA8/MSGFi5JFkViw+saP2F/j 2JEbMhmMcjtTchu+s/yNVGJeL0C0DMjh2Ysh/wS/GwbcoXK1RFb602lXtCp2AUz5 Mzn9Xsdv4bUyyoumN5wT6YDdwu6QwvvU5Fh9sTZUwFHsY9RrMy53jQ== =lK0s -----END PGP SIGNATURE-----