Cryptography IV: Public Key Cryptography & Key Management

Private-Key Cryptography

• Traditional cryptography uses a single key.

• The key is shared between the sender and receiver.

• Compromised if the key is disclosed.

• Communications are compromised.

• Symmetric: parties are equal so it does not protect the sender from the receiver forging a message and claiming it was sent by the sender.

Public-Key Cryptography

• Significant cryptographic advancement.

• Uses two keys: a public key and a private key.

• Asymmetric: Parties are not equal.

• Applies number theoretic concepts.

• Complements, rather than replaces, private key crypto.

Why Public-Key Cryptography?

• Developed to address two key issues:

  • Key distribution: Secure communications without trusting a Key Distribution Center (KDC).

  • Digital signatures: Verify a message comes intact from the claimed sender.

Public-Key Cryptography

• Involves two keys:

  • A public key: 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 create signatures.

• Asymmetric:

  • Those who encrypt messages or verify signatures cannot decrypt messages or create signatures.

Public-Key Cryptography

• Alice encrypts a plaintext input using Bob's public key and an encryption algorithm (e.g., RSA) to produce transmitted ciphertext.

• Bob decrypts the ciphertext using Alice's private key, with a decryption algorithm (reverse of encryption algorithm), to output the plaintext.

Public-Key Characteristics

• Relies on two keys with the following characteristics:

  • Computationally infeasible to find the decryption key knowing only the algorithm and encryption key.

  • Computationally easy to encrypt/decrypt messages when the relevant key is known.

  • Either of the two related keys can be used for encryption, with the other used for decryption (for some algorithms).

Public-Key Applications

• Uses are classified into three categories:

  • Encryption/decryption (provide secrecy).

  • Digital signatures (provide authentication).

  • Key exchange (of session keys).

• Some algorithms suit all uses, while others are specific to one.

Security of Public Key Schemes

• Brute force exhaustive search attack is theoretically possible.

• Keys used are too large (> 512 bits).

• Security relies on a large enough difference in difficulty between easy (en/decrypt) and hard (cryptanalyse) problems.

• The hard problem is known, but made too hard to do in practice.

• Requires the use of very large numbers, and is slow compared to private key schemes.

RSA

• by Rivest, Shamir & Adleman of MIT in 1977

• Best known & widely used public-key scheme.

• Based on exponentiation in a finite (Galois) field over integers modulo a prime

  • Exponentiation takes $O((\log n)^3)$ operations (easy).

• Uses large integers (e.g., 1024 bits).

• Security is due to the cost of factoring large numbers.

  • Factorization takes $O(e^{\log n \log \log n})$ operations (hard).

RSA Key Setup

• Each user generates a public/private key pair by:

  • Selecting two large primes at random: p, q.

  • Computing their system modulus $n = p \cdot q$. Note $\phi(n) = (p-1)(q-1)$.

  • Selecting at random the encryption key e where 1 < e < \phi(n), $GCD(e, \phi(n)) = 1$.

  • Solving the following equation to find decryption key d: $e \cdot d = 1 \mod \phi(n)$ and $0 \le d \le n$.

  • Publishing their public encryption key: $KU = {e, n}$.

  • Keeping secret private decryption key: $KR = {d, p, q}$.

RSA Use

• To encrypt a message M, the sender:

  • Obtains the public key of recipient $KU = {e, n}$.

  • Computes: $C = M^e \mod n$, where 0 \le M < n.

• To decrypt the ciphertext C, the recipient:

  • Uses their private key $KR = {d, p, q}, n = p \cdot q$.

  • Computes: $M = C^d \mod n$.

• The message M must be smaller than the modulus n (block if needed).

RSA Example – Key Setup

1. Select primes: $p = 17$ and $q = 11$

2. Compute $n = pq = 17 \times 11 = 187$

3. Compute $\phi(n) = (p – 1)(q - 1) = 16 \times 10 = 160$

4. Select e: 1 < e < 160, $GCD(e, 160) = 1$. Choose $e = 7$

5. Determine d: $de = 1 \mod 160$ and d < 160. Value is $d = 23$ since $23 \times 7 = 161 = 10 \times 160 + 1$

