Some Additional RSA information

From http://jya.com/whprsa.htm

16 May 1997
Source: William H. Payne
See related documents.


[No date]

[Handwritten: "(90)    NOT CORRECTED    (90)"]




                         RSA ENCRYPTION



                          W. H. Payne
                          Sandia Labs






                            Abstract


Rivest, Shamir, Adleman (RSA) public key encryption is based on

number theory.  While most individuals involved with encryption

and authentication understand how RSA is applied, many do not

understand how it works.  The purpose of this tutorial is to

explain how RSA encryption works by use of simple examples which

do not require a knowledge of number theory.  These examples

clarify mathematical and computer technical issues which must be

resolved to successfully implement RSA encryption.







[Hand written: "Not sent to Japan."]






                                [ 1 ]


Public Rey Encryption


Encryption transforms a message into another message which
appears to be indecipherable.  A transformation E converts the
message "This is Bill" into "zfgnkgnkrghh".  This is written

     E(This is Bill) = zfgnkgnkrghh

Decryption transforms the apparently indecipherable message into
a meaningful plain text message.  The corresponding decryption
transformation for E, called D, transforms "zfgnkgnkrghh" into
the plain text message.

     D(zfgnkgnkrghh) = This is Bill

Knowledge of E immediately reveals D for most cryptographgic
systems.  D=E for many systems.

Public key cryptography requires discovery of E from knowledge of
D to be computationally unfeasable.  RSA public key cryptography
uses modular arithmetic to construct encryption and decryption
functions.



Modular Arithmetic



Division has the parts

     o  dividend    number to be divided

     o  divisor     number to divide by

     o  quotient    how many time the divisor goes into the
                    dividend

     o  remainder   the number "left over".  This must be
                    between 0 and the divisor minus one.


                           2


For example

     13 = dividend

     3 = divisor

then

     4 = quotient

     1 = remainder

This can be written

     13 = 3x4+1

where x stands for "multiply".

If the divisor divides the dividend with a 0 remainder, the
divisor is said to "divide" the dividend.  For example, 3
divides 15 since

     15 = 3x5+0

"Divides" is used as a technical term to mean divides without
remainder.  The converse is "not divide".  For example 3 does not
divide 13.  This only means, of course, without 0 remainder.

Modular arithmetic is arithmetic using the remainder instead of
the dividend after division by the divisor.  The quotient is
ignored.  The divisor is called the "modulus".  The dividend is
"congruent" to the remainder modulo the modulus.  For example

     13 = 1 mod 3

= is read "is congruent to".

Modular arithmetic divides integers into "congruence or residue
classes".

     0 3 6  9 12 ... = 0 mod 3
     1 4 7 10 13 ... = 1 mod 3
     2 5 8 11 14 ... = 2 mod 3

0 3 6 9 12 ... belong to the 0 class mod 3.  1 3 7 10 13 ...
belong to the 1 class mod 3 while 2 5 8 11 14 ... belong to the 2
class mod 3.

Operations of addition and multiplication are valid using modular
arithmetic.  For addition examples

     3+4 = 7 = 1 mod 3


                           3


4+8 = 12 = 0 mod 3

and multiplication examples


     3x7 = 21 = 0 mod 3

     4xll = 44 = 2 mod 3

In both these examples the numbers could have been reduced by the
modulus before they were added or multiplied.

     3+4 = 3 mod 3 + 4 mod 3 = 0+1 = 1 mod 3

     4+8 = 4 mod 3 + 8 mod 3 = 1+2 = 3 = 0 mod 3

     3x7 = 3 mod 3 x 7 mod 3 = 0xl = 0 = 0 mod 3

     4xll = 4 mod 3 x 11 mod 3 = lx2 = 2 = 2 mod 3

Any number can be reduced by its modulus before further
modular arithmetic is performed.

Multiplication via a modulus gives rise to exponentiation.  For
example 35 mod 7 is computed

     35 = 32X32x3 = (32)2x3

            = (32 mod 7 )2 mod 7 x3

            = (2)2 mod 7 x3

            = 4x3 = 12 = 5 mod 7


which is the same as

     35 = 3x3x3x3x3 = 9x9x3 = 81x3 = 243 = 5 mod 7



Exponentiation



Exponentiation of integers less than the modulus modulo the
modulus give rise to fascinating properties of numbers, one
method for generating pseudorandom numbers on a computer, and
forms the basis for RSA encryption.

The following table contains powers of each integer from two to
one less than the modulus for the moduli 5 through 11.  If the
power of a number equals one, the cycle of numbers repeats.  On
the other hand, for some moduli successive powers never equal
one.  These numbers are commented "no solution".


                           4


mod 5
     1  2  3  4  5 power
2    2  4  3  1  2                  cycle 5
3    3  4  2  1  3                  cycle 5
4    4  1  4  1  4                  cycle 2


mod 6
     1  2  3  4  5  6  power
2    2  4  2  4  2  4               no solution
3    3  3  3  3  3  3               no solution
4    4  4  4  4  4  4               no solution
5    5  1  5  1  5  1               cycle 2


mod 7
     1  2  3  4  5  6  7  power
2    2  4  1  2  4  1  2            cycle 3
3    3  2  6  4  5  1  3            cycle 6
4    4  2  1  4  2  1  4            cycle 3
5    5  4  6  2  3  1  5            cycle 6
6    6  1  6  1  6  1  6            cycle 2


mod 8
     1  2  3  4  5  6  7  8  power
