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(base2) m shifts, adds, and compares.
A continued product between the modulus and its multiplier which
matches a criterion solves the FermatEuler 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) =
(p1)(q1). 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 (p1)(q1)
To break RSA (i.e., solve the private key, given the public
key), one need only find the product (p1)(q1), 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, ... , n1 }:
/ (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 "exponentialtime"
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
4155957703
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 counterexample. 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 counterexample 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
5052927037
                                 
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) 2365897
Work: BLM, SC342D, Bldg 50, DFC, Denver, CO 802250047
Residence: CEC Services, 2080 Kipling St, Lakewood, CO 802151502
(303) 2319437 Voice [cjames@microksy.org & cojames@nyx.cs.du.edu]
(303) 2319438 Fax and Windows NT RAS to Ada repository (ftp soon!)