current community

your communities

more stack exchange communities

company blog
Stack Exchange Inbox Reputation and Badges
tour help
Sign up ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.
up vote 6 down vote favorite

Diffie-Hellman is a key exchange that allows 2 people to share a symmetric key without interaction before hand, 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 for 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 < bin.length; i++){
    tota[i] = 1;
    if(bin.substring(i, i + 1) === "1"){
      for (var l = grow; l > 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);
share|improve this question
1  
Its very laggy, and I have a feeling the code can be optimized. – AppIns yesterday
    
This post is currently being discussed on meta. – SirPython yesterday
    
I think you will have much better performance if you keep n an integer and forget all about the string and array. Replace string.substring(i, i+1) and array[i] with (number >> i) & 1. Put n = n | 0; near the top, too. – sqykly yesterday

2 Answers 2

up vote 3 down vote accepted

You can't overcome the inherent loopiness of the algorithm, therefore the function can be made only very slightly more economical :

  • avoid the need for substring() by leaving the reversed string as an array - don't join()it.
  • avoid double assignments when one will suffice.
  • tota is only ever written to, never read back from nor returned. "tota[i]" would be better as a var.

You can also better exploit javascript's array methods :

  • the algorithm is a reduction of the reversed string, so use Array#reduce().
function KeyGen(p1, p2, n) {
    var grow = n;
    return n.toString(2).split('').reverse().reduce(function(total, char) {
        var x = 1;
        if(char === '1') {
            for (var i=grow; i>0; i--) {
                x = (x * p1) % p2; // any performance gain will be here
            }
        }
        grow *= n;
        return (total * x) % p2;
    }, 1);
}

Unfortunately, I doubt whether any of that will make a big difference.

EDIT

With regard to the improved algorithm (OP's own answer), I would guess that any performance gain is due to not performing the (massive) inner for loop, rather than pre-calculating the powers of p1.

FWIW, here is a cleaner version :

function KeyGen(p1, p2, n) {
    var binArray = n.toString(2).split('').map(function(char) {
        return +char; // convert String to Number
    });
    var bin = binArray.reduce(function(arr, digit, i) {
        arr.push( (arr[i] * arr[i]) % p2 );
        return arr;
    }, [p1]);
    return binArray.reduce(function(total, digit, i) {
        return digit ? (total * bin[i]) % p2 : total;
    }, 1);
}
share|improve this answer
    
This helped a bit, thanks! – AppIns yesterday
    
Would it help if I executed it differently? – AppIns yesterday
    
Differently, in what way? – Roamer-1888 yesterday
    
I don't know, I meant out of browser, I found an answer that works in browser and fast though. – AppIns yesterday
    
I would guess that chips/chip-sets (specialized maths coprocessors) are available to do this and related cryptographic computations. I know that's not the answer you want, but it's the best I can offer. – Roamer-1888 13 hours ago
up vote 0 down vote

I found a really efficient way to solve this problem! It requires calculating the values before hand, my code goes as follows:

function KeyGen(p1, p2, n) {
    var inc = 0;
    var bin = [];
    bin[0] = p1;
    for (var i = 1; i <= n.toString(2).length; i++){
      bin[i] = (bin[i-1] * bin[i-1]) % p2;
      console.log(bin[i] + " and " + bin[i-1]);
    }
    console.log("loop");
    return n.toString(2).split('').reverse().reduce(function(total, char) {
        if(char === '1') {
              total = (total * bin[inc]) % p2;
              console.log("current "+ total);
            }
        inc++;
        return total % p2;
    }, 1);
}
share|improve this answer
1  
I am quite positive it will still be quicker to use bit math. Strings and arrays are big slow objects with methods to call, properties to look up, and unpredictable return types. Strings are further immutable and are getting copied all over. Integers are tiny piles of bits that can be instantly transformed into the bits you want with no allocating, no call, no lookup, no uncertainty of type. – sqykly yesterday
    
I understand it would be faster, but this by far suits my needs, it can do 256 bit operations in seconds! – AppIns yesterday
    
Have you tested it with an actual 256 bit number? That's way past the precision limit. – sqykly yesterday
    
I think neither approach is going to work then. Best bet will be a typed array of integers. Will likely do 256 bits in milliseconds. – sqykly yesterday
    
This executed in seconds, this is an actual 256 bit number generated for diffe-hellman KeyGen(3, 112457129983317064494133258034491756790943511028023366901014968560410379195027, 23984081230374123749712934791249172394719237497219347129374498); – AppIns yesterday

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.