1

CS 161, Summer 2026 @ UC Berkeley

Slides credit: Nick Weaver, Nicholas Ngai, Peyrin Kao, Henry Corrigan-Gibbs, Jonah Bedouch

Diffie-Hellman Key Exchange and Public-Key Cryptography

Lecture 15 (Transport 3)

Diffie-Hellman Key Exchange

Lecture 15, CS 161, Summer 2026

Diffie-Hellman Key Exchange

Public-Key Encryption

• Public-Key Cryptography
• ElGamal Encryption
• RSA Encryption
• Hybrid Encryption

Secure Secret Sharing

Symmetric-key cryptography relies on Alice and Bob sharing a secret key.

• Today's goal: Share a secret key over an insecure channel.

​

As an analogy, consider Alice and Bob sharing a secret color over an insecure channel.

• Idea: To disguise a secret color, mix it with a public common color.

Analogy: Secure Color Sharing

Alice generates a secret color amber (A).�Bob generates a secret color blue (B).

Alice mixes G+A, and Bob mixes G+B.

Alice and Bob exchange the mixed G+A and G+B.

Alice mixes G+B with A to get G+A+B.�Bob mixes G+A with B to get G+B+A.

Alice, Bob agree on a public color grey (G).

​

B

+

+

=

=

+

=

+

=

​

A

​

G+A

​

B

​

A

​

G

​

G

​

G+B

​

G+B

​

G+A

G+B+A

G+B+A

Bob

Eve

Alice

Analogy: Secure Color Sharing

If Eve can see the insecure channel, there are two things she might try.

​

1. Un-mix G+A or G+B to learn A or B?�Problem: Unmixing paint is difficult.

​

• Combine G+A and G+B to get G+B+A?�Problem: She ends up with G+A+G+B.�Too much of the shared color!

​

B

+

+

=

=

+

=

+

=

​

A

​

G+A

​

B

​

A

​

G

​

G

​

G+B

​

G+B

​

G+A

G+B+A

G+B+A

Bob

Eve

Alice

Discrete Log Problem: Math Version of Paint Mixing

The discrete logarithm problem:

• Everyone knows public parameters g and p.
• Alice picks a random secret a in {1, 2, ..., p–2}.
• Alice computes g^a mod p.
• Given g^a mod p, it is computationally hard to compute a.

​

The discrete log problem is a mathematical version of "paint mixing."

• g, p is the public color.
• a is the secret color.
• g^a mod p is the "mix" of secret and public colors.

a

g^a mod p

Easy

Hard

a can't be 0 or p–1 because g⁰ = g^p–1 = 1 mod p, making it easy to recover a.

g must be carefully selected to be a "generator," and p must be prime.�Won't discuss further.

Why Discrete Log is Hard

Given y = g^x mod p, no "log" operation exists for recovering x.

All known algorithms to recover x are exponential-time.

Plot of y = g^x mod p

Plot of y = g^x

In mod space, there's no pattern: Given y, it's hard to find x.

With real numbers, there's a pattern: �Larger y corresponds to larger x.

Diffie-Hellman Key Exchange

Alice

Eve

Bob

Randomly generate a

Calculate g^a mod p

Randomly generate b

Calculate g^b mod p

Public values: g, p

Calculate shared symmetric key:

(g^b)^a mod p

Calculate shared symmetric key:

(g^a)^b mod p

g^a mod p

g^b mod p

Given g^a mod p and g^b mod p, Eve cannot compute g^ab mod p.

She could try g^a × g^b mod p, but that is g^a+b mod p, not (g^a)^b mod p.

Properties of Diffie-Hellman

For correctness, both users should end up with the same key.

(g^a)^b mod p = (g^b)^a mod p

For security, we define the Computational Diffie-Hellman (CDH) assumption:�Given g, p, g^a mod p, and g^b mod p, it is hard to compute g^ab mod p.

