The Diffie-Hellman key method is weak from a security point-of-view, as Eve can perform an Eve-in-the-middle attack, and Alice does not authenticate the value received from Bob, and vice-versa. One way to overcome this is MTI (Matsumoto, Takashima, Imai)/CO key agreement [1,2], and where Bob and Alice perform a trusted key exchange for a one-time setup. This passes \(z_a\) and \(z_b\), and then each session passes public keys of \(a_{pub}\) and \(b_{pub}\). The \(a_{pub}\) value is created from Bob's public key, and \(b_{pub}\) value is created from Alice's public key. In this case we will use the inverse of Bob's and Alice's keys. For Alice's private key of \(a\), we determine \(a^{-1}\) for \(a \times a^{-1} \pmod {(p-1)}\). For two secret values of \(x\) and \(y\), the resultant shared key is \(xyG\). [MTI/A0][MTI/A0 (EC)][MTI/B0][MTI/B0 (EC)][MTI/C0][MTI/C0 (EC)][MTI/C1].
Key exchange (MTI/C0) - Elliptic Curve (secp256k1) |
Theory
The Diffie-Hellman key method is weak from a security point-of-view, as Eve can perform an Eve-in-the-middle attack, and Alice does not authenticate the value received from Bob, and vice-versa. One way to overcome this is MTI/CO key agreement, and where Bob and Alice perform a trusted key exchange for a one-time setup. This passes \(z_a\) and \(z_b\), and then each session passes public keys of \(a_{pub}\) and \(b_{pub}\). The \(a_{pub}\) value is created from Bob's public key, and \(b_{pub}\) value is created from Alice's public key. In this case we will use the inverse of Bob's and Alice's keys. For Alice's private key of \(a\), we determine \(a^{-1}\) for \(a \times a^{-1} \pmod {(p-1)}\). For two secret values of \(x\) and \(y\), the resultant shared key is \(g^{xy} \pmod p\). An outline is:
The first phase is a one-time setup, and where Alice and Bob agree on a generator value (\(g\)) and a prime number (\(p\)). Next Alice generates a private key of \(a\) and Bob generates a private key of \(b\). Alice then passes her public key of:
\(z_a = g^a \pmod p\)
Bob passes his public key of:
\(z_b = g^b \pmod p\)
When Bob and Alice want to generate a new key, Alice generates a random value \(x\) and Bob generates a random value \(y\). Alice sends a public key value to Bob of:
\(a_{pub} = {z_b}^x \pmod p\)
Bob sends a public key value to Alice of:
\(b_{pub} = {z_a}^y \pmod p\)
Alice then generates a shared key of:
\(K_{alice} = { ({(b_{pub}) }^{a^{-1}}) }^x \pmod p\)
and Bob generates:
\(K_{bob} = { ({(a_{pub}) }^{b^{-1}}) }^y \pmod p\)
These will be the same as:
\(K_{alice} = { ({(b_{pub}) }^{a^{-1}}) }^x \pmod p = { ({( {z_a}^y ) }^{a^{-1}}) }^x \pmod p g^{xy} \pmod p\)
and Bob generates:
\(K_{bob} = { ({(a_{pub}) }^{b^{-1}}) }^y \pmod p = { ({ {z_b}^x ) }^{b^{-1}}) }^y \pmod p = g^{xy} \pmod p\)
The value of \(a^{-1}\) is calculated with:
\(a \times a^{-1} \pmod {(p-1)}\)
Elliptic Curve conversion
The first phase is a one-time setup, and where Alice and Bob agree on secp256k1 and a prime number (\(p\)). Next Alice generates a private key of \(a\) and Bob generates a private key of \(b\). Alice then passes her public key of:
\(z_a = aG\)
Bob passes his public key of:
\(z_b = bG\)
When Bob and Alice want to generate a new key, Alice generates a random value \(x\) and Bob generates a random value \(y\). Alice sends a public key value to Bob of:
\(a_{pub} = x{z_b} \)
Bob sends a public key value to Alice of:
\(b_{pub} = y{z_a} \)
Alice then generates a shared key of:
\(K_{alice} = a^{-1} x (b_{pub})\)
and Bob generates:
\(K_{bob} = b^{-1} y (a_{pub}) \)
These will be the same as:
\(K_{alice} = a^{-1} x (b_{pub}) = a^{-1} x y z_a = a^{-1} x y a G = xyG \)
and Bob generates:
\(K_{bob} = b^{-1} y (a_{pub}) = b^{-1} y x z_b = b^{-1} y x b G = xyG \)
An overview is:
The value of \(a^{-1}\) is calculated with:
\(a \times a^{-1} \pmod {n} = 1\)
In Python, this is achieved with:
a_inv = libnum.invmod(a,curve.n)
and where \(n\) is the order of the curve.
Coding
The following is the code:
from secp256k1 import curve,scalar_mult, inverse_mod import random print("Basepoint:\t", curve.g) a = random.randrange(1, curve.n) aG = scalar_mult(a, curve.g) b = random.randrange(1, curve.n) bG = scalar_mult(b, curve.g) x = random.randrange(1, curve.n) xbG = scalar_mult(x, bG) y = random.randrange(1, curve.n) yaG = scalar_mult(y, aG) a_inv=inverse_mod(a,curve.n) b_inv=inverse_mod(b,curve.n) k_a = scalar_mult(a_inv,scalar_mult(x,yaG)) k_b = scalar_mult(b_inv,scalar_mult(y,xbG)) print("\nAlice\'s secret key (a):\t", a) print("Alice\'s public key:\t", aG) print("\nBob\'s secret key (b):\t", b) print("Bob\'s public key:\t", bG) print("==========================") print("\nAlice\'s session secret key (x):\t", x) print("Alice\'s session public key (xG):\t", xbG) print("\nBob\'s session secret key (y):\t", y) print("Bob\'s session public key (yG):\t", yaG) print("\n==========================") print("Shared Alice: x(a^{-1}))yaG: \t", (k_a[0])) print("Shared Bob: y(b^{-1})xbG: \t", (k_b[0])) print("\n\n======Checking=========") res=(x*y) % curve.n res=scalar_mult(res, curve.g) print("\n(xy)G \t", (res[0]))
And a sample run:
Basepoint: (55066263022277343669578718895168534326250603453777594175500187360389116729240, 32670510020758816978083085130507043184471273380659243275938904335757337482424) Alice's secret key (a): 45823269020600467138137707569309365646723371873640025594336307424487917761747 Alice's public key: (2876880575297427933915432095031015528062039520618058182736696692701918185916, 68314098275077494982807594672276128925242861033607450997587943485451207010025) Bob's secret key (b): 92471351920214443833678181892914881004204129980889202002940346423536242764606 Bob's public key: (21637480964860722962883644128201306786007357866988929674371162959053331712588, 44188945336271449043224489370130658483918245765596678633144947074767316778125) ========================== Alice's session secret key (x): 36080500895122586437811031679905421334925626708378136747175958154669667310626 Alice's session public key (xG): (5685292395693849722854857689108575622238772935065818975695408513573814903787, 54788363039608065834544616273400976882551562181858643113590630133923917329843) Bob's session secret key (y): 81138567563560856210457402678768846409162465364776566217501629664645729709391 Bob's session public key (yG): (56871745336637545732307623534308444016265247667097095232646996841589494669585, 26612242450631870826535557617481814243809460191226798261784838432015131549030) ========================== Shared Alice: x(a^{-1}))yaG: 22573139531088231866180893405649247450386850394656969830082752911193051114285 Shared Bob: y(b^{-1})xbG: 22573139531088231866180893405649247450386850394656969830082752911193051114285 ======Checking========= (xy)G 22573139531088231866180893405649247450386850394656969830082752911193051114285
Presentation
Reference
[1] Matsumoto, Tsutomu, Youichi Takashima, and Hideki Imai. "On seeking smart public-key-distribution systems." IEICE TRANSACTIONS (1976-1990) 69.2 (1986): 99-106.
[2] Menezes, A. J., Van Oorschot, P. C., & Vanstone, S. A. (2018), Handbook of applied cryptography. CRC press, Page 517-518.