From msuinfo!agate!howland.reston.ans.net!europa.eng.gtefsd.com!uunet!bloom-beacon.mit.edu!senator-bedfellow.mit.edu!athena.mit.edu!burt Sat Jan 22 17:09:40 1994 Path: msuinfo!agate!howland.reston.ans.net!europa.eng.gtefsd.com!uunet!bloom-beacon.mit.edu!senator-bedfellow.mit.edu!athena.mit.edu!burt From: burt@chirality.rsa.com (Burt Kaliski) Newsgroups: sci.crypt Subject: Re: RUMOUR: RSA has been broken! Comments please! Date: 19 Jan 94 16:53:58 Organization: RSA Data Security, Inc. Lines: 92 Distribution: world Message-ID: References: <2h4a60$nd@linus.mitre.org> <2h6e88$2vui@ep130.wg2.waii.com> NNTP-Posting-Host: rsa.com In-reply-to: mwj@se17.wg2.waii.com's message of 14 Jan 1994 15:37:44 GMT In article <2h6e88$2vui@ep130.wg2.waii.com> mwj@se17.wg2.waii.com (Michael W. Johnson) writes: Pardon me. I missed the early posts on this thread. Who is supposed to have broken RSA, and how was it done? Would someone please repost this? Actually, I was just about to fill in the details. The supposed break is due to Bill Payne, who 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, while 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 for 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 RESULT 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 phi(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 phi(n) steps! Since phi(n) is almost as large as n, if n is just tens of 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. ------------------------------------------------------- Burt Kaliski, Chief Scientist RSA Laboratories (415) 595-7703 100 Marine Parkway, Suite 500 (415) 595-4126 (fax) Redwood City, CA 94065 USA burt@rsa.com ------------------------------------------------------- From msuinfo!agate!library.ucla.edu!europa.eng.gtefsd.com!howland.reston.ans.net!cs.utexas.edu!news.unt.edu!sol.acs.unt.edu!fc14 Sat Jan 22 17:10:16 1994 Path: msuinfo!agate!library.ucla.edu!europa.eng.gtefsd.com!howland.reston.ans.net!cs.utexas.edu!news.unt.edu!sol.acs.unt.edu!fc14 From: fc14@sol.acs.unt.edu (Steve Tate) Newsgroups: sci.crypt Subject: Re: RUMOUR: RSA has been broken! Comments please! Date: 20 Jan 1994 02:24:40 GMT Organization: University of North Texas Lines: 17 Distribution: world Message-ID: <2hkq18$rc6@hermes.unt.edu> References: NNTP-Posting-Host: sol.acs.unt.edu X-Newsreader: TIN [version 1.2 PL2] Burt Kaliski (burt@chirality.rsa.com) wrote: > [Description of Bill Payne's algorithm deleted] > There's only one problem: Finding x can take up to phi(n) > steps! Since phi(n) is almost as large as n, if n is just > tens of digits long (not to mention the hundreds of digits > in RSA), the amount of work is enormous. That's actually a very cute trick, even if it's totally useless. One thing to point out if anyone still thinks that might prove some danger to RSA: The described method can take approximately n steps, but the most entirely stupid factoring algorithm you can think of takes only square_root(n) steps. In other words, the proposed method is lots worse than even the worst previously proposed technique (and both are highly unpractical). From msuinfo!agate!howland.reston.ans.net!europa.eng.gtefsd.com!MathWorks.Com!news.kei.com!bloom-beacon.mit.edu!senator-bedfellow.mit.edu!senator-bedfellow.mit.edu!not-for-mail Sun Feb 27 19:34:12 1994 Path: msuinfo!agate!howland.reston.ans.net!europa.eng.gtefsd.com!MathWorks.Com!news.kei.com!bloom-beacon.mit.edu!senator-bedfellow.mit.edu!senator-bedfellow.mit.edu!not-for-mail From: tytso@ATHENA.MIT.EDU (Theodore Ts'o) Newsgroups: sci.crypt Subject: Re: Non invertible encryption Date: 26 Feb 1994 10:39:02 -0500 Organization: The Internet Lines: 132 Sender: news@athena.mit.edu Distribution: world Message-ID: <2knqem$o40@senator-bedfellow.MIT.EDU> Reply-To: tytso@ATHENA.MIT.EDU (Theodore Ts'o) NNTP-Posting-Host: senator-bedfellow.mit.edu From: Colin James X-Mailer: SCO System V Mail (version 3.2) Who is the academic / industrial (non NSA) authority(s) on the subject. Dr. Burt Kaliski, Ph.D is certinaly one of the authorities; so is Professor Ron Rivest at MIT. Unfortunately, you may consider their views biased. :-) Seriously, though, I suggest you find any professor in mathematics, and ask them; the mathematics involved here are not hard. My degree was in computer science, but nevertheless, it seems fairly clear to me that Bill Payne has convinced himself that he has "squared the circle", and is squawking because no one is taking him seriously. If he really thinks RSA is so easy to crack, he should take some well-known public key, say one of RSADSI's PEM Public Certification Authority public keys, and demonstrate that he knows the factors of them. That will get him immediate attention, I promise you! Here are the details why RSA is broken (so Ada developers of RSA and DES algorithms will know)...... 3. The letter of Bill Payne to Kaliski of January 30, 1994 pointing out an enormous blunder by Kaliski in his "post". There were no enormous blunders by Dr. Kaliski, at least that I can detect. Let's review what was said in Payne's letter: 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. Only a few minutes thought is required to show that Dr. Kaliski's statement is true. Given n and phi(n), where n=pq, it is trivial to find p and q. In fact, it is so obvious that I can't fault Dr. Kaliski for not including the proof. (I'm not sure it would even make it as a homework question on an undergraduate math course. :-) Considering that Payne was not able to figure this out, my respect of him as a mathematician has taken another quantuum leap downward. Consider, and judge for yourself: Phi(n) = (p-1)(q-1) (Definition of Phi(n)) Phi(n) = pq - q - p + 1 (polynomial expansion) Phi(n) = n - q - p + 1 (substitution of n=pq) p = n - Phi(n) + 1 - q (rearranging the above) Since n and Phi(n) is known, one can easily compute n - Phi(n) + 1. So let K = n - Phi(n) + 1. p = K - q (from definition of K) n = (K-q)q (from n=pq) n = Kq - q^2 (algebraic manipulation) We now solve for q using the quadratic formula, and I will leave the rest as an exercise to the reader. 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. .... 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). Dr. Kaliski had just shown the following: ``Indeed, this is an "exponential-time" algorithm for finding phi(n), the slowest kind.'' You don't refute that argument by saying that you can reduce the time in half. A multiplicative factor of two is completely meaningless when you are talking about exponential-time algorithms. If Payne doesn't even realize this, he is completely ignorant of some of the fundamental principals of mathematic algorithm analysis. Even if you grant that his "indefinite division" buys you a factor of two, this doesn't change the fact that his algorthm is still O(2^n). Consider what an algorithm which is O(2^n) means; let's look at how fast various other different types of algorithms are: n O(1) O(n) O(n^2) O(2^n) 1 1 1 1 1 2 1 2 4 2 3 1 3 9 8 4 1 4 16 16 5 1 5 25 32 6 1 6 36 64 7 1 7 49 128 8 1 8 64 256 9 1 9 81 512 10 1 10 100 1024 11 1 11 121 2048 Do you see how rapidly the O(2^n) numbers are growing? They are doubling at every step. So just imagine how big 2**1024 is. And you will immediately realize that a factor of two is just completely in the noise. This is why for the purposes of computing "the big O" of an algorithm, O(0.5 * 2^n - 2n - 12) is still considered equivalent to O(2^n). If you don't believe me, ask any math professor, or indeed any computer science graduate from MIT --- at MIT, all C.S. students are required to take an algorithm class. One of the reasons for this is so that they won't embarass themselves as Payne has. :-) In summary, I see no evidence in the papers you have submitted to me that Payne has managed to "break" RSA. I do see evidence that Payne is missing a fundamental education in mathematics, or at least as far as algorithms analysis is concerned. This reminds me of the continuous streams of "proofs" submitted by people who know nothing about mathemtics that they are able to "square the circle", and are complaining that there is a conspiracy by the mathematical community since everyone refuses to look at their "proofs". The reason for this, of course, is that it has already been mathematically *proven* that it is impossible to "square the circle", and so matheticians, unless they are being very generous with their time, aren't going to bother looking for the hole in the proof which they know is there. Payne's case is somewhat different, since there is no conclusive proof that RSA is impossible to break. However, it shares similar elements in that someone who is an "outsider", who is apparently not trained in mathematics, is sure that he has found something which the rest of the mathematical community has completely missed. To be fair, this is possible, and has happened. However, in most cases, it is the outsider who is pathetically wrong. - Ted P.S. If someone could forward this analysis back to the ADA development list, I'd appreciate it.