From: Jim choate <ravage@bga.com>
Date: Mon, 13 Jun 94 11:59:14 PDT
To: cypherpunks@toad.com
Subject: Crytography - Solution (long) (fwd)
Message-ID: <199406131859.NAA26946@zoom.bga.com>
MIME-Version: 1.0
Content-Type: text


Forwarded message:
From hip-hop!benjie@amdahl.com Mon Jun 13 12:14:22 1994
Apparently-To: ravage@vern.bga.com, ean@u.washington.edu,
        reading@io.dsd.litton.com, kmj@bilbo.baylor.edu,
        marc@pxcl1.gi.rwth-aachen.de
Message-Id: <m0qDFEY-0000eFa@hip-hop.hh.sbay.org>
Date: Mon, 13 Jun 94 09:51 PDT
Sender: benjie@hh.sbay.org (Benjie KE6BCU)
From: ua532@freenet.victoria.bc.ca (David Snook)
Reply-To: ua532@freenet.victoria.bc.ca
Subject: Crytography - Solution (long)
Designated-To: Internet Amateur Mathematics Society
Replied-From: Internet Amateur Mathematics Society
Precedence: bulk
Sender: iams@hh.sbay.org (Internet Amateur Mathematics Society)
X-Info: email to listserv@hh.sbay.org with "FAQ iams" in the message
X-Ignore: iams  Ignore this line. It's a mailing-list-loop detector.



Iams Post. June 12/94


	The plaintext messsage was "Leonard Euler Pi", which was deciphered
by David Wagner of Princeton. It is Euler's Totient Function that is the
mathematical basis for the RSA Cryptographic System, hence the message. The
trailing "Pi" was included to minimize the possibility of a "lucky guess".

The 'cheap' scientific calculator, referred to in the original posting, was
an old Radio Shack EC-4024, programmable. The problem itself, however, was
set up on a 386DX using MathCAD and Qbasic.
   
Below, is a detailed method for deciphering the encrypted message, a brief
explanation of some of the how's and why's,  and a copy of the original
problem posting. Thanx.


David





*------------------------------------------------------------------------*
A Cryptographic Problem  ---------------------------------> The Solution:
*------------------------------------------------------------------------*

        N = p*q               (p) and (q) both prime        PUBLIC
   Phi(N) = (p-1)(q-1)        Totient function (Euler)
        E = Integer           (E)nciphering Key             PUBLIC

             -1
        D = E   mod Phi(N)    (D)eciphering key             PRIVATE

*-------*
STEP #1:
*------------------------------------------------------------------------*

You're given:      E = 2683

                   N = 83323
                   N = p*q     (p) & (q) both prime
By factoring:     
                   p = 97
                   q = 859

Then:        Phi(N)  = (97-1)(859-1)   
             Phi(N)  = 82368

*-------*
STEP #2:
*------------------------------------------------------------------------*

                        -1
You're given:      D = E   mod Phi(N)
                  DE = 1   mod Phi(N)
                   1 = DE  mod Phi(N)

Then:              1 = DE - (k * Phi(N))    Algebraic form of equation
                  DE =  1 + (k * Phi(N))

                   D = 1 + (k * 82368)      Where D must be integer
                       ---------------
                             E

                   D = 1 + (k * 82368)      
                       ---------------
                            2683

Set k = 1,2,3, ... i                        Trial and error .. k = 10


                   D = 1 + (10 * 82368)
                       ----------------
                            2683

                   D = 307                  !THIS IS THE DECIPHERING KEY!
                       
*------------------------------------------------------------------------*


*-------*
STEP #3:
*------------------------------------------------------------------------*
To recover the plaintext:

                        D
                   P = C  mod N
                    1   1

                            307
                   P = 48284    mod 83323                  See NOTE 1 
                    1

                   P = 3805
                    1

Look up (38) and (05) in the encoding alphabet:

                   M =  L e
                    1

Repeat STEP #3 for the remaining (C)iphertext blocks to obtain:  
 
 Message   =      L e   o n   a r   d     E u   l e   r     P i

 Plaintext =     3805  1514  0118  0463  3121  1205  1863  4209

 Ciphertext=    48284 65276 34353 19422 26879 31970 31567 52773

*-------*
NOTE 1:
*------------------------------------------------------------------------*
                 307
The number  48284    is very large,  so break up the process and handle
it piece meal as follows.

             1         1                 2
           (C  mod N)(C  mod N) mod N = C    mod N
             2         1                 3 
           (C  mod N)(C  mod N) mod N = C    mod N
             3         1                 4
           (C  mod N)(C  mod N) mod N = C    mod N

             etc.

             4         4                 8  
           (C  mod N)(C  mod N) mod N = C    mod N
             8         8                 16
           (C  mod N)(C  mod N) mod N = C    mod N
             16        16                32
           (C  mod N)(C  mod N) mod N = C    mod N

             etc.

Hint: (256+32+16+3) = 307
                                             2
The largest number to be processed is then  C , (11 digits) max. 
*------------------------------------------------------------------------*