6. Publish public key $KU = {7, 187}$

7. Keep secret private key $KR = {23, 17, 11}$

RSA Example – En/Decryption

• Given message $M = 88$ (note 88 < 187).

• Encryption: $C = 88^7 \mod 187 = 11$

• Decryption: $M = 11^{23} \mod 187 = 88$

Exponentiation

• Can use the Square and Multiply Algorithm.

• A fast, efficient algorithm for exponentiation.

• Concept is based on repeatedly squaring the base and multiplying in the ones that are needed to compute the result.

• Look at the binary representation of the exponent.

• Takes $O(\log_2 n)$ multiples for number n

  • $7^5 = 7^4 \cdot 7^1 = 3 \cdot 7 = 10 \mod 11$

  • $3^{129} = 3^{128} \cdot 3^1 = 5 \cdot 3 = 4 \mod 11$

Square and Multiply Algorithm

• Compute $a^e \mod n$:

  • Convert e to binary: $b<em>{i-1} \dots b</em>1 b_0$

  • $z = 1$

  • for $k = i-1$ downto 0 do

    • $z = z^2 \mod n$

    • if $b_k = 1$ then $z = (z^2 \times a) \mod n$

  • return z

S & M Algorithm - Example

• $11^{23} \mod 187 = 88$

RSA Key Generation

• Users of RSA must:

  • Determine two primes at random: p, q.

  • Select either e or d and compute the other.

• Primes p, q must not be easily derived from modulus $n = p \cdot q$.

  • Means must be sufficiently large.

  • Typically guess and use probabilistic test.

• Exponents e, d are inverses, so use inverse algorithm to compute the other.

RSA Security

• Possible approaches to attacking RSA:

  • Brute force key search (infeasible given the size of numbers).

  • Mathematical attacks (based on difficulty of computing $\phi(n)$, by factoring modulus n).

  • Timing attacks (on running of decryption).

  • Chosen ciphertext attacks (given properties of RSA).

Factoring Problem

• Mathematical approach takes 3 forms:

  • Factor $n = p \cdot q$, hence find $\phi(n)$ and then d.

  • Determine $\phi(n)$ directly and find d.

  • Find d directly.

• Currently believe all equivalent to factoring.

• Have seen slow improvements over the years.

• As of Feb-20, the best is 250 decimal digits (829 bit) with GNFS.

• Currently assume 1024+ bit RSA is secure.

• Ensure p, q of similar size and matching other constraints.

Timing Attacks

• Developed by Paul Kocher in the mid-1990s.

• Exploit timing variations in operations.

  • Multiplying by a small vs a large number.

  • Or IF's varying which instructions are executed.

• Infer operand size based on time taken.

• RSA exploits time taken in exponentiation.

• Countermeasures:

  • Use constant exponentiation time.

  • Add random delays.

  • Blind values used in calculations.

Key Management

• Public-key encryption helps address key distribution problems.

• There are two aspects to this:

  • Distribution of public keys.

  • Use of public-key encryption to distribute secret keys.

Public-Key Distribution of Secret Keys

• Use previous methods to obtain the public key.

• Can use it for secrecy or authentication.

• Public-key algorithms are slow.

• Want to use private-key encryption to protect message contents.

• Need a session key.

• Have several alternatives for negotiating a suitable session.

Diffie-Hellman Key Exchange

• First public-key type scheme proposed.

• By Diffie & Hellman in 1976 along with the exposition of public key concepts.

  • James Ellis (UK CESG) secretly proposed the concept in 1970.

• A practical method for public exchange of a secret key.

• Used in a number of commercial products.

Diffie-Hellman Key Exchange

• A public-key distribution scheme.

  • Cannot be used to exchange an arbitrary message.

  • Rather, it can establish a common key.

  • The value of the key depends on the participants (and their private and public key information).

• Based on exponentiation in a finite (Galois) field (modulo a prime or a polynomial) - easy.

• Security relies on the difficulty of computing discrete logarithms (similar to factoring) - hard.

Diffie-Hellman Setup

• All users agree on global parameters:

  • Large prime integer or polynomial q.

  • α, primitive root mod q.

