# Cryptography- Public Key Encryption Algorithms

This lesson discusses the development of public key cryptography as an alternate to the more traditional private key systems, its advantages and disadvantages, and describes the Diffie-Hellman algorithm.

## Objectives

• understand the general concept of public key cryptography
• know the distinction between the public and private keys
• understand how the Diffie-Hellman key exchange algorithm works
• ## Public-Key Cryptography

1. Private-Key Cryptography
• traditional private/secret/single key cryptography uses one key
• shared by both sender and receiver
• if this key is disclosed communications are compromised
• also is symmetric, parties are equal
• hence does not protect sender from receiver forging a message & claiming is sent by sender

So far all the cryptosystems discussed have been private/secret/single key (symmetric) systems. All classical, and modern block and stream ciphers are of this form.

2. Public-Key Cryptography
• public-key/two-key/asymmetric cryptography involves the use of two keys:
• a public-key, which may be known by anybody, and can be used to encrypt messages, and verify signatures
• a private-key, known only to the recipient, used to decrypt messages, and sign (create) signatures
• is asymmetric because parties are not equal
• those who encrypt messages or verify signatures cannot decrypt messages or create signatures
• achieve this through the clever application of number theoretic concepts
• its development is the single most significant advance in the 3000 year history of cryptography

Will now discuss the radically different public key systems, in which two keys are used. Anyone knowing the public key can encrypt messages or verify signatures, but cannot decrypt messages or create signatures, counter-intuitive though this may seem. It works by the clever use of number theory problems that are easy one way but hard the other. Note that public key schemes are neither more secure than private key (security depends on the key size for both), nor do they replace private key schemes (they are too slow to do so), rather they complement them.

3. Public-Key Cryptography

Asymmetric (Public Key) Encrpytion Scheme

Note here the keys are created by the receiver not the sender (as is more common in private key systems, though either party can do so). In public key systems, the owner of the keys is the receiver, since they need to decrypt the message.

4. Theory of Public Key
• the public-key is easily computed from the private key and other information about the cipher (a polynomial time (P-time) problem)
• however, knowing the public-key and public description of the cipher, it is still computationally infeasible to compute the private key (an NP-time problem)
• thus the public-key may be distributed to anyone wishing to communicate securely with its owner
• although the secure distribution of the public-key is a non-trivial problem - the key distribution problem

Public key schemes utilise problems that are easy (P type) one way but hard (NP type) the other way, eg exponentiation vs logs, multiplication vs factoring. Consider the following analogy using padlocked boxes: traditional schemes involve the sender putting a message in a box and locking it, sending that to the receiver, and somehow securely also sending them the key to unlock the box. The radical advance in public key schemes was to turn this around, the receiver sends an unlocked box to the sender, who puts the message in the box and locks it (easy - and having locked it cannot get at the message), and sends the locked box to the receiver who can unlock it (also easy), having the key. An attacker would have to pick the lock on the box (hard). There is one problem - how does the sender know they have the correct unlocked box for the person they wish to send a message to? Thats the key distribution problem, which we'll talk about soon.

5. Classes of Public-Key Algorithms
Public-Key Distribution Schemes (PKDS)
• used to securely exchange a single piece of information
• value depends on the two parties, but cannot be set
• value is normally used as a session key for a private-key scheme
Public Key Encryption (PKE)
• used to encrypt any arbitrary message
• anyone can use the public-key to encrypt a message
• owner uses the private-key to decrypt the messages
• any public-key encryption scheme can be used as a PKDS by using the session key as the message
• many public-key encryption schemes are also signature schemes (provided encryption & decryption can be done in either order)
Signature Schemes
• used to create a digital signature for some message
• owner uses private-key to signs (create) the signature
• anyone can use the public-key to verify the signature

Distinguish between 3 classes of public key algorithms, depending on their use. We will consider each of these classes of algorithms in turn.

6. Security of Public Key Schemes
• security relies on a large enough difference in difficulty between the easy problem (en/decryption) and the hard problems (cryptanalysis)
• as with private key schemes a brute force exhaustive search attack is always theoretically possible
• but in practise the keys used are much too large for this (>512bits)
• more generally the hard problem is known, its just made too hard to do in practise
• this requires the use of very large numbers (>512 bits)
• which means that implementations are slow compared to private key schemes

Public key schemes are no more or less secure than private key schemes - in both cases the size of the key determines the security. Note also that you can't compare key sizes - a 64-bit private key scheme has very roughly similar security to a 512-bit RSA - both could be broken given sufficient resources. But with public key schemes at least there's usually a firmer theoretical basis for determining the security since its based on well-known and well studied number theory problems.

## Diffie-Hellman Public-Key Distribution Scheme

1. Diffie-Hellman Public-Key Distribution Scheme
• first public-key type scheme proposed
• by Diffie & Hellman in 1976:
• a practical method for public exchange of a secret key
• along with the first public exposition of the concept of public key schemes
• W Diffie, M E Hellman, "New directions in Cryptography", IEEE Trans. Information Theory, IT-22, pp644-654, Nov 1976
• now know that James Ellis (UK CESG) secretly proposed the concept in 1970

The idea of public key schemes, and the first practical scheme, which was for key distribution only, was published in 1977 by Diffie & Hellman. The concept had been proeviously described in a classified report in 1970 by James Ellis (UK CESG) - and subsequently declassified in 1987. See History of Non-secret Encryption (at CESG). Its interesting to note that they discovered RSA first, then Diffie-Hellman, opposite to the order of public discovery!

