Diffi-Hellman Key Exchange¶

References:

  • [GCAC] A Graduate Course in Applied Cryptography, Dan Boneh and Victor Shoup
  • [CINTA] A Computational Introduction to Number Theory and Algebra, Victor Shoup
  • [HAC] Handbook of Applied Cryptography, Alfred J. Menezes, Paul C. van Oorschot and Scott A. Vanstone
  • [ITMC] Introduction to Modern Cryptography, Jonathan Katz and Yehuda Lindell (3rd Edition)
  • Elementary number theory in sage

Dependencies:

This notebook uses sage math as kernel

In [1]:
import sage.misc.banner # sage math version info 
rchars = "┘─│┐┌└"
smallbanner = sage.misc.banner.banner_text(full=True)
for c in rchars:
    smallbanner = smallbanner.replace(c,"") # remove ascii art box
print(smallbanner)
#banner() # full banner with box

 SageMath version 9.5, Release Date: 2022-01-30                     
 Using Python 3.10.12. Type "help()" for help.
In [2]:
import secrets
def gen_rand_int(lower_bound, upper_bound):
    """ Generate random integer between lower_bound and upper_bound """ 
    if lower_bound > upper_bound:
        raise ValueError("Lower bound must not exceed upper bound!")
    range_size = upper_bound - lower_bound + 1
    random_offset = secrets.randbelow(int(range_size))
    return int(lower_bound + random_offset)

DH - Diffie Hellman¶

  • Diffie-Hellman (DH) - Martin Hellman, Whitfield Diffie
  • Algorithm first published 1976 "New Directions in Cryptography" ($\approx$ 24 K citations)
    • authors received Turing Award 2015
    • earliest publicly known work of public-key cryptography
    • since 1969 the British signals intelligence GCHQ knew about public-key cryptography (first RSA then DH like)

Diffie and Hellman

(image source)

New Directions in Cryptography¶

  • Paper published 1976

"We stand today on the brink of a revolution in cryptography. The development of cheap digital hardware has freed it from the design limitations of mechanical computing and brought the cost of high grade cryptographic devices down to where they can be used in such commercial applications as remote cash dispensers and computer terminals. In turn, such applications create a need for new types of cryptographic systems which minimize the necessity of secure key distribution channels and supply the equivalent of a written signature. At the same time, theoretical developments in information theory and computer science show promise of providing provably secure cryptosystems, changing this ancient art into a science."

Discrete Logarithm Problem (DLP)¶

  • Underlying mathematical problem required to be "hard" for DH to work
  • Assuming a cyclic group $\mathbb{G}$ of order $ q $ with generator $ g $
    • such that $ \{g^0, g^1, \dots, g^{q-1} \}$ represents all elements in the group
  • Then the discrete logarithm is the unique $ x \in \mathbb{Z}_q $ such that $ g^x = h $
    • $ x = \log_g h $
    • $ x $ is the discrete logarithm (index) of $ h $ to the base $ g $ modulo $ q $
    • note that we are in a group therefore everything computed modulo the order
  • Logarithms in such a cyclic group are called discrete since they can only result in integer values as opposed to standard logarithms over the real numbers

The Diffi-Hellman problems¶

These problems have later been defined to formally analyze the security of DH and are related to the DLP but not known to be equivalent:

  • Computational Diffi-Hellman problem (CDH)
  • Decisional Diffi-Hellman problem (DDH)

Computational Diffi-Hellman problem (CDH)¶

  • Fix a cyclic group $\mathbb{G}$ and a generator $ g\in \mathbb{G}$
  • Take two elements $h_1, h_2 \in \mathbb{G}$, where $ h_1 = g^{x_1} $ and $h_2 = g^{x_2} $
  • The CDH problem is to compute $ g^{x_1 \cdot x_2} $, only given $h_1$ and $ h_2 $

Decisional Diffi-Hellman problem (DDH)¶

  • Fix a cyclic group $\mathbb{G}$ and a generator $ g\in \mathbb{G}$
  • Take two elements $h_1, h_2 \in \mathbb{G}$, where $ h_1 = g^{x} $ and $h_2 = g^{y} $
  • The DDH problem is to distinguish between $ h = g^{xy} $ and some random element $ h'= g^{z}$, only given $ h_1,h_2$ and $ h $ or $ h'$

