Cryptography - Lecture 17 - Public Key Encryption Algorithms

1. Public-Key Encryption

• public-key encryption schemes can be used to encrypt arbitrary messages
• often can also be used as signature schemes and to exchange keys
• eg. RSA, ElGamal
• these are based on exponentiation in various finite fields (galois fields over integers or polynomials, elliptic curves etc)
• other problems have been proposed for use (Knapsacks, Error Correcting Codes)
• but all these have been broken

2. RSA (Rivest, Shamir, Adleman)

• best known and widely regarded as most practical public-key scheme
• first proposed by Rivest, Shamir & Adleman (RSA) in 1977
• R L Rivest, A Shamir, L Adleman, "On Digital Signatures and Public Key Cryptosystems", Communications of the ACM, vol 21 no 2, pp120-126, Feb 1978
• based on exponentiation in a finite (Galois) field over integers modulo a prime
  • nb exponentiation takes O((log n)³) operations (easy)
• security relies on the difficulty of calculating factors of large numbers
  • nb factorization takes O(e ^{log n log log n}) operations (hard)
  • (same as for discrete logarithms)
• RSA algorithm is patented in North America (and some other countries)
• this is a source of legal difficulties in using the scheme

3. RSA Setup

• initially each user generates their public/private key pair by:
• selecting two large primes at random (~100 digit), p, q
• computing their system modulus N=p.q
• selecting at random the encryption key e, where e<N, gcd(e,ø(N))=1
• solving the following congruence to find the decryption key d:
• e.d=1 mod ø(N) and 0<=d<=N
• making public their public encryption key: Kr={er,Nr}
• keeping secret their private decryption key: K-1r={d,p,q}

4. RSA Parameter Selection

• need to choose suitably large p, q
• usually choose the encryption exponent e to be a small number
• which must be relatively prime to ø(N)
• typically e may be the same for all users
• (provided certain precautions are taken)
• originally a value of 3 was suggested
• now regarded as too small
• but 216-1 = 65535 is often used
• note that the decryption exponent d will then be large

5. RSA Usage

• to encrypt a message M the sender obtain the public key of the recipient Kr={er,Nr}
• then computes: C=Mer mod Nr, where 0<=M<N
• to decrypt the ciphertext C the owner uses their private key K-1r={d,p,q}
• and computes: M=Cd mod Nr

6. Theory Behind RSA

• RSA works because of Euler's Generalisation of Fermat's Theorem:
• if N = pq where p, q are primes, then:
  Xø(N) = 1 mod N
• for all x not divisible by p or q, ie gcd(x,ø(N))=1
• where ø(N)=(p-1)(q-1)
• but in RSA have carefully chose e & d to be inverses mod ø(N)
• ie e.d=1+q.ø(N)
• hence have:
  M = Cd = Me.d = M1+q.ø(N) =
M1.(Mø(N))q = M1.(1)q = M1 mod N

7. RSA Example

• choose modulus N=11*47=517
• compute ø(N) = (p-1)(q-1) = 10*46 = 460
• choose encryption exponent 3
• check GCD(3,ø(N)) = GCD(3,460) = 1
• compute decryption exponent d by solving:
  e.d=1 mod ø(N) where 0<=d<=N
• use Extended Euclid's/Binary GCD calculation to do this:
  d=Inverse(3,460)=307 by Euclid's alg
• hence public key is: K=(3,517)
• and private key is: K-1=(307,11,47)

8. RSA Example cont.

• a sample RSA encryption/decryption calculation is:
• given message M = 26
• encryption: C = 263 mod 517 = 515
• decryption: M = 515307 mod 517 = 26

9. RSA Security

• security of RSA rests on the difficulty of computing ø(N)
• which is assumed to require factoring the modulus N
• given that 1e+14 operations is regarded as a limit for computational feasability and there are 3e+13 usec/year
• best known theoretical factoring alg (Brent-Pollard) takes:

  Decimal Digits in N	#Bit Operations to Factor N
  20	7.20e+03
  40	3.11e+06
  60	4.63e+08
  80	3.72e+10
  100	1.97e+12
  120	7.69e+13
  140	2.35e+15
  160	5.92e+16
  180	1.26e+18
  200	2.36e+19

10. Actual Progress in Factoring

• have seen slow improvements over the years
• biggest improvement comes from improved algorithm
• but barring a dramatic breakthrough 1024+ bit RSA looks secure for now
  

  Decimal Digits	Bits	When	MIPS-Years	Alg Used
  100	332	Apr 91	7	Quadratic Sieve
  110	365	Apr 92	75	Quadratic Sieve
  120	398	Jun 93	830	Quadratic Sieve
  129	428	Apr 94	5000	Quadratic Sieve
  130	431	Apr 96	500	Number Field Sieve
  140	464	Feb 99	1500	Number Field Sieve

  
  Progress In Factorisation Against RSA Challanges

11. RSA in Practise

• this leads to a modulus of length 300 digits (or 1024+ bits)
• but most (all!!) computers can't directly handle numbers larger than 32-bits (64-bits on the very newest)
• hence need to use multiple precision arithmetic libraries to handle numbers this large
• as saw before with Diffie-Hellman
• however can consider some techniques for speeding up RSA calcs specifically

12. Speeding up RSA - Alternate Multiplication Techniques

