Nathan Zook <nzook@bga.com> writes:
-----BEGIN PGP SIGNED MESSAGE-----
The algorithm I posted the second time works, (nice improvement, eh?) but is likely to take several thousand years to complete. And when it does, we can expect weak primes. The enhancement I propose should fix that.
I did not realize before that p was an output of your algorithm, rather than an input. That explains better what you were trying to do. You are in effect trying to search for a prime such that e's multiplicative inverse has a lot of 0's. This looks like it will work pretty well, with the caveat as we discussed before that going too far with this could make searching for the primes easier. But the only obvious attack would be to try to reproduce your prime-finding algorithm to find a p which divides the modulus n, and that is basically a sqrt(n) algorithm, which is far from the worst-case attack we face. The search space can be reduced by a considerable factor before it becomes competitive with modern algorithms. I guess another point is that if i is 2 or 4 then p itself will likely be 0-rich and conceivably there could be some attacks against a modulus known to be the product of two 0-rich primes even when the primes are not weak in the normal sense. (p = (ed-1)/i+1, d is 0-rich, and e has only 2 bits on so ed is likely also to be somewhat 0-rich; dividing by i is just a shift right if i is 2 or 4, and adding 1 won't make much difference.) Restricing i to other numbers would still give p a simple arithmetical relation to a 0-rich number (i=3 --> p*3 is 0-rich). Maybe you could choose a d such that d itself was 0-rich while ed happens not to be 0-rich; this might feel safer since p would have less of an arithmetical relation to a 0-rich number. (Admittedly, I don't know of any factoring attacks directly applicable to 0-rich factors but there is at least a superficial similarity to weak primes and that suggests caution.) Hal