Cryptography - Lecture 16 - Public Key Encryption Algorithms

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

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

3. Public-Key Cryptography

Asymmetric (Public Key) Encrpytion Scheme

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

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

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

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

8. 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)³) 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)

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

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

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

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

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

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

15. 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 + bi-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
  

16. Summary

• concept of public key cryptography
• Diffie-Hellman Public Key Distribution Scheme
• implementation of multi-precision arithmetic

17. Exercises

1. Illustrate the operation of the Diffie-Hellman public key exchange scheme, given the following public parameters:
   
   • prime p=37
   • prim root a=5
   Compute suitable public keys for users Alice and Bob, and illustrate the key exchange, verifying that the same shared session key is obtained.
2. Illustrate the operation of the Diffie-Hellman public key exchange scheme, given the following public parameters:
   
   • prime p=59
   • prim root a=6
   As above.