Асимметричная криптография в I2P всегда приводила к замедлению: алгоритм Диффи-Хеллмана при установлении транспортных сессий и, на мой взгляд, неудачный выбор схемы Эль-Гамаля в адресах I2P. Особенно это заметно при работе на слабом железе и заливках.
Предложенный в статье подход основан на использовании некоторых возможностей I2P и позволяет добиться значительного ускорения и снизить нагрузку на процессор.
Асимметричное шифрование в I2P
В настоящее время асимметричное шифрование основано на операции возведения в степень и гипотезе о том, что дискретные логарифмы практически невозможны.Есть планы использовать и другие типы асимметричного шифрования, но они пока не реализованы.
Открытый ключ y рассчитывается на основе закрытого ключа x по формуле y=g^x mod p, где p — простое число, и в общем случае в качестве ключа передается тройка чисел (y, p, g).
.
В I2P числа p и g являются константами и должны быть одинаковыми для всех реализаций: г = 2, р = 2^2048 - 2^1984 - 1 + 2^64 * ([pi*2^1918] + 124476), где pi обозначает число 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.
указывает модуль (в нашем случае p)int BN_MONT_CTX_set(BN_MONT_CTX *mont, const BIGNUM *m, BN_CTX *ctx);
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 и включено для других.Рекомендуется включить работу в режиме заливки, если нет строгих ограничений на использование памяти.
При этом нагрузка на процессор снижается более чем в 2 раза из-за необходимости часто устанавливать соединения с другими узлами.
Он используется для генерации пар ключей при установлении соединений, асимметричного шифрования при построении туннелей и «чесночного» шифрования между адресами.
Аналогично можно ускорить подписание DSA, но в I2P оно считается устаревшим и постепенно заменяется EdDSA. Подход, обсуждаемый в статье, может показаться тривиальным, но его реализация показала свою эффективность, дав возможность работать на тех платформах, которым ранее не хватало производительности.
Теги: #i2p #i2pd #C++ #eddsa #Elgamal #Криптография #Криптография #i2p
-
Сервисы Статистики Для Мобильных Приложений
19 Oct, 24 -
Использование Checkstyle И Gerrit Вместе
19 Oct, 24 -
Безопасность Microsoft Office: Макросы Vba
19 Oct, 24
