Головна |
На першому кроці алгоритмічних процесів проводиться вибір генераторної точки G в заданому просторі, а потім необхідно виконати операції подвоєння, почетвереній і т.д. координат генераторної точки, тобто отримати безліч точок: G; [2] G; [4] G; [8] G ... [2n] G.
На наступному кроці визначаються композиції різних точок еліптичної кривої, наприклад:
[3] G = G + [2] G; [5] G = G + [4] G;
[3] G = (x1; y1) + (X2; y2) [5] G = (x1; y1) + (X4; y4)
і так далі.
Ці операції над множинами точок заданої еліптичної кривої необхідні для обчислення будь-якої точки, що належить цієї кривої, тому що будь-який представник цієї множини може бути відображений як результат операцій подвоєння, почетвереній і т.д. значень генераторної точки G і результатів композицій одержуваних значень.
В криптографічних перетвореннях ці функціональні операції необхідні для обчислення відкритих ключів шифрування, вибору значень закритих (секретних) ключів дешифрування за умови випадковості такої вибірки, безпосереднього виконання операцій шифрування-дешифрування і аутентифікації відкритих повідомлень з використанням безлічі точок, що належать заданим еліптичних кривих.
При визначенні кількості точок, що належать заданій еліптичної кривої для виконання операцій обчислення ключів шифрування-дешифрування, формування криптограми і їх розшифровки, а також виконання операцій аутентифікації електронних повідомлень необхідно розглянути процеси обчислення операцій подвоєння генераторної точки G і далі одержуваних точок, а також операцій обчислення композицій різних точок еліптичної кривої. Спочатку розглянемо процес обчислення операцій подвоєння точок еліптичної кривої.
Нехай прийнята генераторная точка G на заданій еліптичної кривої Z: Y2 = (X3 + AX + b) mod P, для прикладу розглянемо еліптичну криву Z: Y2 = (X3 + 8X + 5) mod 293. Випадково задається значення генераторної точки, що належить цій кривій, наприклад, приймається значення хG = 18. Значення генераторної точки, що задається випадковим чином, має одну дуже важливу обмеження - необхідно і достатньо, щоб при заданому значенні абсциси генераторної точки (хG) Існувало ціле значення ординати (yG) Цієї точки, тобто умова існування целочисленного значення квадратного кореня, що витягується з заданого рівняння еліптичної кривої:
YG = = = .
Знайдено відразу дві точки еліптичної кривої G = (18; 11) і G = (18; -11) = (18; 282). Приймемо значення генераторної точки G = (18; 11).
Для визначення безлічі точок, що належать заданій еліптичної кривої обчислюється значення подвоєння генераторної точки G, наприклад: точка G2 > [2] G. Ця запис інтерпретується наступним чином - визначення значення точки G2 тягне за собою операцію подвоєння генераторної точки G. Для визначення координат точки G2 необхідно скористатися наступними співвідношеннями:
xn = k2 - xn-2 - xn-1 числове значення абсциси нової обчислюється точки;
yn = K (xn-1 - xn) - Yn-1 числове значення ординати нової обчислюється точки;
до - числове значення кутового коефіцієнта дотичної, проведеної в точці подвоєння (на першому кроці обчислень дотична проведена в генераторної точці).
Для обчислення кутового коефіцієнта дотичної необхідно продифференцировать обидві частини заданого рівняння еліптичної кривої ZР (А, в): Y2 = (X3 + AX + b) mod P
(Y2)' = (X3 + AX + b) '; 2YY '= 3X2 + A, звідки Y '= k = .
В окремому випадку k = , Тобто кутовий коефіцієнт дотичної визначається через параметр еліптичної кривої «а» і координати розглянутої точки - точки подвоєння. Так, наприклад для рівняння:
Z: Y2 = (X3 + 8X + 5) mod 293 кутовий коефіцієнт дотичної в генераторної точці (точці подвоєння) визначається як:
k = mod 293 = mod 293 = mod 293 =
= 980 * 22-1 mod 293.
Для обчислення значення 22-1 mod 293 скористаємося наступним співвідношенням за умови, що Р = 293 просте число, то відповідно до малої теореми Ферма «а-1 mod P = a ? (P) - 1 mod P », де« 22-1 mod 293 »- функція Ейлера, яка при Р - просте число визначається як:
? (Р) = Р-1.
Отже, «22-1 mod 293 = 22291 mod 293 ». Для виконання операції піднесення числа до степеня за модулем необхідно застосувати методику розділу 1.3. В результаті обчислень отримуємо «kG = 22291 mod 293 = 40 mod 293 > 40, 980 * 40 mod 293 = 39200 mod 293 = 231 mod 293 > 231 ».
Для визначення координат точки подвоєння генераторної точки необхідно виконати наступні обчислення за умови, що при подвоєнні генераторної точки еліптичної кривої числові значення абсцис точки подвоєння (xn-1; xn-2) Рівні між собою. отже,
x[2]G = K2 - 2xG; y[2]G = K * (xG - x[2]G) - YG
Координати точки подвоєння, що розглядається як приклад, визначаться як:
- При обраної генераторної точки G = (xG; yG) = (18, 11) і значенні кутового коефіцієнта дотичної kG = 231;
- Числове значення абсциси точки подвоєння
x[2]G = (KG2 - 2 xG) Mod 293 = (2312 - 2 * 18) mod 293 = 292 mod 293
292.
Y[2] G = K * (xG - x[2] G) - YG = 231 * (18 - 292) - 11 mod 293 =
= 276 mod 293 > 276.
Таким чином, результат подвоєння генераторної точки G = (18; 11) визначиться як [2] G = (x[2]G; Y[2]G) = (292; 276).
Наступною операцією при обчисленні безлічі точок, що належать заданій еліптичної кривої, є операція обчислення композицій на множинах. Для прикладу розглянемо обчислення точки [3] G як результат композиції точок G і [2] G; [3] G = G + [2] G.
Для визначення координат точки [3] G як результат композиції точок еліптичної кривої G і [2] G спочатку обчислюється значення кутового коефіцієнта прямої, що проходить через точки G і [2] G:
k = (y[2] G - yG) (x[2] G - xG) Mod P = (276 - 11) (292 - 18) mod 293 =
= 265 274 mod 293 = 265 * 274-1 mod 293 = 265 * 274? (p) - 1 mod 293 =
= 265 * 274291 mod 293 = 265 * 185 mod 293 = 49025 mod 293 = 94 mod 293 > 94.
Потім визначаються координати точки [3] G = (x[3]G; y[3]G):
x[3] G = k2 - xG - x[2] G
y[3] G = K * (xG - x[3] G) - YG
Для даної еліптичної кривої
Z: Y2 = (X3 + 8X + 5) mod 293 ці координати визначаться як:
x[3] G = k2 - xG - x[2] G = (942 - 18 - 292) mod 293 = 8526 mod 293 =
= 29 mod 293 > 29.
y[3] G = K * (xG - x[3] G) - YG = 94 (18 - 29) - 11 mod 293 =
= - 1045 mod 293 = - 852 mod 293 = - 559 mod 293 = -166 mod 293 =
= 127 mod 293 > 127.
Таким чином, результат обчислення композиції двох точок G і [2] G визначається як [3] G = (x[3]G; y[3]G) = (29; 127).
Після виконання операції обчислення безлічі точок додатково перевіряється умова їх приналежності обраної еліптичної кривої. Так наприклад, в розглянутій задачі при визначенні координат генераторної точки (розділ 3.3.1) процес підтвердження її приналежності до заданої еліптичної кривої виконується наступним чином:
1. Заданий рівняння еліптичної кривої визначається як:
ZP(A; b) = Z293(8; 5) = X3 + 8X + 5 mod 293.
2. При значеннях координат генераторної точки G = (18; 11), yG = 11;
xG = 18; a = 8; b = 5; P = 293 отримуємо:
yG2 = (XG 3 + axG + B) mod P;
112 = (183 + 8 * 18 + 5) mod 293;
121 mod 293 = (5832 + 144 + 5) mod 293;
121 mod 293 = 5981 mod 293;
121 mod 293 = 121 mod 293.
Отже, генераторна точка G належить заданій еліптичної кривої, тому що ліві і праві частини рівняння еліптичної кривої при заданих параметрах і обчислених значеннях координат (yG; xG) Рівні між собою.
Далі були визначені координати подвоєння генераторної точки [2] G = (x[2]G; y[2]G) = (292; 276) і координати композиції точок G і [2] G:
[3] G = G + [2] G = (x[3]G; y[3]G) = (29; 127).
Перевіряються умови приналежності точок [2] G і [3] G заданої еліптичної кривої.
Для точки [2] G = (292; 276):
2762 mod 293 = (2923 + 8 * 292 + 5) mod 293;
76176 mod 293 = (24897088 + 2336 +5) mod 293;
289 mod 293 = 24899429 mod 293;
289 mod 293 = 289 mod 293 - достовірно.
Для точки [3] G = (29; 127):
1272 mod 293 = (293 + 8 * 29 + 5) mod 293;
16129 mod 293 = (24389 + 232 + 5) mod 293;
14 mod 293 = 24626 mod 293;
14 mod 293 = 14 mod 293 - достовірно.
Результати перевірки достовірні, отже отримані точки G; [2] G; [3] G певної вибраної еліптичної кривої.
У практичній криптографії з використанням методів перетворень на еліптичних кривих для кожної отриманої точки [n] G проводиться перевірка на достовірність факту її приналежності заданої еліптичної кривої. Це умова необхідна для побудови операцій шифрування-дешифрування і аутентифікації відкритих повідомлень, тому що в іншому випадку функціонування системи виключається.
В. В. Сюзев | В. Ф. Макаров | Вступ | Основні напрямки криптології. | Методи криптографічних перетворень з відкритим ключем. | Обчислення зворотних величин в модулярной алгебри. | Алгоритм операції зведення числа в ступінь по модулю. | Визначення односторонньої функції. | Алгоритм криптографічного системи RSA (Райвест-Шамір-Адлеман). | Алгоритм криптографічного системи на основі обчислення дискретних логарифмів в кінцевому полі - алгоритм Ель Гамаля. |