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.
Рассмотренный в статье подход может показаться тривиальным, однако его реализацию показала свою эффективность, давая возможность работать на тех платформах, на которых ранее не хватало производительности.
