Dominik Farhan

Diffie-Hellman key exchange

On the origin of the name

The system...has since become known as Diffie–Hellman key exchange. While that system was first described in a paper by Diffie and me, it is a public key distribution system, a concept developed by Merkle, and hence should be called 'Diffie–Hellman–Merkle key exchange' if names are to be associated with it. I hope this small pulpit might help in that endeavor to recognize Merkle's equal contribution to the invention of public-key cryptography. — Hellman 2002

Description

The following was take from a Wikipedia article on it which I recommend to read to anyone interested.

Both Alice and Bob are now in possession of the group element gab=gbag^{ab} = g^{ba}, which can serve as the shared secret key. Group GG satisfies the requisite condition for secure communication if there is not an efficient algorithm for determining gabg^{ab} given gg, gag^a, and gbg^b.

Used in ElGamal cipher.

Such construction is not attackable by a passive attacker but someone more active can do it. For this, it is important to sign the conversation (usually with RSA). Ideally the complete exchange.

An interesting idea is to hash the result of the communication before using it further in the protocol.

Some common pitfalls

Agreeing

If we are agreeing on g,ng,n or we don’t trust the authority that chose them, it is necessary to check that nn is really a prime and that gg is a generator of a sufficiently large subgroup.

Small subgroups, tricky attacker

Attacker can find kk so that gkg^k is little baby subgroup. When this happens, she can change gag^a to (ga)k(g^a)^k and the same for Bob’s. Voilà, we are a small subgroup once again. This is the chief reason why we are signing the whole communication, not just the result.

QR and Legendre

The symbol of monsieur Legendre leaks in DH so it is possible to say if a in gaa \text{ in } g^a was odd or even. But not a big deal.

Avoiding small subgroups

If 2∣p−12|p-1 which is almost always the case, then there is a subgroup with two elements. QR subgroup, has p−12\frac{p-1}{2} elements.

Safe primes

To avoid falling into some ugly small subgroups we use so-called safe primes.

p=2q+1p = 2q + 1

The multiplicative group of this prime has 2q2q elements and from monsieur’s Lagrange theorem there are just three subgroups we can venture to. The full group, the two-element group, and qq group. We can also jump straight into the qq group because of the leak on QR.

Speeding it up

We can use a different prime than the one specified above, but they are pretty much the same. p=Nq+1p = Nq + 1 NN is even and laarge. qq can have around 256256 bits.

We will work in a nice group defined by gNg^N — order qq, we can easily check that xq=1x^q = 1 and computation in such setting are reasonably fast.

p−1p-1 has a lot of small factors

This is generally something that must be avoided.

Like an asymmetric cipher

xx is the private key.

gxg^x is the public.

The more follows.

ElGamal

Params: p,gp, g

Key setup: k∈RZp−1k \in_R \mathbb{Z}_{p-1} — private decryption key, h=gkh = g^k — public encryption key.

Encryption

x∈Zp∗x \in \mathbb{Z}_{p}^* is plaintext. t∈RZp−1t \in_R \mathbb{Z}_{p-1} s=ht=gkts = h^t = g^{kt} this is the shared secret. y=sxy = sx send (gt,y),(g^t, y), acts as one-time pad.

Decryption

calculate (gt)−k=g−kt(g^t)^{-k} = g^{-kt}. Then x=yg−kt=xgktg−ktx = y g^{-kt} = x g^{kt} g^{-kt}

Some interesting properties

The encryption key can be generated from the decryption — a big difference from RSA. You can’t sign with it.

There is ElGamal signing protocol (used in DSA), different and more complicated than what is described here.