Javascript алгоритм умножения эллиптических точек - PullRequest
Новая
       39

Javascript алгоритм умножения эллиптических точек

0 голосов
/ 01 декабря 2018

Ниже приведена реализация эллиптической кривой Умножение точек , но она работает не так, как ожидалось (используя последние Chrome / Node с 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)
}

Учитывая известная кривая со свойствами, вышеупомянутое успешно для точек 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

Известная кривая имеет значения: 

P   X    Y
—————————— 
1   5    1
2   6    3
3  10    6
4   3    1
5   9   16
6  16   13
7   0    6
8  13    7
9   7    6
10  7   11

Я не уверен, что неправильно понял алгоритм или допустил ошибку в реализации.

1 Ответ

0 голосов
/ 01 декабря 2018

Я не очень хорошо знаю javascript, поэтому код меня смущает.Но ...

В функции pointAdd, и везде, "деление" должно быть сделано мод р.Вы, очевидно, делаете это правильно в pointDouble, но не в pointAdd.В pointAdd используйте тот же шаблон: вместо 

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

do 

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

, хотя я думаю, что было бы намного яснее и менее подвержено ошибкам просто иметь модульную обратную функциювместо вычисления X p-2 везде, где это необходимо.

...