*------------------------------------------------------------------------*
How it all works ........... and why!
*------------------------------------------------------------------------*

        N = p*q               (p) and (q) both prime        PUBLIC
   Phi(N) = (p-1)(q-1)        Totient function (Euler)
        E = Integer           (E)nciphering Key             PUBLIC

             -1
        D = E   mod Phi(N)    (D)eciphering key             PRIVATE
        1 = ED  mod Phi(N)    See below !!!


The sender enciphers her/his (P)laintext message, P, into (C)iphertext
blocks using the published, public keys E and N, as follows,

            E                                          E
       C = P  mod N     --------->       C  mod N  =  P   mod N

The receiver deciphers the (C)iphertext blocks by using her/his private
key D, and the public key N, as follows,

            D                             D            ED
       P = C  mod N     --------->       C  mod N  =  P   mod N

This is possible because the arithmetic performed in the exponent is
done Phi(N), such that,
                           Y           (Y mod Phi(Z))
                          X  mod Z  = X

*------------------------------------------------------------------------*

        D          ED         (ED mod Phi(N))
So:    C  mod N = P  mod N = P


But:   ED mod Phi(N) = 1                                    See above !!!

        D          ED         1
So:    C  mod N = P  mod N = P              The Original Plaintext Block!

*------------------------------------------------------------------------*

It is Euler's Totient Function that makes it all work. Hence the message.

*------------------------------------------------------------------------*


*------------------------------------------------------------------------*
A Crytographic Problem            May 22, 1994             David J. Snook
*------------------------------------------------------------------------*

	There has been a great deal of media discussion, about Clipper
Chips, information privacy, and the "cracking" of RSA-129. This problem
is designed around the underlying mathematics of modern crytographic
systems: RSA, in this particular case. (Rivest, Shamir, Adleman)

	The security of these systems is based on the fact that very
large numbers (200 digits) are very difficult and time consuming to
factor. The numbers associated with this problem are very small, in
crytographic terms, and therefore provide little or no security from
the amateur crypt-analyst. In fact, this problem can be solved with
paper, pencil and a "cheap" scientific calculator.

	Below, is a line of ciphertext, two(2) public keys, followed
by the procedures and equations used to encipher and decipher the message.

The problem ........ What was the original message?  


                  C     C     C     C     C     C     C     C   
                   1     2     3     4     5     6     7     8     

 Ciphertext=    48284 65276 34353 19422 26879 31970 31567 52773


 Key #1  N= 83323
 Key #2  E=  2683

*--------------------*
Procedures & Equations
*------------------------------------------------------------------------*

        N = p*q               (p) and (q) both prime        PUBLIC
   Phi(N) = (p-1)(q-1)        Totient function (Euler)
        E = Integer           (E)nciphering Key             PUBLIC

             -1
        D = E   mod Phi(N)    (D)eciphering key             PRIVATE

Enciphering was done, two(2) characters at a time, using the encoding
alphabet listed below to form (P)laintext blocks. Each block was then
raised to the power of E modulo N to produce the blocks of (C)iphertext.
There are eight(8) blocks of (C)iphertext with each containing exactly
two(2) characters.

             E                E                        E
        C = P  mod N ,   C = P  mod N ,  ........ C = P  mod N
         1   1            2   2                    8   8 

Deciphering is accomplished by raising each (C)iphertext block to the
power of D modulo N. This recovers the (P)laintext blocks and hence the
original message text. 

             D                D                        D
        P = C  mod N ,   P = C  mod N ,  ........ P = C  mod N
         1   1            2   2                    8   8 
*-------------------------------------------------------------------------*


*---------------*
Encoding alphabet
*-------------------------------------------------------------------------*
  a = 01    b = 02    c = 03    d = 04    e = 05    f = 06    g = 07
  h = 08    i = 09    j = 10    k = 11    l = 12    m = 13    n = 14 
  o = 15    p = 16    q = 17    r = 18    s = 19    t = 20    u = 21
  v = 22    w = 23    x = 24    y = 25    z = 26    A = 27    B = 28
  C = 29    D = 30    E = 31    F = 32    G = 33    H = 34    I = 35
  J = 36    K = 37    L = 38    M = 39    N = 40    O = 41    P = 42
  Q = 43    R = 44    S = 45    T = 46    U = 47    V = 48    W = 49
  X = 50    Y = 51    Z = 52    0 = 53    1 = 54    2 = 55    3 = 56
  4 = 57    5 = 58    6 = 59    7 = 60    8 = 61    9 = 62      = 63
  . = 64    , = 65    ; = 66    ? = 67
*-------------------------------------------------------------------------*
Plaintext example
*---------------*

 Message   =      S i   r     I s   a a   c     N e   w t   o n 

 Plaintext =     4509  1863  3519  0101  0363  4005  2320  1514

                   P     P     P     P     P     P     P     P    ... P
                    11    12    13    14    15    16    17    18        k 
*-------------------------------------------------------------------------*

--
David J. Snook.................................ua532@freenet.victoria.bc.ca