Diffie-Hellman in JavaScript

Diffie-Hellman is a key exchange that allows 2 people to share a symmetric key without interaction beforehand. First, a person shares an equation; in this case, we use:

$$3^x \mod{17}$$

Next, each person generates a random, usually prime, number. Then, they plug it in the equation. Let's use 5 and 7:

• Alice: \$3^5 \mod{17} \equiv 9 \$

• Bob: \$3^7 \mod{17} \equiv 6 \$

Finally, they share their generated numbers and calculate a "Shared Secret", this is done by (\$U\$ represents your private number):

\$\text{Public}^U \mod{17}\$

In this case:

• Alice: \$6^5 \mod{17} \equiv 2\$

• Bob: \$9^7 \mod{17} \equiv 2\$

Resulting in both parties having the same number. Confused? See this video.

I've implemented a function to generate that key. Thoughts?

function KeyGen(p1, p2, n){
  // Get a binary string, reverse it
  var bin = String((n).toString(2)).split("").reverse().join("");
  // Base for growth
  var grow = n;
  // Holds values for totals
  var tota = [];
  var total = 1;
  // The main loop
  for(var i = 0; i  0;l--){
        tota[i] *= p1;
        tota[i] %= p2;
      }
    }
    total *= tota[i];
    total %= p2;
    grow *= n;
  }
  return total;
}

// Example of gen
var gen = KeyGen(3, 17, 5);

Variable Naming

