Public Key Cryptography

Public key encryption is a much slower alternative to symmetric cryptography. Its based upon mathematical functions upon two pairs of numbers. For the well-known RSA algorithm, the security comes from the difficulty of factoring large numbers in Galois Fields.^10.4

Each key is a pair of keys K and K-1. If a message is encrypted using K then it can only be decrypted using K-1. If $\wedge$ means the application of the encryption function and text is the cleartext, then the following all hold true.

$$(text) \wedge K \wedge K-1 = text$$

$$(text) \wedge K \wedge K \neq text$$

$$(text) \wedge K-1 \wedge K = text$$

$$(text) \wedge K-1 \wedge K-1 \neq text$$

Importantly, one cannot derive K from knowledge of K-1 or vice versa. This allows the primary use of public key technology, where one key is made public and one key remains secret. This provides a much larger degree of functionality, extending the use of cryptography to supply authentication and integrity as well as confidentiality.

Authentication is provided by taking a piece of text, encrypting it using the private key which is only known by you. If it can be decrypted using your public key, then it is known to be encrypted by you. This then functions to authenticate the text.

But, encryption is slow, so what is used is another mathematical function which takes text in and produces a pseudo random fixed size number out that can only have come from the original input text. This is known as a hash function. The hash function takes in the whole of the cleartext, generates a 128 byte message digest, which is then encrypted using the public key. This is known as a digital signature. When the receiver receives the message, they run the hash function over the data to regenerate the message digest. They decrypt using the public key, and if the digests match, then they know that the message was really sent by the purported sender, and that the message was not interfered with - the integrity of the message has been protected.

  

Figure 10.2: Authentication and Integrity with digital signatures

In the original Diffie-Hellman proposal, the two parties, Alice and Bob, choose two large integers, n and g, such that g is less than n. Then the following occurs:

1.

Alice chooses a random large integer x and calculates

$$X = g^{x} \bmod n$$ (10.1)

2.

Bob also chooses a random large integer y and calculates

$$Y = g^{y} \bmod n$$ (10.2)

3.

Alice sends Bob X and Bob sends Alice Y. x and y are both kept secret.

4.

Alice computes

$$k = Y^{x} \bmod n$$ (10.3)

5.

Bob computes

$$k' = X^{y} \bmod n$$ (10.4)

Both k and k' equal $g^{xy} \bmod n$. However, its very unlikely that anyone else listening on the channel can calculate the key, since the calculation of discrete logarithms under field arithmetic is very hard (see Galois Fields).

Whilst RSA is the normal set of algorithm used in public key cryptography, Diffie-Hellman is still used in such places as the SKIP protocol.