2    2  4  0  0  0  0  0  0         no solution
3    3  1  3  1  3  1  3  1         cycle 2
4    4  0  0  0  0  0  0  0         no solution
5    5  1  5  1  5  1  5  1         cycle 2
6    6  4  0  0  0  0  0  0         no solution
7    7  1  7  1  7  1  7  1         cycle 2


mod 9
     1  2  3  4  5  6  7  8  9  power
2    2  4  8  7  5  1  2  4  8      cycle 6
3    3  0  0  0  0  0  0  0  0      no solution
4    4  7  1  4  7  1  4  7  1      cycle 3
5    5  7  8  4  2  1  5  7  8      cycle 6
6    6  0  0  0  0  0  0  0  0      no solution
7    7  4  1  7  4  1  7  4  1      cycle 3
8    8  1  8  1  8  1  8  1  8      cycle 2


mod 10
     1  2  3  4  5  6  7  8  9  10 power
2    2  4  8  6  2  4  8  6  2  4   no solution
3    3  9  7  1  3  9  7  1  3  9   cycle 4
4    4  6  4  6  4  6  4  6  4  6   no solution
5    5  5  5  5  5  5  5  5  5  5   no solution
6    6  6  6  6  6  6  6  6  6  6   no solution
7    7  9  3  1  7  9  3  1  7  9   cycle 4
8    8  4  2  6  8  4  2  6  8  4   no solution
9    9  1  9  1  9  1  9  1  9  1   cycle 2


mod 11


                            5


1  2  3  4  5  6  7  8  9 10  11 power
 2    2  4  3  5 10  9  7  3  6  1  2    cycle 10
 3    3  9  5  4  1  3  9  5  4  1  3    cycle 5
 4    4  5  9  3  1  4  5  9  3  1  4    cycle 5
 5    5  3  4  9  1  5  3  4  9  1  5    cycle 5
 6    6  3  7  9 10  5  8  4  2  1  6    cycle 10
 7    7  5  2  3 10  4  6  9  8  1  7    cycle 10
 8    8  9  6  4 10  3  2  5  7  1  8    cycle 10
 9    9  4  3  5  1  9  4  3  5  1  9    cycle 5
10   10  1 10  1 10  1 10  1 10  1 10    cycle 2



Additive and multiplicative inverses



The additive inverse of a mod m is b where

     a+b = 0 mod m

and the multiplicative inverse of a is b where

     axb = 1 mod m

For example

     3+4 = 0 mod 7       3 is the additive inverse of 4

     2+5 = 0 mod 7       2 is the additive inverse of 5

     3x5 = 1 mod 7       3 is the multiplicative inverse of 5

     4x2 = 1 mod 7       4 is the multiplicative inverse of 2

RSA encryption uses exponentiation for encryption and decryptlon.
The decryption exponent, D, is derived from the encryption
exponent, E, by solution of

     ExD = 1 mod m

The exponentiation tables reveal one method for solving this
equation.  For example, for D=3 find E.

     3xE = 1 mod 11

From the tables

     35 = 1 mod 11

therefore

     3x34 = 1 mod 11

and E equals


                           6


34 = 4 mod 11

which is verified by

     3x4 = 12 = 1 mod 11

This is one method for solving this equation.



Prime numbers and the sieve of Eratosthenes



Prime numbers play a critical role in RSA encryption.

A number is prime if it is only divisible by itself and one.

One is prime.  Two is the only even prime.  One method to compute
primes is to "sieve" for them.  Only odd numbers greater than two
need be considered as candidates for primes since all others are
divisible by 2.  Here is the beginning of the list

3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47

Three is a prime but any multiple of three is divisi~le by three.
Cross off (a caret beneath the number) all odd multiples of three
since the are divisible by three.

3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47
^     ^        ^        ^        ^        ^        ^        ^

Five is the next prime.  Cross off all odd multiples of 5
since they are divisible by 5.  These number are 5, 15, 25, 35,
45, ...

3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47
^ ^   ^        ^        ^     ^  ^        ^  ^     ^        ^

The next integer not crossed of the list is the next prime.  This
is one way to find primes.

Here is a list of primes less than 1000.  The number of primes


   1   2   3   5   7  11  13  17  19  23   29  31  37  41  43  47
  53  59  61  67  71  73  79  83  89  97  101 103 107 109 113 127
  131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211
  223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307
  311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401
  409 419 421 431 433 439 443 449 457 461 463 467 479 487 491 499
  503 509 521 523 541 547 557 563 569 571 577 587 593 599 601 607
  613 617 619 631 641 643 647 653 659 661 673 677 683 691 701 709
  719 727 733 739 743 751 757 761 769 773 787 797 809 811 821 823
  827 829 839 853~857 859 863 877 881 883 887 907 911 919 929 937
  941 947 953 967 971 977 983 991 997


                           7


1ess than x is approximately x/ln(x).



Prime number representation



Any integer can be represented by a unique product of primes.
For example,

     6 = 2x3

     8 = 23

     15 = 3x5

The product of primes called the "factorization" of the number.
RSA encryption rests on the fact that integer factorization is
one of the more difficult computation problems using existing
factorization algorithms.



Greatest common divisor and Euclid's algorithm



The "greatest common divisor or gcd" of two integers is the
largest integer which divides both.  For example,  the greatest
common denominator of 36 and 45 is 9.   Here is the reason

          36 = 2x32

          45 = 5x32

