# Is it possible to attack RSA with a WalkSat derivative?

We consider a large $n$-bit number $N$. We want to find a factor, if it admits any.

For $m$ taking values from $1$ to $n$, perform the following three steps (actually, for each $m$, perform many cycles, as described below).

1. Generate a random $m$-bit $x$.

2. If $x$ is a divisor of $N$, return $x$. If ~$x$ is a divisor of $N$, return ~$x$. (~$x$ is the complementary of $x$, basically flip every bit)
Otherwise go to Step 3.

3. Choose a random bit $x_i$ and flip its value. Repeat Steps 2 and 3 for $t * m^2$ cycles, if necessary (where t is a fixed number).

This algorithm runs for a total of $C * n^3$ cycles (where the constant $C$ can be determined), and it either finds a divisor of $N$, or else says that $N$ is prime.

The probability of reporting a false prime will be as small as we want, as we have a random walk with two absorbing barriers.

This is basically a WalkSat - type algorithm, and we define the Hamming distance and the random walk on the space of $m$-bit binary strings, where $m$ takes values from $1$ to $n$. We can probably run the random walk search directly for n - bit numbers, without the m - bit levelling (the algorithm can be improved).

Is this a feasible factorization algorithm? Could it be used to crack RSA in practice?

Sept. 2017. I found a fatal flaw in the mathematics long time ago (this is an older, edited question ). This particular algorithm is not efficient.

• Your algorithm obviously doesn't work. You should try it. – K.G. Nov 25 '13 at 22:59
• Are you looking for the error in your algorithm? That's not really crypto, it's the math behind crypto, so you should ask on Mathematics, or on Computer Science rather than here. Or are you wondering about the consequences on crypto if there was a way to factor integers in polynomial time (in which case why describe this obviously broken algorithm in so much detail)? – Gilles 'SO- stop being evil' Nov 25 '13 at 23:09
• Thank you for the above comments. I am pretty sure that the mathematics behind the algorithm is correct (if someone finds an error in the mathematics, I am sure that it is not obvious, look deeper). What are the consequences? – Cristian Dumitrescu Nov 25 '13 at 23:20
• None, since your algorithm is way too slow and/or has a way too small probability of success. $\hspace{.68 in}$ – user991 Nov 26 '13 at 1:05
• re close votes: Whilst this algorithm is clearly flawed, I do not think the question is unclear. There is no ambiguity, just some mathematical errors. – Cryptographeur Nov 26 '13 at 9:59

No, it not possible to attack RSA (and practical modulus size) with a WalkSat derivative, as far as we know, or using the algorithm in the question.

Problem with that algorithm is: in order to have a sizable/constant rate of success as $n$ increases, we have to repeat steps 2 and 3 not the stated $t\cdot m^2$ times, but rather $t\cdot 2^m$ times. That's because a divisor is found only when the random walk in steps 2/3 hits one of the few $m$-bit values that divides $N$, which we walk quasi randomly in a search space of $2^{m-1}$ values (refers to an earlier variant of the algorithm). The cost of the algorithm is thus not polynomial in $n$, but exponential in $n$. In fact, the algorithm is a randomized trial division, and has the same big-O cost.

Yes, RSA is secure as we know it — although recommended key sizes are ever-increasing, as expected. Any seemingly-simple result that suggests a long-studied, well battle-hardened cryptosystem is insecure should throw up red flags.

As an exercise, I wrote up your algorithm in simple C code:

#include <stdio.h>
#include <stdlib.h>

int main(int argc, char **argv) {
unsigned x = 2385065119;

srand(0); // deterministic randomness
unsigned test = rand();
char bit;
while (x % test != 0) {
do {
bit = rand() % 32;
test ^= (1 << bit);
} while (x == test || test == 1);
}

printf("found factor: %u\n", test);

return 0;
}


Hopefully I transcribed it correctly. It'll loop infinitely on prime numbers, however, so this is a simplified version.

I generated a random x with OpenSSL to factor. Note that this x is a mere 32 bits, far away from the size of numbers you'd find with modern-day RSA (which hover anywhere from 1024 to 4096 bits).

So, how fast is it?

$time ./a.out found factor: 890947 ./a.out 10.85s user 0.00s system 99% cpu 10.882 total  This was compiled with gcc -O3 and ran on a system with an Intel i5-3570k. Nearly 11 seconds. In comparison, Mathematica 8 completely factors the above x in 0.001606 seconds, as measured by AbsoluteTiming@FactorInteger. Hopefully this demonstrates the exceptional speed of modern-day factoring algorithms, and how yours compares to them. That I used srand(0), thereby making the program deterministic, severely affects the runtime length of your algorithm. Swapping over to srand(time(NULL)), the results were all over the place — sometimes it took as "little" as 1 second to find a factor, while at other times it took up to 22 seconds, in my (admittedly limited) testing. If you're wondering where you've erred in your analysis, note the line Repeat Steps 2 and 3 for t * m^2 cycles On average, it will take far longer than$m^2$"cycles" to find a factor; with the random walk method you're employing, you're essentially doing random trial division, except you're not doing even the most basic optimizations like only testing numbers up to$\sqrt{x}\$.

• Comments are not for extended discussion; this conversation has been moved to chat. – e-sushi Sep 4 '17 at 0:12

RSA is secure currently as we do not have an efficient way to factorize the two primes ( within our lives anyways.. ) HOWEVER, if factoring becomes easier or when quantum computers become more large scale and accessible you can expect them to be factored within minutes.

• Speak for yourself - I can factorize the primes in my head... – Cryptographeur Nov 27 '13 at 9:49
• I found a fatal flaw in the mathematics long time ago, this is a newly edited, but much older question. This algorithm is not efficient. The interested reader can read the new question "Assuming that NP = RP, how would this impact cryptography? " – Cristian Dumitrescu Sep 4 '17 at 1:24