Avatar of brunnock

brunnock's solution

to Diffie Hellman in the JavaScript Track

Published at Aug 19 2018 · 0 comments
Instructions
Test suite
Solution

Note:

This exercise has changed since this solution was written.

Diffie-Hellman key exchange.

Alice and Bob use Diffie-Hellman key exchange to share secrets. They start with prime numbers, pick private keys, generate and share public keys, and then generate a shared secret key.

Step 0

The test program supplies prime numbers p and g.

Step 1

Alice picks a private key, a, greater than 1 and less than p. Bob does the same to pick a private key b.

Step 2

Alice calculates a public key A.

A = g**a mod p

Using the same p and g, Bob similarly calculates a public key B from his private key b.

Step 3

Alice and Bob exchange public keys. Alice calculates secret key s.

s = B**a mod p

Bob calculates

s = A**b mod p

The calculations produce the same result! Alice and Bob now share secret s.

Setup

Go through the setup instructions for JavaScript to install the necessary dependencies:

http://exercism.io/languages/javascript/installation

Running the test suite

The provided test suite uses Jasmine. You can install it by opening a terminal window and running the following command:

npm install -g jasmine

Run the test suite from the exercise directory with:

jasmine diffie-hellman.spec.js

In many test suites all but the first test have been marked "pending". Once you get a test passing, activate the next one by changing xit to it.

Source

Wikipedia, 1024 bit key from www.cryptopp.com/wiki. http://en.wikipedia.org/wiki/Diffie%E2%80%93Hellman_key_exchange

Submitting Incomplete Solutions

It's possible to submit an incomplete solution so you can see how others have completed the exercise.

diffie-hellman.spec.js

var DiffieHellman = require('./diffie-hellman');

describe('diffie-hellman', function () {
  var p = 23;
  var g = 5;
  var diffieHellman = new DiffieHellman(p, g);

  var alicePrivateKey = 6;
  var alicePublicKey = 8;

  var bobPrivateKey = 15;
  var bobPublicKey = 19;

  it('throws an error if the constructor arguments are out of range', function () {
    expect(function () {
      return new DiffieHellman(0, 9999);
    }).toThrow();
  });

  xit('throws an error if the constructor arguments are not prime', function () {
    expect(function () {
      return new DiffieHellman(10, 13);
    }).toThrow();
  });

  xit('throws an error if private key is negative', function () {
    expect(function () {
      diffieHellman.getPublicKeyFromPrivateKey(-1);
    }).toThrow();
  });

  xit('throws an error if private key is zero', function () {
    expect(function () {
      diffieHellman.getPublicKeyFromPrivateKey(0);
    }).toThrow();
  });

  xit('throws an error if private key is one', function () {
    expect(function () {
      diffieHellman.getPublicKeyFromPrivateKey(1);
    }).toThrow();
  });

  xit('throws an error if private key equals the modulus parameter p', function () {
    expect(function () {
      diffieHellman.getPublicKeyFromPrivateKey(p);
    }).toThrow();
  });

  xit('throws an error if private key is greater than the modulus parameter p', function () {
    expect(function () {
      diffieHellman.getPublicKeyFromPrivateKey(p + 1);
    }).toThrow();
  });

  xit('when given a private key, returns the correct public one', function () {
    expect(diffieHellman.getPublicKeyFromPrivateKey(alicePrivateKey)).toEqual(alicePublicKey);
  });

  xit('when given a different private key, returns the correct public one', function () {
    expect(diffieHellman.getPublicKeyFromPrivateKey(bobPrivateKey)).toEqual(bobPublicKey);
  });

  xit('can generate a shared secret from our private key and their public key', function () {
    var sharedSecret = 2;

    expect(diffieHellman.getSharedSecret(alicePrivateKey, bobPublicKey))
      .toEqual(sharedSecret);

    expect(diffieHellman.getSharedSecret(bobPrivateKey, alicePublicKey))
      .toEqual(sharedSecret);
  });
});
function notPrime(num) {
  const sqrt = ~~Math.sqrt(num);
  const possibleFactors= Array(sqrt).fill(true);
  for (let x=2; x<=sqrt; ++x) {
    if (possibleFactors[x]) {
      if (num % x === 0) return (true);
      for (let y=(x+x); y<=sqrt; y+=x) possibleFactors[y]=false;
    }
  }
  return (false);
}
class DiffieHellman {
  constructor(p,g){
    if ( (p<2) || (g<2)) throw('out of range');
    if ( notPrime(p) || notPrime(g)) throw('not prime');
    this.p=p;
    this.g=g;
  }
  getPublicKeyFromPrivateKey(privKey) {
    if ( (privKey<2) || (privKey>=this.p)) throw('key out of range');
    return(this.g**privKey % this.p);
  }
  getSharedSecret(privKey, pubKey) {
    return(pubKey**privKey % this.p);
  }
}
module.exports=DiffieHellman;

Community comments

Find this solution interesting? Ask the author a question to learn more.

What can you learn from this solution?

A huge amount can be learned from reading other people’s code. This is why we wanted to give exercism users the option of making their solutions public.

Here are some questions to help you reflect on this solution and learn the most from it.

  • What compromises have been made?
  • Are there new concepts here that you could read more about to improve your understanding?