• Best-known algorithm: Find a, then compute (g^b)^a mod p.�Requires solving the discrete log problem, which is hard.
• CDH is slightly different from discrete log.�(Algorithms that skip finding a might exist, but we don't know any efficient ones.)

Bob receives g^a and�raises it to the bth power.

Alice receives g^b and�raises it to the ath power.

Using Diffie-Hellman

There are two ways of using Diffie-Hellman Key Exchange:

​

1. Generate a key the first time you talk with someone, and use it every time.

• Problem: If Eve records some encrypted communications, then later steals the key, she can decrypt all past messages.

​

2. Generate a new key every time you talk with someone.

• This is sometimes called Diffie-Hellman Ephemeral (DHE).
• Both parties discard a, b, and K = g^ab mod p when they're done.�K is called a session key (only used for a single session).
• Now, an attacker who steals the key cannot decrypt past recorded messages.�This property is called forward secrecy.

Problem: Mallory

Alice

Mallory

Bob

Randomly generate a

Calculate g^a mod p

Public values: g, p

(g^m)^a mod p

(g^m)^b mod p

g^a mod p

g^b mod p

Randomly generate m

Calculate g^m mod p

g^m mod p

g^m mod p

(g^a)^m mod p

(g^b)^m mod p

Randomly generate b

Calculate g^b mod p

Mallory and Alice have derived the shared secret g^ma mod p.

Mallory and Bob have derived the shared secret g^mb mod p.

Diffie-Hellman: Issues

Diffie-Hellman is not secure against a MITM adversary.

• Mallory can cause Alice and Bob to each derive a (different) key that she knows.
• In other words: Mallory steps in and completes two separate handshakes between Alice–Mallory and Mallory–Bob.

​

Diffie-Hellman does not provide authentication.

• You exchanged keys with someone, but Diffie-Hellman makes no guarantees about who you exchanged keys with; it could be Mallory!

​

DHE is an active protocol: Alice and Bob need to be online at the same time.

• What if Bob wants to encrypt something and send it to Alice for her to read later?

Elliptic-Curve Diffie-Hellman (ECDH)

The math of Diffie-Hellman can be generalized to:

• A finite set of elements. (In our case, the integers mod p.)
• Binary operations that operate on those elements. (In our case, multiplication.)

​

Elliptic-curve Diffie-Hellman (ECDHE) is a variant that uses different math:

• The set of elements is points on an elliptic curve.
• A binary operation exists that takes in two points and outputs a third point.
• Won't discuss the math further.

​

The underlying problem in ECDHE is harder to solve, so we can use smaller keys for equal security. (DHE with 3027-bit keys is about as secure as ECDHE with 256-bit keys.)

​

Public-Key Cryptography

Lecture 15, CS 161, Summer 2026

Diffie-Hellman Key Exchange

Public-Key Encryption

• Public-Key Cryptography
• ElGamal Encryption
• RSA Encryption
• Hybrid Encryption

Public-Key Cryptography: A Brief History

New Directions in Cryptography by Whitfield Diffie and Martin Hellman (1976) is the foundational paper in modern cryptography.

• Gave the first "secure" key-exchange scheme.
• Defined public-key encryption and digital signatures.
• >99% of modern cryptography uses ideas from this paper!

​

Their big idea: Who said you have to encrypt and decrypt with the same key?

Public-Key Cryptography: Definition

A public-key encryption scheme consists of three efficient algorithms:

• KeyGen() → PK, SK generates a public-private keypair.
• Enc(PK, M) → C encrypts plaintext M into ciphertext C, using the public key.
• Dec(SK, C) → M decrypts ciphertext C into plaintext M, using the secret key.

Message�(Plaintext)

PKB

Encryption

Algorithm

Ciphertext

SKB

Decryption

Algorithm

Alice

Bob

Insecure Channel

Message�(Plaintext)

ElGamal Encryption

Lecture 15, CS 161, Summer 2026

Diffie-Hellman Key Exchange

Public-Key Encryption

• Public-Key Cryptography
• ElGamal Encryption
• RSA Encryption
• Hybrid Encryption

ElGamal Encryption: Intuition

Diffie-Hellman is great: It lets Alice and Bob share a secret over an insecure channel.

• Problem: Diffie-Hellman by itself isn't enough to send an encrypted message.�The secret g^ab mod p is random.
• Idea: Modify Diffie-Hellman to support encrypting and decrypting messages.

​

Using a Diffie-Hellman secret g^ab mod p as the key, how to encrypt and decrypt?

• Encrypt: C ← M × g^ab mod p.
• Decrypt: M ← C × (g^ab)^–1 mod p.

​

Dec(g^ab, Enc(g^ab, M)) = M × g^ab × (g^ab)^–1 = M mod p

In modular arithmetic, "division" is multiplying by the multiplicative inverse.

g^ab × (g^ab)^–1 = 1 mod p.

ElGamal Encryption

Decrypt: Bob derives the inverse key and uses it to decrypt the message.

Encrypt: Alice completes her half of DHE, and encrypts the message with the key.

Alice

Bob

Pick random r, and compute g^r mod p

Pick random b, and publish g^b mod p

Public values: g, p

Compute inverse key: ((g^r)^b)^–1 mod p

Compute key: (g^b)^r mod p

M × (g^b)^r mod p

g^b mod p

Encrypt message with key: M × (g^b)^r mod p

Decrypt ciphertext with inverse key:

M × (g^b)^r × ((g^r)^b)^–1 = M mod p

KeyGen: Bob completes his half of DHE.

g^r mod p

ElGamal Definition

Like DHE, ElGamal security uses the Computational Diffie-Hellman (CDH) assumption:�Given g, p, g^r mod p, and g^b mod p, it is hard to compute g^rb mod p.

Public parameters.

Part of ciphertext.

Bob's public key.

Secret used to encrypt message.

Sometimes written as B.

Sometimes written as R.

ElGamal is Malleable

Problem: Mallory can tamper with the ciphertext in predictable ways,�even if she doesn't know the plaintext.�

• Alice encrypts M as:�(g^r mod p, M × (g^b)^r mod p)�
• Mallory tampers with the ciphertext by doubling the second value:�(g^r mod p, 2 × M × (g^b)^r mod p)�
• Bob decrypts the message as 2 × M.

​

Schemes vulnerable to this type of attack are called malleable.

RSA Encryption

Lecture 15, CS 161, Summer 2026

Diffie-Hellman Key Exchange

Public-Key Encryption

• Public-Key Cryptography
• ElGamal Encryption
• RSA Encryption
• Hybrid Encryption

Recall: Trapdoor One-Way Permutation

A trapdoor function consists of three efficient algorithms:

• KeyGen() → PK, TD generates a trapdoor.
• Eval(PK, x) → y is easy for everyone.
• Invert(TD, y) → x requires the trapdoor to invert.

x

f(x)

Easy

Hard

x

f(x)

Easy

Hard

Easy with trapdoor

Public-Key Encryption from Trapdoor Functions

Building blocks:

• A trapdoor function T {0,1}ⁿ → {0,1}ⁿ

From these, we can build an encryption scheme:

x

f(x)

Easy

Hard

Easy with trapdoor

Use the invert direction to decrypt.

Use the eval direction to encrypt.

Recall: RSA Trapdoor Function

Forward direction: Raise to e (public key value) power.

Invert direction: Raise to d (secret key value) power.

p and q are usually 1024–2048 bits long.

Other e values work as long as they're relatively prime to (p – 1)(q – 1).

^–1 is modular multiplicative inverse:�ed = 1 mod (p – 1)(q – 1).

Public-Key Encryption with the RSA Trapdoor Function

Public-key encryption schemes can be created using a trapdoor function.

RSA is a trapdoor function.

RSA Encryption Requires "Padding"

As presented, "plain" RSA encryption is not IND-CPA secure.

• One problem: Deterministic.
• Other subtle problems exist. (Won't discuss here. Don't try rolling your own RSA.)

​

In order for plain RSA to be IND-CPA secure, a padding scheme is necessary.

• "Padding" here refers to adding randomness, not dummy bytes for length reasons.
• Won't discuss further. (Look up OAEP if curious.)

Hybrid Encryption

Lecture 15, CS 161, Summer 2026

Diffie-Hellman Key Exchange

Public-Key Encryption

• Public-Key Cryptography
• ElGamal Encryption
• RSA Encryption
• Hybrid Encryption

Issues with Public-Key Encryption

Public-key encryption is often expensive and slow.

• It relies on slow math operations like exponentiation.
• By contrast, symmetric-key schemes use fast bit operations like XOR.

​

Message length is often limited.

• Example: If encryption works modulo a ~2048-bit prime, we can only encrypt messages shorter than ~2048 bits = ~2 KB.
• By contrast, symmetric-key schemes like AES-CTR have no length limit.

Best of Both Worlds: Hybrid Encryption

Hybrid encryption has the benefits of both symmetric-key and public-key encryption:

1. Use public-key encryption to send a symmetric key.�(Thus, Alice and Bob don't need a shared secret.)
2. Use the symmetric key to encrypt the actual data.�(Thus, we avoid the length and performance limits of public-key encryption.)

Message

K

Symmetric-Key

Encryption

Ciphertext

Alice

Bob

Insecure Channel

Public-Key

Encryption

PKB

K

Symmetric-Key

Decryption

Public-Key

Decryption

SKB

Message

Encrypted Key