Насколько опасна утечка $k$ в RSA?

В RSA используется небольшой публичный показатель $е$ такие как $65537$, насколько это плохо, если значение $к$ утечки? $к$ как в следующих уравнениях:

$ed - 1 = k \phi(n)$

или же

$ed - 1 = k \cdot \operatorname{lcm}(p-1,q-1)$

Интуитивно это уменьшит сложность взлома системы только на $65535$ раз, но далеко не так важно, хотя я предполагаю, что GNFS не улучшится, зная $к$.

РЕДАКТИРОВАТЬ: Это пришло к размышлению о том, что произойдет, если высокий кусочки $д$ утечка в отличие от низких битов. Низкие биты $д$ утечка приводит к ключевой факторизации. Старшие биты, однако, просто раскрывают $к$, так как $n$ можно использовать как аппроксимацию $\фи(п)$ для вычисления старшей половины $д$ данный $к$.

Это совсем не плохо.

Практический аргумент: многие реализации вычисляют $д$ как $e^{-1} \mod \mathrm{lcm}(p-1,q-1)$ (OpenSSL, wolfCrypt, Mbed TLS) или $e^{-1} \mod \mathrm{(p-1)(q-1)}$ (Криптлиб, Крапива). Так что на практике противник все равно может сделать хорошее предположение.

Мета-аргумент: частный показатель RSA, соответствующий открытому ключу. $(п,е)$ любой $д$ такой, что $\forall x, (x^e)^d = x \mod{n}$. Подойдет любой вариант — иначе расшифровка RSA не сработает, так как шифрование зависит только от $n$ и $е$. Таким образом, выявление того, какой конкретный выбор $д$ используемый владелец закрытого ключа не допускает утечки информации о закрытом ключе. Это только утечка информации о том, как работает реализация операции с закрытым ключом.

Математический аргумент: вы выбрали частный показатель $д = к \, а$ куда $a = \mathrm{lcm}(p-1,q-1)$. Предположим, что противник находит значение $к$, и использует это знание, чтобы найти частную экспоненту-кандидата $d'$. Противник проверяет свою догадку, вычисляя $(x^e)^{d'} \mod{n}$. Неважно, нашли ли они тот же частный показатель, который используете вы: это не влияет на проверку предположения. $d'$, и это не влияет на полезность знания $d'$.

Единственная причина утечки $к$ вообще может иметь значение, если есть побочный канал в реализации операции с закрытым ключом, и знание того, какой частный показатель используется, помогает в эксплуатации этого побочного канала. Что касается математического анализа, затронутым шагом является «использование этих знаний для поиска потенциальной частной экспоненты»: если на этом шаге используются внутренние детали вашей реализации, было бы проще, если бы $к$ известен. Это касается только тех реализаций, которые используют частную экспоненту: большинство реализаций используют оптимизацию CRT с возведением в степень в степени $d_P$ и $d_Q$, и размер этих двух значений не коррелирует с размером $д$ (чтобы сделать любую такую ​​корреляцию, вам нужно знать $р$ и $q$, что было бы отдельным перерывом). Боковой канал, вероятно, покажет приблизительный размер $д$ тем не мение. Побочный канал, который пропускает некоторую информацию о $д$ без раскрытия его размера кажется мне надуманным, но у меня нет веских аргументов, что этого не могло произойти.