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)/BO 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 {n} =1\). For two secret values of \(x\) and \(y\), the resultant shared key is \((x+y)G\). 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/B0) - 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/BO 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^{x+y} \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}} g^x \pmod p\)
and Bob generates:
\(K_{bob} = {(a_{pub})}^{b^{-1}} g^y \pmod p\)
These will be the same as:
\(K_{alice} = {(b_{pub})}^{a^{-1}} g^x \pmod p = {(z_a^y)}^{a^{-1}} g^x \pmod p = g^{a y a^{-1}} g^x \pmod p = g^y g^x \pmod p = g^{x+y} \pmod p\)
and Bob generates:
\(K_{bob} = {(a_{pub})}^{b^{-1}} g^y \pmod p = {(z_b^x)}^{b^{-1}} g^y \pmod p = g^{b x b^{-1}} g^y \pmod p = g^x g^y \pmod p = g^{x+y} \pmod p\)
The value of \(a^{-1}\) is calculated with:
\(a \times a^{-1} \pmod {(p-1)} = 1\)
In Python, this is achieved with:
a_inv = libnum.invmod(a,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}) + xG\)
and Bob generates:
\(K_{bob} = b^{-1} y (a_{pub}) + yG \)
These will be the same as:
\(K_{alice} = a^{-1} (b_{pub}) + xG = a^{-1} z_a + xG = a^{-1} y a G + xG= (x+y)G \)
and Bob generates:
\(K_{bob} = b^{-1} (a_{pub}) + yG = b^{-1} z_b + yG = b^{-1} x b G + yG = (x+y)G \)
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, 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) xbG = scalar_mult(x, bG) y = random.randrange(1, curve.n) yG = scalar_mult(y, curve.g) yaG = scalar_mult(y, aG) a_inv=inverse_mod(a,curve.n) b_inv=inverse_mod(b,curve.n) k_a = point_add(scalar_mult(a_inv,yaG),xG) k_b = point_add(scalar_mult(b_inv,xbG),yG) 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+xG: \t", (k_a[0])) print("Shared Bob: y(b^{-1})xbG+yG: \t", (k_b[0])) print("\n\n======Checking=========") res=(x+y) % curve.n res=scalar_mult(res, curve.g) print("\n(x+y)G \t", (res[0]))
And a sample run:
Basepoint: (55066263022277343669578718895168534326250603453777594175500187360389116729240, 32670510020758816978083085130507043184471273380659243275938904335757337482424) Alice's secret key (a): 106904942598152759518983510550726887948306855133424328634269103563681845956071 Alice's public key: (26615866721974855598596703625128006895470057952418807010156976838028049142531, 30180655135608613859439561208283802855785968006453466319430257917997091436495) Bob's secret key (b): 1009580881564934133689500548429731937966 Basepoint: (55066263022277343669578718895168534326250603453777594175500187360389116729240, 32670510020758816978083085130507043184471273380659243275938904335757337482424) Alice's secret key (a): 17113081046210166189347404221169430773468001159029457655097098248161535231182 Alice's public key: (35990588842839367210467709638863243536086746781056010089055302564793903443532, 1713936799332839144155698585553685588971563173303221620041019021384494406944) Bob's secret key (b): 49009926991296184699123457386728920933128177033047896221792873472751519645232 Bob's public key: (115275083538517141694305605579533592975786251949511885853628037836402155998032, 39148341283842713459828029651902102633499351978727662701607538941341280031757) ========================== Alice's session secret key (x): 58449967469872869162500676617357145371066185662049974425622979899754987599736 Alice's session public key (xG): (24511090105354024090537302434929499505479627484885747995332880446061667840935, 107263594119726358557249506488733603319077939019646871234340406341441142484464) Bob's session secret key (y): 30950966045821518251793522365752455213205498615029892717910544673169182517419 Bob's session public key (yG): (43733132293492386171679752679076598094421169795196902538308739582892295109429, 61191346771607515641288328334203430094265594191563059908201889067475689577050) ========================== Shared Alice: x(a^{-1}))yaG+xG: 73783244358280538616816530218461327833624854651044165536499712939950997587900 Shared Bob: y(b^{-1})xbG+bG: 73783244358280538616816530218461327833624854651044165536499712939950997587900 ======Checking========= (x+y)G 73783244358280538616816530218461327833624854651044165536499712939950997587900
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.