If the greatest common divisor of two number is one, then the
numbers are said to be "relatively prime".  Six and 35 are
relatively prime since

          6 = 2x3

          35 = 5x7

but neither one of them is prime.

Euclid observed that the greatest common divisor of two integers
divides both their sum and difference.  This is easy to see from

     45-36 = 5X32 - 2x32 = (5-2)x32 = 9

Euclid's algorithm variations make it easy to compute the
greatest common divisor about any size number quickly.  Here is
an example of computing the greatest common divisor of 5467 =
7x11x71 and 21109 = 11x19x101.  The modulus prior to the 0


                           8


21109 = 4708 mod 5467

      5467 = 579 mod 4708  [579 hand-circled]

      4708 = 154 mod 759  [759 hand-circled]

       759 = 143 mod 154

       154 = 11 mod 143

       143 = 0 mod 11

remainder is the greatest common divisor.  6 and 35 are relative
prime.  Here are the computations to show this.

     35 = 5 mod 6

     6 = 1 mod 5

     5 = 0 mod 1

Euclid's algorithm provides another way to solve the eqation

     ExD=1 mod M

by writing

     ExD + AxM = 1

For example,

     3xD = 1 mod 11

is solved by finding the greatest common denominator of 3 and 11.

     11 = 2 mod 3        11 = 3x3 + 2

      3 = 1 mod 2         3 = 2xl + 1

Thus

     3 = (11 - 3x3)x1 +1

     3 + 3x3 - 11 = 1

or

     4x3 + (-1)x11 = 1

so E=4. The solution is reached by working backwards through the
steps of Euclid's algorithm.


                           9


Euler's totient function, 



The totient, , of n is the number of numbers less than and relative
prime to n.  For the prime number 7, 1 2 3 4 5 6  are all less
than and relatively prime to 7 so (7) = 6.  For a prime number
p, (p) = p-1.

For two prime numbers, p and q, p not equal q, (pq) = (p-1)(q-1).
Look at p=3 and q=5 or pq = 15.  Write the numbers 1 through 15

     1 2 3 4 5 6 7 8 9 10 11 12 13 14   15

Each third number and each 5 number divides 15.  ^ denotes
multiples sieved from the list

     1 2 3 4 5 6 7 8 9 10 11 12 13 14   15
         ^     ^     ^        ^                3's sieved
                                               5's sieved

so (15) = 14 - 4 - 2 = 8 which is (15) = 0(3x5) = 2x4 = 8.

(pn) = pn-lx(p) for prime p.

Euler's totient function gives the number of possible cryptograms
using RSA encryption.



Cycle length: Euler's and Fermat's theorems



The exponentiation tables enumerated powers of a mod m for values
of a from two to m-l for m = 5 through 11.  Euler's theorem is

     a(m) = 1 mod m  where a and m are relatively prime

Fermat's theorem is

     ap-1 = 1 mod p  where p is prime

Since (p) = p-1 for prime p, Fermat's theorem is a special
application of Euler's theorem.

The condition that a and m be relatively prime is important for
RSA encryption because

     ExD = 1 mod m

has no solution (responsible for the comment in the
exponentiation tables) if they are not.


                           10


Euler's theorem does not say that (m) is the smallest number
for which the theorem is true.  If there is a number smaller than
(m), say r, for which

     ar = 1 mod m  gcd(a,m) = 1  (relatively prime)

then (m) is a multiple of r.  The cycle length of the
exponentiations mod m divides (m).  Here is the table of
exponentiations analyzed from Euler's theorem standpoint.

mod 5  (5) = 4 = 2x2xl
     1  2  3  4  5 power
2    2  4  3  1  2                 24 = 1 mod 5
3    3  4  2  1  3                 34 = 1 mod 5
4    4  l  4  1  4                 44 = 1 mod 5 and 42 = 1 mod 5


mod 6  (6) = (2)x0(3) = 1x2 = 2x1
     1  2  3    4  5  6  power
2    2  4  2    4  2  4            gcd(2,6) = 2 no solution
3    3  3  3    3  3  3            gcd(3,6) = 3 no solution
4    4  4  4    4  4  4            gcd(4,6) = 2 no solution
5    5  1  5    1  5  1            52 = 1 mod 6


mod 7  (7) = 6 = 3x2xl
     1  2  3  4  5  6  7 power
2    2  4  l  2  4  1  2           2 6 = 1 mod 7 and 23 = 1 mod 7
3    3  2  6  4  5  1  3           3 6 = 1 mod 7
4    4  2  1  4  2  1  4           4 6 = 1 mod 7 and 43 = 1 mod 7
5    5  4  6  2  3  1  5           5 6 = 1 mod 7
6    6  1  6  1  6  1  6           6 6 = 1 mod 7 and 62 = 1 mod 7


mod 8  (8) = (23) = 22x(2) = 4 = 2x2xl
     1  2  3  4  5  6  7  8 power
2    2  4  0  0  0  0  0  0        gcd(2,8) = 2 no solution
3    3  1  3  1  3  1  3  1        34 = 1 mod 8 and 3 2 = 1 mod 8
4    4  0  0  0  0  0  0  0        gcd(4,8) = 4 no sol~tion
5    5  1  5  1  5  1  5  1        54 = 1 mod 8 and 5 2 = 1 mod 8
6    6  4  0  0  0  0  0  0        gcd(6,8) = 2 no solution
7    7  1  7  1  7  1  7  1        54 = 1 mod 8 and 5 2 = 1 mod  8