Hardness of DH problems¶

  • If DLP is easy, so is CDH
  • If CDH is easy, so is DDH
    • the converse is not true, if DDH is easy, CDH might still be hard
  • It is not clear (in general) if DLP implies hardness of CDH

Usage of Prime-Order Groups for DH¶

The usage of cyclic groups of prime order (i.e., the number of elements in the cyclic group is $ q \in \texttt{Primes}$) is preferred for Diffi-Hellman as the discrete-logarithm problem (DLP) is hardest in such groups

There are two main reasons for preferring cyclic groups of prime order:

  1. The problem of finding the discrete-logarithms in a group of order $ q $ becomes easier if $ q $ has small prime factos due to the Pholing-Hellman algorithm. This can be ruled out if $ q $ itself is prime.
    • Also the DDH problem becomes easier if $ q \not \in \text{Primes}$ and has (small) prime factors (e.g., $ q = p_1 \cdot p_2 \cdot p_3 \dots $)
  2. Finding generators in groups of prime order is easy, as every element of such a group (except the identity) is also a generator

A Subgroup-generation algorithm for $\mathbb{Z}^*_p$¶

  • As $ p \in \text{Primes} $ all elements in $\mathbb{Z}^*_p$ have a multiplicative inverse, since for all $ x \in \mathbb{Z}^*_p$ it holds that $\gcd(x,p) = 1 $ per definition of a prime
  • The order $q = |\mathbb{Z}^*_p|$ is $ p-1 $ since $ 0 $ had to be removed from $\mathbb{Z}^*_p$, as it is the only element in $Z_p$ which does not have a multiplicative inverse
  • As the order $ q $ of $ \mathbb{Z}^*_p$ is $ p - 1 $ the multiplicative group is not of prime-order, therefore DDH is not necessarily as hard as possible in such a group
  • Therefore, we want to generate a cyclic prime-order subgroup of $\mathbb{Z}^*_p$ where DDH is believed to be hard
  • We want a subgroup of prime order $ q $ s.t. $ p = rq + 1 $, where $ p,q \in \texttt{Primes}$, i.e.,
    • $ r = (p-1)/q $
    • $ q = (p-1)/r $

Subgroup-generation¶

ALGORITHM: Subgroup-generation according to Algorithm 9.67 in [ITMC]:

Input: Security parameter $ 1^n $ and $\ell $ specifying the bit length of the primes to use

Output: Cyclic group $\mathbb{G}$ with prime order $q$ and generator $g$

  • chose $\ell$ bit prime $ p $ and $n$ bit prime $ q $ s.t. $ q | (p-1) $
  • until $ g\neq 1 $ do
    • choose uniform $ h \in \mathbb{Z}^*_p $
    • set $ g := h^{(p-1)/q} \pmod p $
  • return $p,q,g$