2. Diffie-Hellman Public-Key Distribution Scheme
• a public-key distribution scheme
• cannot be used to exchange an arbitrary message
• rather it can establish a common key
• known only to the two participants
• whose value depends on the participants (and their private and public key information)
• is based on exponentiation in a finite (Galois) field (modulo a prime or a polynomial)
• nb exponentiation takes O((log n)3) operations (easy P type)
• its security relies on the difficulty of computing discrete logarithms
• nb discrete logarithms takes O(e log n log log n) operations (hard NP type)

Diffie-Hellman key exchange is widely used in a number of products to establish a common secret key, which is then used in a block cipher to encrypt a communications link (cf SSH). Is secure against passive eavesdropping, though additional steps are needed to secure against active attack.

3. Diffie-Hellman Setup
• have two people Alice & Bob
• who wish to exchange some key over an insecure communications channel
• initially they (and all who participate in key exchanges):
• select a large prime integer or polynomial `p` (~200 digits)
• `a` a primitive root `mod p`
• Alice chooses a secret key (number) `xA < p`
• Bob chooses a secret key (number) `xB < p`
• Alice and Bob compute their public keys:
```yA = axA mod p
yB = axB mod p
```
• Alice and Bob make public `yA` and `yB` respectively

The prime p and primitive root a can be common to all using some instance of the D-H scheme. Note that the primitive root `a` is a number whose powers successively generate all the elements mod p. Alice and Bob choose random secrets `x`'s, and then "protect" them using exponentiation to create the `y`'s. For an attacker monitoring the exchange of the `y`'s to recover either of the `x`'s, they'd need to solve the discrete logarithm problem, which is hard.

4. Diffie-Hellman Key Exchange
• the key is then calculated as:
```KAB = axA.xB mod p
= yAxB mod p (which B can compute)
= yBxA mod p (which A can compute)
```
• `KAB `may then be used as a session key in a private-key cipher to secure communications between Alice and Bob
• note if Alice and Bob subsequently wish to communicate, they will have the same key as before, unless they choose new public-keys

The actual key exchange for either party consists of raising the others "public key' to power of their private key. The resulting number (or as much os as is necessary) is used as the key for a block cipher or other private key scheme. For an attacker to obtain the same value they need at least one of the secret numbers, which means solving a discrete log, which is computationally infeasible given large enough numbers.

5. Diffie-Hellman Example
• given prime `p=97` with primitive root `a=5`
• Alice chooses secret `xA=36` & computes public key `yA=536=50 mod 97`
• Bob chooses secret `xB=58` & computes public key `yB=558=44 mod 97`
• Alice and Bob exchange their public keys (50 & 44 respectively)
• Alice computes the shared secret ```K=4436=75 mod 97```
• Bob computes the shared secret `K=5058=75 mod 97`
• an attacker Charlie would need to first crack one of the secrets knowing only the public information, eg Alice's by solving `xA=log550=36 mod 97` (hard), and then doing Alice's key computation `K=4436=75 mod 97`

This examples illustrates the use of DH key exchange. Note that the "square and multiply" algorithm, with suitable modulo reductions would be used to do the calculations. Also see how an attacker would have to solve the "hard" discrete log problem in order to obtain the shared secret.

6. Diffie-Hellman in Practise
• each time any 2 parties want to communicate they could choose new, random secret keys, and compute and exchange public keys
• safe against passive eavesdropping, but not active attacks
• does give new session keys each time though
• to secure against active attack additional protocols are needed
• alternatively they can generate "long-term" public keys
• and have them placed in a secure central directory
7. Multi-Precision Arithmetic
• involves libraries of functions that work on multiword (multiple precision) numbers
• classic references are in Knuth vol 2 - "Seminumerical Algorithms"
• multiplication digit by digit (word by word)
• do exponentiation using square and multiply
• are a number of well known multiple precision libraries available - so don't reinvent the wheel!!!!
• can use special tricks when doing modulo arithmetic, especially with the modulo reductions

Implementation of public key crypto requires the use of multi-precision arithmetic libraries. A number of these are now commonly available. Show slides illustrating multi-digit calcs.

8. Faster Modulo Reduction
• Chivers (1984) noted a fast way of performing modulo reductions whilst doing multi-precision arithmetic calcs
• given an integer A
• can be written as n characters ```a0, ... , an-1``` of base b
• where the base `b` is the "most convenient" word size
```    n-1
A = SUM ai.bi
i=0
```
• then
```      n-2
A = { SUM ai.bi + an-1.bn-1 (mod jm) } mod m
i=0
```
• ie: this implies that the MSD of a number can be removed and its remainder mod m added to the remaining digits will result in a number that is congruent mod m to the original

Idea here is that, as always, can modulo reduce numbers at any time. In particular if think of a number as the sum `A=Atop+Arest` can freely replace `Atop` with its modulo reduced equivalent. And keep doing this till the number is "small enough".

9. Chivers Algorithm
• Construct an array R = (bd, 2.bd, ... , (b-1).bd)(mod m)
• Modulo reduce at any stage by doing:
```FOR i = n-1 to d do
WHILE A[i] != 0 do
j = A[i];
A[i] = 0;
A = A + bi-d.R[j];
END WHILE
END FOR
```
• where `A[i]` is the ith character of number A
`R[j]` is the jth integer residue from the array R
`n` is the number of symbols in A
`d` is the number of symbols in the modulus

To implement Chivers Algorithm first compute an array of all possible `Atop` values (obviously trade-off size of digit with size of array - 4 to 8 bits is most likely). Then while doing calculations simply replace the top "digit" with its modulo reduced equivalent. Can even do this process in stages (ie if need a "top digit" thats too large, could do in halves etc, with separate arrays). Show slides illustrating multi-digit calcs with modulo reductions.