-----BEGIN PGP SIGNED MESSAGE----- From: Nathan Zook <nzook@bga.com>
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.
This would only be true for prime p, but with RSA we are dealing with composite moduli. What we want is ed=1 mod phi(n), where phi(n)=(p-1)(q-1). (Actually you want to use (p-1)(q-1)/gcd((p-1),(q-1)). I forget what that is called.) Conceptually, I gather you are setting e = 0x10001, then finding its multiplicative inverse d mod phi(n) (or mod p-1 in your example). Then you are looking for other possible values for d. I am a little unclear on what the interval would be between suitable values of d. I think it would be phi(n)/gcd as above, or p-1 in your example, but I am not sure.
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.
I still don't follow this. Is k claimed to be d? Where do we verify that ed=1 mod (p-1)? ed would be n1, right? When you said "If (n1-1)/i + 1 is prime" did you mean "is p"? I really don't think this whole thing works. Let me tell you what I tried. I inverted e to get a correct d. Then I looked at different d's to find one with lots of 0's. This turned out to be useless! The reasons is that PGP does not use d. It uses the Chinese Remainder Theorem to do its exponentiation. The two exponentiations it does use exponents d mod (p-1) and d mod (q-1). Adding multiples of phi to d does not change these values (since it is a multiple of both p-1 and q-1). Now one thing you could do is to use in place of d mod (p-1), (d mod (p-1)) + k*(p-1) where we choose k to minimize the sum of the number of bits and the number of 1 bits in this expression. Unfortunately the PGP data structures do not store d mod (p-1), it is constructed on the fly when you do a decryption. So there is no where to save a pre-computed optimal value for the two exponents used in the CRT exponentiations. So, this was a good idea, but the implementation does not fit into the current structure very well. Hal -----BEGIN PGP SIGNATURE----- Version: 2.6 iQBVAwUBLzA/mhnMLJtOy9MBAQEjmAIAzQbwkia3F7+4F7tNUewKnZVYsBEhgoBk h5jem/qjUxFeGhYNUL/pSLKJPR+PlzleZmBQJyOlk3q7KL0ety851g== =EHVe -----END PGP SIGNATURE-----