Рейтинг:2

Crypto

Добавление точки ECC к координате Джейкоба — не коммутативно?

LeonMSH

13.12.2022, 04:58

У меня есть скрипт на Python, который добавляет точку ECC (вставка кода ниже), он просто выполняет P = Q1 + Q2 для координации Джейкоба. Однако, выполняя некоторые регрессионные тесты, я обнаружил, что если я поменяю позиции P1 и P2, я получу разные результаты, один из которых правильный. Ниже приведен пример простого использования точки G secp256k1 в качестве одной точки и 2*G в качестве второй точки для запуска теста.

Мои вопросы (Обновите комментарии после получения ответа от @fgrieu) 1). Добавление точки ECC на кривой - будет ли это коммутативным (должно быть)?

2). Я заметил, что для результатов координата x одинакова, а y/z отличается (они представляют одно и то же в аффинной координате).

3). Основываясь на предложениях, я обновляю скрипт, делая его завершенным.

def Point_Add (я, Q1, Q2):
    если (Q1.x==self.p): 
        возврат Q2
    если (Q2.x==self.p):
        возврат Q1
    Q1z2 = (Q1.z*Q1.z) % само.p
    Q2z2 = (Q2.z*Q2.z) % от себя.p

    U1 = (Q1.x*Q2z2) % от себя.p
    U2 = (Q2.x*Q1z2) % от себя.p

    S1 = (Q1.y*Q2z2*Q2.z) % от себя.p
    S2 = (Q2.y*Q1z2*Q1.z) % от себя.p
    если (U1 == U2): 
        if (S1!=S2): # противоположная пара, т.е. Q1 = -Q2
            вернуть self.Unit
        иначе: # Q1 = Q2
            вернуть self.Point_Double (Q1)

    H = (U2-U1) % соб.р   
    R = (S2-S1) % self.p
    H2 = (H*H) % от себя.p
    H3 = (H2*H) % собств.p

    x3 = (R*R-H3-2*U1*H2 ) % от себя.p
    y3 = (R*(U1*H2-x3)-S1*H3 ) % self.p
    z3 = (H*Q1.z*Q2.z) % self.p

вернуть JBPoint(я, x3, y3, z3)

Результат испытаний
Отладка 1: тест P=Q1+Q2:
Point.X(Джейкоб): 0xca90ef9b06d7eb51d650e9145e3083cbd8df8759168862036f97a358f089848
Point.Y(Джейкоб): 0x435afe76017b8d55d04ff8a98dd60b2ba7eb6f87f6b28182ca4493d7165dd127
Point.Z(Джейкоб): 0x9242fa9c0b9f23a3bfea6a0eb6dbcfcbc4853fe9a25ee948105dc66a2a9b5baa
Точка.X(аффинная): 0xf9308a019258c31049344f85f89d5229b531c845836f99b08601f113bce036f9
Point.Y(аффинный): 0x388f7b0f632de8140fe337e62a37f3566500a99934c2231b6cb9fd7584b8e672
Точка.X(аффинная): 112711660439710606056748659173929673102114977341539408544630613555209775888121
Точка.Y(аффинная): 25583027980570883691656905877401976406448868254816295069919888960541586679410
Отладка 2: тест P=Q2+Q1:
Point.X(Джейкоб): 0xca90ef9b06d7eb51d650e9145e3083cbd8df8759168862036f97a358f089848
Point.Y(Джейкоб): 0xbca50189fe8472aa2fb007567229f4d458149078094d7e7d35bb6c27e9a22b08
Point.Z(Джейкоб): 0x6dbd0563f460dc5c401595f1492430343b7ac0165da116b7efa23994d564a085
Точка.X(аффинная): 0xf9308a019258c31049344f85f89d5229b531c845836f99b08601f113bce036f9
Point.Y(аффинный): 0x388f7b0f632de8140fe337e62a37f3566500a99934c2231b6cb9fd7584b8e672
Точка.X(аффинная): 112711660439710606056748659173929673102114977341539408544630613555209775888121
Точка.Y(аффинная): 25583027980570883691656905877401976406448868254816295069919888960541586679410

127

1 + 0

эллиптические кривые

secp256k1

Рейтинг:4

Crypto

fgrieu

13.12.2022, 06:29

Сложение точек ECC является коммутативным.
Возникшая проблема заключается в том, что в якобианской системе координат точка, отличная от нейтральной, имеет несколько одинаково допустимых троек координат. $(х,у,г)$, все соответствует одному $(г^{-2}\,х,г^{-3}\,у)$ в декартовой системе координат. Равенство можно проверить как ${z_2}^2\,x_1-{z_1}^2\,x_2\bmod p=0$ и ${z_2}^3\,y_1-{z_1}^3\,y_2\bmod p=0$ (Если есть ярлык, помимо повторного использования $г^2$ вычислить $г^3$ предполагая, что точки находятся на кривой, я хочу ее изучить).
изначально показан код не рассматривал случай, когда Q1 и Q2 представляют одну и ту же точку (то есть удвоение точек). Далее, ничего не уточняло, как нейтраль представлена на входе и выходе. Теперь это исправлено.

Обновление, расширение на 3: есть несколько особых случаев для добавления точки $Q_1+Q_2$, которые требуют специального лечения:

когда $Q_1$ является нейтральным, результат $Q_2$;
когда $Q_2$ является нейтральным, результат $Q_1$;
когда $Q_1=Q_2$ (в рамках определения в 2) это удвоение очков;
когда $Q_1=-Q_2$, результат нейтрален.

