Applied Mathematics, 2013, 4, 1635-1636
Published Online December 2013 (http://www.scirp.org/journal/am)
http://dx.doi.org/10.4236/am.2013.412222
Open Access AM
The RSA Cryptographic Protocol Is Not Secure
Cristian Dumitrescu
Kitchener, Canada
Received August 31, 2013; revised September 30, 2013; accepted October 7, 2013
Copyright © 2013 Cristian Dumitrescu. This is an open access article distributed under the Creative Commons Attribution License,
which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
ABSTRACT
In this article I describe a randomized algorithm based on random walks with two absorbing barriers that solves the sat-
isfiability problem (known to be NP complete) with arbitrary high probability. As a consequence of this algorithm, I
also prove that the RSA cryptographic protocol is not secure.
Keywords: The Satisfiability Problem; Hamming Distance; Random Walk with Two Absorbing Barriers
1. Useful Notions That Are Used for the
Analysis of the Algorithm
A Boolean expression is said to b e in conjunctive normal
form (CNF) if it is of the form 123 k,
and each Ei, called a clause (or conjunct), is of the form
123ii iir
EEE E

   , where each 
ij is a literal, either x
or x, for some variable x.
A Boolean expression is said to be in disjunctive nor-
mal form (DNF) if it is of the form 123 k
F
FF F ,
and each Fj, called a clause (or disjunct), is of the form
123jj jjr

  , where each

jk is a literal, ei-
ther y or y, for some variable y.
A Boolean expression in CNF form is called satisfi-
able if there is some assignment of 0’s and 1’s to the
variables that gives the expression the value 1.
The satisfiability problem is to determine, given a
Boolean expression, whether it is satisfiable. We note
that any Boolean expression E in CNF form has a dual
Boolean expression E* in DNF form (we only replace
every  with a , and replace every  with a ). For ex-
ample, if 



12341 23 4
,,,Exxx xxxxx
 

, then


2341 23 4
,xxx xxx

123
,,, ,
n
*1
,,Exx . We note that the
binary vector
x
xxx x represents a solu-
tion for the equation


1,2,3 ,, 1 n
Eyyyy 

12
,, (in CNF form) if the binary vector

,
n
x
xx x re-
presents a solution for the dual equation


*12
,,Eyy
12
,,Eyy
3
,,0
n
y y
  
3 123
,, 1,,, ,
n
yyEyy yy
. This follows immediately from
the equivalence



0
n
An expression is said to be 3-CNF if each clause has
exactly three distinct literals.

Theorem 1 (see Reference [1]). L3SAT, the satisfiabil-
ity problem for 3-CNF expressions, is NP-complete.
The Hamming distance dH(x, y) between two vec tor s x,
y is the number of components in which they differ. It is
known that the Hamming distance dH(x, y) satisfies the
conditions for a metric.
Related to the theory of symmetric random walks (in
one dimensi on ), we have the followi n g t heorem.
Theorem 2 (see Reference [2]). Limit theorem for first
passages. For fixed t, the probability that the first passage
through r occurs before epoch tends to
2
tr
1
21PN
t


 




, as , where N is the normal r
distribution func tion. We note that when , then P
tends to 1. t
2. The Description and Analysis of the
Algorithm
We consider a Boolean expression
in 3-CNF form with n variables. We want to determine
whether it is satisfiable.

123
,,,,
n
Eyy yy
Step 1. Randomly generate a binary vector


123
,,,,
n
x
xxx x, each xi, will be 0 or 1 in a random
manner.
Step 2. If


123
,,, ,
n
x
xxx x is a solution for the
equation


123
,,,, 1
n
Eyy yy, then return


,,
n123
,,
x
xxx x.
Otherwise, if


123 n
,,,,
x
xxxx is a solution for
the equation


*123
,,,,
n
Eyyyy0, then return


,
n12
,,
x
xx x.
Otherwise go to Step 3.

C. DUMITRESCU
1636
Step 3. Randomly choose a component of the vector x,
and flip its binary value. In other words, randomly
choose a value i in th e set {1, 2, ··· n}, and flip the value
of xi. If xi is 0, then put xi = 1, and if xi is 1, then put xi =
0.
Repeat Steps 2 and 3 for cycles (where t is a
fixed number). If no solution for our Boolean equation
has been found after cycles, then the 3-CNF ex-
pression under consideration is considered not satisfiable.
2
tn
2
tn
If the 3-CNF expression is not satisfiable, then the al-
gorithm will report that the expression is not satisfiable.
If the expression is satisfiable, then the initially randomly
generated vector will be at a certain Hamming distance d
from a solution of the equation 
123
,,,, 1
n
Eyy yy


,
and at Hamming distance n  d from the corresponding
solution of the equation


*
Ey
123
,,,, 0
n
yy y

. With
each cycle (in particular step 3), it is as likely that the
Hamming distance d will increase or decrease. The
Hamming distance d will increase or decrease with
probability 1
2. We basically have a symmetric random
walk with two absorbing barriers. From Theorem 2, we
see that by choosing a large t, we can make the probabil-
ity that the algorithm will fail as small as we want (we
say that the algorithm will fail if it reports that our 3-
CNF form is not satisfiable, when in fact it is satisfiable).
We can also use parallel computers (processors) that
deal with the same problem in parallel, an d the probabil-
ity that the algorithm will fail on all simultaneously will
be as small as we want. We can design the system so that
we can run the algorithm for many problems, for a time
comparable with the age of the Universe, and we can
expect it to fail once or twice. I think that this is accept-
able, in relation to practical applications. Since we are
dealing with a NP-complete problem, this algorithm will
solve a multitude of problems.
3. Applications
This algorithm will have applications in industry, medi-
cine, and many other domains of activity (where effi-
ciency is an issue, see Reference [3]). It can also be
proved that the RSA cryptographic protocol, on which
most of the Internet transactions and activity are based, is
not secure. RSA relies on the assumption that it is easy
to multiply numbers, but very difficult to factor them.
Here is an randomized algorithm for factoring large num-
bers, that is polynomial, and it is based on a random walk
with an absorbing barrier and a reflecting barrier.
We consider a large n-bit number N written in binary.
We want to factor it.
For m taking values from 1 to n, perform the following
three steps (actually, for each m, perform many cycles, as
escribed below). d
Step 1. Randomly generate an m-bit binary number x.
Step 2. If x is a divisor of N, then return x.
Otherwise go to Step 3.
Step 3. Randomly choose a bit of the m-bit number x,
and flip its binary value. In other words, randomly
choose a value i in the set {1, 2, ··· m}, and flip the i-th
bit of x.
Repeat Steps 2 and 3 for cycles (where t is a
fixed number).
2
tm
This algorithm runs for a total of cycles (where
the constant C can be determined), and it either finds a
divisor of N, or else says that N is prime (we make sure
that we exclude 1 and N itself, when we run the algo-
rithm, also other implementation details must be taken
into consideration), and the probability of failure will be
as sma l l a s we wa n t ( a similar theoretical analysis app li e s,
as described in the previous section, but here we have a
random walk with one absorbing barrier and one reflect-
ing barrier).
3
Cn
4. Conclusion
For all practical purposes, we can assume that P = NP,
even the conjecture P  NP might be true, if we exclude
randomized algorithms. It is also interesting to note that
all financial transactions over the Internet are based on a
cry ptographic protocol that is not secure. In Reference [4]
it is mentioned a somewhat similar algorithm for the 2-
SAT problem, which is not NP complete. The generali-
zation to 3-SAT and other NP complete problems and
possible applicatio ns of th ese ideas were presented in this
article.
5. Note
The symmetrical random walk model used here is just an
approximation. In fact, we have to use a random walk
with probabilities varying from place to place. This more
exact model could lead to more different conclusions
than presented here, in this article.
REFERENCES
[1] J. E. Hopcroft and J. D. Ullman, “Introduction to Auto-
mata Theory, Langiages, and Computation,” Addison-
Wesley Publishing Company, Cambridge, 1979.
[2] W. Feller, “An Introduction to Probability Theory and Its
Applications,” John Wiley & Sons, New York, 1968.
[3] L. Fortnow, “The Golden Ticket, P, NP, and the Search
for the Impossible,” Princeton University Press, Prince-
ton, 2013.
[4] C. H. Papadimitriou, “On Selecting a Satisfying Truth
Assignment,” Proceedings of the 32nd Annual Sympo-
sium on Foundations of Computer Science, San Juan, 1-4
October 1991, pp. 163-169.
Open Access AM