mod 9  (9) = (32) = 3x(3) = 3x2 = 6 = 3x2xl
     1  2  3  4  5  6  7  8  9 power
2    2  4  8  7  5  1  2  4  8     2 6 = 1 mod 9
3    3  0  0  0  0  0  0  0  0     gcd(3,9) = 3 no solution
4    4  7  1  4  7  1  4  7  1     46 = 1 mod 9 and 4 3 = 1 mod  9
5    5  7  8  4  2  1  5  7  8     5 6 = 1 mod 9
6    6  0  0  0  0  0  0  0  0     gcd(6,9) = 3 no solution
7    7  4  1  7  4  1  7  4  1     76 = 1 mod 9 and 7 3 = 1 mod  9
8    8  1  8  1  8  1  8  1  8     86 = 1 mod 9 and 8 2 = 1 mod  9

mod 10  (10) = (5)x(2) = 4xl = 4 = 2x2xl
     1  2  3  4  5  6  7  8  9 10 power
2    2  4  8  6  2  4  8  6  2  4  gcd(2,10) = 2 no solution
3    3  9  7  1  3  9  7  1  3  9  34 = 1 mod 10
4    4  6  4  6  4  6  4  6  4  6  gcd(4,10) = 2 no solution


                           11


5    5  5  5  5  5  5  5  5  5  5  gcd(5,10) = 5 no solution
6    6  6  6  6  6  6  6  6  6  6  gcd(6,10) = 2 no solution
7    7  9  3  1  7  9  3  1  7  9  74 = 1 mod 10
8    8  4  2  6  8  4  2  6  8  4  gcd(8,10) = 2 no solution
9    9  1  9  1  9  1  9  1  9  1  94 = 1 mod 10 and
                                   9 2 = 1 mod 10

mod 11  (11) = 10 = 5x2xl
      1  2  3  4  5  6  7  8  9 10 11 power
2     2  4  8  5 10  9  7  3  6  1  2   210 = 1 mod 11
3     3  9  5  4  1  3  9  5  4  1  3   310 = 1 mod 11 and
                                        35 = 1 mod 11
4     4  5  9  3  1  4  5  9  3  1  4   410 = 1 mod 11 and
                                        45 = 1 mod 11
5     5  3  4  9  l  5  3  4  9  1  5   510 = 1 mod 11 and
                                        55 = 1 mod 11
6     6  3  7  9 10  5  8  4  2  1  6   610 = 1 mod 11
7     7  5  2  3 10  4  6  9  8  1  7   710 = 1 mod 11
8     8  9  6  4 10  3  2  5  7  1  8   810 = 1 mod 11
9     9  4  3  5  1  9  4  3  5  1  9   910 = 1 mod 11 and
                                         95 = 1 mod 11
10   10  1 10  1 10  1 10  1 10  1 10   1010 = 1 mod 11 and
                                        102 = 1 mod 11


One raised to any power is one and thus has cycle length one.

If (m) is the smallest number for which a raised to this power
mod m is congruent to one, the "a" is called a "primitive root" mod
m.  Two, 6, 7, and 8 are all primitive roots mod 11.  Three, 4
and 5 are said to "belong to the exponent 5" since the 5th power
of these numbers is congruent to one.  Ten belongs to the
exponent 2 and one belongs to the exponent 1.

Subcycling is important to the security of RSA.  If a number has
too short of a cycle (belongs to a small exponent), then RSA
encryption can be broken.

Euler's theorem is also used to check a number for primality.
Suppose p is to be checked for primality.  A number "a" is
selected.  The numbers "a" and "p" are checked using Euclid's
algorithm to insure that they are relative prime.  If they are
not, then "p" is not prime.  If "p" passes this test, then is

      ap-1 mod p

computed.  If this is not one, then p is not a prime.  If p
passes this negative test, it still may be composite (has
factors).  Composite numbers which pass this test are called
"pseudoprimes".



Hellman and Diffie exchange of keys encryption


                           12


Exponentiations modulo a modulus can be done in any order
(called "commutative"). For example

     23X5 mod 11 = (23 mod 11)5 mod 11

     = (25 mod 11)3 mod 11

By direct computation

     215 mod 11 = 32768 mod 11 = 10

and from the exponentiation tables

     (23 mod 11)5 mod 11 = 8 5 mod 11 = 10

and

     (25 mod 11)3 mod 11 = (32 mod 11)3 mod 11

     = 103 mod 11 = 10

The commutative property of exponentiations is applied to
exchange secret number by only exchanging public numbers.

Alice and Bob both exchange publicly known integers a and prime p.

Alice selects a secret number X and computes

     aX = Xa mod p

She sends Xa to Bob.

Bob selects a secret number Y and computes

     aY = Yb mod p

He sends Yb to Alice.

Alice computes

     YbX mod p = (aY mod p)X mod p = aYxX mod p = Z

and Bob computes

     XaY mod p = (aX mod p)Y mod p = aXxY mod p = Z

At this point both Bob and Alice know the value of Z.  Anyone
else would have a difficult time discovering Z.  The degree of
difficulty is solely the difficulty of finding w knowing the
values of u, a, and p in


                           13


aw = u mod p

How difficult is this to solve?  Suppose Alice selected 5 as her
secret exponent for a = 8 and p = 11.  This means

     85 = 10 mod 11

so the code breaker must solve

     8w = 10 mod 11

