Paper Menu >>
Journal Menu >>
![]() 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 Email: cristiand43@gmail.com, cristiand41@hotmail.com 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 xxx x. Otherwise, if 123 n ,,,, x xxxx is a solution for the equation *123 ,,,, n Eyyyy0, 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 |