The Diffie-Hellman key exchange 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)/AO 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}\). In this page we will convert the original discrete log definition into an elliptic curve implementation, and use the secp256k1 curve. [MTI/A0][MTI/A0 (EC)][MTI/B0][MTI/B0 (EC)][MTI/C0][MTI/C0 (EC)][MTI/C1].
Key exchange (MTI/A0) - 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/AO 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}\). 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} = g^x \pmod p\)
Bob sends a public key value to Alice of:
\(b_{pub} = g^y \pmod p\)
Alice then generates a shared key of:
\(K_{alice} = {(b_{pub})}^x {(z_b)}^a \pmod p\)
and Bob generates:
\(K_{bob} = {(a_{pub})}^y {(z_a)}^b \pmod p\)
These will be the same as:
\(K_{alice} = {(b_{pub})}^x {(z_b)}^a \pmod p = {(g^b)}^x {(g^y)}^a \pmod p = g^{ba} g^{yx} \pmod p = g^{ab+xy} \pmod p\)
and Bob generates:
\(K_{bob} = {(a_{pub})}^y {(z_a)}^b \pmod p = {(g^a)}^y {(g^x)}^b \pmod p = g^{ab} g^{xy} \pmod p = g^{ab+xy} \pmod p \)
Elliptic Curve conversion
The first phase is a one-time setup, and where Alice and Bob agree on secp256k1. 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} = xG\)
Bob sends a public key value to Alice of:
\(b_{pub} = yG\)
Alice then generates a shared key of:
\(K_{alice} = x{(b_{pub})} + a{(z_b)}\)
and Bob generates:
\(K_{bob} = y{(a_{pub})} + b{(z_a)} \)
These will be the same as:
\(K_{alice} = x{(b_{pub})} + a{(z_b)} = a{(bG)} + x{(yG)} = abG + xyG = (ab+xy)G \)
and Bob generates:
\(K_{bob} = y{(a_{pub})} + b{(z_a)} = b{(aG)} + y{(xG)} = abG + xyG = (ab+xy)G \)
The value of \(a^{-1}\) is calculated with:
\(a \times a^{-1} \pmod n\)
In Python, this is achieved with:
a_inv = libnum.invmod(a,curve.n)
and where \(n\) is the order of the curve.
The conversion to ECC is thus:
Coding
The following is the code:
from secp256k1 import curve,scalar_mult,point_add 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) xG = scalar_mult(x, curve.g) y = random.randrange(1, curve.n) yG = scalar_mult(y, curve.g) k_a = point_add(scalar_mult(a,bG),scalar_mult(x,yG)) k_b = point_add(scalar_mult(b,aG),scalar_mult(y,xG)) 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", xG) print("\nBob\'s session secret key (y):\t", y) print("Bob\'s session public key (yG):\t", yG) print("\n==========================") print("Shared Alice: abG+xyG: \t", (k_a[0])) print("Shared Bob: baG+yxG: \t", (k_b[0])) print("\n\n======Checking=========") res=(a*b+x*y) % curve.n res=scalar_mult(res, curve.g) print("\n(ab+xy)G \t", (res[0]))
And a sample run:
Basepoint: (55066263022277343669578718895168534326250603453777594175500187360389116729240, 32670510020758816978083085130507043184471273380659243275938904335757337482424) Alice's secret key (a): 7719118273964745162089875365017749865146125355147672324967267116674912631966 Alice's public key: (114909776106160478428487666439623733829503564087230949253288025744543608392752, 18988828265393408832535164438954730124818697597861593961381133370728463896865) Bob's secret key (b): 101054413446790509311259796828386517216215676567399324366307475804998193140176 Bob's public key: (38450902636173947033090810996002564077506614764209395094056826311037065864665, 40707544650167473033814586258902173863606241942875427441979163940986966850724) ========================== Alice's session secret key (x): 71405269235247825927998982013409317933623117760852711650116277365479813889907 Alice's session public key (xG): (61644234921220870873906889870342029978265859332508332811655488685323426961733, 79180268580980077409827956151931551514545277010593532565775554094242925373179) Bob's session secret key (y): 93432797447594359898540578504293586650437361461892726449242708636606995234646 Bob's session public key (yG): (46304347095846435267670333645998613129303797296467777606571618159618808914956, 41721972604232105609420272497017438415465367187921097151033588859509803088783) ========================== Shared Alice: abG+xyG: 67507659737005567396624717095100698131443371783163644539960106856807125317272 Shared Bob: baG+yxG: 67507659737005567396624717095100698131443371783163644539960106856807125317272 ======Checking========= (ab+xy)G 67507659737005567396624717095100698131443371783163644539960106856807125317272
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.