Я много почитал статей по эллиптическим кривым, и теперь хочу описать свои впечатления.
Самое сильное из моих впечатлений - это часики. Это понятная аналогия, проясняет сознание.
Возьмем к примеру окружность, часики с круглым циферблатом, уравнение окружности:
x^2+y^2 = 1
Примем за начало отсчета точку O = (0,1) . 12часов 00 минут.
К чему мы клоним, чтобы сразу стало понятно. Мы вводим группу вращения стрелок на циферблате. Время складывается: минуты в часы...
Стараемся думать про одну стрелку. за минуту стрелка отклонилась на (x1, y1). Эту точку можно выразить через синусы и косинусы единичного перемещения 360/60 = 6 градусов. Координаты единичного перемещения обозначим точкой G=(x1,y1)
Утверждаем что это у нас Группа точек на кривой, Группа в математическом смысле.
Свойство Группы:
1) Существование нейтрального элемента, такого что P+O = P, O = (0,1)
2) Существование обратного элемента для каждого члена группы, -P= (-x,y). Перевели стрелки назад. P+(-P)=O
Вводим операцию удвоения точки, с ней можно будет ввести операцию умножения на скаляр через удвоение и сложение.
3) 2P = ... осторожно можно споткнуться... = (cos(2ф), sin(2ф)) = (x^2-y^2, yx+xy)
4) Закон сложения точек (x1, y1)+(x2, y2) = (cos(a+b), sin(a+b)) = (x1x2-y1y2, y1x2+x1y2)
А теперь можно заставить часики ходить...
Алгоритм №1 умножения на скаляр Q = kP, k-раз по минуте.
Q:=O;
for i=.. downto 0 begin
Q := 2Q;
if (k_i !=0) Q:= Q+P;
end
Минуты считаются по модулю 60. Число 60 не является простым, его можно на множители раскладывать. Число Р назовем генератором группы, обозначим буквой G чтобы всех запутать.
Алгоритм №2 умножение лесенкой Монтгомери.
Q:=O; P=G;
for i=.. downto 0 begin
if (k_i !=0){
Q:= Q+P, P=2P;
} else {
P: =P+Q, Q=2Q;
}
end
return Q
Эти алгоритмы не зависят от того как выглядит операция удвоения и сложения. Алгоритмов умножения можно придумать великое множество: справа налево, слева направо, комбинированные, с окном, со сложением и вычитанием, с разложениями и окнами.
Оба алогоритма можно свести к одной или двум операциям: удвоение точки Q=2Q и Q=2Q+G
Или иными словами мы на каждом шаге алгоритма вычисляем либо удвоение Q_{2n} зная Q_{n}, или Q_{2n+1} зная Q_{n}, Q_{n+1} и Q_1
Я знаю сколько было времени на часах, когда я их запустил - это мой секрет, могу выразить его в минутах d (число минут). Могу рассказать всем, что если умножить Q = dG получится некоторая точка с координатами (Q.x, Q,y) - которая однозначно связана с моим секретом - это будет точка для проверки подписи. Я хочу подписать сообщение. Мне нужно представить сообщение в виде числа m. Тогда подписанное сообщение - это показание часиков R = (m*d)G. Которое можно проверить с использованием открытой точки: R = mQ.
Цифровая подпись, ее неподдельная сущность, держится на том, что никто не может вычислить обратное число d, зная R, m и Q. Или плохо старается.
Все известные алгоритмы нахождения обратного числа держаться на Алгоритм № 3 НОД наибольший общий делитель. На базе него можно получить алгоритм деления или нахождения обратного числа по отношению к операции умножения. Для изготовления понадобится число типа скаляр и операция над точками - уполовинивание. Уполовинивание связано с неопределенностью при операциях с нечетными числами, которую надо как-то разрешать на каждом шаге алгоритма.
...
И тут пришел Монтгомери со своими кривыми алгоритмами и решил все "упросить": проекция x в операции удвоения не зависит от координаты y!
2P = (2x^2-1, 2xy)
Это значит, что мы можем считать удвоение без использования второй координаты. После этого берем паузу и думаем, а как теперь считать сложение точек без использования y- координаты.
x = x_2 x_3 - y_2 y_3 =... надо выразить через X координаты точек P Q и G.
x = 2 x_2 x_3 - x_1
Утверждение такое:
x_{2n} = 2x_{n}^2 -1
x_{2n+1} = 2x_{n} x_{n+1} - x_1
Начальное состояние для вычисления умножения при n=0 (x_{n}, x_{n+1}) = (1, x1).
По сути венец творения Монтгомери - это утверждение, что операцию вычисления x координаты при сложении точек на эллиптической кривой, можно представить в общем виде, как
x_{m+n} = f(x_m, x_n, x_{m-n}) вот и думай теперь над своим алгоритмом.
Откуда взяты идеи с часами и Алгоритмы Монтгомери:
https://eprint.iacr.org/2017/293.pdf -- оттуда
Самое сильное из моих впечатлений - это часики. Это понятная аналогия, проясняет сознание.
Возьмем к примеру окружность, часики с круглым циферблатом, уравнение окружности:
x^2+y^2 = 1
Примем за начало отсчета точку O = (0,1) . 12часов 00 минут.
К чему мы клоним, чтобы сразу стало понятно. Мы вводим группу вращения стрелок на циферблате. Время складывается: минуты в часы...
Стараемся думать про одну стрелку. за минуту стрелка отклонилась на (x1, y1). Эту точку можно выразить через синусы и косинусы единичного перемещения 360/60 = 6 градусов. Координаты единичного перемещения обозначим точкой G=(x1,y1)
Утверждаем что это у нас Группа точек на кривой, Группа в математическом смысле.
Свойство Группы:
1) Существование нейтрального элемента, такого что P+O = P, O = (0,1)
2) Существование обратного элемента для каждого члена группы, -P= (-x,y). Перевели стрелки назад. P+(-P)=O
Вводим операцию удвоения точки, с ней можно будет ввести операцию умножения на скаляр через удвоение и сложение.
3) 2P = ... осторожно можно споткнуться... = (cos(2ф), sin(2ф)) = (x^2-y^2, yx+xy)
4) Закон сложения точек (x1, y1)+(x2, y2) = (cos(a+b), sin(a+b)) = (x1x2-y1y2, y1x2+x1y2)
А теперь можно заставить часики ходить...
Алгоритм №1 умножения на скаляр Q = kP, k-раз по минуте.
Q:=O;
for i=.. downto 0 begin
Q := 2Q;
if (k_i !=0) Q:= Q+P;
end
Минуты считаются по модулю 60. Число 60 не является простым, его можно на множители раскладывать. Число Р назовем генератором группы, обозначим буквой G чтобы всех запутать.
Алгоритм №2 умножение лесенкой Монтгомери.
Q:=O; P=G;
for i=.. downto 0 begin
if (k_i !=0){
Q:= Q+P, P=2P;
} else {
P: =P+Q, Q=2Q;
}
end
return Q
Эти алгоритмы не зависят от того как выглядит операция удвоения и сложения. Алгоритмов умножения можно придумать великое множество: справа налево, слева направо, комбинированные, с окном, со сложением и вычитанием, с разложениями и окнами.
Оба алогоритма можно свести к одной или двум операциям: удвоение точки Q=2Q и Q=2Q+G
Или иными словами мы на каждом шаге алгоритма вычисляем либо удвоение Q_{2n} зная Q_{n}, или Q_{2n+1} зная Q_{n}, Q_{n+1} и Q_1
Я знаю сколько было времени на часах, когда я их запустил - это мой секрет, могу выразить его в минутах d (число минут). Могу рассказать всем, что если умножить Q = dG получится некоторая точка с координатами (Q.x, Q,y) - которая однозначно связана с моим секретом - это будет точка для проверки подписи. Я хочу подписать сообщение. Мне нужно представить сообщение в виде числа m. Тогда подписанное сообщение - это показание часиков R = (m*d)G. Которое можно проверить с использованием открытой точки: R = mQ.
Цифровая подпись, ее неподдельная сущность, держится на том, что никто не может вычислить обратное число d, зная R, m и Q. Или плохо старается.
Все известные алгоритмы нахождения обратного числа держаться на Алгоритм № 3 НОД наибольший общий делитель. На базе него можно получить алгоритм деления или нахождения обратного числа по отношению к операции умножения. Для изготовления понадобится число типа скаляр и операция над точками - уполовинивание. Уполовинивание связано с неопределенностью при операциях с нечетными числами, которую надо как-то разрешать на каждом шаге алгоритма.
...
И тут пришел Монтгомери со своими кривыми алгоритмами и решил все "упросить": проекция x в операции удвоения не зависит от координаты y!
2P = (2x^2-1, 2xy)
Это значит, что мы можем считать удвоение без использования второй координаты. После этого берем паузу и думаем, а как теперь считать сложение точек без использования y- координаты.
x = x_2 x_3 - y_2 y_3 =... надо выразить через X координаты точек P Q и G.
x = 2 x_2 x_3 - x_1
Утверждение такое:
x_{2n} = 2x_{n}^2 -1
x_{2n+1} = 2x_{n} x_{n+1} - x_1
Начальное состояние для вычисления умножения при n=0 (x_{n}, x_{n+1}) = (1, x1).
По сути венец творения Монтгомери - это утверждение, что операцию вычисления x координаты при сложении точек на эллиптической кривой, можно представить в общем виде, как
x_{m+n} = f(x_m, x_n, x_{m-n}) вот и думай теперь над своим алгоритмом.
Откуда взяты идеи с часами и Алгоритмы Монтгомери:
https://eprint.iacr.org/2017/293.pdf -- оттуда