Using the exponentiation tables this is a simple process.  But
think how much work this is if p is a prime several hundred
digits long!  There currently is no efficient method for solving
this equation.

A corollary to Fermat's and Euler's theorems is

     a(m)+1 = a mod m  gcd(a,m) = 1

Multiplication by a on both sides of the = sign is permissible
if a and m are relatively prime.

Hellman and Diffie proposed the encryption and decryption function

     aDxE = a mod p

for prime p.  This means

     DxE = 1 mod (p-1)

From previous results, this equation only has a solution if D and
E are relative prime to (p).  There are ((p)) integers less
than and relatively prime to (p).

The encryption of a message a is performed by

     aE mod m = b   (b is the cipher text)

The decryption is performed by

     bD mod m = (aE mod m )D mod m

                  = aExD mod m = a (a is the clear text)

Here is an example.  The modulus is 11.

     (11) = 10

     ((11)) = (10) = (5)x(2) = 4x1 = 2x2x1

The encryptor must select an encryption exponent which is
relatively prime to 10.  The gcd(2,10) = 2 so two cannot be used.
The gcd(3,10) = 1 so it can be used.  In practice a "good" random
encryption exponent is generated and Euclid's algorithm used to


                           14


check whether it and p-1 ((p)) are relatively prime.  The
decryption exponent, D, is computed from

     3xD = 1 mod 10

Look at the exponentiation table mod 10

     35 = 1 mod 10

or

     3x34 = 1 mod 10

so

     D = 34 mod 10 = 7

and the solution is verified by

     3x7 = 21 = 1 mod 10

Any message, a, is relatively prime to the prime modulus so to
encrypt it is raised to the 3 power mod 11.  Let a=5.  The
encryption using the exponentiation tables mod 11 is

     53 = 4 mod 11

The ciphertext is 4.  The decryption using the exponentiation
tables mod 11 is

     47 = 5 mod 11

The message must be relatively prime to the modulus.  With
Hellman and Diffie exchange of keys encryption this presents no
problem since the modulus is prime.  RSA uses a composite modulus
so not any message less than the modulus can be encrypted.

The Hellman-Diffie exchange of keys encryption (the Cylink SEEK
algorithm) uses Z or some derivative of it as the encryption
exponent.  A potential problem with Z is that it may be even.  If
it is even, then it cannot be used since (p) = p-1 is even and
the gcd of Z and p-1 is at least two.  Z and p-l must be relatively
prime.  If Z happens to be even Bob and Alice must convert Z to
an odd number.  Bob and Alice should check to see if the original
or revised Z and p-1 are relatively prime using Euclid's
algorithm.  In practice, some feel that the probability is
practically zero of gcd(Z,p-1) > 1 so this sometimes goes
unchecked.

Bob and Alice both compute Z  in

     ZxZ* = 1 mod p

and begin encrypted communication.


                           15


Cylink selects p = 2q+1 where q and p are prime.  Here are the
reasons

     ((p)) = (p-1) = (2q) = (2)(q) = q-l

By Euler's equation

     Z(p-1) = 1 mod (p-1)

so the inverse of Z can be computed from

     ZxZ(p-l)-l = ZxZq-2 = 1 mod (p-1)

and is

     Z* = Zq-2 mod (p-l)

Let p = 11 and q = 5.  11 = 2x5 + 1 so this satisfies the Cylink
criterion.  (11) = 10 = 5x2x1 so the encryption exponent must be
selected relatively prime to 10.  Select the random encryption
exponent Z = 3.

          3q-2 = 33 = 27 mod 10 = 7 = Z*

The message a = 8 is encrypted

     83 mod 11 = 6

and decrypted

     67 mod 11 = 8



RSA public key encryption


Bob generates two secret large primes, p and q.  He multiplies
them together

     N = pxq

and makes N public.  A message a is encrypted by raising it to
an encryption exponent, E, modulo N

     aE mod N  where gcd(a,N) = 1

The maximum cycle length for an message is

     (pxq) = (p)x(q) = (p-1)x(q-1)

Bob randomly generates a secret decryption exponent, D.  He needs
to solve for the encryption exponent E.  Since


                           16


aExD = a mod N

This means that

     ExD = 1 mod (N)

or

     ExD = 1 mod ((p-1)x(q-1))   gcd(E,(p-1)x(q-1)) = 1

First Bob must check whether D and (p-1)x(q-1) are relatively
prime.

Bob must be able to compute 0((p-1)x(q-1)) to use Euler's theorem
to solve for E.  He generally cannot compute  because he needs
to know its factorization.  Unless he selected p and q similar to
Cylink's method, he must use Euclid's algorithm to compute E.

Bob makes E and N public.  Anyone sends an encrypted message to
Bob checks to see that the message is relatively prime to N and
raises the message to the Eth power mod N.  Bob decrypts the
message message by raising it the the Dth power mod N.

Suppose Bob selects p = 5 and q = 7.  N = 5x7.  (5x7) =
(5)x(7) = 4x6 = 24 = 3x8 = 3x2x2x2x1.  Bob randomly selects D =
11 and checks gcd(24,11) = 1.  He then solves

     11xE = 1 mod 24

using a variation of Euclid's algorithm.

     24 = 2 mod 11

     11 = 1 mod 2

so

     11 = 2x5 + 1

     24 = 2x11 + 2

Thus

     11 = (24 - 2x11)x5 + 1

     11x(1 + 2x5) = 24x5 + 1