In [10]:
def generate_subgroup(p,q):
    assert p in Primes() and q in Primes(),"q is not a prime order"
    assert (p-1) % q == 0,"q does not divide (p-1)"
    g = 1
    while g == 1: # try until g is not the identity
        h = gen_rand_int(lower_bound=1,upper_bound=p-1) # uniform h in Z*p
        g = pow(h,(p-1)//q,p)
    assert pow(g,q,p) == 1,f"For h = {h}, g = {g} is not a generator of a subgroup with order {q}"
    return p,q,g

Example from group to prime order subgroup¶

Define additive group $\mathbb{Z}_p$ in sage math:¶
In [12]:
p = 11; assert p in Primes() # define some prime
In [13]:
Zp = IntegerModRing(p) # define integers mod p 
Zp.list() # list all integers mod p forming a group under addition
Out[13]:
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
In [14]:
Zp.order() # order of the additive group
Out[14]:
11
In [15]:
Zp(2).order() # order of the element in the additive group
Out[15]:
11
Interpret integers mod p as multiplicative group mod $p$:¶
In [16]:
gZp = Zp.multiplicative_generator(); print(f"g in Z*p = {gZp}")

g in Z*p = 2
In [17]:
assert Zp(gZp).multiplicative_order() == p-1
print(f"order of g in Z*p = {Zp(gZp).multiplicative_order()}")

order of g in Z*p = 10
Define multiplicative group $\mathbb{Z}^*_p$ from $\mathbb{Z}_p$ explicitly:¶
In [18]:
G = Zp.unit_group() # define multiplicative group mod p from Zp
print(f"identity  e = {G.identity()}"); g = G.gen() 
print(f"generator g = {G.gens_values()[0]}")
print(f"g.order()   = {g.order()}")
print(f"G.list()    = {G.list()}")

identity  e = 1
generator g = 2
g.order()   = 10
G.list()    = (1, f, f^2, f^3, f^4, f^5, f^6, f^7, f^8, f^9)
In [22]:
p = 11; g = 2; print_group(p,g)

00: g^ 0  mod 11 =   1
01: g^ 1  mod 11 =   2
02: g^ 2  mod 11 =   4
03: g^ 3  mod 11 =   8
04: g^ 4  mod 11 =   5
05: g^ 5  mod 11 =  10
06: g^ 6  mod 11 =   9
07: g^ 7  mod 11 =   7
08: g^ 8  mod 11 =   3
09: g^ 9  mod 11 =   6
10: g^10  mod 11 =   1
Generate a sub-group of $\mathbb{Z}^*_p$:¶

First pick a prime factor of $p-1$ as the desired prime order $ q $ of the sub-group

In [23]:
factor(p-1) # possible prime orders for sub-groups
Out[23]:
2 * 5
In [24]:
generate_subgroup(p,q=5) # with prime order 5
Out[24]:
(11, 5, 3)
In [25]:
p = 11; q = 5; g = 3; print_subgroup(p,q,g)

00: g^ 0  mod 11 =   1
01: g^ 1  mod 11 =   3
02: g^ 2  mod 11 =   9
03: g^ 3  mod 11 =   5
04: g^ 4  mod 11 =   4
In [26]:
Zp(3).multiplicative_order()
Out[26]:
5
In [27]:
generate_subgroup(p,q=2)
Out[27]:
(11, 2, 10)
In [28]:
p = 11
q = 2
g = 10
print_subgroup(p,q,g)

00: g^ 0  mod 11 =   1
01: g^ 1  mod 11 =  10
In [29]:
Zp(10).multiplicative_order()
Out[29]:
2

Diffie-Hellman Key eXchange (DHKX or DH)¶

The underlying Diffie-Hellman algorithm can be used over different algebraic structures:

  • FFDH: The variant without elliptic curves is called algebraic DH or finite field DH
  • ECDH: When used over elliptic curves it is referred to as elliptic curve DH

FFDH - Finite Field Diffie-Hellman Key Exchange¶

Key exchange between Alice and Bob:

  • prime $ p \in $ Primes (in practise >= 2048 bits in size)
  • generator $ g < p $ where $ g $ is a generator of the cyclic (sub-)group $\mathbb{Z}_q$ in which DDH is hard
  • secret keys $ a, b \in \mathbb{Z}_q $, where only Alice knows $ a $ and only Bob knows $ b$
  • Alice computes $ A = g^a \pmod p $ and sends it to -> Bob
  • Bob computes $ B = g^b \pmod p $ and sedns it to -> Alice
  • Alice computes $ AB = B^a = {(g^{b})}^{a} = g^{ba} \pmod p $
  • Bob computes $ AB = A^b = {(g^{a})}^{b} = g^{ab} \pmod p $

FFDH Toy Example¶

In [30]:
def FFDH(p,g,x):
    return pow(g,x,p)
In [31]:
# Values from https://en.wikipedia.org/wiki/Diffie%E2%80%93Hellman_key_exchange
p = 23; g = 5; a = 6; b = 15
A = FFDH(p,g,x=a); B = FFDH(p,g,x=b)
AB_alice = FFDH(p,B,x=a); AB_bob = FFDH(p,A,x=b)
print(f"Alice computes  A = g^a (mod p) = {A}")
print(f"Bob   computes  B = g^b (mod p) = {B}")
print(f"Alice computes AB = B^a (mod p) = {AB_alice}")
print(f"Bob   computes AB = A^b (mod p) = {AB_bob}")
assert AB_alice == AB_bob

Alice computes  A = g^a (mod p) = 8
Bob   computes  B = g^b (mod p) = 19
Alice computes AB = B^a (mod p) = 2
Bob   computes AB = A^b (mod p) = 2

NIST/RFC FFDH parameters¶

  • NIST SP 800-56A Rev. 3 standardizes groups and DH parameters specified in RFC 7919
    • ffdhe2048, ffdhe3072, ffdhe4096, ffdhe6144, ffdhe8192

ffdhe2048¶

Defines $ p,q \in \text{Primes} $, where $ q $ defines a prime order sub-group with generator $ g $ in which DDH is hard.

  • Eulers number $ e = 2.71828... $ is used to ensure randomness (as deliberate manipulation is harder) and it provides a deterministic yet non-repeating numerical starting point
  • Moreover $ p $ is a safe-prime ($p = 2q + 1$ where $q \in \text{Primes}$) due to security and performance reasons (only two possible sub-group orders $ 2 $ and $ q $ to check)

$ p = 2^{2048} - 2^{1984} + (\lfloor 2^{1918} \cdot e\rfloor) + 560316 ) \cdot 2^{64} - 1 $

