Асимметричное шифрование в 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.
Рассмотренный в статье подход может показаться тривиальным, однако его реализацию показала свою эффективность, давая возможность работать на тех платформах, на которых ранее не хватало производительности.
Комментарии (3)
orignal
25.05.2016 13:53+1>могу сказать что оптимизация низкоуровневых функций (сложение, умножение, деление, модуль и тп) даёт как правильно не очень большую прибавку к скорости
Здесь не оптимизация низкоуровневых функций, а использование того факта что p — одно и то же.
>Те у меня сильные подозрения что как минимум некоторые из тех методов можно адаптировать и для возведения в степень.
Вероятнее всего да. Здесь описан лишь первый шаг для ускорения работы.
>Использование таблиц — означает что код становится уязвим для тайминг атак
Как раз наоборот в этом случае время вычисления становится постоянным, в отличие от простого «double-and-add», время подписи в котором будет зависеть от числа единичных бит в ключе.
>«Длина p — 256 байт» — чего то много, наверное бит.
Именно байт — 2048 бит. Отсюда и все тормоза.
dmitryredkin
26.05.2016 00:17О, надо будет попробовать! А то пришлось выключить i2p на роутере (atom 1.6GHz), т.к. он давал постоянную нагрузку по 70% на каждом из 2 ядер. Все варианты повышения производительности были опробованы и улучшений не дали.
Ivan_83
По своему опыту оптимизации ECDSA/ГОСТ2012 чего то там, могу сказать что оптимизация низкоуровневых функций (сложение, умножение, деление, модуль и тп) даёт как правильно не очень большую прибавку к скорости, при том что оптимизация высокоуровневых алгоритмов (умножения точки на скаляр) даёт сразу очень весомую прибавку к скорости.
Есть замечательная книжка которую можно найти в pdf: Guide to Elliptic Curve Cryptography
Darrel Hankerson, Alfred Menezes, Scott Vanstone
Там подробно/доходчиво описаны методы ускорения умножения точки на скаляр.
Самый шустрый метод это комбинированный с двумя таблицами, притом таблицы раздувать не стоит, тк на больших таблицах скорость не растёт, те она довольно резко растёт до определённого значения и дальше при увеличении таблиц прост совсем незначительный.
Те у меня сильные подозрения что как минимум некоторые из тех методов можно адаптировать и для возведения в степень.
Использование таблиц — означает что код становится уязвим для тайминг атак, если не вводить мусорные вычисления и не химичить с перфетчем/кешем проца.
«Длина p — 256 байт» — чего то много, наверное бит.