I2P: Прозора реалізація підпису EdDSA

Останнім часом все більшу популярність набирає електронний підпис Ed25519, заснована на різновиди еліптичної кривої, запропонованої Берштейном. У міру збільшення числа вузлів I2P з даним видом підпису виникла необхідність її підтримки в своїй реалізації I2P, оскільки Ed25519 не входить до складу популярних криптографічних бібліотек. Як правило використовуються різновиди ref10 з бібліотеки SUPERCOP, реалізованої самим Берштейном на асемблері, і потім портувати на інші мови. Дана реалізація працює добре і швидко, однак у неї є головний недолік — вона незрозуміла. Дійсно, якщо заглянути у вихідний код, то можна побачити велику кількість однотипних рядків, оперують з множиною «магічних» чисел, зрозуміти ж, що вони означають, без заглиблення в теорію не представляється можливим. Метою даної статті є математично прозора реалізація Ed22519, використовуючи лише стандартні операції з великими числами, що присутні в будь криптографічного бібліотеці, зі швидкістю, достатньою для практичного використання в I2P.


Принцип роботи еліптичної криптографії

Задається неявне рівняння плоскої кривої спеціального виду, званого еліптичної кривої. Задається просте число, утворює поле відрахувань по модулю. Координати точок кривої належать цьому полю, тобто є цілими неотрицательными числами, що не перевищує модуль. Над двома точками кривої задається операція додавання таким чином, щоб нова точка належала кривої. Якщо точку скласти саму з собою то вийде множення на 2, якщо додати ще раз на 3, і так далі множення на довільне число n. Також разом з кривою задається базова точка, що належить кривій, операції над якою і використовуються у криптографії.
Для криптографії вибирається довільне велике число n, що є секретним ключем, на нього перемножується базова точка і нова точка служить публічним ключем, який потім множиться протилежною стороною на інше число з метою узгодження ключа або перевірки підпису. Стійкість ґрунтується відсутністю на даний момент відомого способу визначення множника по точці за розумний час

Ed25519

Берштейн запропонував використовувати еліптичну криву з наступними параметрами.
Рівняння кривої:
, де
Модуль:
q =
звідси і виникла назва кривої.

Базова точка:
(x, 4/5), де x виходить рішенням рівняння (див. нижче)
Її координати в явному вигляді:
x=15112221349535400772501151409588531511454012693041857206046113283949847762202,
y=46316835694926478169428394003475163141307993866256225615783033603165251855960.

Додавання:
, де

Слід зауважити, що поділ тут це не звичайне ділення з залишком, а множення на зворотний по модулю елемент, обчислюваний згідно малої теореми Ферма за формулою , тобто операція зведення в ступінь по модулю.

У якості публічного ключа пропонується використовувати тільки координату y, при необхідності вирішуючи рівняння кривої відносно х, і обчислюючи його за формулою .

Оскільки q представимо у вигляді 8*k+5, то для обчислення квадратного кореня з х слід скористатися формулою . Дійсно q = = , звідси квадратний корінь .

Реалізація

Код повністю розташовується за адресою у файлі Signature.cpp. Для роботи з великими числами використовуються функції бібліотеки BN з openssl.
Створимо клас Ed25519, що реалізує саму криву, і містить параметри кривої, що розраховуються в його конструкторі. В першу чергу необхідні 3 методи: додавання, множення на число і обчислення x по заданому y.
class Ed25519
{
//... 
EDDSAPoint Sum (const EDDSAPoint& p1, const EDDSAPoint& p2) const
EDDSAPoint Mul (const EDDSAPoint& p, const BIGNUM * e) const
BIGNUM * RecoverX (const BIGNUM * y) const
//...
}