or

     11x11 = 1 mod 24


so E = 11.

A message a = 3 is encrypted

     311 mod 35


                           17


The intermediate computatlons are

     32 mod 35 = 9

     33 mod 35 = 27

     39 mod 35 = 27x27x27 mod 35 = 13

so

     311 mod 35 = 13x9 mod 35 = 12

The message is decrypted

     121l mod 35

The intermediate computations are

     122 mod 35 = 4

     123 mod 35 = 4x12 mod 35 = 13

     129 mod 35 = 13x13x13 mod 35 = 27

so

     1211 mod 35 = 4x27 mod 35 = 3



Exponentiation computations


Exponentiation calculations are easy to implement on a computer.
The number a raised to the b power is represented

     ab

The binary (base two radix) expansion of b is

     b = b0 + b12 + b222 + b323 + ...

and a to the b power is

     ab0 + b12 + b222 + b323 + ...

which equals

      b0    b12    b222    b323
     a  x  a   x  a    x  a  x ...


                        18


This is also written

      b0     b1     b2     b3
    (a) x (a2) x (a4) x (a8) x ...

This is the way 210 is evaluated.  The binary representation of
1010 is 10109 or b0 = 0, b1 = 1, b2 = 0, and b3 = 1.
The exponentiation is started by setting a product to one.
Squares of the preceding base (base to an exponent) are included
in the product if the binary coefficient is one and not included
if it is zero.

     Power of           b            product
     base

                                     1

     21 = 2         b0 = 0           1

     22 = 4         b1 = 1           4

     24 = 16        b2 = 0           4

     28 = 256       b3 = 1           1024

Computation of an exponentiation modulo a modulus is done by
reducing, if necessary, the product when it is equal or greater
than the modulus.  For example, 310 mod 7 is computed


     Power of                b            product
     base

                                          1

     31 = 3              b0 = 0           1

     32 = 9 mod 7 = 2    b1 = 1           2

     24 = 4              b2 = 0           2  [24 = 4 as written]

     28 = 16 mod 7 = 2   b3 = 1           4



RSA software computations



RSA computations require exponentiation mod m for encryption and
decryption.  Addition and multiplication mod m are used to
compute the encryption or decryption exponent and greatest common
divisors with Euclid's algorithm.


                           19


Speed of execution of software implementation of the computations

     1    xz mod m        exponentation mod m

     2    xz mod m            multiplication mod m

     3    x+z mod m           addition mod m

depends on the speed of the computer, presence or absence of an
arithmetic unit, its speed, and the "word size" architecture of
the computer.  The "word size" can be thought of the maximum
number of digits which can be held in an accumulator.  For a
microcomputer is value is usually either 8, 16 or 32.  For a Cray
supercomputer this value is 64.

A common value for_RSA computation is 1024 bits (bit is a binary
digit)(10y = 21024. y equals about 308 which means that 2308
contains about 309 declmal digits).  Representation of 1024 bits
require 16 64 bit Cray words or 128 8 bit microcomputer words.

Number which exceed the word size of a computer are represented
as polynomials in the computer.  The binary number 00000001
00000010 00000011 is represented in an eight bit microcomputer

     00000001x22 + 00000010x2 + 00000011

polynomial addition of a 1024 bit number in the eight bit
microcomputer consists of 128 8 bit additions, observing carries.
On a Cray this is 16 64 bit additions observing carries.

Polynomial multiplication multiplication [sic] is more complicated.  A
1024 bit multiplicand times a 1024 bit multiplier yields a 2048
bit product.  1024 bit number is represented a polynomial with
128 terms in an eight bit microcomputer or 16 terms in a Cray.
The polynomial product on an eight bit microcomputer requires
16384 8 bit by 8 bit products each which gives a 16 bit result.
Each of these products must be polynomial added to give the final
2048 bit result.  Computations on a Cray are less but still time
consuming.

Exponentiation requires squaring the base for each bit in the
exponent.  This value has to be multiplied times the partial
product if the exponent bit is one.  Intermediate computations
are reduced by the modulus.  Exponentiation is the most
complicated of the three computations.

Microcomputers are used for these computations.  Extremely
efficient modular arithmetic packages written in assembler permit
moderately complex computations (selecting RSA primes of length
256 bits) in about 20 minutes using a 1 MHz 6502 microprocessor.
Many months labor is required to write and test such software
packages.  For example, at Sandia it took more than six months to
implement these computations in portable FORTRAN 77.  Even with
extensive initial testing a bug in the software was discovered


                           20


one year and a half later.



RSA hardware computations



The slow speed of software RSA computations plus the potential
wide use prompted several companies to build chips which compute
modular arithmetic to at least several hundred bits.  Most of
these chips "cascade" to compute with a larger number of bits.

Corporations involved in building these chips are

     1  IBM  Firefly

     2  AT&T

     3  Motorola (apparently a three chip set)

     4  Cylink   Pittway-First alert

     5  Sandia Labs (Algorithm M and predecessor chip)

Details of the IBM chip is classified.  AT&T as of July 1987 has
not released details of their chip.  Little information is
available on the Motorola chip set.

The Cylink chip is commercially available.  Its price dropped
from $1,500 to $600 each in June 1987.  Data is transferred to
and from the chip with serial shift register communication.

The early Sandia chip was limited in speed.  The replacement
chip is cascadeable, communicates with 8 or 16 bits parallel,
matches the speed of the Cylink chip, but is not out of
fabrication.

