javascript - Diffie-Hellman 实现不适用于更大的数字

Question

上下文

我在看这个视频DHE explained

它讲的是两个人如何在没有吸管的情况下交换 key 以了解更多信息。

根据视频实现

// INITIALIZERS (video's values)-------------------------

var prefx = 3
var modulo = 17

// SECRET NUMBERS ---------------------------------------

var alice_secret_number = 19 // replaced 54 since there is a precision loss with it.
var bob_secret_number = 24

// PUBLIC KEYS ------------------------------------------

var public_alice = Math.pow(prefx , alice_secret_number) 
var public_bob = Math.pow(prefx , bob_secret_number)

// Check potential overflow -----------------------------
console.log(public_alice , public_bob)

// Apply the modulo -------------------------------------
public_alice %= modulo
public_bob %= modulo

// Check the value again --------------------------------
console.log( public_alice , public_bob )

// Calculate the good number ------------------------------------------
var final_alice = Math.pow( public_bob , alice_secret_number ) % modulo
var final_bob = Math.pow( public_alice , bob_secret_number ) % modulo

console.log( final_alice , final_bob )

问题

这并不总是有效。首先，例如 javascript 会失去精度。所以你只能尝试小数字。演讲者谈论大模数。再小的也不行。我给了你代码，它不是针对性能而是针对可读性量身定制的。

有人可以给我他/她对我做错了什么的意见吗？

Answer 1

JavaScript 中的所有数字都是 float (实际上是 double )。对应的规范为IEEE 754 .要在不损失精度的情况下表示一个整数，它必须适合 mantissa对于 64 位 float 来说是 53 位大。您可以使用 Number.MAX_SAFE_INTEGER 检查最大整数，即 9007199254740991。超出此范围的所有内容都会失去精度。

为什么这是个问题？ (大部分)密码学必须是精确的，否则无法得知 secret 。您尝试做的是取幂然后应用模数，但由于您单独执行此操作，因此在通过模数运算减少之前，您会在取幂后得到一个非常大的数字。

解决方案是使用某种 BigNumber 库(如 BigInteger )来为您处理所有这些大数字。请注意，有一个 modPow(exp, mod) 函数可以结合这两个步骤并有效地计算结果。

请注意，用户 secret 应小于模数。