Public Key Cryptography: Basic Notions and Key

Establishment

07 October, 2024
Symmetric Key Cryptography

Fundamental Assumption: Alice and Bob a priori share some secret

information.

SKC allows us to achieve both confidentiality and authenticity.

1. Build a secure channel over a public channel.
2. Well studied and standardised primitives are secure against classical
attackers.
3. Many of these schemes are secure against quantum attackers.
Question of key establishment

How do the communicating parties get the shared secret (key) in the first
place?
Strategy 1: Point to Point key distribution.
I Alice chooses a secret key and then transmits it to Bob through a
secure channel.

Secure channel:
1. A trusted courier.
2. A face-to-face meeting.
Not a practical solution for large scale applications.
Question of key establishment (Contd.)

Strategy 2: Use a trusted third party (TTP).

I Each user A shares a secret key kAT with a trusted third party T for a
symmetric-key encryption scheme E .
I A must visit T once to establish this key with T .
I T is called the key distribution centre (KDC).
Key Distribution Center

1. Both A and B must be registered with T

2. A sends T a request for a key to share with B.
3. T selects a session key k, and encrypts it for A using kAT .
4. T encrypts k for B using kBT .
I Drawback: The KDC must be unconditionally trusted.
I Attractive target of attack.
I Critical reliability point.
I User’s SIM in mobile communication system contains a symmetric
key that is shared with the network service provider.
I This key is used in an authentication protocol which returns a fresh
symmetric data encryption key.
Question of key management

Consider a network of n users each having a secret key with every other
user.

Each user has to maintain (n − 1) secret keys.

Total number of secret keys to be managed: n C2 ≈ n2 /2.

What happens when a new member joins the network?

Problem of Non-repudiation

I Non-repudiation: Prevents an entity from denying some previous

actions or commitments.
I Denying being the source of a message.
I No satisfactory and practical solution for non-repudiation is available
through symmetric-key techniques.
I Typically requires the services of an on-line TTP.
I Use a MAC scheme where each user shares a secret key with the TTP.
Public Key Cryptography
Public Key Cryptography

Alice and Bob share some a-priori information which is authenticated but
not secret.
Public Key Cryptography

Alice and Bob share some a-priori information which is authenticated but
not secret.
Invented by Diffie and Hellman in 1975.
And by Merkle in 1974 (as part of his under-grad student project).
And in the early 70s by scientists attached with British secret service.
“Publishing a new idea”

“The human mind treats a new idea the same way the body treats a
strange protein; it rejects it.”
See www.merkle.com/1974/

See the survey by Whitfield Diffie:

The First Ten Years of Public-Key Cryptography
Available at: cr.yp.to/bib/1988/diffie.pdf
Merkle’s Proposal

It might seem intuitively obvious that if two people have never had
the opportunity to prearrange an encryption method, then they
will be unable to communicate securely over an insecure channel.
While this might seem intuitively obvious, I believe it is false. I
believe that it is possible for two people to communicate securely
without having made any prior arrangements that are not com-
pletely public. My quarter project would be to investigate any
method by which this could be accomplished, and what advan-
tages and disadvantages these methods might have over other
ways of establishing secure communications.
[From Merkle’s UG Project Proposal for Computer Security (UC Berkeley,
1974)]
Merkle Puzzle

Alice and Bob execute the following protocol over a public (but
authenticated) channel:
1. Alice creates a large number of puzzles Pi for 1 ≤ i ≤ N for, say,
N = 109 .
I Each Pi will take, say, 5 hours to solve.
I Solving a puzzle Pi gives a secret key ski and some random
identification number ni (selected and stored by Alice).
2. Alice sends P1 , P2 , . . . PN to Bob.
Merkle Puzzle

Alice and Bob execute the following protocol over a public (but
authenticated) channel:
1. Alice creates a large number of puzzles Pi for 1 ≤ i ≤ N for, say,
N = 109 .
I Each Pi will take, say, 5 hours to solve.
I Solving a puzzle Pi gives a secret key ski and some random
identification number ni (selected and stored by Alice).
2. Alice sends P1 , P2 , . . . PN to Bob.
3. Bob selects a random j ∈ [1, N]; solves Pj to retrieve skj and nj .
4. Bob sends nj to Alice.
5. Both parties can securely communicate using skj .
Merkle Puzzle