Rumors circulate that there is about an order of magnitude
performance difference between some of these chips.

These hardware chips improve exponentiation speed about 3 orders
of magnitude over software implementation benchmarked on an Intel
8086 family microcomputer.



RSA prime and decryption exponent selection



If the numbers required to implement RSA encryption are
improperly chosen, RSA can be broken.  "Strong primes" resist
factorization methods when multiplied together.  A definition of
a strong prime is


                           21


o  p is prime

     o  p-1 has a large prime factor r

     o  p+1 has a large prime factor

     o  r-1 has a large prime factor

This method or others are used to select RSA values.
The point to this section is individuals or agencies with
demonstrable expertise should be in charge of RSA value selection
algorithms.  Theoretical and applied research required to
competently complete this task runs into many years of work.










                            22


[End]


16 May 1997
Source: William H. Payne


Communications of the ACM, April 1978, Volume 21, Number 4

Scientific Applications
F.N. Fritsch Editor

Orderly Enumeration of Nonsingular Binary Matrices Applied to Text Encryption

W. H. Payne and K. L. McMillen
Washington State University


[Abstract] Nonsingular binary matrices of order N, i.e., nonsingular over the field {0, 1}, and an initial segment of the natural numbers are placed in one-to one correspondence. Each natural number corresponds to two intermediate vectors. These vectors are mapped into a nonsingular binary matrix. Examples of complete enumeration of all 2 x 2 and 3 x 3 nonsingular binary matrices were produced by mapping the intermediate vectors to the matrices.

The mapping has application to the Vernam encipherment method using pseudorandom number sequences. A bit string formed from bytes of text of a data encryption key can be used as a representation of a natural number. This natural number is transformed to a nonsingular binary matrix. Key leverage is obtained by using the matrix as a "seed" in a shift register sequence pseudorandom number generator.

Key Words and Phrases: binary matrices, combinatorics, combinations, nonsingular matrices, encryption, Vernam, pseudorandom numbers, feedback shift register sequences, random numbers.

CR Categories: 3.7, 5.3

_____________________

[Hand-circled footnote] Work funded by NSF Grant DCR7S-08822. [Handwritten: "NSA killed this."]

[Balance of 5-page article omitted.]


MAY 12 '92 12:37 SANDIA LAB ORG 9240 505-846-6652       P.1/3


     ***THIS MACHINE FOR UNCLASSIFED USE ONLY***

[Handritten: NSA proposal. Omura sent it back to me"]


Sandia
National
Laboratories


ALBUQUERQUE, NEW MEXICO






                          FACSIMILE TRANSMITTAL SHEET
                          MACHINE:      (505) 846-6652
                                        FTS   846-6652
                                        AV    246-6652


                          VERIFICATION: (505)_________


TRANSMIT
TO:              CYLINK                               



FOR:             JIM OMURA                            
           (NAME)         (OFFICE)        (PHONE)


FROM:            Bill                                 
           (NAME)         (OFFICE)        (PHONE)



                   NUMBER OF PAGES:___________________
                                   (INCLUDING COVER)



[Handwritten: "Got your message. Will phone aftger lunch."]



     ***THIS MACHINE FOR UNCLASSIFED USE ONLY***



MAY 12 '92 12:37 SANDIA LAB ORG 9240 505-846-6652       P.2/3

                               DRAFT


                New Directions for Data Authentication


            W. H. Payne, 5031 and H. B. Durham, consultant
               Sandia National Laboratories, Albuquerque

                               01/15/92

                             1 Introduction

Current data authentication methods use single key finite
field/combinatoric or public key algorithmg.  These algorithms
were developed to provide a single party a means to verify that a
message had not been altered at transmission time or data
handling.  However, these algorithms do not prevent the
generation of "false" authenticated data by any party having
access to the data authentication keys.

Advantages of single key finite field/combinatoric algorithms
include simplicity, demonstrable security, ease of implementation
in hardware, speed in hardware, good operational reliability, and
ease of implementation in software in eight bit microcontrollers
if speed is not required.  Under current operation concepts, a
significant disadvantage results from the logistical requirements
associated with key generation, distribution, record keeping and
eventual key release.

Advantages of public key authentication algorithms include
immediate verification of authenticity by all parties.
Disadvantages include complicated hardware and software
implementation, slow processing, the necessity of using an
auxiliary hashing function to speed processing, construction of a
hashing function to reasonably guarantee that two messages do not
have the same message digest, expensive field failure examples,
and may prove vulnerable to currently unknown or not yet revealed
analytic or algorithmic attacks.

The evolving world political organization now indicates a
potential need for many multilateral treaties requiring multi-party
acceptance and and participation in the monitoring and
verification processes.  All parties must have the capability of
verifying the integrity of transmitted data independent of all
other parties.  Current finite field/combinatoric authentication
algorithms are not well suited to these new needs.

                      2  Project Objectives

The proposed project will contribute to the development of new
technologies needed to support future data authentication
requirements.  The authors will work with the sponsor to share
ideas and develop concepts, software and hardware, within the
sponsor's guidelines.  Potential concepts to examined lnclude:



                               DRAFT



MAY 12 '92 12:37 SANDIA LAB ORG 9240 505-846-6652       P.3/3



                              DRAFT




          A    multi-party authenticators
          B    table driven algorithms for small low-power micros
          C    pipelined algorithms
          D    self-keying authenticators
          E    RAM and ROM authentication algorithm sequencers
          F    matrix authentication algorithms
          G    serial stream authenticators
          H    transparent authenticators
          I    other ideas

                     3  Project Deliverables

Algorithm and hardware used to authenticate messages will depend
on the application.  Therefore, the product required to meet most
future requirements is a set of publications defining:

          A     algorithms
          B     operational concepts
          C     hardware/software implementations
          D     test vectors
          E     hardware schematics
          F     computer code

                        4 Proiect Schedule

Month
1 through 6          Operational concepts and algorithms: draft
                     document reports and monthly status reports.
7 through 12         Hardware/software, test vectors, hardware
                     schematics, computer code, and final reports.

                         5 Project Budget

Activity                                               K$ Cost

W. H. Payne     1/2 time                                 114
H. B. Durham    24 days @ 50/hr                           10
Technician      full time                                114
Travel                                                    30
Prototype hardware manufacture                           100
Subtotal                                                 368
Sandia overhead               TBD by supervision
Total                         TBD by supervision





                              DRAFT

Proceedings of the IEEE, Vol.76, No. 5, May 1988

CYLINK

The First Ten Years of Public-Key Cryptography

WHITFIELD DIFFIE

Invited Paper

[Abstract] Public-key cryptosystems separate the capacities for encryption and decryption so that 1) many people can encrypt messages in such a way that only one person can read them or 2) one person can encrypt messages in such a way that many people can read them. This separation allows important improvements in the management of cryptographic keys and makes it possible to 'sign' a purely digital message.

