умножение точек эллиптической кривой иногда дает неверные результаты - PullRequest
Новая
       41

умножение точек эллиптической кривой иногда дает неверные результаты

1 голос
/ 28 апреля 2019

Я пытаюсь реализовать точку эллиптической кривой со скалярным умножением в Python, и у меня возникает проблема, заключающаяся в том, что в некоторых случаях я получаю неправильные результаты и пытаюсь выяснить, что может быть не так.

Вот функция, выполняющаявычисление: 

def __mul__(self, other):
    """
    Scalar multiplication of a point with a integer
    The point gets added to itself other times
    This can be efficiently computed using binary
    representation of the scalar

    :param other: int number to multiply the point with
    :return: Point point after applying the multiplication
    """
    if other < 1 or other > self.order():
        raise Exception("Scalar for point mult is out of range")

    # Convert into binary representation
    scalar_bin = str(bin(other))[2:]

    new_point = self.curve().g()
    # Iterate through every bit of the scalar
    # double the current point and if it is a 1 bit
    # we add the generator point
    for i in range(1, len(scalar_bin)):
        new_point = new_point + new_point
        if scalar_bin[i] == "1":
            new_point = new_point + self.curve().g()
    return new_point

Я проверил это для множественных значений и иногда получаю правильные, а иногда и неправильные результаты.Вот несколько примеров на кривой secp256k1: 

Correct case:

Point: 
x: 55066263022277343669578718895168534326250603453777594175500187360389116729240
y: 32670510020758816978083085130507043184471273380659243275938904335757337482424

Scalar:
24917563387128992525586541072555299775466638713533702470001729610242625242518

Result:
x: 30761640594611050927920473896980176618852175787129035469672454552631110981601
y: 71589730992642335000963807008595655528549796860255114743222783656832671116115

Incorrect case:

Point:
x: 55763821349469695143251444157857527262741225298806100934200365505846997750729
y: 108311437762381308673474438597429390041179265557837286648496266777408263200496

Scalar:
14153923515125836933174734651094672686604752309351060890449588899992278900437

Result:
x: 33276244942913720410563273329803338573012270278748134958920446992664092974057
y: 38066195899997010281080208319525128360573241938488491930954474962286948555539

1 Ответ

0 голосов
/ 28 апреля 2019

Итак, я разобрался с проблемой, и ее трудно увидеть, поскольку математика кажется правильной, но вместо этого я допустил программную ошибку, которую не так легко увидеть, если вы посмотрите на функцию вне контекста.

Представленный код будет делать скалярное умножение точки генератора кривой все время, но не точки, на которую собственно ссылается self. Self является экземпляром точки, но в приведенном коде никогда не указывается прямая ссылка, вместо этого умножается точка генератора кривой. 

new_point = self.curve().g()

следует заменить на 

new_point = self

и 

new_point = new_point + self.curve().g()

по 

new_point = new_point + self

Мне все еще неясно, как этот код мог привести к правильным примерам в некоторых случаях.

...