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 = 17 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
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
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]