Я воспроизвел недопустимую точечную атаку на ECC, используя короткие кривые Вейерштрасса. Для этого я написал «глупую» реализацию, которая не проверяет, находятся ли точки на кривой, прежде чем перейти к скалярному умножению. Для плана атаки я в значительной степени заимствовал превосходное описание Самуэля Невеса, которое он дал здесь: Понимание Twist Security относительно коротких кривых Вейерштрасса
Я могу воспроизвести это без каких-либо проблем, когда $д = -1$ является квадратичным невычетом в $\mathbb{F}_p$, то все работает "из коробки". Однако, когда $р$ так что $-1$ является квадратичным вычетом, и поэтому мне нужно выбрать другое значение для $д$, все разваливается.
Для простоты в первом запуске я не использую кривые в $\mathbb{F}_{p^2}$ потому что для малого $р$ исчерпывающее перечисление для нахождения младших точек не является проблемой.
В качестве примера, скажем, моя кривая определена $\mathbb{F}_{101}$; здесь, $-1$ является квадратичным модом остатка $р$, поскольку $10 \cdot 10 = -1 \mod 101$. Моя кривая дается
$Е: у^2 = х^3 + 13х + 29$
И с $д = 2$, квадратичный невычет по модулю 101,
$E^d: у^2 = х^3 + 52х + 30$
Получатель чего-то $E^d$ является 111$ = 3\cdot 37$. Я выбрал две точки на $E^d$ которые имеют заказы 3 и 37 соответственно:
$P_1 = (28, 62)$
$P_2 = (8, 7)$
Когда я запускаю эти значения через скалярное умножение без проверки точки (для закрытого ключа $ д = 58 $, я получаю следующий вывод:
$S_1 = (94, 53)$
$S_2 = (32, 14)$
Ни один $S_1$ ни $S_2$ является точкой на квадратичном повороте $E^d$. Я могу поднять любую координату X в $E^d$, но тогда порядок точек неправильный.
Вот мой пример кода:
Fp = GF(101)
Д = Fp(2)
print(D, "является квадратным?", D.is_square())
(а, б) = (13, 29)
E = Эллиптическая кривая (Fp, [a, b])
Et = EllipticCurve(Fp, [a*D^2, b*D^3])
print("Et.order()", фактор(Et.order())))
очки атаки = [
Et(28, 62),
Ет(8, 7),
]
печать (Е)
печать(и)
для P в Attack_points:
печать (P, P.order())
# закрытый ключ d = 58
mul_results = [
Et(94, 53),
Ет(32, 14),
]
#print(Et.lift_x(94).order())
#print(Et.lift_x(32).order())
Что выводит:
2 квадрат? ЛОЖЬ
Эт.заказ() 3 * 37
Эллиптическая кривая, определяемая y^2 = x^3 + 13*x + 29 над конечным полем размером 101
Эллиптическая кривая, определяемая y ^ 2 = x ^ 3 + 52 * x + 30 над конечным полем размером 101
(28 : 62 : 1) 3
(8 : 7 : 1) 37
Ошибка типа: координаты [94, 53, 1] не определяют точку на эллиптической кривой, определяемую y^2 = x^3 + 52*x + 30 над конечным полем размером 101
Как я могу выполнить эту атаку для квадратичного поворота, где $d \neq -1$?
