**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 ENCRYPTIONW. 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:"Notsent to Japan."][ 1 ]

Public Rey EncryptionEncryption 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 ArithmeticDivision 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 3^{5}mod 7 is computed 35 = 3^{2}X3^{2}x3 = (3^{2})^{2}x3=(3^{2}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 7ExponentiationExponentiation 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 2Additive and multiplicative inversesThe 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 3^{5}=1 mod 11 therefore 3x3^{4}= 1 mod 11 and E equals 6

3^{4}=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 EratosthenesPrime 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 representationAny 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 algorithmThe "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 = 2x3^{2}45 = 5x3^{2}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 = 5X3^{2}- 2x3^{2}= (5-2)x3^{2}= 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) = p^{n-l}xø(p) for prime p. Euler's totient function gives the number of possible cryptograms using RSA encryption.Cycle length: Euler's and Fermat's theoremsThe 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 a^{p-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 a^{r}=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 2^{4}=1 mod 5 3 3 4 2 1 3 3^{4}=1 mod 5 4 4 l 4 1 4 4^{4}=1 mod 5 and 4^{2}=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 5^{2}=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 2^{3}=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 4^{3}=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 6^{2}=1 mod 7 mod 8 ø(8) = ø(2^{3}) = 2^{2}xø(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 3^{4}=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 5^{4}=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 5^{4}=1 mod 8 and 5^{2}=1 mod 8 mod 9 ø(9) = ø(3^{2}) = 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 4^{6}=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 7^{6}=1 mod 9 and 7^{3}=1 mod 9 8 8 1 8 1 8 1 8 1 8 8^{6}=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 3^{4}=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 7^{4}=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 9^{4}=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 2^{10}=1 mod 11 3 3 9 5 4 1 3 9 5 4 1 3 3^{10}=1 mod 11 and 3^{5}=1 mod 11 4 4 5 9 3 1 4 5 9 3 1 4 4^{10}=1 mod 11 and 4^{5}= 1 mod 11 5 5 3 4 9 l 5 3 4 9 1 5 5^{10}=1 mod 11 and 5^{5}= 1 mod 11 6 6 3 7 9 10 5 8 4 2 1 6 6^{10}=1 mod 11 7 7 5 2 3 10 4 6 9 8 1 7 7^{10}=1 mod 11 8 8 9 6 4 10 3 2 5 7 1 8 8^{10}=1 mod 11 9 9 4 3 5 1 9 4 3 5 1 9 9^{10}=1 mod 11 and 9^{5}=1 mod 11 10 10 1 10 1 10 1 10 1 10 1 10 10^{10}=1 mod 11 and 10^{2}=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 a^{p-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 encryption12

Exponentiations modulo a modulus can be done in any order (called "commutative"). For example 2^{3X5}mod 11 = (2^{3}mod 11)^{5}mod 11 = (2^{5}mod 11)^{3}mod 11 By direct computation 2^{15}mod 11 = 32768 mod 11 = 10 and from the exponentiation tables (2^{3}mod 11)^{5}mod 11 = 8^{5}mod 11 = 10 and (2^{5}mod 11)^{3}mod 11 = (32 mod 11)^{3}mod 11 = 10^{3}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 a^{X}=X_{a}mod p She sends X_{a}to Bob. Bob selects a secret number Y and computes a^{Y}=Y_{b}mod p He sends Y_{b}to Alice. Alice computes Y_{b}^{X}mod p = (a^{Y}mod p)^{X}mod p = a^{YxX}mod p = Z and Bob computes X_{a}^{Y}mod p = (a^{X}mod p)^{Y}mod p = a^{XxY}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

a^{w}=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 8^{5}=10 mod 11 so the code breaker must solve 8^{w}=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 a^{DxE}=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 a^{E}mod m = b (b is the cipher text) The decryption is performed by b^{D}mod m = (a^{E}mod m )^{D}mod m = a^{ExD}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 3^{5}=1 mod 10 or 3x3^{4}=1 mod 10 so D = 3^{4}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 5^{3}=4 mod 11 The ciphertext is 4. The decryption using the exponentiation tables mod 11 is 4^{7}=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}= ZxZ^{q-2}=1 mod (p-1) and is Z* = Z^{q-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. 3^{q-2}= 3^{3}= 27 mod 10 = 7 = Z* The message a = 8 is encrypted 8^{3}mod 11 = 6 and decrypted 6^{7}mod 11 = 8RSA public key encryptionBob 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 a^{E}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

a^{ExD}=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. 2^{4}=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 3^{11}mod 35 17

The intermediate computatlons are 3^{2}mod 35 = 9 3^{3}mod 35 = 27 3^{9}mod 35 = 27x27x27 mod 35 = 13 so 3^{11}mod 35 = 13x9 mod 35 = 12 The message is decrypted 12^{1l}mod 35 The intermediate computations are 12^{2}mod 35 = 4 12^{3}mod 35 = 4x12 mod 35 = 13 12^{9}mod 35 = 13x13x13 mod 35 = 27 so 12^{11}mod 35 = 4x27 mod 35 = 3Exponentiation computationsExponentiation 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 = b_{0}+ b_{1}2 + b_{2}2^{2}+ b_{3}2^{3}+ ... and a to the b power is a^{b0 + b12 + b222 + b323 + ...}which equals b^{0}b^{12}b_{2}2^{2}b_{3}2^{3}a x a x a x a x ... 18

This is also written b_{0}b_{1}b_{2}b_{3}(a) x (a^{2}) x (a^{4}) x (a^{8}) x ... This is the way 2^{10}is evaluated. The binary representation of 10_{10}is 10^{109}or b_{0}= 0, b_{1}= 1, b_{2}= 0, and b_{3}= 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 2^{1}= 2 b_{0}= 0 1 2^{2}= 4 b_{1}= 1 4 2^{4}= 16 b_{2}= 0 4 2^{8}= 256 b_{3}= 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, 3^{10}mod 7 is computed Power of b product base 1 3^{1}= 3 b_{0}= 0 1 3^{2}= 9 mod 7 = 2 b_{1}= 1 2 2^{4}= 4 b_{2}= 0 2[22^{4}= 4 as written]^{8}= 16 mod 7 = 2 b_{3}= 1 4RSA software computationsRSA 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 x^{z}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)(10^{y}= 2^{1024}. y equals about 308 which means that 2^{308}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 00000001x2^{2}+ 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 computationsThe 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 selectionIf 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 MEXICOFACSIMILE TRANSMITTAL SHEETMACHINE: (505) 846-6652 FTS 846-6652 AV 246-6652 VERIFICATION: (505)_________ TRANSMIT TO:CYLINKFOR: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]*