Есть несколько способов справиться с этим. Если вас попросят изменить Первоначально показан код Python, я бы сначала добавил заметные оговорки о том, что код даже не пытается смягчить атаки по времени (что в любом случае практически невозможно сделать идеально в Python), поэтому его нельзя использовать, когда это проблема (часто включая вычисление подписи); то я бы, наверное:

определить, что что-либо с $г=0$ является нейтральным, и используйте его, чтобы обработать первые два случая очевидным образом, а четвертый — без дополнительного кода.
обнаружить, что $Ч=0$ и $R=0$, что говорит о том, что мы делаем удвоение точек и, следовательно, нам нужны другие формулы.

Показанный сейчас код использует другой (я думаю, допустимый) метод, где $(р,0,1)$ является нейтральным. Это тоже работает, с (вероятно, едва измеримым) недостатком производительности и размера кода:

нужен явный код для $Q_1=-Q_2$ ненейтральный случай, когда он не для нейтрального определяется как $(р,0,1)$. При законном практическом использовании в криптографии этот особый случай настолько редок, что его удаление повышает производительность.
два начальных теста для нейтрали немного больше и медленнее.

Опять же, следует добавить комментарии о том, что код не предпринимает никаких усилий, чтобы избежать зависимостей времени, зависящих от данных, которые могут представлять собой побочный канал.

0 + 8

LeonMSH

13.12.2022, 08:10

Большое спасибо за быстрый ответ... Q2). Означает ли это, что оба полученных мной результата действительны (представляют одну и ту же точку в декартовой координате)? Есть ли какое-то дополнительное ограничение, которое я могу установить, чтобы я мог получить ту же уникальную координату Джейкоба, я могу преобразовать обратно, чтобы проверить декартову координату для этого, но поскольку у меня есть контрольный тест, который нужно выполнить позже, чтобы убедиться, что координата Джейкоба работает идеально, без уникального значения это очень неудобно). 3)Да найдёте, я ещё не ставил проверку спец.кейса, что надо добавить;

Ответить

LeonMSH

13.12.2022, 08:23

Да, я делаю проверку аффинных координат, на самом деле точки результата совпадают. Мой левый вопрос: есть ли какой-нибудь способ (или сложный), чтобы я всегда мог получить одну и ту же координату Джейкоба (мне все равно, охват, просто важна правильность.

Ответить

fgrieu

13.12.2022, 08:48

@LeonMSH: единственный способ, которым я вижу «всегда получать одну и ту же координату Джейкоба [ian]», - это нормализовать до одного и того же $z$, например $z=1$, то есть заменить $(x,y,z)$ результата на $(z^{-2}\,x,z^{-3}\,y,1)$. Но это сводит на нет смысл использования координат Якоби в первую очередь, который состоит в том, чтобы избежать модулярной инверсии.

Ответить

111

13.12.2022, 11:09

Возможно, если использовать только аффинные координаты. Имея аффинные координаты, скажем, $(a,b)$, чтобы получить проективные координаты этой точки, просто отправьте их в $[a:b:1].$ Для бесконечно удаленной точки требуется особая осторожность. Если вы добавляете точки $(a_1,b_1)$ и $(a_2,b_2)$, вы должны проверить, $b_1=b_2.$ Сложение этих точек равно бесконечно удаленной точке $[0:1:0]$ (с использованием модели Вейерштрасса). Надеюсь, это поможет.

Ответить

LeonMSH

16.12.2022, 02:36

@111, для аффинной точки P1(a1,b1) и P2(a2,b2), если b1=b2, P1+P2 должна быть двойной точкой? Я думаю, вы имеете в виду случай b1 = -b2?

Ответить

LeonMSH

16.12.2022, 02:48

@fgrieu с точки зрения точки бесконечности O координата Якоби - я вижу разные представления, например O= (p, 0, 1), (0, 1, 0), (1, 1, 0) , тогда как правильно?

Ответить

111

16.12.2022, 14:43

@LeonMSH верно. b1=-b2.

Ответить

LeonMSH

17.12.2022, 04:44

@fgrieu Я обновляю скрипт, кстати, единица измерения, которую я использую для этого кода, равна O (p, 0,1), но не точка с z = 0 .. Это все равно работает. вот почему я задаю вопрос относительно точки О, для точки Джейкоба..

Ответить

Admin

Этот вопрос на других языках:

EN: ECC Point Addition on Jacob coordinate -- Not Commutative?

TH: การเพิ่มจุด ECC บนพิกัด Jacob -- ไม่สับเปลี่ยน?

RO: Adăugarea punctului ECC pe coordonatele Jacob -- Nu este comutativă?

RU: Добавление точки ECC к координате Джейкоба — не коммутативно?

VI: Bổ sung điểm ECC trên tọa độ Jacob - Không giao hoán?

Ответить или комментировать

Большинство людей не понимают, что склонность к познанию нового открывает путь к обучению и улучшает межличностные связи. В исследованиях Элисон, например, хотя люди могли точно вспомнить, сколько вопросов было задано в их разговорах, они не чувствовали интуитивно связи между вопросами и симпатиями. В четырех исследованиях, в которых участники сами участвовали в разговорах или читали стенограммы чужих разговоров, люди, как правило, не осознавали, что задаваемый вопрос повлияет — или повлиял — на уровень дружбы между собеседниками.