Diffie-Hellman key exchange in Javascript

The Diffie-Hellman key exchange protocol (RFC2641) is an efficient way for two parties (that do not know each other beforehand) to establish a shared secret. This secret can then be used for encrypted communication between the two parties. Because of the simplicity of the algorithm it is a feasible to implement it in Javascript. It could serve as a way to communicate between to participants of a social network in a host-proof way (meaning the host can not access the messages that are exchanged between Alice and Bob).

The following straight forward implementation is based on the ingenious BigInt Javascript library created by Leemon Baird:

function d_h()
{
  // Alice tries to send to Bob, they agree on a 256 bit prime
  var p = str2bigInt(
    "10883804965994030335610375728683210724614077" + 
    "5791152305372594007835539736018383", 10, 80); 
  var g = str2bigInt("2", 10, 80);       // and on a generator
  
  // Alice chooses her secret randomly
  var a = str2bigInt(
    "3103830701216420526524336327874353922197141754" + 
    "5159778383387464250", 10, 80);

  // Bob chooses his secret randomly
  var b = str2bigInt(
    "26264611999731746945409581849451656136966431" + 
    "516270225144913718599547", 10, 80);

  // calculate the public key
  var A = powMod(g,a,p); var B = powMod(g,b,p);

  // A and B are exchanged publicly
  // Alice and Bob can compute the same key from A and B
  var a_sec = powMod(B, a, p);
  var b_sec = powMod(A, b, p);

  alert(bigInt2str(a_sec, 10) + '\n ' + bigInt2str(b_sec, 10));
}

In case you wonder how to choose p and g – so did I. Turns out a generator for those numbers is part of the Crypto++ library. The following application uses this library to calculate p and g with different length.

#include 
#include 
#include 
#include "dh.h"
#include "osrng.h"

using namespace std;
using namespace CryptoPP;
using namespace TCLAP;

int main(int argc, char** argv)
{
                                                   // read command line
  CmdLine cmd("Diffie Hellman p g generator", ' ', "0.1");
  UnlabeledMultiArg m("bv", "bits and values", true, "");
  cmd.add( m ); cmd.parse(argc, argv);
  vector mv = m.getValue(); mv.push_back(1);
  unsigned int bv = mv[0]; unsigned int nv = mv[1];

  AutoSeededRandomPool arngA;                       // generate p and g
  RandomNumberGenerator& rngA =
    *dynamic_cast(&arngA);
  for(unsigned short i=0; i
The application uses the TCLAP library to parse the command line. The first parameter should be the width of the prime number in bits, the second optional parameter specifies how many primes and generators should be calculated. 
Here's a list of p and g I generated with different widths:
128 bits:
p=197221152031991558322935568090317202983 g=2

256 bits:
p=11245712998331706449413325803449175679094351102802336690101496856041
0379195027 g=3

512 bits:
p=85591083890203292422929753448312002013227700164244056883767436387780
3988137714894694780639823858404151944019992782250585325661689168497741
6276395927762259 g=3

1024 bits:
p=10756096062425499020105845514001321706994933124811434157429824859705
5584898126321093330768462486995125563469663163251404817709163750190539
8111908385982976186475492023836046174671146008757104643109463540714363
4989690852152224155785251701387082100575086970999263664414942032660939
2283245879753842682719140993487 g=2

2048 bits:
p=28401819833194672263220074318568239913240629340614134316461681527129
7400190276361407578313119949940155208450277590596255133024483132860231
2683364685437571458516690608818388566379408009734093619889676676688482
4330230759478149039933887325452487112982841213248410034360015394086822
8492443771741195501623918057531604439427869721645027989688343068984123
6647850119363273567137904693671110310979494733094653291727319950103948
4827099108375018229688415849095088940888827138097109161920916553046346
9800257941704054817481593649080741474714321422084101095199976587101477
59474207550469840261684005212634493995003979085986141372247 g=2

Those numbers do not have to be calculated every time but in fact can be hard-coded in your application.
          




6 Comments

  

    
#1 JVerstry wrote on December 15,  2010:
	  
Hi, 
If I may give feedback, beware of your (p,g) generator. The values it returns for g are too small for sure. Moreover, it’s not clear whether your generator makes sure that g is not a primitive element over Zp. This could lead to easy brute force attacks.
For more details, you may want to read Chapter 12 of the Practical Cryptography book by Neils Fergusson and Bruce Schneier.
Cheers,
J.
  
  

    
#2 Sebastian Schaetz wrote on December 15,  2010:
	  
Jvestry,
thank you for your comment. I am by no means an expert in cryptography so I am thankful. Cryptography is a field where you can easily get a lot of things wrong if you are not knowledgeable about the topic.
I’m not sure how the mistake (too small g) happened. I guess I’m somehow using the Crypto++ library in a wrong way. In their documentation however [0] they show a similarly small value for g.
Maybe it is a good idea to use the generator as specified in RFC 5114 [1].
In any case I updated the post to warn readers about the weakness.
[0] http://www.cryptopp.com/wiki/Diffie-Hellman#Generating_Parameters_.28MODP.29

[1] http://tools.ietf.org/html/rfc5114#section-2.1
  
  

    
#3 Sebastian L. wrote on October 18,  2011:
	  
Hey Sebastian,
I checked the book “Applied Cryptography” of Bruce Schneier (Edition of 2006). On Page 587 it states (Translated from German): “The Security of the System (Diffie-Hellman) depends very much on the values of p and g. The most important thing is that p is a big number […]. g, however, can be chosen arbitrarily if it is modulo primitive to n. There is nothing to be said against choosing the smallest possible value for g – in most cases g has only one digit.” So I guess the numbers generated by your generator are ok!
Cheers,

Sebastian
  
  

    
#4 suzukaII wrote on December 2,  2011:
	  
As far as I know, g is intended to be small

http://en.wikipedia.org/wiki/Diffie-Hellman
  
  

    
#5 Sebastian Schaetz wrote on January 10,  2012:
	  
Sebastian, suzukaII, thanks for the clarification!
  
  

    
#6 SmallGenerator wrote on September 4,  2013:
	  
See the explanation here on why using 2 or 3 is perfectly secure.

http://crypto.stackexchange.com/questions/639/does-the-generator-size-matter-in-diffie-hellman
  



Sorry, the comment form is closed at this time.