Elliptic Curve Diffie Hellman (ECDH) is used to create a shared key. Overall an elliptic curve has the form of \(y^2 = x^3 + ax + b\), and where \(a\) and \(b\) are part of the defined parameters. Within Elliptic Curve Cryptography (ECC), we pick a point on the curve (\(G\) - the generator), and perform our operations with the modulus of \(n\). The final parameters are \(n\) - the size of a subgroup - and \(h\) - the cofactor. There are many different elliptic curve standards, including secp256k1 (as used in Bitcoin), Curve 25519 (as used in SSH and many other applications), p192, p224, p256, and p384. The parameters are typically defined as \((p,a,b,G,n,h)\):
Elliptic Curve Diffie Hellman (ECDH) with differing elliptic curves. |
Elliptic Curves
The following are some of the elliptic curve types:
if (type==1): curve = EllipticCurve( 'secp256k1', # Field characteristic. p=0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f, # Curve coefficients. a=0, b=7, # Base point. g=(0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798, 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8), # Subgroup order. n=0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141, # Subgroup cofactor. h=1, ) if (type==2): curve = EllipticCurve( 'p192', a = -3, b = 0x64210519e59c80e70fa7e9ab72243049feb8deecc146b9b1, p = 6277101735386680763835789423207666416083908700390324961279, g=( 0x188da80eb03090f67cbf20eb43a18800f4ff0afd82ff1012,0x07192b95ffc8da78631011ed6b24cdd573f977a11e794811), n = 6277101735386680763835789423176059013767194773182842284081, h=1, ) if (type==3): curve = EllipticCurve( 'p224', a = -3, b = 0xb4050a850c04b3abf54132565044b0b7d7bfd8ba270b39432355ffb4, p = 26959946667150639794667015087019630673557916260026308143510066298881, g= (0xb70e0cbd6bb4bf7f321390b94a03c1d356c21122343280d6115c1d21,0xbd376388b5f723fb4c22dfe6cd4375a05a07476444d5819985007e34), n = 26959946667150639794667015087019625940457807714424391721682722368061, h=1, ) if (type==4): curve = EllipticCurve( 'p256', a = -3, b = 0x5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b, p = 115792089210356248762697446949407573530086143415290314195533631308867097853951, g = (0x6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296,0x4fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5), n = 115792089210356248762697446949407573529996955224135760342422259061068512044369, h=1, ) if (type==5): curve = EllipticCurve( 'p384', a = -3, b = 0xb3312fa7e23ee7e4988e056be3f82d19181d9c6efe8141120314088f5013875ac656398d8a2ed19d2a85c8edd3ec2aef, p = 39402006196394479212279040100143613805079739270465446667948293404245721771496870329047266088258938001861606973112319, g = (0xaa87ca22be8b05378eb1c71ef320ad746e1d3b628ba79b9859f741e082542a385502f25dbf55296c3a545e3872760ab7,0x3617de4a96262c6f5d9e98bf9292dc29f8f41dbd289a147ce9da3113b5f0b8c00a60b1ce1d7e819d7a431d7c90ea0e5f), n = 39402006196394479212279040100143613805079739270465446667946905279627659399113263569398956308152294913554433653942643, h=1, ) if (type==6): curve = EllipticCurve( 'p512', a = -3, b = 0x051953eb9618e1c9a1f929a21a0b68540eea2da725b99b315f3b8b489918ef109e156193951ec7e937b1652c0bd3bb1bf073573df883d2c34f1ef451fd46b503f00, p = 6864797660130609714981900799081393217269435300143305409394463459185543183397656052122559640661454554977296311391480858037121987999716643812574028291115057151, g = (0xc6858e06b70404e9cd9e3ecb662395b4429c648139053fb521f828af606b4d3dbaa14b5e77efe75928fe1dc127a2ffa8de3348b3c1856a429bf97e7e31c2e5bd66,0x11839296a789a3bc0045c8a5fb42c7d1bd998f54449579b446817afbd17273e662c97ee72995ef42640c550b9013fad0761353c7086a272c24088be94769fd16650), n = 6864797660130609714981900799081393217269435300143305409394463459185543183397655394245057746333217197532963996371363321113864768612440380340372808892707005449, h=1, ) SECP112_PRIME = (2**128 - 3)/76439 SECP128_PRIME = 2**128 - 2**97 - 1 if (type==7): curve = EllipticCurve( 'SECP112r1', a = 0xDB7C2ABF62E35E668076BEAD2088, b = 0x659EF8BA043916EEDE8911702B22, p = SECP112_PRIME, g = (0x09487239995A5EE76B55F9C2F098,0xA89CE5AF8724C0A23E0E0FF77500), n = 0xDB7C2ABF62E35E7628DFAC6561C5, h=1, ) if (type==8): curve = EllipticCurve( 'SECP112r2', a = 0x6127C24C05F38A0AAAF65C0EF02C, b = 0x51DEF1815DB5ED74FCC34C85D709, p = SECP112_PRIME, g = (0x4BA30AB5E892B4E1649DD0928643,0xADCD46F5882E3747DEF36E956E97), n = 0x36DF0AAFD8B8D7597CA10520D04B, h=4, ) if (type==9): curve = EllipticCurve( 'SECP128r1', a = 0xFFFFFFFDFFFFFFFFFFFFFFFFFFFFFFFC, b = 0xE87579C11079F43DD824993C2CEE5ED3, p = SECP128_PRIME, g = (0x161FF7528B899B2D0C28607CA52C5B86,0xCF5AC8395BAFEB13C02DA292DDED7A83), n = 0xFFFFFFFE0000000075A30D1B9038A115, h=1, ) if (type==10): curve = EllipticCurve( 'SECP128r2', a = 0xD6031998D1B3BBFEBF59CC9BBFF9AEE1, b = 0x5EEEFCA380D02919DC2C6558BB6D8A5D, p = SECP128_PRIME, g = (0x7B6AA5D85E572983E6FB32A7CDEBC140,0x27B6916A894D3AEE7106FE805FC34B44), n = 0x3FFFFFFF7FFFFFFFBE0024720613B5A3, h=4, ) if (type==11): curve = EllipticCurve( 'SECP160k1', a = 0, b = 7, p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFAC73, g = (0x3B4C382CE37AA192A4019E763036F4F5DD4D7EBB,0x938CF935318FDCED6BC28286531733C3F03C4FEE), n = 0x100000000000000000001B8FA16DFAB9ACA16B6B3, h=1, ) if (type==12): curve = EllipticCurve( 'SECP160k2', a = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFAC70, b = 0xB4E134D3FB59EB8BAB57274904664D5AF50388BA, p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFAC73, g= (0x52DCB034293A117E1F4FF11B30F7199D3144CE6D,0xFEAFFEF2E331F296E071FA0DF9982CFEA7D43F2E), n = 0x0100000000000000000000351EE786A818F3A1A16B, h=1, ) if (type==13): curve = EllipticCurve( 'SECP192k1', a = 0, b = 3, p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFEE37, g=(0xDB4FF10EC057E9AE26B07D0280B7F4341DA5D1B1EAE06C7D,0x9B2F2F6D9C5628A7844163D015BE86344082AA88D95E2F9D), n = 0xFFFFFFFFFFFFFFFFFFFFFFFE26F2FC170F69466A74DEFD8D, h=1, ) if (type==13): curve = EllipticCurve( 'SECP192k1', a = 0, b = 3, p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFEE37, g=(0xDB4FF10EC057E9AE26B07D0280B7F4341DA5D1B1EAE06C7D,0x9B2F2F6D9C5628A7844163D015BE86344082AA88D95E2F9D), n = 0xFFFFFFFFFFFFFFFFFFFFFFFE26F2FC170F69466A74DEFD8D, h=1, ) po = pow(2,255)-19 if (type==14): curve = EllipticCurve( 'Curve25519_Montgomery', p= po, a =486662, b=1, g=(9,0x20ae19a1b8a086b4e01edd2c7748d14c923d4d7e6d7c61b229e9c5a27eced3d9), n=0x1000000000000000000000000000000014def9dea2f79cd65812631a5cf5d3ed, h=1, ) if (type==15): curve = EllipticCurve( 'Curve25519_Weierstrass', p= po, a =0x2aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa984914a144, b=0x7b425ed097b425ed097b425ed097b425ed097b425ed097b4260b5e9c7710c864, g=(0x2aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaad245a,0x20ae19a1b8a086b4e01edd2c7748d14c923d4d7e6d7c61b229e9c5a27eced3d9), n=0x1000000000000000000000000000000014def9dea2f79cd65812631a5cf5d3ed, h=1, )
Theory
The following is a presentation on elliptic curves:
Overall an elliptic curve has the form of \(y^2 = x^3 + ax + b\), and where a and b are one of the defined parameters. Within Elliptic Curve Cryptography (ECC), we pick a point on the curve (\(G\) - the generator), and perform our operations with the modulus of \(p\). The final parameter are \(n\) - the size of a subgroup - and \(h\) - the cofactor. There are many different elliptic curve standards, including secp256k1, p192, p224, p256, and p384. The parameters are typically defined as \((p,a,b,G,n,h)\).
For secp256k1 (as used in Bitcoin) we use the parameters of:
- p=0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f
- a=0
- b=7
- g= (0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798, 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8)
- n=0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141
- h=1
This gives an elliptic curve of:
\(y^2 = x^3+7\)
with a prime number (p) of 0xFFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F
and which is \( 2^{256} - 2^{32} - 2^9 - 2^8 - 2^7 - 2^6 - 2^4 - 1 \)
All our operations will be (mod p)
Elliptic Curve Diffie Hellman (ECDH)
ECDH is used to create a shared key. Bob will generate a public key and a private key by taking a point on the curve. The private key is a random number (\(d_B\)) and the Bob's public key (\(Q_B\)) will be:
\(Q_B = d_B \times G\)
Alice will do the same and generate her public key (\(Q_A\)) from her private key (\(d_A\)):
\(Q_A = d_A \times G\)
They then exchange their public keys. Alice will then use Bob's public key and her private key to calculate:
SharekeyAlice\( = d_A \times Q_B\)
This will be the same as:
SharekeyAlice\( = d_A \times d_B \times G\)
Bob will then use Alice's public key and his private key to determine:
SharekeyBob \(= d_B \times Q_A\)
This will be the same as:
SharekeyBob\( = d_B \times d_A \times G\)
And the keys will thus match.
The following illustrates the process:
Sample run
A sample run is:
Name: secp256k1 a: 0 b: 7 G: (55066263022277343669578718895168534326250603453777594175500187360389116729240L, 32670510020758816978083085130507043184471273380659243275938904335757337482424L) P: 115792089237316195423570985008687907853269984665640564039457584007908834671663 ========================== Alice's secret key: 56236441279441388955174476549452509616546134038711316702699092191107074151641 Alice's public key: (98364692093822173545938063732543876147536823194001144843916064141925636036667L, 29338504092996471455690036071925952160671867412579634193484795293091905889258L) Bob's secret key: 14088269408994202331064088213586860117107442552939651122294270345300784368215 Bob's public key: (98269351594417908951383185349414679299093362039909520303078579137125049982612L, 17322441480726601900776853563562223560640239401553061070816768002829521212893L) ========================== Alice's shared key: (8950643902111516122781786090464163131148850902710441359618416467133236041113L, 97070080944649341880989572852677270609544184091875097795808265896339240732767L) Bob's shared key: (8950643902111516122781786090464163131148850902710441359618416467133236041113L, 97070080944649341880989572852677270609544184091875097795808265896339240732767L) ========================== The shared value is the x-value: 8950643902111516122781786090464163131148850902710441359618416467133236041113
Code
Here is the code to generate this:
import collections import hashlib import random import binascii type =1 EllipticCurve = collections.namedtuple('EllipticCurve', 'name p a b g n h') if (type==1): curve = EllipticCurve( 'secp256k1', # Field characteristic. p=0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f, # Curve coefficients. a=0, b=7, # Base point. g=(0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798, 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8), # Subgroup order. n=0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141, # Subgroup cofactor. h=1, ) if (type==2): curve = EllipticCurve( 'p192', a = -3, b = 0x64210519e59c80e70fa7e9ab72243049feb8deecc146b9b1, p = 6277101735386680763835789423207666416083908700390324961279, g=( 0x188da80eb03090f67cbf20eb43a18800f4ff0afd82ff1012,0x07192b95ffc8da78631011ed6b24cdd573f977a11e794811), n = 6277101735386680763835789423176059013767194773182842284081, h=1, ) if (type==3): curve = EllipticCurve( 'p224', a = -3, b = 0xb4050a850c04b3abf54132565044b0b7d7bfd8ba270b39432355ffb4, p = 26959946667150639794667015087019630673557916260026308143510066298881, g= (0xb70e0cbd6bb4bf7f321390b94a03c1d356c21122343280d6115c1d21,0xbd376388b5f723fb4c22dfe6cd4375a05a07476444d5819985007e34), n = 26959946667150639794667015087019625940457807714424391721682722368061, h=1, ) if (type==4): curve = EllipticCurve( 'p256', a = -3, b = 0x5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b, p = 115792089210356248762697446949407573530086143415290314195533631308867097853951, g = (0x6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296,0x4fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5), n = 115792089210356248762697446949407573529996955224135760342422259061068512044369, h=1, ) if (type==5): curve = EllipticCurve( 'p384', a = -3, b = 0xb3312fa7e23ee7e4988e056be3f82d19181d9c6efe8141120314088f5013875ac656398d8a2ed19d2a85c8edd3ec2aef, p = 39402006196394479212279040100143613805079739270465446667948293404245721771496870329047266088258938001861606973112319, g = (0xaa87ca22be8b05378eb1c71ef320ad746e1d3b628ba79b9859f741e082542a385502f25dbf55296c3a545e3872760ab7,0x3617de4a96262c6f5d9e98bf9292dc29f8f41dbd289a147ce9da3113b5f0b8c00a60b1ce1d7e819d7a431d7c90ea0e5f), n = 39402006196394479212279040100143613805079739270465446667946905279627659399113263569398956308152294913554433653942643, h=1, ) if (type==6): curve = EllipticCurve( 'p512', a = -3, b = 0x051953eb9618e1c9a1f929a21a0b68540eea2da725b99b315f3b8b489918ef109e156193951ec7e937b1652c0bd3bb1bf073573df883d2c34f1ef451fd46b503f00, p = 6864797660130609714981900799081393217269435300143305409394463459185543183397656052122559640661454554977296311391480858037121987999716643812574028291115057151, g = (0xc6858e06b70404e9cd9e3ecb662395b4429c648139053fb521f828af606b4d3dbaa14b5e77efe75928fe1dc127a2ffa8de3348b3c1856a429bf97e7e31c2e5bd66,0x11839296a789a3bc0045c8a5fb42c7d1bd998f54449579b446817afbd17273e662c97ee72995ef42640c550b9013fad0761353c7086a272c24088be94769fd16650), n = 6864797660130609714981900799081393217269435300143305409394463459185543183397655394245057746333217197532963996371363321113864768612440380340372808892707005449, h=1, ) SECP112_PRIME = (2**128 - 3)/76439 SECP128_PRIME = 2**128 - 2**97 - 1 if (type==7): curve = EllipticCurve( 'SECP112r1', a = 0xDB7C2ABF62E35E668076BEAD2088, b = 0x659EF8BA043916EEDE8911702B22, p = SECP112_PRIME, g = (0x09487239995A5EE76B55F9C2F098,0xA89CE5AF8724C0A23E0E0FF77500), n = 0xDB7C2ABF62E35E7628DFAC6561C5, h=1, ) if (type==8): curve = EllipticCurve( 'SECP112r2', a = 0x6127C24C05F38A0AAAF65C0EF02C, b = 0x51DEF1815DB5ED74FCC34C85D709, p = SECP112_PRIME, g = (0x4BA30AB5E892B4E1649DD0928643,0xADCD46F5882E3747DEF36E956E97), n = 0x36DF0AAFD8B8D7597CA10520D04B, h=4, ) if (type==9): curve = EllipticCurve( 'SECP128r1', a = 0xFFFFFFFDFFFFFFFFFFFFFFFFFFFFFFFC, b = 0xE87579C11079F43DD824993C2CEE5ED3, p = SECP128_PRIME, g = (0x161FF7528B899B2D0C28607CA52C5B86,0xCF5AC8395BAFEB13C02DA292DDED7A83), n = 0xFFFFFFFE0000000075A30D1B9038A115, h=1, ) if (type==10): curve = EllipticCurve( 'SECP128r2', a = 0xD6031998D1B3BBFEBF59CC9BBFF9AEE1, b = 0x5EEEFCA380D02919DC2C6558BB6D8A5D, p = SECP128_PRIME, g = (0x7B6AA5D85E572983E6FB32A7CDEBC140,0x27B6916A894D3AEE7106FE805FC34B44), n = 0x3FFFFFFF7FFFFFFFBE0024720613B5A3, h=4, ) if (type==11): curve = EllipticCurve( 'SECP160k1', a = 0, b = 7, p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFAC73, g = (0x3B4C382CE37AA192A4019E763036F4F5DD4D7EBB,0x938CF935318FDCED6BC28286531733C3F03C4FEE), n = 0x100000000000000000001B8FA16DFAB9ACA16B6B3, h=1, ) if (type==12): curve = EllipticCurve( 'SECP160k2', a = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFAC70, b = 0xB4E134D3FB59EB8BAB57274904664D5AF50388BA, p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFAC73, g= (0x52DCB034293A117E1F4FF11B30F7199D3144CE6D,0xFEAFFEF2E331F296E071FA0DF9982CFEA7D43F2E), n = 0x0100000000000000000000351EE786A818F3A1A16B, h=1, ) if (type==13): curve = EllipticCurve( 'SECP192k1', a = 0, b = 3, p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFEE37, g=(0xDB4FF10EC057E9AE26B07D0280B7F4341DA5D1B1EAE06C7D,0x9B2F2F6D9C5628A7844163D015BE86344082AA88D95E2F9D), n = 0xFFFFFFFFFFFFFFFFFFFFFFFE26F2FC170F69466A74DEFD8D, h=1, ) po = pow(2,255)-19 if (type==14): curve = EllipticCurve( 'Curve 25519', p= po, a =486662, b=1, g=(9,0x20ae19a1b8a086b4e01edd2c7748d14c923d4d7e6d7c61b229e9c5a27eced3d9), h=1, ) # Modular arithmetic ########################################################## def inverse_mod(k, p): """Returns the inverse of k modulo p. This function returns the only integer x such that (x * k) % p == 1. k must be non-zero and p must be a prime. """ if k == 0: raise ZeroDivisionError('division by zero') if k < 0: # k ** -1 = p - (-k) ** -1 (mod p) return p - inverse_mod(-k, p) # Extended Euclidean algorithm. s, old_s = 0, 1 t, old_t = 1, 0 r, old_r = p, k while r != 0: quotient = old_r // r old_r, r = r, old_r - quotient * r old_s, s = s, old_s - quotient * s old_t, t = t, old_t - quotient * t gcd, x, y = old_r, old_s, old_t assert gcd == 1 assert (k * x) % p == 1 return x % p # Functions that work on curve points ######################################### def is_on_curve(point): """Returns True if the given point lies on the elliptic curve.""" if point is None: # None represents the point at infinity. return True x, y = point return (y * y - x * x * x - curve.a * x - curve.b) % curve.p == 0 def point_add(point1, point2): """Returns the result of point1 + point2 according to the group law.""" assert is_on_curve(point1) assert is_on_curve(point2) if point1 is None: # 0 + point2 = point2 return point2 if point2 is None: # point1 + 0 = point1 return point1 x1, y1 = point1 x2, y2 = point2 if x1 == x2 and y1 != y2: # point1 + (-point1) = 0 return None if x1 == x2: # This is the case point1 == point2. m = (3 * x1 * x1 + curve.a) * inverse_mod(2 * y1, curve.p) else: # This is the case point1 != point2. m = (y1 - y2) * inverse_mod(x1 - x2, curve.p) x3 = m * m - x1 - x2 y3 = y1 + m * (x3 - x1) result = (x3 % curve.p, -y3 % curve.p) assert is_on_curve(result) return result def scalar_mult(k, point): """Returns k * point computed using the double and point_add algorithm.""" assert is_on_curve(point) if k % curve.n == 0 or point is None: return None if k < 0: # k * point = -k * (-point) return scalar_mult(-k, point_neg(point)) result = None addend = point while k: if k & 1: # Add. result = point_add(result, addend) # Double. addend = point_add(addend, addend) k >>= 1 assert is_on_curve(result) return result # Keypair generation and ECDSA ################################################ def make_keypair(): """Generates a random private-public key pair.""" private_key = random.randrange(1, curve.n) public_key = scalar_mult(private_key, curve.g) return private_key, public_key print("Name:\t",curve.name) print("a:\t",curve.a) print("b:\t",curve.b) print("G:\t",curve.g) print("P:\t",curve.p) print("==========================") aliceSecretKey, alicePublicKey = make_keypair() bobSecretKey, bobPublicKey = make_keypair() print("Alice\'s secret key:\t", aliceSecretKey) print("Alice\'s public key:\t", alicePublicKey) print("Bob\'s secret key:\t", bobSecretKey) print("Bob\'s public key:\t", bobPublicKey) sharedSecret1 = scalar_mult(bobSecretKey,alicePublicKey) sharedSecret2 = scalar_mult(aliceSecretKey,bobPublicKey) print("==========================") print("Alice\'s shared key:\t",sharedSecret1) print("Bob\'s shared key:\t",sharedSecret2) print("==========================") print("The shared value is the x-value:\t", (sharedSecret1[0]))