Appendix 1

Creating a key pair using the RSA Algorithm

(CALCULATIONS AND SOME TEXT TAKEN FROM APPENDIX J OF THE CODE BOOK BY SIMON SINGH, PUBLISHED BY FOURTH ESTATE PUBLISHING LTD)

148. In creating the key pair the objective is to arrive at a public and private key such that in the current state of mathematical knowledge and with available computer capacity:

(i) encryption using the public key takes a reasonable time.
(ii) decryption using the private key on an electronic document encrypted using the public key takes a reasonable time.
(iii)it would take an unreasonable amount of time for an opponent, knowing the public key, to calculate the private key.
(iv) it would take an unreasonable amount of time for an opponent, knowing the public key and the ciphertext, C, to recover the original electronic document.

149. The RSA Algorithm is the one most commonly used for achieving these objectives. The private key is the unique mathematical inverse of the public key but it can only be calculated if extra information (the d number) below is known. Prime numbers are used because of the difficulty of finding them from their product by factoring (paragraph 132). In the example below n is that product.

150. The following example indicates how the keys are generated and used. The processes all take place inside computers or on smart cards. They are not controlled by the user but are preset on programs.

1) Take two giant prime numbers, p and q. The primes should be enormous, but for this example we are using

p = 17, q = 11.

2) p and q are multiplied together to get another number, n.

n = 187.

When the computer calculates n it will use a special process to ensure that it uses good primes p and q to make it as difficult as possible to factor n. n is the modulus at the point in the RSA calculation when modular arithmetic comes into play.

3) Having determined n which will be part of the public key and part of the private key it is necessary to find two further numbers. One, d, will be part of the private key and known only to the owner of that key and the other number, e, will be part of the public key and made public together with n.

4) e and (p - 1) x (q - 1) should be relatively prime, that is they should have no common denominator other than 1.

p-1 and q-1 are used rather than p and q because of a quantity in number theory known as Euler’s Totient function which is written Øn, where Øn is the number of positive integers less than n and relatively prime to n. If n is prime (ie nothing divides into it except itself and 1) then to arrive at the number of positive integers less than n and relatively prime to n (ie which have no other common denominator with n than 1) Euler’s Totient is

Øn = n-1

The greatest common denominator of e and Øn must be 1.

In this example e is 7.

5) The number d is calculated according to the following formula

e x d = 1 (mod (p-1) x (q-1))

7 x d = 1 (mod 16 x 10)

7 x d = 1 (mod 160)

d = 23

This calculation is carried out by Euclid’s algorithm which, where the greatest common denominator of two numbers is 1, will determine the inverse of one of the two numbers modulo the other.

6) To encrypt an electronic document for confidentiality purposes (this is not a digital signature process in which the hash is encrypted using the private key but the process outlined under the heading “ Confidentiality” above.) the electronic document must first be converted into a number, M. For example, a word is changed into ASCII binary digits, and the binary digits can be considered as a decimal number. M is then encrypted to give the ciphertext, C, according to the formula C = Mc (mod N)

7) Assume the electronic document is just the letter X. In ASCII this is represented by 101100, which is equivalent to 88 in decimal. So, M= 88.

8) Encrypt this electronic document using the public key which is

n = 187 and e = 7.

With M= 88, the formula gives

C = 887 (mod 187)

9) Working this out directly on a calculator is not straightforward, because the display cannot cope with such large numbers. However, there is a neat trick for calculating exponentials in modular arithmetic. We know that, since

7 = 4 + 2 + 1,

887 (mod 187) = [884 (mod 187) x

882 (mod 187) x 881 (mod 187)] (mod 187)

881 = 88 = 88 (mod 187)

882 = 7,744 = 77 (mod 187)

884 = 59,969,536 = 132 (mod 187)

887 = 881 x 882 x 884 = 88 x 77 x 132 = 894,432 = 11 (mod 187)

The ciphertext which is sent is

C = 11

10) Exponentials in modular arithmetic are oneway functions, so it is very difficult to work backwards from C = 11 and recover the original electronic document, M. So somebody with the public key could not decipher the electronic document 11 so as to find out it was 88 or X.

11) To decrypt the electronic document, the receiver simply uses the following formula

M= Cd (mod 187)

M = 1123 (mod 187)

M = [111 mod 187) x 112 (mod 187) x

114 (mod 187) x 1116 (mod 187)] (mod 187)

M= 11 x 121 x 55 x 154 (mod 187)

M = 88 = X in ASCII.