It took me a while to figure out what are p1, p2 and n (and you don't mention them in your example).

String operation

You could use math operation to do the computation:

function KeyGen(base, modulo, exponent) {
  var result = 1;
  while(exponent > 0){
    if(exponent % 2 == 1){
        result = (result * base) % modulo;
    }
    base = (base * base) % modulo;
    exponent = exponent >>> 1;
  }
  return result;
}

The memory footprint is then very small (no array required).

Big numbers

Issues appear when you try to use big integers (more than 54 bits - like in your comment).
To handle them correctly, I would recommand an external library like BigInt:



`var bigInt=function(e){"use strict";function o(e,t){this.value=e,this.sign=t,this.isSmall=!1}function u(e){this.value=e,this.sign=e0?Math.floor(e):Math.ceil(e)}function d(e,n){var r=e.length,i=n.length,s=new Array(r),o=0,u=t,a,f;for(f=0;f=u?1:0,s[f]=a-ou;while(f0&&s.push(o),s}function v(e,t){return e.length>=t.length?d(e,t):d(t,e)}function m(e,n){var r=e.length,i=new Array(r),s=t,o,u;for(u=0;u0)i[u++]=n%s,n=Math.floor(n/s);return i}function g(e,n){var r=e.length,i=n.length,s=new Array(r),o=0,u=t,a,f;for(a=0;a=0?r=g(e,t):(r=g(t,e),n=!n),r=l(r),typeof r=="number"?(n&&(r=-r),new u(r)):new o(r,n)}function b(e,n,r){var i=e.length,s=new Array(i),a=-n,f=t,c,h;for(c=0;c0)i[a++]=o%s,o=Math.floor(o/s);return i}function S(e,t){var n=[];while(t-->0)n.push(0);return n.concat(e)}function x(e,t){var n=Math.max(e.length,t.length);if(n=0;d--){p=s-1,f[d+i]!==u&&(p=Math.floor((f[d+i]s+f[d+i-1])/u)),v=0,m=0,y=c.length;for(g=0;gi&&(c=(c+1)u),a=Math.ceil(c/h);do{p=E(n,a);if(O(p,o)=0;--o)f=as+e[o],u=p(f/n),a=f-un,i[o]=u|0;return[i,a|0]}function A(e,n){var r,i=Q(n),s=e.value,a=i.value,c;if(a===0)throw new Error("Cannot divide by zero");if(e.isSmall)return i.isSmall?[new u(p(s/a)),new u(s%a)]:[G[0],e];if(i.isSmall){if(a===1)return[e,G[0]];if(a==-1)return[e.negate(),G[0]];var h=Math.abs(a);if(ht.length?1:-1;for(var n=e.length-1;n>=0;n--)if(e[n]!==t[n])return e[n]>t[n]?1:-1;return 0}function M(e){var t=e.abs();if(t.isUnit())return!1;if(t.equals(2)||t.equals(3)||t.equals(5))return!0;if(t.isEven()||t.isDivisibleBy(3)||t.isDivisibleBy(5))return!1;if(t.lesser(25))return!0}function H(e){return(typeof e=="number"||typeof e=="string")&&+Math.abs(e)=0;h--){var d=c?s.value[h]:t,v=p(Math.random()d);f.unshift(v),v"}function $(e,t){t=bigInt(t);if(t.isZero()){if(e.isZero())return"0";throw new Error("Cannot convert nonzero numbers to base 0.")}if(t.equals(-1))return e.isZero()?"0":e.isNegative()?(new Array(1-e)).join("10"):"1"+(new Array(+e)).join("01");var n="";e.isNegative()&&t.isPositive()&&(n="-",e=e.abs());if(t.equals(1))return e.isZero()?"0":n+(new Array(+e+1)).join(1);var r=[],i=e,s;while(i.isNegative()||i.compareAbs(t)>=0){s=i.divmod(t),i=s.quotient;var o=s.remainder;o.isNegative()&&(o=t.minus(o).abs(),i=i.next()),r.push(V(o))}return r.push(V(i)),n+r.reverse().join("")}function J(e){if(a(+e)){var t=+e;if(t===p(t))return new u(t);throw"Invalid integer: "+e}var r=e[0]==="-";r&&(e=e.slice(1));var i=e.split(/e/i);if(i.length>2)throw new Error("Invalid integer: "+f.join("e"));if(i.length===2){var s=i[1];s[0]==="+"&&(s=s.slice(1)),s=+s;if(s!==p(s)||!a(s))throw new Error("Invalid integer: "+s+" is not a valid exponent.");var f=i[0],l=f.indexOf(".");l>=0&&(s-=f.length-l,f=f.slice(0,l)+f.slice(l+1));if(s0)d.push(+e.slice(g,v)),g-=m,g=0)},u.prototype.minus=u.prototype.subtract,o.prototype.negate=function(){return new o(this.value,!this.sign)},u.prototype.negate=function(){var e=this.sign,t=new u(-this.value);return t.sign=!e,t},o.prototype.abs=function(){return new o(this.value,!1)},u.prototype.abs=function(){return new u(Math.abs(this.value))},o.prototype.multiply=function(e){var n,r=Q(e),i=this.value,s=r.value,u=this.sign!==r.sign,a;if(r.isSmall){if(s===0)return G[0];if(s===1)return this;if(s===-1)return this.negate();a=Math.abs(s);if(a4e3?new o(x(i,s),u):new o(w(i,s),u)},o.prototype.times=o.prototype.multiply,u.prototype._multiplyBySmall=function(e){return a(e.valuethis.value)?new u(e.valuethis.value):T(Math.abs(e.value),f(Math.abs(this.value)),this.sign!==e.sign)},o.prototype._multiplyBySmall=function(e){return e.value===0?G[0]:e.value===1?this:e.value===-1?this.negate():T(Math.abs(e.value),this.value,this.sign!==e.sign)},u.prototype.multiply=function(e){return Q(e)._multiplyBySmall(this)},u.prototype.times=u.prototype.multiply,o.prototype.square=function(){return new o(N(this.value),!1)},u.prototype.square=function(){var e=this.value*this.value;return a(e)?new u(e):new o(N(f(Math.abs(this.value))),!1)},o.prototype.divmod=function(e){var t=A(this,e);return{quotient:t[0],remainder:t[1]}},u.prototype.divmod=o.prototype.divmod,o.prototype.divide=function(e){return A(this,e)[0]},u.prototype.over=u.prototype.divide=o.prototype.over=o.prototype.divide,o.prototype.mod=function(e){return A(this,e)[1]},u.prototype.remainder=u.prototype.mod=o.prototype.remain

StackExchange Code Review Q#113860, answer score: 5