Public key cryptography was discovered in the Spring of 1975 and has followed a surprising course. Although diverse systems were proposed early on the ones that appear both practical and secure today are all very ciosely related and the search for new and different ones has met with littie success. Despite this reliance on a limited mathematical foundation public-key cryptography is revolutionizing communicabon security by making possible secure communication networks with hundreds of thousands of subscribers.

Equally important is the impact of public key cryptography on the theoretical side of communication security. It has given cryptographers a systematic means of addressing a broad range of security objectives and pointed the way toward a more theoretical approach that allows the development of cryptographic protocols with proven security characteristics.

* * * *

VIII. APPLICATION AND IMPLEMENTATION

While arguments about the true worth of public-key cryptography raged in the late 1970s, it came to the attention of one person who had no doubt: Gustavus J. Simmons, head of the mathematics department of Sandia National Laboratories. Simmons was responsible for the mathematical aspects of nuclear command and control and digital signatures were just what he needed. The applications were limitless: A nuclear weapon could demand a digitally signed order before it would arm itself; a badge admitting someone to a sensitive area could bear a digitally signed description of the person; a sensor monitoring compliance with a nuclear test ban treaty could place a digital signature on the information it reported. Sandia began immediately both to develop the technology of public-key devices [108], [107], [89] and to study the strength of the proposed systems [105], [16], [34].

[Following paragraph hand-marked with handwritten note: "Simmons had nothing to do with seismic verification."]

The application about which Simmons spoke most frequently, test-ban monitoring by remote seismic observatories [106], is the subject of another paper in this special section (G. J. Simmons, "How to Insure that Data Acquired to Verify Treaty Compliance are Trustworthy"). If the United States and the Soviet Union could put seismometers on each other's territories and use these seismometers to monitor each other's nuclear tests, the rather generous hundred and fifty kiloton upper limit imposed on underground nuclear testing by the Limited Nuclear Test Ban Treaty of 1963 could be tightened considerably -- perhaps to ten kilotons or even one kiloton. The problem is this: A monitoring nation must assure itself that the host nation is not concealing tests by tampering with the data from the monitor's observatories. Conventional cryptographic authentication techniques can solve this problem, but in the process create another. A host nation wants to assure itself that the monitoring nation can monitor only total yield and does not employ an instrument package capable of detecting staging or other aspects of the weapon not covered by the treaty. If the data from the remote seismic observatory are encrypted, the host country cannot tell what they contain. [End hand mark]

Digital signatures provided a perfect solution. A digitally signed message from a remote seismic observatory cannot be altered by the host, but can be read. The host country can assure itself that the observatory is not exceeding its authority by comparing the data transmitted with data from a nearby observatory conforming to its own interpretation of the treaty language.

The RSA system was the one best suited to signature applications, so Sandia began building hardware to carry out the RSA calcuiations. In 1979 it announced a board implementation intended for the seismic monitoring application [106]. This was later followed by work on both low- and high-speed chips [89], [94].

Sandia was not the only hardware builder. Ron Rivest and colleagues at MIT, ostensibly theoretical computer scientists, learned to design hardware and produced a board at approximately the same time as Sandia. The MIT board

[Image] Sandia 256-bit RSA board.

[Image] Wafer photo: Sandia low speed chip.

would carry out an RSA encryption with a one hundred digit modulus in about a twentieth of a second. It was adequate "proof of concept" but too expensive for the commercial applications Rivest had in mind.

No sooner was the board done than Rivest started studying the recently popularized methods for designing large-scale integrated circuits. The result was an experimental nMOS chip that operated on approximately 500 bit numbers and should have been capable of about three encryptions per second [93]. This chip was originally intended as a prototype for commercial applications. As it happened, the chip was never gotten to work correctly, and the appearance of a commercially available RSA chip was to await the brilliant work of Cylink corporation in the mid-1980s [31].  [End article portion]

__________

[Handwritten: Sandia chips failed (100%) in field.]


[End 16 May 1997 documents]