Introduction to Public Key Cryptography II

In this session we discuss more concepts related to PKC, talking about DLP and DH key exchange...

Diffie-Hellman Key Exchange

This mechanism is one of the earliest approaches in public-key cryptography. Its primary objective is to address the key distribution problem. While it is not an encryption algorithm, it serves as a key exchange protocol that employs clever mathematical principles to securely establish a shared key between two parties.

How DH works:

Assume we have 2 parties, Alice and Bob

1. Parameter Agreement:

Alice and Bob agree on two public parameters, ggg and PPP, over an insecure channel.

• g: A generator (usually a small integer).

• P: A large prime number.

1. Secret Value Generation:

Alice generates a secret value $\alpha$, and uses it to derive A, where $A \equiv g^{\alpha} \pmod P$

Bob generates a secret value $\beta$, and uses it to derive B, where $B \equiv g^{\beta} \pmod P$

1. Exchnage

Alice and Bob exchange A and B over the insecure channel.

1. Shared Secret Computation:

Alice computes the shared secret by computing $S \equiv B^{\alpha} \pmod P$

Bob computes the shared secret by computing $S \equiv A^{\beta} \pmod P$

Let's breakdown the math:

$S \equiv A^{\beta} \equiv g ^{\alpha^{\beta}} \equiv g^{\alpha\times \beta} \pmod P$ # Bob Side

$S \equiv B^{\alpha} \equiv g ^{\beta^{\alpha}} \equiv g^{\beta \times \alpha} \pmod P$ # Alice Side

Diffie-Hellman Security (Discrete Logarithm Problem)

The Discrete Logarithm Problem (DLP) is a foundational mathematical challenge in the field of cryptography. Its significance lies in its use for ensuring the security of key exchange protocols, digital signatures, and other cryptographic primitives.

What Is the Discrete Logarithm Problem?

The problem is defined as follows: Given three numbers g, P, and A, where $A = g^a \mod P$, find the exponent a. This is the discrete logarithm of A to the base g, modulo P. Symbolically:

$a = \log_g A \mod P$

Unlike logarithms in real numbers, finding a in modular arithmetic is computationally hard when P is large, even though the forward operation $A = g^a \mod P$ is straightforward. This one-way property is what makes the DLP crucial for cryptographic security.

Learn more about DH by playing with https://cryptohack.org/challenges/diffie-hellman/