Elliptic Curve Diffie Hellman with JavaScript
Elliptic Curve Diffie Hellman (ECDH) is used to generate a shared key. This implementation uses Elliptic Curve Cryptography (ECC) with JavaScript [curves]:
Elliptic Curve parametersECC Type: Secp128r1 - 128-bit security, Secp160r1 - 160-bit security, etc. Hex:
|
Theory
Elliptic Curve Diffie Hellman (ECDH) is used to create a shared key. In this example we use secp256k1 (as used in Bitcoin) 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\)) 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:
Code
Some example code is [code]:
<script language="JavaScript" type="text/javascript" src="/jsbn.js"></script> <script language="JavaScript" type="text/javascript" src="/jsbn2.js"></script> <script language="JavaScript" type="text/javascript" src="/prng4.js"></script> <script language="JavaScript" type="text/javascript" src="/rng.js"></script> <script language="JavaScript" type="text/javascript" src="/ec.js"></script> <script language="JavaScript" type="text/javascript" src="/sec.js"></script> <script language="JavaScript"> <!-- type = "secp128r1"; qval = 0; aval = ("0").toBigInteger(); bval = ("0").toBigInteger(); nval = "0"; gx = ("0").toBigInteger(); gy = ("0").toBigInteger(); r = 0; function do_status(s) { document.getElementById('status').innerHTML = s; } function do_method(s) { document.getElementById('method').innerHTML = s; } function set_ec_params(name) { if (name == "") name = type; var c = getSECCurveByName(name); var elm = document.getElementById('dec'); qval = c.getCurve().getQ(); aval = c.getCurve().getA().toBigInteger(); bval = c.getCurve().getB().toBigInteger(); nval = c.getN(); gx = c.getG().getX().toBigInteger(); gy = c.getG().getY().toBigInteger(); if (elm.checked == true) { document.getElementById('q').innerHTML = qval.toString(16).toString(); document.getElementById('a').innerHTML = aval.toString(16).toString(); document.getElementById('b').innerHTML = bval.toString(16).toString(); document.getElementById('gx').innerHTML = gx.toString(16).toString(); document.getElementById('gy').innerHTML = gy.toString(16).toString(); document.getElementById('n').innerHTML = nval.toString(16).toString(); } else { document.getElementById('q').innerHTML = qval.toString(); document.getElementById('a').innerHTML = aval.toString(); document.getElementById('b').innerHTML = bval.toString(); document.getElementById('gx').innerHTML = gx.toString() document.getElementById('gy').innerHTML = gy.toString(); document.getElementById('n').innerHTML = nval.toString(); } // Changing EC params invalidates everything else document.getElementById('alice_priv').innerHTML = ""; document.getElementById('bob_priv').innerHTML = ""; document.getElementById('alice_pub_x').innerHTML = ""; document.getElementById('alice_pub_y').innerHTML = ""; document.getElementById('bob_pub_x').innerHTML = ""; document.getElementById('bob_pub_y').innerHTML = ""; document.getElementById('alice_key_x').innerHTML = ""; document.getElementById('alice_key_y').innerHTML = ""; document.getElementById('bob_key_x').innerHTML = ""; document.getElementById('bob_key_y').innerHTML = ""; do_method("Using " + name + " EC parameters"); } function set_secp128r1() { set_ec_params("secp128r1"); type = "secp128r1"; } function set_secp160k1() { set_ec_params("secp160k1"); type = "secp160k1"; } function set_secp160r1() { set_ec_params("secp160r1"); type = "secp160r1"; } function set_secp192k1() { set_ec_params("secp192k1"); type = "secp192k1"; } function set_secp192r1() { set_ec_params("secp192r1"); type = "secp192r1"; } function set_secp224r1() { set_ec_params("secp224r1"); type = "secp224r1"; } function set_secp256r1() { set_ec_params("secp256r1"); type = "secp256r1"; } var rng; function do_init() { if (qval == 0) set_secp160k1(); rng = new SecureRandom(); } function get_curve() { return new ECCurveFp(new BigInteger(qval.toString()), aval, bval); } function get_G(curve) { return new ECPointFp(curve, curve.fromBigInteger(gx), curve.fromBigInteger(gy)); } function pick_rand() { var n1 = nval.subtract(BigInteger.ONE); var r = new BigInteger(nval.bitLength(), rng); return r.mod(n1).add(BigInteger.ONE); } function do_alice_rand() { var r = pick_rand(); document.getElementById('alice_priv').innerHTML = r.toString(); document.getElementById('alice_pub_x').innerHTML = ""; document.getElementById('alice_pub_y').innerHTML = ""; document.getElementById('alice_key_x').innerHTML = ""; document.getElementById('alice_key_y').innerHTML = ""; document.getElementById('bob_key_x').innerHTML = ""; document.getElementById('bob_key_y').innerHTML = ""; do_status("Alice's random value generated"); } function do_bob_rand() { r = pick_rand(); document.getElementById('bob_priv').innerHTML = r.toString(); document.getElementById('bob_pub_x').innerHTML = ""; document.getElementById('bob_pub_y').innerHTML = ""; document.getElementById('alice_key_x').innerHTML = ""; document.getElementById('alice_key_y').innerHTML = ""; document.getElementById('bob_key_x').innerHTML = ""; document.getElementById('bob_key_y').innerHTML = ""; do_status("Bob's random value generated"); } function do_alice_pub() { if (document.getElementById('alice_priv').innerHTML.length == 0) { alert("Please generate Alice's private value first"); return; } var before = new Date(); var curve = get_curve(); var G = get_G(curve); var a = new BigInteger(document.getElementById('alice_priv').innerHTML); var P = G.multiply(a); var after = new Date(); document.getElementById('alice_pub_x').innerHTML = P.getX().toBigInteger().toString(); document.getElementById('alice_pub_y').innerHTML = P.getY().toBigInteger().toString(); document.getElementById('bob_key_x').innerHTML = ""; document.getElementById('bob_key_y').innerHTML = ""; do_status("Alice's public point computed in " + (after - before) + "ms"); } function do_bob_pub() { if (document.getElementById('bob_priv').innerHTML.length == 0) { alert("Please generate Bob's private value first"); return; } var before = new Date(); var curve = get_curve(); var G = get_G(curve); var a = new BigInteger(document.getElementById('bob_priv').innerHTML); var P = G.multiply(a); var after = new Date(); document.getElementById('bob_pub_x').innerHTML = P.getX().toBigInteger().toString(); document.getElementById('bob_pub_y').innerHTML = P.getY().toBigInteger().toString(); document.getElementById('alice_key_x').innerHTML = ""; document.getElementById('alice_key_y').innerHTML = ""; do_status("Bob's public point computed in " + (after - before) + "ms"); } function do_alice_key() { if (document.getElementById('alice_priv').innerHTML.length == 0) { alert("Please generate Alice's private value first"); return; } if (document.getElementById('bob_pub_x').innerHTML.length == 0) { alert("Please compute Bob's public value first"); return; } var before = new Date(); var curve = get_curve(); var P = new ECPointFp(curve, curve.fromBigInteger(new BigInteger(document.getElementById('bob_pub_x').innerHTML)), curve.fromBigInteger(new BigInteger(document.getElementById('bob_pub_y').innerHTML))); var a = new BigInteger(document.getElementById('alice_priv').innerHTML); var S = P.multiply(a); var after = new Date(); document.getElementById('alice_key_x').innerHTML = S.getX().toBigInteger().toString(); document.getElementById('alice_key_y').innerHTML = S.getY().toBigInteger().toString(); do_status("Alice's key derived in " + (after - before) + "ms"); } function do_bob_key() { if (document.getElementById('bob_priv').innerHTML.length == 0) { alert("Please generate Bob's private value first"); return; } if (document.getElementById('alice_pub_x').innerHTML.length == 0) { alert("Please compute Alice's public value first"); return; } var before = new Date(); var curve = get_curve(); var P = new ECPointFp(curve, curve.fromBigInteger(new BigInteger(document.getElementById('alice_pub_x').innerHTML)), curve.fromBigInteger(new BigInteger(document.getElementById('alice_pub_y').innerHTML))); var a = new BigInteger(document.getElementById('bob_priv').innerHTML); var S = P.multiply(a); var after = new Date(); document.getElementById('bob_key_x').innerHTML = S.getX().toBigInteger().toString(); document.getElementById('bob_key_y').innerHTML = S.getY().toBigInteger().toString(); do_status("Bob's key derived in " + (after - before) + "ms"); } //--> </script>
The setting for the curves:
// Named EC curves // Requires ec.js, jsbn.js, and jsbn2.js // ---------------- // X9ECParameters // constructor function X9ECParameters(curve,g,n,h) { this.curve = curve; this.g = g; this.n = n; this.h = h; } function x9getCurve() { return this.curve; } function x9getG() { return this.g; } function x9getN() { return this.n; } function x9getH() { return this.h; } X9ECParameters.prototype.getCurve = x9getCurve; X9ECParameters.prototype.getG = x9getG; X9ECParameters.prototype.getN = x9getN; X9ECParameters.prototype.getH = x9getH; // ---------------- // SECNamedCurves function fromHex(s) { return new BigInteger(s, 16); } function secp128r1() { // p = 2^128 - 2^97 - 1 var p = fromHex("FFFFFFFDFFFFFFFFFFFFFFFFFFFFFFFF"); var a = fromHex("FFFFFFFDFFFFFFFFFFFFFFFFFFFFFFFC"); var b = fromHex("E87579C11079F43DD824993C2CEE5ED3"); //byte[] S = Hex.decode("000E0D4D696E6768756151750CC03A4473D03679"); var n = fromHex("FFFFFFFE0000000075A30D1B9038A115"); var h = BigInteger.ONE; var curve = new ECCurveFp(p, a, b); var G = curve.decodePointHex("04" + "161FF7528B899B2D0C28607CA52C5B86" + "CF5AC8395BAFEB13C02DA292DDED7A83"); return new X9ECParameters(curve, G, n, h); } function secp160k1() { // p = 2^160 - 2^32 - 2^14 - 2^12 - 2^9 - 2^8 - 2^7 - 2^3 - 2^2 - 1 var p = fromHex("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFAC73"); var a = BigInteger.ZERO; var b = fromHex("7"); //byte[] S = null; var n = fromHex("0100000000000000000001B8FA16DFAB9ACA16B6B3"); var h = BigInteger.ONE; var curve = new ECCurveFp(p, a, b); var G = curve.decodePointHex("04" + "3B4C382CE37AA192A4019E763036F4F5DD4D7EBB" + "938CF935318FDCED6BC28286531733C3F03C4FEE"); return new X9ECParameters(curve, G, n, h); } function secp160r1() { // p = 2^160 - 2^31 - 1 var p = fromHex("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF7FFFFFFF"); var a = fromHex("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF7FFFFFFC"); var b = fromHex("1C97BEFC54BD7A8B65ACF89F81D4D4ADC565FA45"); //byte[] S = Hex.decode("1053CDE42C14D696E67687561517533BF3F83345"); var n = fromHex("0100000000000000000001F4C8F927AED3CA752257"); var h = BigInteger.ONE; var curve = new ECCurveFp(p, a, b); var G = curve.decodePointHex("04" + "4A96B5688EF573284664698968C38BB913CBFC82" + "23A628553168947D59DCC912042351377AC5FB32"); return new X9ECParameters(curve, G, n, h); } function secp192k1() { // p = 2^192 - 2^32 - 2^12 - 2^8 - 2^7 - 2^6 - 2^3 - 1 var p = fromHex("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFEE37"); var a = BigInteger.ZERO; var b = fromHex("3"); //byte[] S = null; var n = fromHex("FFFFFFFFFFFFFFFFFFFFFFFE26F2FC170F69466A74DEFD8D"); var h = BigInteger.ONE; var curve = new ECCurveFp(p, a, b); var G = curve.decodePointHex("04" + "DB4FF10EC057E9AE26B07D0280B7F4341DA5D1B1EAE06C7D" + "9B2F2F6D9C5628A7844163D015BE86344082AA88D95E2F9D"); return new X9ECParameters(curve, G, n, h); } function secp192r1() { // p = 2^192 - 2^64 - 1 var p = fromHex("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFFFFFFFFFFFF"); var a = fromHex("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFFFFFFFFFFFC"); var b = fromHex("64210519E59C80E70FA7E9AB72243049FEB8DEECC146B9B1"); //byte[] S = Hex.decode("3045AE6FC8422F64ED579528D38120EAE12196D5"); var n = fromHex("FFFFFFFFFFFFFFFFFFFFFFFF99DEF836146BC9B1B4D22831"); var h = BigInteger.ONE; var curve = new ECCurveFp(p, a, b); var G = curve.decodePointHex("04" + "188DA80EB03090F67CBF20EB43A18800F4FF0AFD82FF1012" + "07192B95FFC8DA78631011ED6B24CDD573F977A11E794811"); return new X9ECParameters(curve, G, n, h); } function secp224r1() { // p = 2^224 - 2^96 + 1 var p = fromHex("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF000000000000000000000001"); var a = fromHex("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFFFFFFFFFFFFFFFFFFFE"); var b = fromHex("B4050A850C04B3ABF54132565044B0B7D7BFD8BA270B39432355FFB4"); //byte[] S = Hex.decode("BD71344799D5C7FCDC45B59FA3B9AB8F6A948BC5"); var n = fromHex("FFFFFFFFFFFFFFFFFFFFFFFFFFFF16A2E0B8F03E13DD29455C5C2A3D"); var h = BigInteger.ONE; var curve = new ECCurveFp(p, a, b); var G = curve.decodePointHex("04" + "B70E0CBD6BB4BF7F321390B94A03C1D356C21122343280D6115C1D21" + "BD376388B5F723FB4C22DFE6CD4375A05A07476444D5819985007E34"); return new X9ECParameters(curve, G, n, h); } function secp256r1() { // p = 2^224 (2^32 - 1) + 2^192 + 2^96 - 1 var p = fromHex("FFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFF"); var a = fromHex("FFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFC"); var b = fromHex("5AC635D8AA3A93E7B3EBBD55769886BC651D06B0CC53B0F63BCE3C3E27D2604B"); //byte[] S = Hex.decode("C49D360886E704936A6678E1139D26B7819F7E90"); var n = fromHex("FFFFFFFF00000000FFFFFFFFFFFFFFFFBCE6FAADA7179E84F3B9CAC2FC632551"); var h = BigInteger.ONE; var curve = new ECCurveFp(p, a, b); var G = curve.decodePointHex("04" + "6B17D1F2E12C4247F8BCE6E563A440F277037D812DEB33A0F4A13945D898C296" + "4FE342E2FE1A7F9B8EE7EB4A7C0F9E162BCE33576B315ECECBB6406837BF51F5"); return new X9ECParameters(curve, G, n, h); } function secp256k1() { var p = fromHex("fffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f"); var a = fromHex("0"); var b = fromHex("7"); //byte[] S = Hex.decode("C49D360886E704936A6678E1139D26B7819F7E90"); var n = fromHex("fffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141"); var h = BigInteger.ONE; var curve = new ECCurveFp(p, a, b); var G = curve.decodePointHex("04" + "79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798" + "483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8"); return new X9ECParameters(curve, G, n, h); } // TODO: make this into a proper hashtable function getSECCurveByName(name) { if(name == "secp128r1") return secp128r1(); if(name == "secp160k1") return secp160k1(); if(name == "secp160r1") return secp160r1(); if(name == "secp192k1") return secp192k1(); if(name == "secp192r1") return secp192r1(); if(name == "secp224r1") return secp224r1(); if(name == "secp256r1") return secp256r1(); if(name == "secp256k1") return secp256k1(); return null; }
Presentation
The following is an outline presentation: