4.2.1 Еліптичні криві над простим полем

Еліптична крива Е у кінцевому полі E (GF (P)) за модулем Р (еліптична крива у формі Вейерштрасса) визначається співвідношенням:

,

де:

у та х – точки на еліптичній кривій;

а та b – параметри еліптичної кривої, які обираються над полем Р;

P – просте число.

а і b мають задовольняти таким умовам:

і Р>3.

4.2.2 Правила додавання, подвоєння і скалярного множення для еліптичних кривих над простим полем

Правило додавання двох різних і не взаємно зворотних точок, які належать кривій:

точки мають задовольняти умові:

Правило подвоєння однієї точки, яка належить кривій:

точка має задовольняти умові:

Скалярне множення:

Еквівалентна операція приведення у міру в групах точок еліптичної кривої, є операція скалярного множення.

де:

d – секретний ключ (еквівалентний х або К_c);

G – базова точка на еліптичній кривій з координатами, яка породжує групу точок порядку n.

Базова точка має властивість: .

За допомогою описаних вище правил можна обчислити точку kP для будь-якого цілого числа k і будь-якої точки Р еліптичної кривої. Однак зворотне розв’язання задачі – знаходження числа k за відомими точками Р і kP – є важкою проблемою. Вирішення проблеми дискретного логарифма еліптичної кривої є значно складнішим, ніж проблема дискретного логарифмування, на якій базуються RSA та інші подібні асиметричні криптосистеми. Складність вирішення даної проблеми обумовлена ресурсоємкістю операцій додавання і дублювання точок, за допомогою яких обчислюється kP, звідки випливає можливість застосування більш коротких ключів.

4.2.3 Алгоритм асиметричного шифрування на базі еліптичних кривих eces

В алгоритмі ECES (Elliptic Curve Encryption Scheme) на першому етапі мають бути визначені параметри, які є загальною відкритою інформацією для всіх користувачів системи:

• кінцеве поле GF (p);

• еліптична крива E (GF (p));

• великий простий дільник кількості точок кривої n;

• точка G, координати якої мають порядок, що й число n.

Кожен користувач системи генерує пару ключів так:

• вибирає випадкове ціле число K_c, 1 <K_c<n - 1;

• обчислює точку K_o = K_c * G.

При цьому секретним ключем користувача є число K_c, відкритим ключем – точка K_o. Крім того, повідомлення M розбивається на блоки довжиною 2L - 16 біт, де L дорівнює найближчому великому цілому від log₂ p;

• вибирається випадкове ціле число k, 1 <k <n - 1;

• обчислюється точка (х₁, у₁) = k * G;

• обчислюється точка (х₂, у₂) = k * Ko.

Відомо декілька підходів до за шифрування/розшифрування інформації, що передбачають використання еліптичних кривих. Розглянемо найбільш простий з цих підходів:

1) зашифроване повідомлення пересилається у вигляді значення (х, у) для точки P_m. Тут точка P_m являтиме зашифрований текст і згодом буде розшифрована;

2) як параметр даної криптосистеми розглядається точка G і еліптична група Еp (а, b);

3) користувачі А і В обирають секретні ключі K_cА і K_cB, а також генерують відкриті ключі K_оA = K_cА * G і K_оB = K_cB * G відповідно;

4) щоб зашифрувати повідомлення P_m, користувач А вибирає випадкове позитивне ціле число k і обчислює криптограму С_m за допомогою відкритого ключа сторони В (K_оB), що складається з двох точок

С_m = {(kG), (P_m + k * K_оB)};

5) щоб розшифрувати цю криптограму, користувач В помножує першу точку (kG) на cвій секретний ключ K_cB і віднімає результат з другої точки:

(P_m + k*K_оB) - K_cB*(kG) = P_m + k(K_cB*G) - K_cB*(kG) = P_m.

Користувач А замаскував повідомлення P_m за допомогою додавання до нього маски k * K_оB. Однак слід зауважити, що ніхто не зможе прибрати маску k* K_оB, окрім користувача, який знає значення k і має особистий ключ K_cB. Супротивнику для відновлення повідомлення доведеться обчислити k за даними G і kG, що є важким завданням.