$ q = (p-1)/2 \;$ (i.e., $ r = 2 $)

$ g = 2 $

Compute prime p for ffdhe2048:¶
In [34]:
# calculate prime using sage math
# sage has a built in floor function and eulers number e 
p = 2^2048 - 2^1984 + (floor(2^1918 * e) + 560316 ) * 2^64 - 1
q = (p-1)/2
g = 2
print(f"p = {hex(p)}")
print(f"q = {hex(q)}")
print(f"g = {hex(g)}")

p = 0xffffffffffffffffadf85458a2bb4a9aafdc5620273d3cf1d8b9c583ce2d3695a9e13641146433fbcc939dce249b3ef97d2fe363630c75d8f681b202aec4617ad3df1ed5d5fd65612433f51f5f066ed0856365553ded1af3b557135e7f57c935984f0c70e0e68b77e2a689daf3efe8721df158a136ade73530acca4f483a797abc0ab182b324fb61d108a94bb2c8e3fbb96adab760d7f4681d4f42a3de394df4ae56ede76372bb190b07a7c8ee0a6d709e02fce1cdf7e2ecc03404cd28342f619172fe9ce98583ff8e4f1232eef28183c3fe3b1b4c6fad733bb5fcbc2ec22005c58ef1837d1683b2c6f34a26c1b2effa886b423861285c97ffffffffffffffff
q = 0x7fffffffffffffffd6fc2a2c515da54d57ee2b10139e9e78ec5ce2c1e7169b4ad4f09b208a3219fde649cee7124d9f7cbe97f1b1b1863aec7b40d901576230bd69ef8f6aeafeb2b09219fa8faf83376842b1b2aa9ef68d79daab89af3fabe49acc278638707345bbf15344ed79f7f4390ef8ac509b56f39a98566527a41d3cbd5e0558c159927db0e88454a5d96471fddcb56d5bb06bfa340ea7a151ef1ca6fa572b76f3b1b95d8c8583d3e4770536b84f017e70e6fbf176601a0266941a17b0c8b97f4e74c2c1ffc7278919777940c1e1ff1d8da637d6b99ddafe5e17611002e2c778c1be8b41d96379a51360d977fd4435a11c30942e4bffffffffffffffff
g = 0x2
In [38]:
%time assert p in Primes() and q in Primes()

CPU times: user 32.9 s, sys: 136 ms, total: 33.1 s
Wall time: 32.7 s

FFDH Toy Example with NIST/RFC values¶

In [35]:
a = gen_rand_int(lower_bound=1,upper_bound=q)
b = gen_rand_int(lower_bound=1,upper_bound=q)
A = FFDH(p,g,x=a)
B = FFDH(p,g,x=b)
AB_alice = FFDH(p,B,x=a)
AB_bob = FFDH(p,A,x=b)
print(f"Alice computes  A = g^a (mod p) = {hex(A)}")
print(f"Bob   computes  B = g^b (mod p) = {hex(B)}")
print(f"Alice computes AB = B^a (mod p) = {hex(AB_alice)}")
print(f"Bob   computes AB = A^b (mod p) = {hex(AB_bob)}")
assert AB_alice == AB_bob

