Javascript椭圆点乘算法

Question

以下是椭圆曲线的实现Point Multiplication，但它没有按预期工作（使用最近的 Chrome / Node with BigInt 进行说明）：

const bi0 = BigInt(0)
const bi1 = BigInt(1)
const bi2 = BigInt(2)
const bi3 = BigInt(3)

const absMod = (n, p) => n < bi0 ? (n % p) + p : n % p

export function pointAdd (xp, yp, xq, yq, p) {
  const lambda = (yq - yp) / (xq - xp)
  const x = absMod(lambda ** bi2 - xp - xq, p)
  const y = absMod(lambda * (xp - x) - yp, p)
  return { x, y }
}

export function pointDouble (xp, yp, a, p) {
  const numer = bi3 * xp ** bi2 + a
  const denom = (bi2 * yp) ** (p - bi2)
  const lambda = (numer * denom) % p
  const x = absMod(lambda ** bi2 - bi2 * xp, p)
  const y = absMod(lambda * (xp - x) - yp, p)
  return { x, y }
}

export function pointMultiply (d, xp, yp, a, p) {
  const add = (xp, yp, { x, y }) => pointAdd(xp, yp, x, y, p)
  const double = (x, y) => pointDouble(x, y, a, p)
  const recur = ({ x, y }, n) => {
    if (n === bi0) { return { x: bi0, y: bi0 } }
    if (n === bi1) { return { x, y } }
    if (n % bi2 === bi1) { return add(x, y, recur({ x, y }, n - bi1)) }
    return recur(double(x, y), n / bi2)
  }
  return recur({ x: xp, y: yp }, d)
}

给定一个 known curve 属性，上面的点 P2 - P5 成功，但从 P6 开始失败：

const p = BigInt('17')
const a = BigInt('2')
const p1 = { x: BigInt(5), y: BigInt(1) }

const d = BigInt(6)
const p6 = pointMultiply(d, p1.x, p1.y, a, p)
p6.x === BigInt(16) // incorrect value of 8 was returned
p6.y === BigInt(13) // incorrect value of 14 was returned

已知曲线的值为：

我不确定是我误解了算法还是我在实现中犯了错误。

Answer 1

我不太了解javascript，所以代码让我很困惑。但是...

在函数 pointAdd 和其他地方，"division" 必须完成 mod p。您显然在 pointDouble 中正确地做到了，但在 pointAdd 中却没有。在 pointAdd 中，使用相同的模式：而不是

const lambda = (yq - yp) / (xq - xp)

做

const numer = yq - yp
const denom = (xq - xp) ** (p - bi2)
const lambda = (numer * denom) % p

虽然我认为简单地使用 modular 反函数而不是在任何需要的地方计算 X^p-2 会更清晰并且更不容易出错.

Javascript椭圆点乘算法

Javascript elliptical point multiplication algorithm

javascript

elliptic-curve