Рейтинг:7

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

флаг in

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

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

или же

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

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

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

Рейтинг:2
флаг cn

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

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

Fractalice avatar
флаг in
У меня такое чувство, что ответ больше фокусируется на разнице между использованием $\varphi(n)$ или $\lambda(n)$, но вопрос больше касается значения самого $k$.
Gilles 'SO- stop being evil' avatar
флаг cn
@Fractalice Я не понимаю твоего комментария. Я хочу сказать, что не имеет значения, используете ли вы $k=1$, $k=\phi(n)/\lambda(n)$ или какое-либо другое значение $k$, поскольку это просто выбор представление закрытого ключа.
Fractalice avatar
флаг in
Нет, $k$ в вопросе — это отношение $(ed-1)/\phi(n)$, а не порядок секретной группы (также может быть $\lambda(n)$ или любой другой кратный). Он пропускает некоторую информацию о $d$, например, о старшей половине. Но напр. для маленького $e$ это действительно не имеет большого значения, так как об этом можно догадаться.

Ответить или комментировать

Большинство людей не понимают, что склонность к познанию нового открывает путь к обучению и улучшает межличностные связи. В исследованиях Элисон, например, хотя люди могли точно вспомнить, сколько вопросов было задано в их разговорах, они не чувствовали интуитивно связи между вопросами и симпатиями. В четырех исследованиях, в которых участники сами участвовали в разговорах или читали стенограммы чужих разговоров, люди, как правило, не осознавали, что задаваемый вопрос повлияет — или повлиял — на уровень дружбы между собеседниками.