Alice and Bob execute the following protocol over a public (but
authenticated) channel:
1. Alice creates a large number of puzzles Pi for 1 ≤ i ≤ N for, say,
N = 109 .
I Each Pi will take, say, 5 hours to solve.
I Solving a puzzle Pi gives a secret key ski and some random
identification number ni (selected and stored by Alice).
2. Alice sends P1 , P2 , . . . PN to Bob.
3. Bob selects a random j ∈ [1, N]; solves Pj to retrieve skj and nj .
4. Bob sends nj to Alice.
5. Both parties can securely communicate using skj .
Eve needs to solve on an average 5 × 108 puzzles to find nj and skj .
Asymmetric Key/Two-key Cryptography

Each party A generates a key pair (PA , SA ).

1. A publishes PA as her public key.
2. A keeps SA as her secret key.
Obviously, there is some mathematical relation between SA and PA .

But it should be computationally infeasible to recover the secret key SA

from the public key PA .

Security is conditional – based on some intractability assumption.

Public Key Encryption

I To send a secret message m to Bob, Alice does:

1. Obtain an authentic copy of Bob’s public key PB .
2. Compute c = E (PB , m) where E is the public key encryption function.
3. Send c to Bob.
I To decrypt c, Bob does:
1. Compute m = D(SB , c) where D is the corresponding decryption
function.
Digital Signature

I To sign a message m, Alice does:

1. Compute s = Sign(SA , m).
2. Send (m, s) to Bob.
I To verify Alice’s signature s on m, Bob does:
1. Obtain an authentic copy of Alice’s public key PA .
2. Accept σ as a valid signature on m if Verify(PA , m, σ) = Accept.
I How does digital signature differ from MAC?
Finite group

A finite group is a pair G = (S, ∗), S is a finite set and ∗ is a binary

operation defined on S that satisfies the following properties:
1. The operation ∗ is closed: a ∗ b ∈ S, ∀a, b ∈ S.
2. The operation ∗ is associative: (a ∗ b) ∗ c = a ∗ (b ∗ c), ∀a, b, c ∈ S.
3. There exists an element id ∈ S called the identity, s.t.
a ∗ id = id ∗ a = a, ∀a ∈ S.
4. ∀a ∈ S, ∃b ∈ S called the inverse of a, s.t. a ∗ b = b ∗ a = id.
The order of the group G = (S, ∗) is ord(G) = |S|.

H ⊆ G is a subgroup of G if H itself forms a group under the same

operation.
Finite Abelian Group

G is abelian if the operation ∗ is commutative, i.e., a ∗ b = b ∗ a for all

a, b ∈ S.
Example: Define Z∗p = Zp \ {0} where p ≥ 2 is a prime.
I (Z∗p , ∗) is an abelian group of order p − 1.
I The operation ∗ denotes multiplication modulo p.
I The identity element is 1.
I The inverse of a is denoted by a−1 .
I Question: Given a how do you compute a−1 ?
Order of an element
I For a finite group G = (S, ∗) define the order of an element a ∈ S
(ord(a)) to be the smallest positive integer m such that

|a ∗ a ∗{z· · · ∗ a} = id
m

I Given G = (S, ∗) if the operation ∗ is “multiplication” then we write:

n
|a ∗ a ∗{z· · · ∗ a} = a
n

called an exponentiation by n.
I If the group operation is “addition” then the same expression is
written as a multiplication by m, ma.
I The identity element has order 1.
I Fact: Order of any a ∈ S is a divisor of the order of the group,
ord(a)|ord(G).
Cyclic Groups

I A finite abelian group G = (S, ∗) is a cyclic group if there exists an

element a ∈ S whose order is |S|.
I Such an element is called a generator of G.
I Example: G = (Z∗7 , ·) is a cyclic group.
I Can you find a generator of G?
I Fact: If G is a finite group and ord(G) is a prime numeber p, then G
is cyclic.
I Every non-identity element of G is a generator of G.
I Henceforth, for a multiplicative group G of prime order p, we’ll write
G = hg i, i.e., G = {1, g , g 2 , . . . , g p−1 } and the operation ∗ is
understood from the context.
Diffie-Hellman Key Agreement

The description of G = hg i is publicly available, |G| = p.

We also assume that there is an algorithm for efficient exponentiation in G.
Diffie-Hellman Key Agreement