• Each user (e.g., A) generates their key:

  • Chooses a secret key (number): x_A < q.

  • Computes their public key: $y<em>A = \alpha^{x</em>A} \mod q$.

• Each user makes public that key $y_A$.

Diffie-Hellman Key Exchange

• Shared session key for users A & B is $K_{AB}$:

  • $K<em>{AB} = \alpha^{x</em>A \cdot x<em>B} \mod q = y</em>A^{x_B} \mod q$ (which B can compute)

  • $= y<em>B^{x</em>A} \mod q$ (which A can compute)

• $K_{AB}$ is used as the session key in a private-key encryption scheme between Alice and Bob.

• If Alice and Bob subsequently communicate, they will have the same key as before, unless they choose new public-keys.

• Attacker needs an x, must solve the discrete log.

Diffie-Hellman Example

• Users Alice & Bob who wish to swap keys:

• Agree on prime $q = 353$ and $\alpha = 3$

• Select random secret keys:

  • A chooses $x<em>A = 97$, B chooses $x</em>B = 233$

• Compute public keys:

  • $y_A = 3^{97} \mod 353 = 40$ (Alice)

  • $y_B = 3^{233} \mod 353 = 248$ (Bob)

• Compute the shared session key as:

  • $K<em>{AB} = y</em>B^{x_A} \mod 353 = 248^{97} = 160$ (Alice)

  • $K<em>{AB} = y</em>A^{x_B} \mod 353 = 40^{233} = 160$ (Bob)

Man in the Middle Attack

• Charles chooses a secret key, $x_c = 3$

• He intercepts $q = 353, \alpha = 3, y<em>A = 40, y</em>B = 248$

• He computes public key $y_c = 3^3 \mod 353 = 27$ and sends it to Alice and Bob

• He then computes $K<em>{AC} = 40^3 \mod 353 = 107$ and $K</em>{BC} = 248^3 \mod 353 = 215$

• Not knowing the public key is from Charles:

  • Alice computes $K = 27^{97} \mod 353 = 107$

  • Bob computes $K = 27^{233} \mod 353 = 215$

El Gamal Public-Key Encryption Scheme

• A variant of the Diffie-Hellman key distribution scheme.

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

• A major disadvantage is that it doubles the size of the information sent.

El Gamal Setup

• Key Generation:

  • Select a large prime p, and α, a primitive element mod p.

  • Recipient Bob chooses a secret number xB (0 < xB < p) and computes $y<em>B = \alpha^{x</em>B} \mod p$

El Gamal Encryption

• To encrypt a message M into ciphertext C:

• Sender selects a random number n (sender’s private key), 0 < n < p

• Computes the message key, $K = (y_B)^n \mod p$

• Then computes the ciphertext pair: $C = {C<em>1, C</em>2}$, where

  • $C_1 = \alpha^n \mod p$

  • $C_2 = K \cdot M \mod p$

• This is then sent to the recipient.

• Note that K should be destroyed after use and never knowingly used again.

El Gamal Decryption

• To decrypt the message:

• Extracts the message key K:

  • $K = (C<em>1)^{x</em>B} \mod p$

• Extracts M by solving for M in the following equation:

  • $M = C_2 \cdot K^{-1} \mod p$

El Gamal Example

• Given prime $p = 97$ with primitive root $\alpha = 5$

• Recipient Bob chooses secret key, $x<em>B = 58$ & computes & publishes his public key, $y</em>B = 5^{58} = 44 \mod 97$

• Alice wishes to send the message $M = 3$ to Bob

• She obtains Bob's public key, $y_B = 44$

• She chooses random $n = 36$ (her private key) and computes the message key:

  • $K = 44^{36} = 75 \mod 97$

• She then computes the ciphertext pair:

  • $C_1 = 5^{36} = 50 \mod 97$

  • $C_2 = 75 \cdot 3 \mod 97 = 31 \mod 97$

  • and sends the ciphertext ${{50, 31}}$ to Bob

• Bob recovers the message key $K = 50^{58} = 75 \mod 97$

• Bob computes the inverse $K^{-1} = 22 \mod 97$

