Public Key Cryptography

Overview and Background

The practical use of this is for security with data transfer, where the 'public key' (decryption key) can be transmitted, followed by the encrypted data. This ensures that any other source, even if it has seen all the data which has been transmitted, cannot send meaningful data or alter the data being sent in a meaningful way, since to do so would require the encryption key, which cannot be determined. On the other hand, if the information itself must not be accessible to intermediate carriers, then the recieving end can send a public encryption key to the source, which then uses the key to encrypt the data before sending. In this case, the decryption key is the private key.

Creating the Keys

Note that finding two large prime numbers presents a problem in itself. The best bet seems to be to choose a random number in the required range, test it for primality; if unsuccessful, increment the number and repeat.

2. Choose E, such that E is less than the modulus, and E has no common factors with (P-1) or (Q-1).

3. Compute D such that (DE - 1) mod ((P-1)(Q-1)) = 0. The easiest way to do this is as following:

• Use a loop, with a variable i which is incremented each iteration.
• Let x be i(P-1)(Q-1) + 1.
• Let D equal x divided by E. If the remainder of the division is not zero, this is not a valid value for D, so the loop must continue; otherwise the value is valid and the loop can be broken.

4. The decryption key is now the pair of numbers (PQ, D). The encryption key is the pair (PQ, E).

Note: the expression 'x^y' here refers to the value x raised to the power of the value y. The expression 'x mod y' refers to the modulus (remainder) of the division of x by y.

• Encrypt(T) = T^E mod PQ
• Decrypt(C) = C^D mod PQ

This exact formula has a minor problem in that the numbers 0 and 1 are never encrypted: they come out as the same unchanged value. A solution, if this is a problem, might be to the use the following method, which requires a key space (PQ) at least 2 greater than the code space:

• Encrypt(T) = (T+2)^E mod PQ
• Decrypt(C) = (C^D mod PQ) - 2

Note also that, in computing the power y^x in both of the above cases, the efficiency can be greatly increased (realistically, it needs to be increased) by use of the following identities:

• y^a * y^b = y^(a+b) which also yields y^a * y^a = y^2a and
• (y^a mod d) * (y^b mod d) = y^(a+b) mod d.
• ((y^a mod d) * y^b) mod d = y^(a+b) mod d.

What are the practical upshots? Firstly, calculating a large power is made faster by multiplying lesser powers, in particular powers of powers of 2, giving us the following algorithm for y^x:

• let result = 1
• let product = y
• repeat: {
  • if the lowest bit of x is set, multiply result by product
  • multiply product by itself (*)
  • shift x right by one bit
  • if x is 0, break from the loop
• } (end of repeat block)

Now, the second identity gives us a solution to the further problem that 'result' quickly becomes very large, too large to fit into any of the normal computer variable storage sizes. To get around this problem, we make use of the second and third identities by inserting just after the line marked with a star (*) in the algorithm above:

• let product = the modulus of itself with PQ

Highest common factors

It starts with two variables, a and b, which are two integers such that a > b.

Declare variable 'tmp' of same type as a/b;
tmp = b;
while( tmp doesn't equal 0 ) {
  b = tmp;
  tmp = a mod b;
  a = b;
} (reiterate)
return (b) as highest common factor

Davin McCall. 1998, 1999, 2005.