Alice computes  A = g^a (mod p) = 0xda6aa04f81fb50e026130a11a123ac744bfef134d9bea293118257fa47de9a570762a1a188b9dce7189b19900b9c8930a88cc5b1c773ccffd798de1b53a79f1712aba718d0cc5da5710f6ac87669265798b6b1f5d58a2d48adf045e86e6bd07ff52364f25b53df5a6ba1936c05406b9ab11d7e96a5a86b4bb1bedfda38ed14b3f3a3a74dddbc499185831aea60e157588668ee293cdb56ae9db53a231c259903285e05c990f4976aea177c089d72d0cc46980a2562ae74134e7ddb3ef49117b357a740d1ae11a92fa7fd6c3f72df757b5e4621483d9ee65ebc19b4029330a90343af995ca49f6cdd7b424885e8c7c48b2c3c1a6161e135214af6bf8a188206c4
Bob   computes  B = g^b (mod p) = 0xf635181d2f9f5aef365776374d33d0bdc167a69b4b41853b0123e4f33d4b3a44ee114a132f2fc02e289c2e41e46f419d2bfcaa860e1c3bc38db3dec7163dc84cd0bf54af373a262dd40d2d1411e0068d1b26e7b787fcb5d27f8dbda3c4c20c23a673c4e930fa7dc366d017c63bbb131d6ed33c2102696b3fddb0ad98aaccf7e9ed9a7ff16efec702e476320dc4b52f20b6d11d9582e0029d4a4d04d408db186fbf31edb64a0421bf34f3e4314e29797feb48a7812b9bc18007ad299f257962552703908e721a9211440b0d1124e382e78422fa8f8d25bc27a5d3b73535a2e1610c6b6e242044706b10c7390db27a7ba0cc39bdb16d9990f88518e908c0b99d90
Alice computes AB = B^a (mod p) = 0xaabff6fbaab060c56d3a3eff218a4dad842ae7954ad00e90bdd937fcdaa170f5d4c0a8f7670190c9b91f4a91adf3d50a1dc4350166d10acde2128f73a3a36aa6986ab7a05331f298acef9b7a6f1af4da4f070242b80a188a6f5e876b8dbec36fe4e4e8486a8cbf7ad4c407415b7ee1c3472466d67f6c0c8f997ba5724a5ca0873984c8c2a04afb8e6596a70456ab46d7a5838b5f8f77361cc79fa6a962b2c387ff551297e2f47ea46f30277abe6ced2a51f99678d2f2bf5447892f333a0d9a34aad37999e9c0a7fb9ea9ac5b34e08bd78304d01e1a0d84d6db1ba7eff88a735c1849c1f147e00747a538560ecec4bf48d4555e5180c2c299d2bfd7b6c7635baf
Bob   computes AB = A^b (mod p) = 0xaabff6fbaab060c56d3a3eff218a4dad842ae7954ad00e90bdd937fcdaa170f5d4c0a8f7670190c9b91f4a91adf3d50a1dc4350166d10acde2128f73a3a36aa6986ab7a05331f298acef9b7a6f1af4da4f070242b80a188a6f5e876b8dbec36fe4e4e8486a8cbf7ad4c407415b7ee1c3472466d67f6c0c8f997ba5724a5ca0873984c8c2a04afb8e6596a70456ab46d7a5838b5f8f77361cc79fa6a962b2c387ff551297e2f47ea46f30277abe6ced2a51f99678d2f2bf5447892f333a0d9a34aad37999e9c0a7fb9ea9ac5b34e08bd78304d01e1a0d84d6db1ba7eff88a735c1849c1f147e00747a538560ecec4bf48d4555e5180c2c299d2bfd7b6c7635baf

Practical considerations¶

  • Use a key derviation function (KDF) to get from a uniform (sub-)group element to a uniform bit string usable in other schemes
  • Use standardized group parameters to prevent small sub-group attacks
    • Validate each others public key $ 1 < A,B < p-1 $ to prevent forcing small sub-groups
  • Use constant-time modular-exponentiation implementations to prevent timing side-channel attacks
    • especailly in so-called "semi-static" configuraitons where secret keys are reused across multiple runs/machines

EOF¶