I2P: Прискорення асиметричної криптографії з допомогою таблиць

Асиметрична криптографія в I2P завжди призводила до уповільнення роботи: алгоритм Діффі-Хельмана при встановленні транспортних сесій і, на мій погляд, невдалий вибір схеми Ель-Гамаля I2P адреси. Це особливо помітно при роботі на слабкому залозі і floodfill-ах. Запропонований у статті підхід заснований на використанні деяких особливостей I2P і дозволяє добитися істотного прискорення роботи і зниження навантаження на процесор.



Асиметричне шифрування в I2P

В даний час асиметричне шифрування ґрунтується на операції зведення в ступінь по модулю і гіпотези про практичну неможливість дискретного логарифмування, Існують плани використання інших видів асиметричного шифрування, але поки вони не реалізовані.
Публічний ключ y обчислюється на основі таємного ключа x за формулою y=g^x mod p, де p — просте, при цьому в загальному випадку в якості ключа передається трійка чисел (y, p, g). У I2P ж числа p та g є константами і повинні бути однакові для всіх реалізацій:
g = 2,
p = 2^2048 — 2^1984 — 1 + 2^64 * ([pi*2^1918] + 124476),
де pi позначає число пі, а [] — операцію взяття цілої частини числа.
Довжина p — 256 байт, відповідно і довжина публічного ключа.

Згідно офіційній документації довжина секретного ключа становить 2048 біт для x64 і 226 біт для всіх інших.

Обчислювані таблиці

Використання обчислюваних таблиць раніше було розглянуто підпису EdDSA.
Нагадаємо коротко суть. Над точками кривої визначена операція додавання і потрібно, користуючись цією операцією, помножити постійну базову точку на 32-х байтне число. Для цього будемо складати побайтно, беручи результат множення точки на значення кожного байта з таблиці, розраховується один раз при старті. Тим самим буде потрібно рівно 32 додавання, при цьому час обчислення стає постійним, що вкрай важливо для множення на секретний ключ.

Аналогічним чином поступимо і для операції зведення g до степеня за модулем p, тільки замість операції додавання буде використана операція множення.
Розрахуємо таблицю всіляких значень ступенів p для кожного байта, заповнюючи для кожного байта масив з 255 елементів, по порядку множачи g=2.
Можна помітити, що перші елементи таблиці зберігати необов'язково, оскільки вони виходять установкою біта у відповідній позиції, однак значення не повинно перевищувати p, фактично це відповідає 2048 = 11 біт, то є лише один і третина байта таблиці.

Таким чином, для закритого ключа довжиною 226 біт розмір таблиці складає 29*255*255 ~ 2 мегабайти, для ключа довжиною 2048 розмір таблиці складе 256*255*255 ~ 16 мегабайт, що може становити значний обсяг, але і ефект у цьому випадку виходить більш значний.

Множення Монтгомері

Оскільки для кожного зведення в ступінь потрібно щонайменше 29 множень по модулю, то для прискорення роботи доцільно скористатися множенням Монтгомері.
Зміст його зводиться до заміни одного модуля на інший, більш зручний для обчислень модуль. Для практичних потреб вибирається ступінь двійки і тоді повільне поділ замінюється швидким побітовим зрушенням.
Недоліком є необхідність перетворення поданням до Монтгомері. Однак у нашому випадку це робиться єдиний раз в момент розрахунку таблиця і єдиним додатковим дією є перетворення результату.
Для практично завдань нам не потрібно реалізовувати множення Монтгомері — відповідні функції представлені в OpenSSL.
int BN_MONT_CTX_set(BN_MONT_CTX *mont, const BIGNUM *m, BN_CTX *ctx);

задає модуль (в нашому випадку p)
int BN_mod_mul_montgomery(BIGNUM *r, BIGNUM *a, BIGNUM *b, BN_MONT_CTX *mont, BN_CTX *ctx);

власне множення Монтгомері в контексті з заданим модулем
int BN_from_montgomery(BIGNUM *r, BIGNUM *a, BN_MONT_CTX *mont, BN_CTX *ctx);

перетворення результату до нормального поданням.

Реалізація в i2pd

Починаючи з релізу 2.7.0 підтримується і управляється параметром precomputation.elgamal, за замовчуванням вимкнено для x64 і включений для інших. Рекомендується включати його для роботи в режимі floodfill-а якщо немає жорстких обмежень щодо використання пам'яті. Навантаження на процесор в цьому випадку знижується більш ніж в 2 рази з-за необхідності частої встановлення з'єднань з іншими вузлами.
Використовується при генерацій пар ключів при встановленні з'єднань, асиметричне шифрування при побудов тунелів і «часниковому» шифруванні між адресами. Аналогічно можна прискорити підпис DSA, проте в I2P вона вважається застарілою і поступово замінюється на EdDSA.
Розглянутий у статті підхід може здатися тривіальним, але його реалізацію показала свою ефективність, даючи можливість працювати на тих платформах, на яких раніше не вистачало продуктивності.
Джерело: Хабрахабр

0 коментарів

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