Через приватного використання операція додавання і трудомісткості операції ділення, наведемо x і y до спільного знаменника (1+m)*(1-m), тим самим позбувшись від одного поділу. У результаті код для додавання виглядає приблизно так:
// m = d*p1.x*p2.x*p1.y*p2.y
BN_mul (xx, p1.x, p2.x, m_Ctx); //p1.x*p2.x
BN_mul (yy, p1.y, p2.y, m_Ctx); //p1.y*p2.y
BIGNUM * m = BN_dup (d);
BN_mul (m, m, xx, m_Ctx);
BN_mul (m, m, yy, m_Ctx);
// x = (p1.x*p2.y + p2.x*p1.y)*inv(1 + m)
// y = (p1.y*p2.y + p1.x*p2.x)*inv(1 - m)
// m1 = 1-m
BN_one (m1);
BN_sub (m1, m1, m);
// m = m+1
BN_add_word (m, 1); 
// y = (p1.y*p2.y + p1.x*p2.x)*m 
BN_add (y, xx, yy);
BN_mod_mul (y, y, m, q, m_Ctx);
// x = (p1.x*p2.y + p2.x*p1.y)*m1
BN_mul (yy, p1.x, p2.y, m_Ctx);
BN_mul (xx, p2.x, p1.y, m_Ctx);
BN_add (x, xx, yy);
// denominator m = m*m1 
BN_mod_mul (m, m, m1, q, m_Ctx);
Inv (m); 
BN_mod_mul (x, x, m, q, m_Ctx); // x = x/m
BN_mod_mul (y, y, m, q, m_Ctx); // y = y/m


Також для подвоєння (додавання точки самої з собою) реалізований окремий метод Double, оскільки в цьому випадку p1.x = p2.x і p1.y = p2.y, що дозволяє скоротити кількість множень. Крім того, замість BN_mul використовується більш швидка BN_sqr.
Множення релизовано найпростішим методом подвоєння і додавання, тобто йти вздовж числа побитово від старшого до молодшого, на кожному кроці подвоювати значення результату, а якщо біт — одиниця, то додавати умножаемую точку.
EDDSAPoint res {zero one};
if (!BN_is_zero (e))
{
int bitCount = BN_num_bits (e);
for (int i = bitCount - 1; i >= 0; i--)
{
res = Double (res);
if (BN_is_bit_set (e, i)) res = Sum (res, p);
}
} 

Обчислення x по y реалізовано тривіально.
Спочатку підкореневий вираз:
BN_sqr (y2, y, m_Ctx); // y^2
// xx = (y^2 -1)*inv(d*y^2 +1) 
BN_mul (xx, d, y2, m_Ctx);
BN_add_word (xx, 1);
Inv (xx);
BN_sub_word (y2, 1);
BN_mul (xx, y2, xx, m_Ctx);

Потім обчислення квадратного кореня за формулою
// x = srqt(xx) = xx^(2^252-2) 
BN_mod_exp (x, xx, two_252_2, q, m_Ctx);


Підпис і перевірка підпису

Дана тема досить цікава і різноманітна, тому цьому питанню буде присвячена окрема стаття. У той же час методи Sign і Verify реалізовані і використовуються практично. Тому, кому цікаво, можна глянути в код. Тут же будуть лише перераховані деякі особливості.
Як і інші системи електронного підпису, підпис EdDSA являє собою пару 32-х байтних чисел (R,S), бо довжина підпису — 64 байти.
Числа представлені в Little Endian.
В якості хеш-функції використовується SHA-512.
При підписи випадкове число не генерується, замість цього використовується права половина SHA-512 хеш-від секретного ключа, об'єднаний з самими підписуються даними.
Також використовується просте число , використовуване при виборі базової точки, з тим розрахунком, щоб множення на нього базової точки давало нуль.

Висновок

Очевидно, що самим повільним місцем даної реалізації є розподіл в операції додавання. Насправді, користуючись сучасними досягненнями теорії чисел і специфікою параметрів EdDSA, можна виключити його повністю, як це зроблено в ref10. Однак це суттєво ускладнить реалізацію і зробить її менш зрозумілою, бо цим слід займатися тільки якщо виникне реальна практична необхідність. В даний час перевірка підпису EdDSA в I2P досить рідкісна подія, порівняно, скажімо, з шифруванням за схемою Ель-Гамаля.
Існує думка, що реалізація власної криптографії це дуже погана ідея. Однак використання незрозуміло як працює реалізації представляється трохи краще. Крім того, дана стаття може бути корисна тим, кому цікаво докопатися до суті, а працює практичний код допоможе в цьому.

Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.