Математическое обеспечение и администрирование информационных систем
Математика эллиптической кривой и конечных полей
жүктеу/скачать 0,92 Mb. Pdf көрінісі
|
- Бұл бет үшін навигация:
- Графики эллиптических кривых
- Сложение точек на эллиптической кривой
| 1.3. Математика эллиптической кривой и конечных полей
Эллиптической кривой E называют множество пар точек (x, y), удовлетворяющих уравнению (1.1): 𝑦 2
1 𝑥𝑦 + 𝑎
3 𝑦 = 𝑥
3 + 𝑎
2 𝑥 2 + 𝑎 4 𝑥 + 𝑎 6
(1.1) Варианты графиков эллиптических кривых приведены на рисунке 1.1.
Рис. 1.1 – Графики эллиптических кривых В большинстве случаев в криптографии основанных на эллиптических кривых рассматриваются 2 вида кривых над конечными полями: 1. простыми полями нечётной характеристики (Zp, где p > 3 и является простым числом) 2.
полями характеристики 2 (GF(2 m )).
В полях характеристики 2 обычно рассматриваются два вида эллиптических кривых (1.2) и (1.3): 1. Суперсингулярная кривая 𝑦 2 + 𝑎𝑦 = 𝑥 3 + 𝑏𝑥 + 𝑐 (1.2) 2.
Несуперсингулярная кривая 𝑦 2 + 𝑎𝑥𝑦 = 𝑥 3 + 𝑏𝑥 2 + 𝑐
(1.3) Но далеко не все эллиптические кривые подходят для реализации в эллиптической криптографии.
15
Согласно ГОСТ 24.10-2012, эллиптическая кривая E(Fp) над конечным простым полем Fp, где p – является порядком поля, которое должно быть больше 3, может быть отображена с помощью модифицированного уравнения, также называемым «каноническим», в форме Вейерштрасса, которая вычисляется по формуле (1.4): 𝑦 2
3 + 𝑎𝑥 + 𝑏 (𝑚𝑜𝑑 𝑝) (1.4) где a и b принадлежат полю Fp и дискриминант 4𝑎 3 + 27𝑏 2 не должен равняться 0 по модулю p. Если это неравенство не может быть выполнено, то кривые считаются сингулярными. В математике сингулярностью обозначается такая точка, в которой предложенная функция имеет странное поведение, например, стремится к бесконечности. Ученые считают, что использование сингулярных кривых в алгоритмах криптографии приводят к уменьшению криптостойкости алгоритма. Поэтому использование таких кривых запрещено. Все арифметические вычисления в эллиптической криптографии проходят не над выбранной кривой, а только над точками, которые принадлежат этой кривой, которые в свою очередь образуют определенную группу. Над точками кривой могут быть выполнены следующие три основные операции: 1. сложение двух разных точек 2. удвоение точки 3. умножение точки на число Основной операцией является операция сложения, так как именно на ней основываются все дальнейшие операции. 1.3.1. Сложение точек на эллиптической кривой Сложение двух точек эллиптической кривой заключается в том, что если взять две точки P и Q, которые лежат на данной кривой, и провести через них прямую, то эллиптическая кривая будет иметь пересечение этой прямой в 16
третьей точке. Так как эллиптическая кривая будет симметричной относительно оси Х, то мы можем зеркально отразить эту точку относительно оси X, получив новую точку P+Q принадлежащую данной кривой (Рис. 1.2).
Рис. 1.2 – Сложение точек на эллиптической кривой Пусть дана кривая 𝑦 2 = 𝑥 3 + 𝑎𝑥 + 𝑏 (1.5) над полем k ( 𝑘 ≠ 2 и 𝑘 ≠ 3), и точки P=(𝑥 𝑝 , 𝑦 𝑝 ) и Q=( 𝑥 𝑞 , 𝑥 𝑞 ) принадлежащие кривой (1.5) Предположим, что 𝑥 𝑝
𝑞 . Пусть формула нахождения углового коэффициент секущей 𝑆 =
𝑦 𝑝 −𝑦 𝑞 𝑥 𝑝 −𝑥 𝑞 (𝑚𝑜𝑑 𝑘) (1.6) так как k — поле, то s строго определено. Тогда мы можем определить 𝑅 = 𝑃 + 𝑄 = (𝑥 𝑟 , 𝑦
𝑟 ) следующим образом: 𝑥 𝑟
2 − 𝑥
𝑝 − 𝑥
𝑞 (𝑚𝑜𝑑 𝑘) (1.7)
17
𝑦 𝑟 = 𝑠(𝑥
𝑃 − 𝑥
𝑅 ) − 𝑦
𝑝 (𝑚𝑜𝑑 𝑘) (1.8) Формулы сложения (1.7) и (1.8) показывают, что координаты суммы двух точек выражаются через координаты слагаемых рационально, следовательно, если координаты выбранных точек принадлежат выбранному полю, то и сумма этих точек принадлежит этому же полю. [8] 1.3.2. Удвоение точек на эллиптической кривой Удвоение точки эллиптической кривой происходит немного по-другому, нежели сложение двух точек. Основное отличие заключается в нахождении углового коэффициент секущей, проведенной через точку. Он высчитывается по формуле (1.9) 𝑆 = 3𝑥
+𝑎 2𝑦 𝑝 (𝑚𝑜𝑑 𝑘) (1.9)
Вычисление же координат остается неизменным, они вычисляются по формулам (1.7) и (1.8). 1.3.3. Оценка числа элементов группы точек эллиптической кривой Данные свойства позволяет говорить о конечной группе точек в котором можно строить криптографические алгоритмы. Для выбранной эллиптической кривой количество точек в группе конечно. Данное количество точек в группе эллиптической кривой m можно определить по формуле (1.10): 𝑝 + 1 − 2√𝑝 ≤ 𝑚 ≤ 𝑝 + 1 + 2√𝑝 (1.10)
где р – порядок поля, над которым определена кривая. |