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!)