Обмен ключами Диффи-Хеллмана с Javascript иногда неверен

После просмотра этого видео http://youtu.be/3QnD2c4Xovk

Я пытался следовать этому шаг за шагом, и не смог добиться тех же результатов.

Примечательно, что когда я пытаюсь выполнить Math.pow(3, 54)%17, я получаю 7. В то время как говорящий получает 15.

Я написал метод, который должен имитировать обмен ключами Диффи Хеллмана, используя именно то, что я нашел на http://en.wikipedia.org/wiki/Diffie%E2%80%93Hellman_key_exchange

Это мой код:

function diffieHellman(generator, prime, alice_secret, bob_secret){
  var alice_public = Math.pow(generator, alice_secret)%prime
    , bob_public = Math.pow(generator, bob_secret)%prime
    , alice_private = Math.pow(bob_public, alice_secret)%prime
    , bob_private = Math.pow(alice_public, bob_secret)%prime;
  console.log("alice"
  , "\n\t", "secret -- ", alice_secret
  , "\n\t", "public -- ", alice_public
  , "\n\t", "private -- ", alice_private
  )
  console.log("bob"
  , "\n\t", "secret -- ", bob_secret
  , "\n\t", "public -- ", bob_public
  , "\n\t", "private -- ", bob_private
  )
  return {
    alice:{
      secret: alice_secret
    , public: alice_public
    , private: alice_private
    },
    bob:{
      secret: bob_secret
    , public: bob_public
    , private: bob_private
    }
  }
};

Эти примеры работают:

diffieHellman(3, 17, 4, 12) // 1, 1
diffieHellman(3, 23, 6, 19) // 12, 12
diffieHellman(3, 13, 8, 4) // 9, 9

Однако некоторые номера не работают

diffieHellman(3, 17, 40, 120) // 13, 0
diffieHellman(3, 23, 16, 129) // 21, 2
diffieHellman(3, 13, 44, 11) // 9, 1

Что я делаю не так?

Изменить. Я не пытаюсь реализовать обмен ключами Диффи-Хеллмана в Javascript для проекта. Это просто язык, с которым мне удобнее всего, но я боюсь, что это может быть ограничением javascript.


javascript diffie-hellman public-key-encryption
person Inkh Su Tesou    schedule 10.07.2014    source источник
comment
Вы пытаетесь выполнить крупномасштабную целочисленную математику на языке, который хранит все числа как числа с плавающей запятой. Вам понадобятся настоящие целочисленные типы.   -  person Paul Roub    schedule 10.07.2014
comment
(3^54) mod 17 = 15 поэтому Javascript может быть здесь неправильным выбором (я также получаю 7 в Chrome)   -  person devnull69    schedule 10.07.2014

Ответы (2)


arrow_upward
3
arrow_downward

3^54 равно 58149737003040059690390169. Это вызывает переполнение, поэтому вам следует реализовать модульное возведение в степень, так как i не слишком хорошо знаю javascript, я написал код c, который легко реализовать в javascript:

int power(int a, int b, int prime){
      int result;
      if(b == 0){
           result = 1;
      }else if(b == 1){
           result = a % prime;
      }else if(b % 2 == 0){
           result = power((a*a) % prime, b/2, prime);
           result = result % prime;
      }else{
           result = power((a*a) % prime, b/2, prime);
           result = (result * a) % prime;
      }
  return result;
  }

Теперь вы можете вызвать эту функцию:

int value = power(3, 54, 17);

и это должно работать.

Изменить: добавлена ​​версия javascript

function power(a, b, prime) {
    if (b <= 0) {
        return 1;
    } else if (b === 1) {
        return a % prime;
    } else if (b % 2 === 0) {
        return power((a * a) % prime, b / 2 | 0, prime) % prime;
    } else {
        return (power((a * a) % prime, b / 2 | 0, prime) * a) % prime;
    }
}
person uSeemSurprised    schedule 16.07.2014
comment
Я попытался использовать эту функцию для своего собственного модульного возведения в степень, но не получил ожидаемого результата. Я нашел другую реализацию здесь, которая мне подошла. - person darksinge; 08.07.2017
comment
@darksinge, вы можете проверить, я изменил функцию, теперь она должна работать. - person uSeemSurprised; 08.07.2017

arrow_upward
4
arrow_downward

Проблема заключается в ограниченной точности чисел Javascript, которая вызывает ошибки округления в вашем коде, где вы сначала возводите в степень, а затем вычисляете модуль. Для ваших примеров вы можете исправить это, периодически вычисляя модуль внутри возведения в степень, например. никогда не вычисляя больше, чем квадрат, прежде чем брать модуль. Но для реальной криптографии ваши вычисления будут включать числа, слишком большие, чтобы их можно было обрабатывать как числа Javascript (и большинство языков программирования создают ту же проблему). Обычный подход заключается в использовании библиотеки больших целых чисел (или даже произвольной точности). Если вы в конечном итоге реализуете свою собственную криптографию, следите за сторонними каналами, например. вызывая библиотечные функции, которые не имеют постоянного времени или допускают атаки на основе кеша, используя индексы массива, зависящие от данных.

person pyramids    schedule 10.07.2014