In response to Taneli Huuskonen [mailto:[EMAIL PROTECTED]]
Sorry to inflict this crapto on you. I came up with the algorithm when I
read Ariel Waissbein's post.
Waissbein said...
check if a number of size 2^1024, e.g. 2^(2^1024), is
congruent to 1 modulo the public exponent n. Hence you
at least need to store 2^1024 digits in your computer
which is a more than a lot.
I knew about generators of cyclic groups, but I was inspired by the need for
a solution to 2^X = 1 mod N, and I thought of shift-and-add on least
significant zero bits as a way of generating a covering of the bitmap of all
ones. Talk about synchronicity... I wrote and posted, then I ran out for
dinner (yes, you can flame me for not doing the literature search). Later,
I read through the web links, and saw that the solution was identical to the
one of de Velez that was torn apart by Rivest a day before (well, almost
synchronous).
I don't recall seeing de Velez's method explicitly discarding the low order
one bits to conserve memory once they are not needed. His inspiration
clearly comes from shift registers, so he could have defended his design by
observing that he could discard low order bits, but he didn't, and he caved
in to the experts. So I won't give him credit for that part, but he did
come up with shift-and-add first.
I violated the memory space constraint with the following snippet of code:
> # complete the solution.
> $b = $a * $n + 1;
> $x = -1;
> while ($b != 0) {
> $b >>= 1;
> $x++;
> }
It should be replaced with:
# complete the solution.
$x = $p;
$b++; # this is a power of 2
while ($b != 1) {
$b >>= 1;
$x++;
}
Please look over the code again. I wrote it to refute the argument that you
need to concurrently store all the digits for 2^X, which it doesn't, in
deriving the number 'a', in aN + 1. The low order one bits of 2^X - 1 are
discarded by a right shift after they have been computed and counted. At
every step, the addition may produce a carry bit beyond the register, but
shifting restores the sum within the bounds.
> Sorry to be a wet blanket, but it should be "O(N) time". As
> a factoring method, this is less efficient than trial division.
Wait a second. I seem to have confused some folks about what the above
algorithm accomplishes. It doesn't break RSA, it solves a problem in number
theory. And it doesn't take O(N). At worst, the outer loop is once per bit
of N (ie. log N) and the inner loop counts bits of N (again, log N). Ergo,
the routine runs in time O(log N)^2. If in breaking RSA, some specific
value of X is required other than the one that this routine finds, then yes,
you'll need to keep shifting and adding to find ever larger values of 'a'
and X. But I thought that this value of X is the order of 2, and that 2 is
a generator of the cyclic group 1 (mod N). I will humbly accept your
corrections in public, for the benefit of all.
<shuts eyes tightly and braces for flogging>
Robert Lacroix
