Головна

Основні операції криптографічних перетворень в метриці еліптичних кривих

  1. Amp; 10. Основні напрямки сучасної філософія історії
  2. I Основні інформаційні процеси і їх реалізація за допомогою комп'ютерів
  3. I. Основні і допоміжні процеси
  4. II. 6.4. Основні види діяльності та їх розвиток у людини
  5. II. Основні завдання та їх реалізація
  6. III. Основні етапи міжнародних відносин в Новий час.
  7. III.2.1) Поняття злочину, його основні характеристики.

На першому кроці алгоритмічних процесів проводиться вибір генераторної точки 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 проводиться перевірка на достовірність факту її приналежності заданої еліптичної кривої. Це умова необхідна для побудови операцій шифрування-дешифрування і аутентифікації відкритих повідомлень, тому що в іншому випадку функціонування системи виключається.



Попередня   5   6   7   8   9   10   11   12   13   14   15   16   17   18   19   20   Наступна

В. В. Сюзев | В. Ф. Макаров | Вступ | Основні напрямки криптології. | Методи криптографічних перетворень з відкритим ключем. | Обчислення зворотних величин в модулярной алгебри. | Алгоритм операції зведення числа в ступінь по модулю. | Визначення односторонньої функції. | Алгоритм криптографічного системи RSA (Райвест-Шамір-Адлеман). | Алгоритм криптографічного системи на основі обчислення дискретних логарифмів в кінцевому полі - алгоритм Ель Гамаля. |

© 2016-2022  um.co.ua - учбові матеріали та реферати