Cryptography - Lecture 17 - Public Key Encryption Algorithms

Objectives

Preliminary Reading

Lecture Content

Public-Key Encryption - RSA

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

     Public-Key Encryption schemes allow us to encrypt arbitrary messages. Whilst a number of proposals have been made over the years, only those based on exponentiation in various finite fields are still secure. This is a worry! It also shows just how difficult it has been to find suitable asymmetric problems to use.

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

     RSA is the best known, and by far the most widely used general public key encryption algorithm. The main hinderance to its further use are legal concerns over its patent status (expired some places, soon to be elsewhere, and likely invalid in others still).

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}

     This key setup is done once (rarely) when a user establishes (replaces) their public key. The exponent e is usually fairly small, just must be relatively prime to ø(N). Need to compute its inverse to find d. It is critically important the {d,p,q} are all kept secret, since if any become known, the system can be broken. Note that different users will have different modulii N.

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

     Note here some caveats on the selection of RSA parameters. Further suggestions have been made about "strong RSA" primes, which may or may not improve security (they concern the makeup of p-1 & q-1).

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

     Would need to use general inverse alg to compute d, and "square and multiply" for all exponentiations.

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

      Original RSA inventors proposed a challenge published in Scientific American in 1977 for US$100 reward. This was for a 129 digit number, and was broken (and the prize claimed) in 1994. Subsequently RSA Labs have issued a series of challenges, complementing their DES/RC-5 challenges for 110, 120, 130, 140 etc digit numbers. nb. A MIPS-year is 3x10¹³ instructions/year.

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

      These are both esorteric approaches that would come into play if exceed 2000 digits, till then the conventional approach is best.

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
      

      Using the Chinese Remainder Theorem though is a well known and fairly widely used method for speeding up decrpytion/signature calculations, by working mod p, mod q separately and then combining the results. Remeber speed of exponentiation is proprtional to the cube of the size of the numbers! Of course, you have to know p, q which means only the key owner can do this.

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

      These figures are all rather dated now. Need an update!!! Key difference is mostly between small end-user systems (PC's to smartcards) which have to do single computations "fast enough" not to annoy user, ie < few secs; to large systems which have to support many users, and hence have to do multiple computations in (pseudo) parallel and still be "fast enough".

Public-Key Encryption - El Gamal

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

     El Gamal is the major alternative to RSA for public key encrpytion use. Whilst there is some patent coverage, it is much less encumbered, and hence has been preferred where patent issues were of concern.

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

     Note that key setup is identical to Diffie-Hellman, each user chooses a random secret number and "protects" it using exponentiation.

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

     The idea with encryption is basically to choose another random key, protect it, then use it to scramble the message by multiplying the message with it. Two bits of info have to be sent: the first to recover this temporary key, the second the actual scrambled message. Note that all trace of the temporary key k should be destroyed once its been used.

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

     Decryption consists of recovering the temporary key K (in a manner very similar to the DH shared secret), and then recovering the message by solving the same equation, this time by dividing by K, ie mult with inverse of K.

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

     This examples illustrates the use of ElGamal encryption & decryption. Would need to use the general inverse alg to compute K^-1, and of course the "square and multiply" alg for all exponentiations.

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

Summary

1. Summary
   • RSA algorithm
   • ElGamal algorithm
   • some implementation issues

Exercises

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

Additional References