- 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.

- traditional
- 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**

- a
- 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.

- Public-Key Cryptography

Asymmetric (Public Key) Encrpytion SchemeNote 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. - 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**problemPublic 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.

- 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.

- 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 schemesPublic 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.

- security relies on a

- 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!

- 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)

- nb exponentiation takes O((log n)
- 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.

- nb discrete logarithms takes O(e

- a public-key distribution scheme
- 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)
`x`

_{A}< p - Bob chooses a secret key (number)
`x`

_{B}< p - Alice and Bob compute their
**public keys**:y

_{A}= a^{xA}mod p y_{B}= a^{xB}mod p - Alice and Bob make public
`y`

and_{A}`y`

respectively_{B}

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. - select a large prime integer or polynomial

- Diffie-Hellman Key Exchange
- the key is then calculated as:
K

_{AB}= a^{xA.xB}mod p = y_{A}^{xB}mod p (which**B**can compute) = y_{B}^{xA}mod p (which**A**can compute) `K`

may then be used as a session key in a private-key cipher to secure communications between Alice and Bob_{AB}- note if Alice and Bob subsequently wish to communicate, they will have
the
**same**key as before, unless they choose new public-keysThe 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.

- the key is then calculated as:
- Diffie-Hellman Example
- given prime
`p=97`

with primitive root`a=5`

- Alice chooses secret
`x`

& computes public key_{A}=36`y`

_{A}=5^{36}=50 mod 97 - Bob chooses secret
`x`

& computes public key_{B}=58`y`

_{B}=5^{58}=44 mod 97 - Alice and Bob exchange their public keys (50 & 44 respectively)
- Alice computes the shared secret
`K=44`

^{36}=75 mod 97 - Bob computes the shared secret
`K=50`

^{58}=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
`x`

(hard), and then doing Alice's key computation_{A}=log_{5}50=36 mod 97`K=44`

^{36}=75 mod 97This 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.

- given prime
- 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

- 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.

- 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
`a`

of base b_{0}, ... , a_{n-1}

- where the base
`b`

is the "most convenient" word sizen-1 A = SUM a

_{i}.b^{i}i=0 - then
n-2 A = { SUM a

_{i}.b^{i}+ a_{n-1}.b^{n-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=A`

can freely replace_{top}+A_{rest}`A`

with its modulo reduced equivalent. And keep doing this till the number is "small enough"._{top}

- Chivers Algorithm
- Construct an array
**R = (b**^{d}, 2.b^{d}, ... , (b-1).b^{d})(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 + b

^{i-d}.R[j]; END WHILE END FOR - where
`A[i]`

is the i^{th}character of number A`R[j]`

is the j^{th}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

`A`

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._{top}

- Construct an array