diffie-hellman - npm Package Compare versions

Comparing version 1.1.2 to 2.0.0

dh.js

 var BN = require('bn.js');
-
+var MillerRabin = require('miller-rabin');
+var millerRabin = new MillerRabin();
+var TWENTYFOUR = new BN(24);
+var ELEVEN = new BN(11);
+var TEN = new BN(10);
+var THREE = new BN(3);
+var SEVEN = new BN(7);
+var primes = require('./generatePrime');
 module.exports = DH;
@@ -18,4 +25,69 @@ function setPublicKey(pub, enc) {
 }
-function DH(prime, crypto, malleable) {
-	this.setGenerator(new Buffer([2]));
+var primeCache = {};
+function checkPrime(prime, generator) {
+	var gen = generator.toString('hex');
+	var hex = [gen, prime.toString(16)].join('_');
+	if (hex in primeCache) {
+		return primeCache[hex];
+	}
+	var error = 0;
+	
+	if (prime.isEven() ||
+		!primes.simpleSieve ||
+		!primes.fermatTest(prime) ||
+		!millerRabin.test(prime)) {
+		//not a prime so +1
+		error += 1;
+		
+		if (gen === '02' || gen === '05') {
+			// we'd be able to check the generator
+			// it would fail so +8
+			error += 8;
+		} else {
+			//we wouldn't be able to test the generator
+			// so +4
+			error += 4;
+		}
+		primeCache[hex] = error;
+		return error;
+	}
+	if (!millerRabin.test(prime.shrn(1))) {
+		//not a safe prime
+		error += 2;
+	}
+	var gen = generator.toString('hex');
+	var rem;
+	switch (gen) {
+		case '02':
+		  if (prime.mod(TWENTYFOUR).cmp(ELEVEN)) {
+		  	// unsuidable generator
+		  	error += 8;
+		  }
+		  break;
+		case '05':
+		  rem = prime.mod(TEN);
+		  if (rem.cmp(THREE) && rem.cmp(SEVEN)) {
+		  	// prime mod 10 needs to equal 3 or 7
+		  	error += 8;
+		  } 
+		  break;
+		default: 
+		  error += 4;
+	}
+	primeCache[hex] = error;
+	return error;
+}
+function defineError (self, error) {
+	try {
+		Object.defineProperty(self, 'verifyError', {
+	    enumerable: true,
+	    value: error,
+	    writable: false
+	  });
+	} catch(e) {
+		self.verifyError = error;
+	}
+}
+function DH(prime, generator,crypto, malleable) {
+	this.setGenerator(generator);
 	this.__prime = new BN(prime);
@@ -25,5 +97,9 @@ this._prime = BN.mont(this.__prime);
 	this._priv = void 0;
+	
 	if (malleable) {
 		this.setPublicKey = setPublicKey;
 		this.setPrivateKey = setPrivateKey;
+		defineError(this, checkPrime(this.__prime, generator));
+	} else {
+		defineError(this, 8);
 	}
@@ -30,0 +106,0 @@ this._makeNum = function makeNum() {

generatePrime.js

 
 module.exports = findPrime;
+findPrime.simpleSieve = simpleSieve;
+findPrime.fermatTest = fermatTest;
+var BN = require('bn.js');
+var TWENTYFOUR = new BN(24);
+var MillerRabin = require('miller-rabin');
+var millerRabin = new MillerRabin();
+var ONE = new BN(1);
+var TWO = new BN(2);
+var ELEVEN = new BN(11);
+var FOUR = new BN(4);
+var TWELVE = new BN(12);
+var primes = null;
 
-// based on find-prime by Kenan Yildirim
-// https://github.com/KenanY/find-prime
+function _getPrimes() {
+  if (primes !== null)
+    return primes;
 
-//and
-//bigi https://github.com/cryptocoinjs/bigi
-//which is based on jsbn by Tom Wu
-//http://www-cs-students.stanford.edu/~tjw/jsbn/
-var BN = require('bn.js');
-var GCD_30_DELTA = [new BN(6), new BN(4), new BN(2), new BN(4), new BN(2), new BN(4), new BN(6), new BN(2)];
+  var limit = 0x100000;
+  var res = [];
+  res[0] = 2;
+  for (var i = 1, k = 3; k < limit; k += 2) {
+    var sqrt = Math.ceil(Math.sqrt(k));
+    for (var j = 0; j < i && res[j] <= sqrt; j++)
+      if (k % res[j] === 0)
+        break;
 
+    if (i !== j && res[j] <= sqrt)
+      continue;
 
-function getMillerRabinTests(bits) {
-  if (bits <= 100) return 27;
-  if (bits <= 150) return 18;
-  if (bits <= 200) return 15;
-  if (bits <= 250) return 12;
-  if (bits <= 300) return 9;
-  if (bits <= 350) return 8;
-  if (bits <= 400) return 7;
-  if (bits <= 500) return 6;
-  if (bits <= 600) return 5;
-  if (bits <= 800) return 4;
-  if (bits <= 1250) return 3;
-  return 2;
+    res[i++] = k;
+  }
+  primes = res;
+  return res;
 }
-var lowprimes = [
-  2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71,
-  73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151,
-  157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233,
-  239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317,
-  331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419,
-  421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503,
-  509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607,
-  613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701,
-  709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811,
-  821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911,
-  919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997
-];
+function simpleSieve(p) {
+  var primes = _getPrimes();
 
-var lplim = (1 << 26) / lowprimes[lowprimes.length - 1];
+  for (var i = 0; i < primes.length; i++)
+    if (p.modn(primes[i]) === 0)
+      return false;
 
-// (public) test primality with certainty >= 1-.5^t
-function isProbablePrime(n, t) {
-  var i, x = n.abs();
-  if (x.isEven()) return false;
-  i = 1;
-  while (i < lowprimes.length) {
-    var m = lowprimes[i],
-      j = i + 1;
-    while (j < lowprimes.length && m < lplim) {
-      m *= lowprimes[j++];
-    }
-    m = x.modn(m);
-    while (i < j) {
-      if (m % lowprimes[i++] === 0) {
-        return false;
-      }
-    }
-  }
-  return millerRabin(x, t);
+  return true;
 }
-function getLowestSetBit(n) {
-  var i = -1;
-  var len = n.bitLength();
-  while (++i < len) {
-    if (n.testn(i)) {
-      return i;
-    }
-  }
-  return -1;
+function fermatTest(p) {
+  var red = BN.mont(p);
+  return TWO.toRed(red).redPow(p.subn(1)).fromRed().cmpn(1) === 0;
 }
-// (protected) true if probably prime (HAC 4.24, Miller-Rabin)
-function millerRabin(n, t) {
-  var n1 = n.sub(new BN(1));
-  var mp = BN.mont(n);
-  var k = getLowestSetBit(n1);
-  if (k <= 0) return false;
-  var r = n1.shrn(k);
-  t = (t + 1) >> 1;
-  if (t > lowprimes.length) {
-    t = lowprimes.length;
-  }
-  var a;
-  var j, bases = [];
-  for (var i = 0; i < t; ++i) {
-    for (;;) {
-      j = lowprimes[Math.floor(Math.random() * lowprimes.length)];
-      if (bases.indexOf(j) == -1) break;
-    }
-    bases.push(j);
-    a = new BN(j);
-    var y = a.toRed(mp).redPow(r).fromRed();
-    if (y.cmp(new BN(1)) != 0 && y.cmp(n1) !== 0) {
-      j = 1;
-      while (j++ < k && y.cmp(n1) !== 0) {
-        y = y.toRed(mp).redPow(new BN(2)).fromRed();
-        if (y.cmp(new BN(1)) === 0) {
-          return false;
-        }
-      }
-      if (y.cmp(n1) !== 0) {
-        return false;
-      }
-    }
-  }
-  return true;
-}
 function findPrime(bits, crypto) {
 
   function generateRandom(bits) {
-    var bytes = bits >> 3;
-    bytes = bytes || 1;
-    var out = new BN(crypto.randomBytes(bytes));
-    while (out.bitLength() > bits) {
-      out.ishrn(1);
+    var r = crypto.randomBytes(Math.ceil(bits / 8));
+    r[0] |= 0xc0;
+    r[r.length - 1] |= 3;
+
+    var out = new BN(r);
+    while (out.mod(TWENTYFOUR).cmp(ELEVEN)) {
+      out.iadd(FOUR);
     }
-    if (out.isEven()) {
-      out.iadd(new BN(1));
-    }
     return out;
@@ -127,18 +65,43 @@ }
 
-  var deltaIdx = 0;
 
-  var mrTests = getMillerRabinTests(num.bitLength());
-
-
+  var runs = 0;
+  var n2 = num.shrn(1);
   while (true) {
+    runs++;
     if (num.bitLength() > bits) {
       num = generateRandom(bits);
+      n2 = num.shrn(1);
     }
-    if(isProbablePrime(num, mrTests)) {
+    if (!simpleSieve(n2)) {
+      num.iadd(TWENTYFOUR);
+      n2.iadd(TWELVE);
+      continue;
+    }
+    if (!fermatTest(n2)) {
+      num.iadd(TWENTYFOUR);
+      n2.iadd(TWELVE);
+      continue;
+    }
+    if (!millerRabin.test(n2)) {
+      num.iadd(TWENTYFOUR);
+      n2.iadd(TWELVE);
+      continue;
+    }
+    if (!simpleSieve(num)) {
+      num.iadd(TWENTYFOUR);
+      n2.iadd(TWELVE);
+      continue;
+    }
+    if (!fermatTest(num)) {
+      num.iadd(TWENTYFOUR);
+      n2.iadd(TWELVE);
+      continue;
+    }
+    if (millerRabin.test(num)) {
       return num;
     }
-
-    num.iadd(GCD_30_DELTA[deltaIdx++ % 8]);
+    num.iadd(TWENTYFOUR);
+    n2.iadd(TWELVE);
   }
 
 }

inject.js

@@ -5,15 +5,31 @@ var primes = require('./primes.json');
 module.exports = function (crypto, exports) {
-	exports.getDiffieHellman = function (mod) {
-		return new DH(new Buffer(primes[mod].prime, 'hex'), crypto);
-	};
-	exports.createDiffieHellman = function (prime, enc) {
+	exports.DiffieHellmanGroup =
+    exports.createDiffieHellmanGroup =
+    exports.getDiffieHellman = DiffieHellmanGroup;
+	function DiffieHellmanGroup(mod) {
+		return new DH(new Buffer(primes[mod].prime, 'hex'),
+			new Buffer(primes[mod].gen, 'hex'), crypto);
+	}
+	exports.createDiffieHellman = exports.DiffieHellman = DiffieHellman;
+	function DiffieHellman(prime, enc, generator, genc) {
 		if (typeof prime === 'number') {
-			return new DH(generatePrime(prime, crypto), crypto, true);
+			return new DH(generatePrime(prime, crypto), new Buffer([2]), crypto, true);
 		}
-		enc = enc || 'utf8';
+		if (Buffer.isBuffer(enc) ||
+			(typeof enc === 'string' && ['hex', 'binary', 'base64'].indexOf(enc) === -1)) {
+			genc = generator;
+			generator = enc
+			enc = void 0;
+		}
+		enc = enc || 'binary';
+		genc = genc || 'binary';
+		generator = generator || new Buffer([2]);
 		if (!Buffer.isBuffer(prime)) {
 			prime = new Buffer(prime, enc);
 		}
-		return new DH(prime, crypto, true);
+		if (!Buffer.isBuffer(generator)) {
+			generator = new Buffer(generator, genc);
+		}
+		return new DH(prime, generator, crypto, true);
 	};
-};
+}

package.json

 {
   "name": "diffie-hellman",
-  "version": "1.1.2",
+  "version": "2.0.0",
   "description": "pure js diffie-hellman",
@@ -26,3 +26,4 @@ "main": "index.js",
   "dependencies": {
-    "bn.js": "0.15.2"
+    "bn.js": "0.15.2",
+    "miller-rabin": "^1.1.1"
   },
@@ -29,0 +30,0 @@ "devDependencies": {

test.js

@@ -12,2 +12,4 @@ var test = require('tape');
   192, 224, 256];
+   var lens2 = [
+  64, 65, 128];
 function run(i) {
@@ -44,3 +46,4 @@ mods.forEach(function (mod) {
 			var p2 = prime2.toString('hex');
-			var dh1 = nodeCrypto.createDiffieHellman(prime2);
+			var dh1 = nodeCrypto.createDiffieHellman(prime2, 2);
+			//console.log('error', dh1.verifyError)
 			var p1 = dh1.getPrime().toString('hex');
@@ -84,8 +87,8 @@ t.equals(typeof dh1.setPublicKey, typeof dh2.setPublicKey, 'same methods');
 }
-if (process.version && process.version.split('.').length === 3 && parseInt(process.version.split('.')[1], 10) > 10) {
-	test('create primes', function (t) {
-		var f = bylen(t);
-		lens.forEach(f);
-	});
-}
+
+test('create primes', function (t) {
+	var f = bylen(t);
+	lens2.forEach(f);
+});
+
 test('create primes other way', function (t) {
@@ -98,2 +101,27 @@ var f = bylen2(t);
 	run(i);
+}
+function isNode10() {
+  return process.version && process.version.split('.').length === 3 && parseInt(process.version.split('.')[1], 10) <= 10;
+}
+if (!isNode10()) {
+	test('check errors', function (t) {
+		t.plan(5);
+		var p1 = new Buffer('db10e7f61adcc193', 'hex');
+		var p2 = new Buffer('db10e7f61adcc194', 'hex');
+		var dh1 = myCrypto.createDiffieHellman(p1);
+		var dh2 = nodeCrypto.createDiffieHellman(p1);
+		t.equals(dh1.verifyError, dh2.verifyError, 'same error for good prime');
+		dh1 = myCrypto.createDiffieHellman(p2);
+		dh2 = nodeCrypto.createDiffieHellman(p2);
+		t.equals(dh1.verifyError, dh2.verifyError, 'same error for bad prime');
+		dh1 = myCrypto.createDiffieHellman(p2, new Buffer([7]));
+		dh2 = nodeCrypto.createDiffieHellman(p2, new Buffer([7]));
+		t.equals(dh1.verifyError, dh2.verifyError, 'same error for bad prime non testable generator');
+		dh1 = myCrypto.createDiffieHellman(p1.toString('hex'), 'hex', new Buffer([5]));
+		dh2 = nodeCrypto.createDiffieHellman(p1.toString('hex'), 'hex', new Buffer([5]));
+		t.equals(dh1.verifyError, dh2.verifyError, 'same error for good prime wrong generator');
+		dh1 = myCrypto.createDiffieHellman(p1, new Buffer([11]).toString('hex'), 'hex');
+		dh2 = nodeCrypto.createDiffieHellman(p1, new Buffer([11]).toString('hex'), 'hex');
+		t.equals(dh1.verifyError, dh2.verifyError, 'same error for good prime non testable generator');
+	});
 }

New alerts

License Policy Violation

License

This package is not allowed per your license policy. Review the package's license to ensure compliance.

Found 1 instance in 1 package

Fixed alerts

License Policy Violation

License

This package is not allowed per your license policy. Review the package's license to ensure compliance.

Found 1 instance in 1 package

Improved metrics

Total package byte prevSize

19900

increased by11.11%

Lines of code

451

increased by21.89%

Worsened metrics

Dependency count

2

increased by100%

Dependency changes

• + Addedmiller-rabin@^1.1.1

• + Addedbn.js@1.3.0(transitive)

• + Addedbrorand@1.1.0(transitive)

• + Addedmiller-rabin@1.1.5(transitive)