# Other Public-Key Cryptosystems

## Diffie-Hellman Key Exchange

- Also called DH Key Exchange (Algorithm/Scheme)
- **The First Published Public-Key Algorithm**
- Proposed by Diffie and Hellman (Stanford University, 1976)
- Key Exchange
- = Key Agreement = Key Establishment = Key Distribution
- Establish a **session key** between two communicants so that the communicants can use a Conventional Encryption Algorithm with the session key to encrypt/decrypt the messages.
- Security Basis: **Discrete Logarithm Problem** (DLP)
- Patent: the Diffie-Hellman patent (expired on April 29, 1997).

### DH Key Exchange Scheme


- Example

### Security of DH Key Exchange Scheme

- Security Basis of the DH key exchange scheme: **Discrete Logarithm Problem** (DLP).
- DLP: Given $\alpha, Y$, and $q$, find $X$ (if exists) $\backepsilon \alpha^X \pmod q = Y$.
- **Computationally Intractable Problem**
- **no efficient classical algorithm** is known for computing discrete logarithms in general
- Discrete Logarithm Algorithms
- Function field sieve
- Number field sieve
- Pohlig–Hellman algorithm
- Pollard's rho algorithm for logarithms
- Pollard's lambda algorithm
- **Quantum Threat** to DLP
- **Shor's quantum algorithm can efficiently solve DLP** by using large scale quantum computers, which do not exist yet.
- Discrete Logarithm Records (Modulo Primes)
- <https://en.wikipedia.org/wiki/Discrete_logarithm_records>
- Man-in-the-Middle Attack（中間人攻擊）
- Bob and Alice will think that they share a secret key, but instead **Bob and Darth share secret key K1** and **Alice and Darth share secret key K2**.
- The DH key exchange scheme is **vulnerable to such an attack** because it does **not authenticate the participants**.

## ElGamal Cryptosystem

- Proposed by T. ElGamal
- ElGamal has been described as the **father of SSL**.
- Security Basis: DLP (Discrete Logarithm Problem)
- Patent: unpatented
- under the Diffie-Hellman patent (expired on April 29, 1997).
- Note that ElGamal Digital Signature Scheme is **another scheme**, which is specifically **used for digital signature**.

### Algorithm of ElGamal Cryptosystem


- Example

### Security of ElGamal Cryptosystem

- Security Basis of ElGamal Cryptosystem: DLP
- DLP is a Computationally Intractable Problem.
- Quantum Threat to DLP
- Shor's quantum algorithm can efficiently solve DLP by using large scale quantum computers, which do not exist yet.
- The initial ElGamal Cryptosystem is **malleable**, and therefore is **vulnerable to Chosen Ciphertext Attack** (CCA).
- An encryption algorithm is malleable if it is possible to transform a ciphertext into another ciphertext which decrypts to a related plaintext.
- Example: Given an encryption (C1, C2) of some message m, the attacker can easily construct a valid encryption (C1, 2C2) of the message 2m.
- Countermeasure: By employing an **appropriate padding mechanism**, CCA can be prevented.
- Drawback of ElGamal Cryptosystem
- The ciphertext is **twice the size** of the plaintext.

## Elliptic Curve Arithmetic

### Abelian Groups


### Elliptic Curves (EC)

- Elliptic Curves are **not ellipses**
- Why named “Elliptic Curve”? Elliptic Curves are described in formulae similar to those used for calculating the circumference of an ellipse.
- An **elliptic curve over real numbers** is defined by an equation in two variables with coefficients, which results in an **abelian group**.
- For cryptography, the **variables and coefficients** are restricted to elements in a **finite field**, which results in a finite abelian group.

### Elliptic Curve over Real Numbers

- E(a, b): The set of Points of EC over Real Numbers $((1)\cup(2))$
- (1) $y^2 = x^3 + ax + b$
- (2) O (Point at Infinity $\equiv$ Zero Point)
- Examples Set 1 (EC over Real Numbers)
- Examples Set 2 (EC over Real Numbers)
- Elliptic Curve Arithmetic over Real Numbers: E(a, b) can be a abelian group if 4a^3^ + 27b^2^ != 0 and the following rules hold:
- O: additive identity
- O = −O
- P + O = P for any point P on E(a, b)
- If P = (x, y) (!= O) is a point on E(a, b), then −P = (x, −y) is also a point on E(a, b).
- If P is a point on E(a, b), then P + (−P) = P − P = O.
- Geometrical Description of Double
- If Q is a point on E(a, b), we can draw the tangent line on Q and find intersection S.
- Q + Q = 2Q is defined to be −S.

<!-- TODO p.16~24 -->

## Elliptic Curve Cryptography