• conventional multiplication takes O(n²) bit operations, faster techniques include:
• the Schonhage-Strassen Integer Multiplication Algorithm:
  • breaks each integer into blocks, and uses them as coefficients of a polynomial
  • evaluates these polynomials at suitable points, & multiplies the resultant values
  • interpolates these values to form the coefficients of the product polynomial
  • combines the coefficients to form the product of the original integer
  • the Discrete Fourier Transform, and the Convolution Theorem are used to speed up the interpolation stage
  • can multiply in O(n log n) bit operations
• the use of specialized hardware because:
  • conventional arithmetic units don't scale up, due to carry propogation delays
  • so can use serial-parallel carry-save, or delayed carry-save techniques with O(n) gates to multiply in O(n) bit operations,
  • or can use parallel-parallel techniques with O(n²) gates to multiply in O(log n) bit operations

13. Speeding up RSA - the Chinese Remainder Theorem

• note encryption using small exponents will be fast
• but then decryption exponent will be large and hence decryption is slower
• a significant improvement in decryption speed for RSA can be obtained by using the Chinese Remainder theorem to work modulo p and q respectively
  • since p,q are only half the size of R=p.q and thus the arithmetic is much faster
• CRT is used in RSA by creating two equations from the decryption calculation:
  M = Cd mod R
• as follows:

  M1 = M mod p = (C mod p)d mod (p-1)
  M2 = M mod q = (C mod q)d mod (q-1)
  

• then solve the pair of equations:

  M = M1 mod p
  M = M2 mod q 
  

• which has a unique solution given by the CRT:

  M = [((M2 +q - M1)u mod q] p + M1
  
  where
  
  p.u mod q = 1
  

14. RSA Implementation in Practice

• Software implementations
  • generally perform at 1-10 bits/second on block sizes of 256-512 bits
  • two main types of implementations:
    • on micros as part of a key exchange mechanism in a hybrid scheme
    • on larger machines as components of a secure mail system
• Harware Implementations
  • generally perform 100-10000 bits/sec on blocks sizes of 256-512 bits
  • all known implementations are large bit length conventional ALU units

15. El Gamal Public Key Encryption Scheme

• a variant of the Diffie-Hellman key distribution scheme
• allowing secure exchange of messages
• published in 1985 by ElGamal:
• T. ElGamal, "A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms", IEEE Trans. Information Theory, vol IT-31(4), pp469-472, July 1985.
• like Diffie-Hellman its security depends on the difficulty of computing discrete logarithms
• major disadvantage is that it doubles the size of info sent
• but is less encumbered by patent issues

16. El Gamal Setup

• Key Generation
• select a large prime p, and
• a a primitive element mod p
• recipient Bob has a secret number xB
• and computes yB = axB mod p

17. El Gamal Encryption

• to encrypt a message M into ciphertext C:
• sender selects a random number k, 0<=k<=p-1
• and computes the message key K as:
  • K = yBk mod p
• then computes the ciphertext pair: C = {C1,C2}
  • C1 = ak mod p
  • C2 = K.M mod p
• this is then sent to the recipient
• note that k should be destroyed after use
• and never knowingly used again

18. El Gamal Decryption

• to decrypt the message:
• extracts the message key K
  • K = C1xB mod p = ak.xB mod p
• extracts M by solving for M in the following equation:
  • M = C2.K-1 mod p

19. El Gamal Example

• given prime p=97 with primitive root a=5
• recipient Bob chooses secret xB=58 & computes & publishes his public key:
  yB=558=44 mod 97
• Alice wishes to send the message M=3 to Bob
• she obtains Bob's public key yB=44
• she chooses random k=36 and computes the stream key:
  K=4436=75 mod 97
• she then computes the ciphertext pair:
  • C1 = 536 = 50 mod 97
  • C2 = 75.3 mod 97 = 31 mod 97
• and send the ciphertext {50,31} to Bob
• Bob recovers the message key K=5058=75 mod 97
• Bob computes the inverse K-1 = 22 mod 97
• Bob recovers the message M = 31.22 = 3 mod 97

20. Current Status of Public-Key Schemes

• only currently known secure public key schemes are based on exponentiation
• BUT can compute exponentiations using a range of finite fields:
  • integers in a prime field GF(p)
  • polynomials GF(2^n)
  • elliptic curves (harder to compute so use smaller sizes)
  • lucas functions (special polynomials in integer fields)
• some of which are patented in North America
• it has proved to be very very difficult to develop secure public key schemes
• this in part is why they have not been adopted faster, as their theorectical advantages might have suggested
• as well as issues of speed and efficiency

21. Practical Use of Public Key Schemes

• given the issue of speed
• generally use public key to exchange a single message containing a session key for use in a block cipher
• and another with a signature to verify message content (next topic)
• use the fast private key schemes to handle the bulk of the data

22. Summary

• RSA algorithm
• ElGamal algorithm
• some implementation issues

23. Exercises

1. Illustrate the operation of RSA, given the following parameters:
   • System modulus n=119 (7x17)
   • encryption exp e=11
   Determine the decryption exponent d, and hence details the public and private keys fro this user. Then show how a message M=20 would be encrypted and decrpyted.
2. Illustrate the operation of RSA, given the following parameters:
   • System modulus n=95 (5x19)
   • encryption exp e=11
   As above.
3. Illustrate the operation of El Gamal encryption, given the following parameters:
   • prime p=31
   • prim root a=3
   Determine a suitable private and public key, and then show the exchange of a message M=4.
4. Illustrate the operation of El Gamal encryption, given the following parameters:
   • prime p=31
   • prim root a=11
   Determine a suitable private and public key, and then show the exchange of a message M=18.