• Bob recovers the message $M = 31 \cdot 22 = 3 \mod 97$

Elliptic Curve Cryptography

• The majority of public-key crypto (RSA, D-H) uses either integer or polynomial arithmetic with very large numbers/polynomials.

• Imposes a significant load in storing and processing keys and messages.

• An alternative is to use elliptic curves.

• Offers the same security with smaller bit sizes.

Real Elliptic Curves

• An elliptic curve is defined by an equation in two variables x & y, with coefficients.

• Consider a cubic elliptic curve of the form:

  • $y^2 = x^3 + ax + b$

  • where x, y, a, b are all real numbers

  • Also define point O (point at infinity)

• Have addition operation for elliptic curve

  • Geometrically sum of Q+R is the reflection of the intersection R

Real Elliptic Curve Example

• This slide shows some example elliptic curves of the form $y^2 = x^3 + ax + b$

Finite Elliptic Curves

• Elliptic curve cryptography uses curves whose variables & coefficients are finite.

• Have two families commonly used:

  • Prime curves $E<em>p(a, b)$ defined over $Z</em>p$

    • Use integers modulo a prime

    • Best in software

  • Binary curves $E_{2^m}(a, b)$ defined over $GF(2^n)$

    • Use polynomials with binary coefficients

    • Best in hardware

Elliptic Curve Cryptography

• ECC addition is analog of modulo multiply.

• ECC repeated addition is analog of modulo exponentiation.

• Need “hard” problem equivalent to discrete log.

  • $Q = kP$, where Q, P belong to a prime curve.

  • It is “easy” to compute Q given k, P.

  • But it is “hard” to find k given Q, P.

  • Known as the elliptic curve logarithm problem.

• Certicom example: E23(9, 17)

  • https://www.certicom.com/content/certicom/en/52-the-elliptic-curve-discrete-logarithm-problem.html

ECC Diffie-Hellman

• Can do key exchange analogous to D-H.

• Users select a suitable curve $E_p(a, b)$

• Select base point $G = (x<em>G, y</em>G)$ with large order n such that $nG = O$

• A & B select private keys kA < n, kB < n

• Compute public keys: $P<em>A = k</em>A G, P<em>B = k</em>B G$

• Compute shared key: $K<em>{AB} = k</em>A P<em>B = k</em>B P_A$

  • Same since $K<em>{AB} = k</em>A k_B G$

ECC Encryption/Decryption

• Several alternatives, will consider the simplest.

• Must first encode any message M as a point on the elliptic curve $P_m$

• Select suitable curve & point G as in D-H.

• Each user chooses a private key kA, kB < n

• and computes the public key $P<em>A = k</em>A G, P<em>B = k</em>B G$

• To encrypt $P<em>m$: $C</em>m = {k<em>A G, P</em>m + k<em>A P</em>B} = {C<em>1, C</em>2}$

• Decrypt $C_m$ compute:

  • $C<em>2 – k</em>B C<em>1 = P</em>m$

ECC Example

• Consider $E_{751}(-1, 188)$ and $G = (0, 376)$

• E is of order $n = 727$ such that $nG = O$

• Alice wishes to send the message $P_m = (562, 201)$ to Bob

• She obtains Bob's public key $P_B = (201, 5)$

• She chooses random $k = 386$

• She then computes the ciphertext $C<em>m = {kG, P</em>m + kP_B}$

  • where $kG = 386(0, 376)$

  • and $P<em>m + kP</em>B = (562, 201) + 386(201, 5) = (385, 328)$

• and sends the ciphertext {{(676, 558), (385, 328)} to Bob

ECC Security

• Relies on the elliptic curve logarithm problem.

• The fastest method is the “Pollard rho method.”

• Compared to factoring, can use much smaller key sizes than with RSA etc.

• For equivalent key lengths, computations are roughly equivalent.

• Hence, for similar security, ECC offers significant computational advantages.

Comparable Key Sizes for Equivalent Security

Summary

• Public-key cryptosystems:

  • RSA

  • Diffie-Hellman key exchange

  • El Gamal Scheme

  • Elliptic Curve cryptography