Here are the details why RSA is broken (so Ada developers of RSA and DES algorithms will know). What follows is in three sections: 1. The 1990 DRAFT paper by Bill Payne "Public Key Cryptography is Easy to Break"; 2. What Burt Kaliski of RSA "posted to sci.crypt a few days ago" from January 25, 1994 [which this reader must have missed]; and 3. The letter of Bill Payne to Kaliski of January 30, 1994 pointing out an enormous blunder by Kaliski in his "post". - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - DRAFT Public Key Cryptography is Easy to Break William H. Payne Sandia National Laboratories October 16, 1990 ABSTRACT Public key, also known as Rivest, Shamir, and Adleman, cryptography is broken without factoring the modulus m. The product of the encryption and the decryption exponent is computed directly with order log(base-2) m shifts, adds, and compares. A continued product between the modulus and its multiplier which matches a criterion solves the Fermat-Euler theorems simply for even large moduli. DRAFT Euler's theorem states phi(m) - a - 1 mod m - for a relatively prime to m where phi(m) is the number of numbers less than and relatively prime to m. For prime p and q, phi(pq) = (p-1)(q-1). For example, if p=5 and q=7, then (5x7) = 4x6=2x2x2x3=24. Then for any number of relatively prime to m, say 2, 24 - 2 - 1 mod 35 - Euler's theorem does not mean that 24 is the smallest value for which the equality is true. The values 2, 4, 8, 6, and 12 must also be checked to determine if they too may solve the equation. Here is an algorithm to solve Euler's theorem but it does not require factoring the modulus (from which the exponent is computed). The algorithm is extremely simple and obviously correct (to those who think in binary). Its explanation is best done by example so the reader can intuitively understand its importance and practical ramifications. The smallest even prime 2 is relatively prime to any odd modulus. Therefore, x - 2 - 1 mod 35 - for some value of x. This means that x 2 - 1 = 35y x for some value of y. A solution 2 -1 is represented in binary as 1 11 111 1111 11111 . . . for some value of x. Computation of 35y must be one of these values. Computation of y is easy. 35 in binary is 100011. A product of 35 times y is developed from right to left forcing the low order bits to one. The algorithm terminates when the high six bits are all one. Here is the algorithm computation. 1 0 0 0 1 1 1 0 0 0 1 1 ------------------ 1 0 1 0 1 1 1 1 1 0 0 0 1 1 --------------------- 1 0 1 1 0 1 1 1 1 1 1 0 0 0 1 1 ----------------------- 1 1 1 0 0 1 1 1 1 1 1 1 0 0 0 1 1 ------------------------- 1 1 1 1 1 1 1 1 1 1 1 1 12 11 10 9 8 7 6 5 4 3 2 1 which means 12 - 2 - 1 mod 35 - One are developed for the low order bits of the computation by shift and add. At each step of the algorithm the high order six bits are checked to see if they are all one. If so (the termination criterion) then algorithm terminates, and the solution is immediate. The algorithm finds the least value for which equality is true. The modulus can be a product of any number of primes excluding two, and the algorithm continues to work. The amount of work required for the algorithm to complete is a linear function of the number of bits in the modulus. Fermat's theorem gives a good example of the worst case amount of work for the theorem to execute. The algorithm finds x such that x - 2 - 1 mod 13 - Here are the computations. 1 1 0 1 1 1 0 1 ------------ 1 0 0 1 1 1 1 1 0 1 ----------------- 1 0 0 0 1 1 1 1 1 1 0 1 ------------------- 1 0 1 0 1 1 1 1 1 1 1 0 1 --------------------- 1 0 1 1 1 1 1 1 1 1 1 1 0 1 ------------------------- 1 1 1 1 1 1 1 1 1 1 1 1 12 11 10 9 8 7 6 5 4 3 2 1 or 12 - 2 - 1 mod 13. - The author discovered this result between 8:30 and 10:08 PM on October 15, 1990. Implications of the algorithm are great.* The author thanks Michael O. Vahle for conversations on strategies to break public key encryption which spanned several years. * More than Euclid's algorithm? - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - Posted to sci.crypt: ------ -- ---------- Bill Payne sent me a copy of his paper "Public Key Cryptography is Easy to Break" and gave me permission by phone to post a description. The quick summary is that his result, wile clever, actually confirms that RSA is still hard to break. Payne says he has better methods, though, which he hasn't published. RSA BACKGROUND An RSA key pair consists of a public key (n,e) and a private key (n,d), where n, the RSA modulus, is the product of distinct primes p and q, and where e and d (respectively the public and private exponents) satisfy the equation ed = 1 mod (p-1)(q-1) To break RSA (i.e., solve the private key, given the public key), one need only find the product (p-1)(q-1), which is usually denoted phi(n). Given phi(n) one can easily find p and q, so a method that finds phi(n) also factors n. PAYNE'S RESULTS According to Fermat's little theorem, for all a, one has a^phi(n) = 1 mod n Consequently, for a=2, one has that 2^phi(n)-1 is divisible by n. One can therefore find phi(n) (or a divisor of it) by constructing a multiple of n whose binary representation is all 1's. Payne's algorithm finds such a multiple by simple binary operations. The algorithm sets bits of an accumulator to 1 by adding shifts of the modulus n, working from least significant to most significant bit of the accumulator. Eventually the accumulator is all 1's, and the number of 1's yields a divisor of ph(n). Here is the algorithm: x := 0 i := 0 while x contains a 0 bit (other than leading bits) do if bit i of x is 0 then x:= x + ( n << i) i := i + 1 return length of x in bits By considering only the window of bits starting at bit i, one can view Payne's algorithm as applying repeatedly the following permutation on the set { 0, ... , n-1 }: / (w + n - 1) / 2 if w is odd f(w) | \ (w - 1) / 2 if w is even The window w at iteration i corresponds to the accumulator value x = 2^i w + 2^i - 1. Since the function f is a permutation, repeated application of f will eventually return to any given starting value. To find a multiple of n whose binary representation is all 1's, it suffices to start with w = 0. When repeated application of f arrives at w = 0 again, the value x = 2^i -1 will be a multiple of n whose binary representation is all 1's. There's only one problem: Finding x can take up to ph(n) steps! Since phi(n) is almost as large as n, if n is just ten digits long (not to mention the hundreds of digits in RSA), the amount of work is enormous. Indeed, this is an "exponential-time" algorithm for finding phi(n), the slowest kind. While Payne's algorithm is curious, public key is no easier to break. - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - January 30, 1994 Burt Kaliski, Chief Scientist RSA Laboratories 100 Marine Parkway Redwood City, CA 94065 415-595-7703 Dear Burt: Thank you for your January 25, 1994 letter and sci.crypt posting of my DRAFT paper results. I attach a copy for your immediate reference. I realize that the subject breaking RSA without factoring may be painful to you. I commiserate. I found your explanation interesting in several respects. I liked your explanation on the last page in terms of w. Very perceptive. There may be an incorrect statement in your posting. Your statement, "Given phi(n) one can easily find p and q, so a method that finds phi(n) also factors n.", I believe is false. Knowledge of phi(n) does not always lead to factors of n. Let me give you a counter-example. Phi(7 x 31) = phi(7) x phi(31) = 6 x 30 = 180. And phi(19 x 11) = phi(19) x phi(11) = 18 x 10 = 180 ! Do you agree? More than one product of two primes can map into the same totient! Even if phi(n) leads to factors of n, phi(n) must be factored. This could be a major computational task. Jim Omura told me that my algorithm is the first algorithm Omura has seen which breaks RSA without factoring. If you agree with my counter-example and Omura's opinion, then perhaps you might post a statement on sci.crypt. Your statement, "There's only one problem: Finding x can take up to phi(n) steps." may be, I believe inaccurate. But your statement is correct. Let me explain this apparent anomaly. You apparently do not know about indefinite division. The algorithm in my DRAFT paper generates a series of even numbers. The algorithm DRAFT paper I sent you did this from right to left termination, as you wisely pointed out, w = 0. But a similar algorithm also works left to right. Indefinite division, I call it. I mentioned this in my January 4, 1994 letter to you. I attach a copy for immediate reference. Therefore, the two algorithms can work simultaneously and meet in the middle of the sequence of even numbers. Phi(n)/2 maximum. Not phi(n). I quote from my January 4 letter to you, "Public key has big problems. I believe that the problems will _slowly_ come to light." You have my permission to post these observations on sci.crypt. I am sensitive to your statement "Bill Payne sent me a copy of his paper". I sent you a copy of a DRAFT paper. ..... Sincerely, /s/ Bill Bill Payne 13015 Calle de Sandias NE Albuquerque, NM 87111 505-292-7037 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - Note: Thanks are due to Mark Riordan (mrr@scss3.cl.msu.edu) who posts regularly to sci.crypt and has kindly agreed to post this message to sci.crypt for this transcriber, Colin James III (cjames@dsc.blm.gov). - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - Disclaimer: The opinions expressed here are responsible for their ~~~~~~~~~~~ content; all email is published at my sole discretion. - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - Colin James III cjames@dsc.blm.gov (303) 236-5897 Work: BLM, SC-342D, Bldg 50, DFC, Denver, CO 80225-0047 Residence: CEC Services, 2080 Kipling St, Lakewood, CO 80215-1502 (303) 231-9437 Voice [cjames@microksy.org & cojames@nyx.cs.du.edu] (303) 231-9438 Fax and Windows NT RAS to Ada repository (ftp soon!)