Elliptic Curve Diffie Hellman (ECDH) is used to create a shared key. Bob will generate a public key (\(Q_B\)) and private key (\(d_B\)), as will Alice (\(Q_A\) and \(d_A\)). They then exchange their public keys, and the shared key will then be \(d_A \times d_B \times G\), and where \(G\) is the generator point on the elliptic curve. Another popular curve is Curve 25519, and which is used by Tor nodes [here]
Elliptic Curve Diffie Hellman (ECDH) |
Theory
Elliptic Curve Diffie Hellman (ECDH) is used to create a shared key. In this example use Curve 25519 to generate points on the curve. Its format is:
\(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)
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\)):
\(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.
Sample run
The following is a sample run:
Basepoint: (920 (mod 3851), 303 (mod 3851)) Alice's secret key: 53249 Bob's secret key: 40519 ========================== Alice's public key: (3776 (mod 3851), 2797 (mod 3851)) Bob's public key: (2291 (mod 3851), 750 (mod 3851)) ========================== Alice's shared key: (2530 (mod 3851), 2232 (mod 3851)) Bob's shared key: (2530 (mod 3851), 2232 (mod 3851)) ========================== The shared value is the x-value: 2530
Code
Here is the code to generate this:
from elliptic import * from finitefield.finitefield import FiniteField import binascii import os def generateSecretKey(numBits): return binascii.hexlify(os.urandom(numBits // 8)) def sendDH(privateKey, generator, sendFunction): privateKey=int(privateKey,16) return sendFunction(privateKey * generator) def receiveDH(privateKey, receiveFunction): privateKey=int(privateKey,16) return privateKey * receiveFunction() def slowOrder(point): Q = point i = 1 while True: if type(Q) is Ideal: return i else: Q = Q + point i += 1 def to_bytes(n, length): return bytes( (n >> i*8) & 0xff for i in reversed(list(range(length)))) if __name__ == "__main__": F = FiniteField(3851, 1) # Totally insecure curve: y^2 = x^3 + 324x + 1287 curve = EllipticCurve(a=F(324), b=F(1287)) # order is 1964 basePoint = Point(curve, F(920), F(303)) aliceSecretKey = generateSecretKey(16) bobSecretKey = generateSecretKey(16) print("Alice\'s secret key:\t", aliceSecretKey) print("Bob\'s secret key:\t", bobSecretKey) print("==========================") alicePublicKey = sendDH(aliceSecretKey, basePoint, lambda x:x) bobPublicKey = sendDH(bobSecretKey, basePoint, lambda x:x) print("Alice's public key:\t",alicePublicKey) print("Bob's public key:\t",bobPublicKey) sharedSecret1 = receiveDH(bobSecretKey, lambda: alicePublicKey) sharedSecret2 = receiveDH(aliceSecretKey, lambda: 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.x.n))