YAK - Authenticated Key Exchange (Elliptic Curve)YAK uses public-key methods to implement authenticated key exchange. It was created by Feng Hao in 2010 [article][Discrete log implementation]. This page converts the discrete log method into an elliptic curve method. |
Outline
With authenticated key exchange, Bob has a private key of \(b\) and a public key of:
\(Bpub=g^b \pmod p\)
Alice has a private key of \(a\) and a public key of:
\(Apub=g^a \pmod p\)
For the key exchange, Alice generates a secret \(x\) and sends Bob:
\(A=g^x \pmod p\)
Bob generates a secret \(y\) and sends Alice:
\(B=g^y \pmod p\)
Alice computes:
\(K=(g^b g^y)^{x+a} \pmod p\)
Bob computes:
\(K=(g^a g^x)^{y+b} \pmod p\)
These values should be the same, as:
\(K=(g^b g^y)^{x+a} \pmod p= g^{(b+y)(x+a)}\)
Bob computes:
\(K=(g^a g^x)^{y+b} \pmod p = g^{(a+x)(y+b)}\)
Conversion to ECC
Around ten years ago, discrete log and RSA methods were riding right. But both of these methods have struggled with increasing levels of security. For discrete log and RSA methods, we are now looking at 2K prime numbers. So, elliptic curve techniques have come along, and with relatively small prime numbers of 256-bits, and which have much-improved performance levels.
So how do we convert from a discrete log problem to an elliptic curve problem? Well, discrete logs are in the form of power:
\(Pub = g^x \pod p)\)
and where \(x\) is the secret, \(g\) is the generator value, and \(p\) is the prime number. For elliptic curves, we take a base point (\(G\)), and a secret value (\(x\)) and generate:
\(Pub = xG \pmod p)\)
and where Pub is a point on the elliptic curve. And so we convert from logs to multiplication. The base operations in elliptic curves is to use point addition (\(P+P\)) and point doubling (\(2P\)).
We thus convert from discrete log method \(g^x \pmod p\) to an elliptic curve method of \(xG\) and where \(G\) is the base point on the elliptic curve, \(x\) is the private key, and \(p\) is a prime number. The multiplication for \(xG\) is \(G+G+...+G\) for \(x\) additions. With authenticated key exchange, Bob has a private key of \(b\) and a public key of (and where \(G\) is the base point on the elliptic curve):
\(Bpub=b G \pmod p\)
Alice has a private key of \(a\) and a public key of:
\(Apub=a G \pmod p\)
For the key exchange, Alice generates a secret \(x\) and sends Bob:
\(A=x G \pmod p\)
Bob generates a secret \(y\) and sends Alice:
\(B=y G \pmod p\)
Alice computes:
\(K=(x+a) (bG + xG) \pmod p\)
Bob computes:
\(K=(y+b) (aG + yG) \pmod p\)
These values should be the same, as:
\(K=(x+a) (bG+yG) \pmod p= (x+a)(b+y)G \pmod p\)
Bob computes:
\(K= (y+b) (aG+xG) \pmod p = (y+b)(a+x)G \pmod p\)
We can see that the equivalence of the discrete log operation of \(g^x g^y\) in elliptic curve is a point add of \(xG + yG\).
Coding
The outline code is:import random from ecc import curve,scalar_mult,point_add print("Basepoint:\t", curve.g) a=random.randint(0,2e255) b=random.randint(0,2e255) Apub =scalar_mult(a, curve.g) Bpub =scalar_mult(b, curve.g) print("\nAlice\'s private key:\t", a) print("Alice\'s public key:\t", Apub) print("\nBob\'s private key:\t", b) print("Bob\'s public key:\t", Bpub) x=random.randint(0,2e16) y=random.randint(0,2e16) print("==========================") print("Alice\'s secret:\t", x) print("Bob\'s secret:\t", y) A = scalar_mult(x, curve.g) B = scalar_mult(y, curve.g) print("\nAlice passes:\t", A) print("Bob passes:\t", B) Akey = scalar_mult((x+a), point_add(B,Bpub)) Bkey = scalar_mult((y+b), point_add(A,Apub)) print("==========================") print("\nAlice\'s shared key:\t", Akey[0]) print("Bob\'s shared key:\t", Bkey[0])
The following is a sample run and have \(p\) and \(q\) have 256 bits and N has 512 bits. We can see the number of decimal digits in \(N\) is 154:
Basepoint: (55066263022277343669578718895168534326250603453777594175500187360389116729240, 32670510020758816978083085130507043184471273380659243275938904335757337482424) Alice's private key: 112182946620095569313068193106676310957375623164976451752524757253399026715484330367307294625816278429414289459642113197237829111557118058464192847241596032297449187921128586528053754317950460274975438961933055849279960178942038178689394456375036655714306 Alice's public key: (10665621333288112755013999333279623506032022287483445436500062192195137992261, 58087694570156162510209133003888730576005574255076918153317115930430271013098) Bob's private key: 1468988400836128377421999167682421150352307983577137687590413218473080056222120777491053235068994917070676042106516175884578705431385693240344591844207481084161254087750678837037307095400106225527063136356179376479055205440596025739632025197568863059840571 Bob's public key: (114781454701692031014020444918679178602807615038807261920001814037487990109703, 101749329057776542100848869379951481940093225037188581639788957889258085110222) ========================== Alice's secret: 15676117802605500 Bob's secret: 9984497725715983 Alice passes: (7588724046693894569412404779979229554789162286461724200993531586242150963559, 28434372896987165674720660999060654812396567367411485914818574690274023924527) Bob passes: (62103473263706976269069651027295469527060460943160998201863776592384240638574, 30553090632228810467699975753637193469152704161936665236587260632253288832148) ========================== Alice's shared key: 79976801751791747837746155366814286293378413853532278453516279836430659630209 Bob's shared key: 79976801751791747837746155366814286293378413853532278453516279836430659630209