The description of G = hg i is publicly available, |G| = p.

We also assume that there is an algorithm for efficient exponentiation in G.

Alice Bob
1. Choose a secret x ∈R Zp . 1. Choose a secret y ∈R Zp .
2. Send g x to Bob 2. Send g y to Alice.
3. Compute K = (g y )x = g xy . 3. Compute K = (g x )y = g xy .
Diffie-Hellman Key Agreement

The description of G = hg i is publicly available, |G| = p.

We also assume that there is an algorithm for efficient exponentiation in G.

Alice Bob
1. Choose a secret x ∈R Zp . 1. Choose a secret y ∈R Zp .
2. Send g x to Bob 2. Send g y to Alice.
3. Compute K = (g y )x = g xy . 3. Compute K = (g x )y = g xy .
Which problem(s) must be computationally infeasible for the adversary?
Hardness Assumption

I The basic hard problem in the setting of cyclic groups is the discrete
log problem.
I A classical problem in number theory.
I Discrete Log Problem (DLP):
I Instance: A cyclic group G = hg i of prime-order p and an element
h ∈ G.
I Task: Compute a ∈ Zp such that h = g a .
I Diffie-Hellman Problem (DHP):
I Instance: A cyclic group G = hg i of order p and a tuple (g , g a , g b )
where a, b ∈R Zp ∗ .
I Task: Compute g ab .
I Security of DH Key agreement requires that DHP is computationally
hard.
A decision problem

I Decisional Diffie-Hellman Problem (DDH):

I Instance: A cyclic group G = hg i of order p and a tuple (g , g a , g b , g c )
where a, b ∈R Zp .
I Task: Determine whether c = ab or whether c is a random element of
Zp .
A decision problem

I Decisional Diffie-Hellman Problem (DDH):

I Instance: A cyclic group G = hg i of order p and a tuple (g , g a , g b , g c )
where a, b ∈R Zp .
I Task: Determine whether c = ab or whether c is a random element of
Zp .
I Hardness of DDH basically means not only the Diffie-Hellman
Problem is hard, you won’t be able to distinguish the solution from a
random group element.
Relation among hard problems

I It is easy to see that:

I DHP is no harder than DLP (DHP ≤ DLP).
I DDH is no harder than DHP (DDH ≤ DHP).
I Hardness of DDH implies the hardness of DHP and hardness of DHP
implies the hardness of DLP.
I What about the other direction?
I For certain groups it is known that DLP ≤ DHP, i.e., DHP and DLP
are equivalent.
I For certain other groups it is known that DDH is easy but DHP is
believed to be hard.
Security of DH Key Agreement

I We assume the adversary (M) is passive.

I M can see the exchanged messages but cannot modify them.
I Can be achieved if there is an authenticated link between Alice and
Bob.
I Test: M is given with equal probability either the actual key or a
random element from the key space.
I Goal: Decide whether M is given the proper key or not.
I This is called key-indistinguishability game.
Security of DH Key Agreement

I We assume the adversary (M) is passive.

I M can see the exchanged messages but cannot modify them.
I Can be achieved if there is an authenticated link between Alice and
Bob.
I Test: M is given with equal probability either the actual key or a
random element from the key space.
I Goal: Decide whether M is given the proper key or not.
I This is called key-indistinguishability game.
I Security is established if we can show that no computationally
bounded adversary can win the key-indistinguishability game with
non-negligible advantage.
Security of DH Key Agreement

I We assume the adversary (M) is passive.

I M can see the exchanged messages but cannot modify them.
I Can be achieved if there is an authenticated link between Alice and
Bob.
I Test: M is given with equal probability either the actual key or a
random element from the key space.
I Goal: Decide whether M is given the proper key or not.
I This is called key-indistinguishability game.
I Security is established if we can show that no computationally
bounded adversary can win the key-indistinguishability game with
non-negligible advantage.
I The task of the adversary is to solve the DDH problem.
(Wo)Man-in-the-Middle Attack
Key Agreement in presence of active adversary

I We remove the assumption that the communication link between A

and B is authenticated.
I A and B need the assurance that they are “talking” to each other
(not with M).
I We need to somehow bind the process of authentication with key
agreement.
I Such a protocol is called an authenticated key agreement scheme.
1. Mutual authentication
2. Key agreement