# 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?

-
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 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}$ – Ricky Demer 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. – figlesquidge 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[2385065119]. 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}\$.

-
Technically, you haven't quite implemented the algorithm he listed. He included the step "For m taking values from 1 to n, perform the following three steps (actually, for each m, perform many cycles, as described below)."; you use a fixed m=32. I suspect that varying m improves the algorithm to a small degree (in the example you sited, the m=12 iteration has a good chance at stumbling upon a factor relatively quickly), however it is still quite pointless against an RSA number. – poncho Nov 26 '13 at 16:01
@poncho: Ah, that's true! Thanks. Still, as you say, I doubt it improves the performance to any noticeable degree. – Reid Nov 26 '13 at 19:01
There is a difference between random sampling and a random walk in a given abstract search space. I run through the steps described for t * m^2 cycles, unless a factor is found sooner. I do not run through the cycles until I find a factor. The Hamming distance between my random m - bit number and a factor (written in binary, if it exists), will increase or decrease, at each step, with probability 1/2. Based on a result in random walk theory, eventually I will hit on a solution if I run t * m^2 cycles, with very high probability (the alg. can be improved, but it is mathematically correct). – Cristian Dumitrescu Nov 26 '13 at 23:46
In order to understand this algorithm, please have a look at the WalkSAT - type algorithms, there are a lot of references about these algorithms om the Internet. This algorithm is in the same spirit. – Cristian Dumitrescu Nov 26 '13 at 23:53
@CristianDumitrescu: Can you verify that this implementation looks correct to you? If so, I'll update this post. – Reid Nov 27 '13 at 16:55

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... – figlesquidge Nov 27 '13 at 9:49