Регистрация Войти
Рейтинг:11
Farzad Sadeghi avatar Crypto

Генерация частного экспонента RSA в соответствии с FIPS 186-4 в openssl v1

флаг us
Farzad Sadeghi

Я предполагаю, что это скорее математическая проблема в контексте криптографии, поэтому я заранее извиняюсь, если это не то место, где можно спросить.По сути, мне нужно проверить, соответствует ли определенная реализация генерации пары ключей RSA FIPS 186-4. В частности, Приложение B-3-1. FIPS 186-4 требует, чтобы $д$ (частный показатель) будет создан следующим образом:

$d = (e^{-1})\bmod(\text{LCM}(p-1, \space q-1))$

Рассматриваемая библиотека (openssl v1.0.1) вычисляет $д$ вот так:

$d = (e^{-1})\bmod((p-1)(q-1))$

Я не могу доказать или опровергнуть, создают ли эти двое один и тот же набор ответов для $д$.
Условие для генерации $р$ и $q$ в том, что $(p-1)$ и $(q-1)$ оба являются относительно простыми для $e$ (общедоступная экспонента), поэтому обе формулы имеют ответы.
Также с тех пор $р$ и $q$ оба простые, $(p-1)$ и $(q-1)$ будут как четные числа, так и из $a \times b=\text{GDC}(a, \space b) \times \text{LCM}(a, \space b)$ мы знаем это $\text{НОД}(p-1, \space q-1) \geq 2$ так $\text{LCM}(p-1, \space q-1) \neq (p-1)(q-1)$.

У меня вопрос, они одинаковые или разные?

Я также был бы признателен, если бы вы могли указать мне правильное направление с точки зрения математики, чтобы я потенциально мог решить это сам.

P.S.: Насколько я понимаю, для openssl v1 есть модуль FIPS, а также то, что openssl v3.0 попытается подать заявку на сертификат FIPS 140-2. К сожалению, я застрял в версии, которую я упомянул, и я не могу ее изменить (это не зависит от меня).

592
2 + 3
Maarten Bodewes avatar
флаг in
Maarten Bodewes
Я думаю, что вы довольно долго объясняли это себе, и ответ fgrieu в основном является подтверждением + некоторой дополнительной информацией о FIPS.Обратите внимание, что фактические ~ 50% очень сложно сузить, поскольку они зависят от $ (p-1) (q-1) $ и, возможно, даже от распределения простых чисел. Однако, если вам просто нужно, чтобы вычисление соответствовало FIPS, это будет означать, что вы можете попробовать использовать выборку отклонения при создании пары ключей RSA (сгенерировать, проверить, выполняются ли дополнительные требования FIPS, и перезапустить, если они не соответствуют). Закрытые ключи в OpenSSL (с внутренним программным движком) генерируются с параметрами CRT.
2
Ответить
dave_thompson_085 avatar
флаг cn
dave_thompson_085
Nit: OpenSSL 'v1' — это не что-то одно; текущий модуль OpenSSL FIPS 2.0.x должен работать с OpenSSL 1.0.1 и 1.0.2, но не с 1.0.0 1.1.0 1.1.1. OpenSSL 3.0.x предназначен для проверки, но не в соответствии с FIPS 140-2, поскольку он больше не доступен; вместо этого он должен пойти на 140-3. Что еще более важно, текущая SecurityPolicy (2.0.16) перечисляет соответствие RSA как 186-2, а не -4, и _keygen_ только как X9.31 для -2 (но _sign_ и _verify_ как X9.31 для -2, так и PKCS1v2 для -3). /4) и ссылается на сертификаты CAVP, в которых указано «RSA KeyGen FIPS186-2» с перечеркнутым указанием «больше не одобрено».
0
Ответить
Farzad Sadeghi avatar
флаг us
Farzad Sadeghi
В уважении да. возможно, v1 в заголовке вопроса может немного ввести в заблуждение. ты прав. Что касается проверки FIPS, openssl 3 пройдет проверку FIPS 140-2, поскольку она доступна до сентября 2021 года. Они не будут проходить проверку FIPS 140-3. Я взглянул на кодовую мысль. тем не менее, они стремятся соответствовать FIPS 186-4.
0
Ответить
Рейтинг:10
fgrieu avatar Crypto
флаг ng
fgrieu

FIPS 186-4 $d_1=e^{-1}\bmod m_1$ с $m_1=\operatorname{lcm}(p-1,q-1)$и OpenSSL $d_2=e^{-1}\bmod m_2$ с $m_2=(p-1)(q-1)$, различны с вероятностью $>1/2$ для случайного выбора $р$ и $q$ и либо исправлено $е$ добавление дополнительных ограничений на $р$ и $q$ (как обычно) или $е$ выбрано несколько случайно после $р$ и $q$.

Обоснование: имеет место $m_2=g\,m_1$ для целого числа $g=\gcd(p-1,q-1)$. Что $г$ является целым числом по крайней мере $2$ (и заметно часто большее даже целое число). Следует $d_2\bmod m_1=d_1$. Хорошо проверено, что $d_2$ примерно равномерно распределен на интервале $[0,м_2)$ в пределах ограничения взаимной простоты с $m_2$. Таким образом, модульная редукция от $d_2$ к $d_1$ вызывает изменение с вероятностью рядом с $1-1/г$, что всегда не менее $1/2$. Легко привести пример, где это происходит. Связанный $1/2$ для вероятности того, что $d_1\ne d_2$ можно улучшить (увеличить, немного $2/3$ на самом деле) с учетом распределения $г$.

Такое частое несоответствие не так плохо, как кажется, потому что

  • Что действительно нужно для $д$ для работы (когда и если используется в качестве частной экспоненты RSA, или для вычисления или проверки $d_p$ и $d_q$ ) в том, что $e\,d\equiv1\pmod{\operatorname{lcm}(p-1,q-1)}$ (при условии $р$ и $q$ различные простые числа). Обе $d_1$ и $d_2$ соответствовать этому и соответствовать ПККС#1 что дополнительно требует $0<d<n$ (что следует из $d_1<m_1<m_2<n$ и $d_2<m_2<n$).
  • На практике $д$ используется редко, потому что операция с закрытым ключом выполняется быстрее с китайской теоремой об остатках, которая обычно использует только $(n,e,p,q,d_p,d_q,q_\text{inv})$ или подмножество этого, и в этом случае единственные возможные проблемы с $d_1$ или же $d_2$ это когда он впервые проверяется, и это обязательно будет обнаружено путем импорта ключа и однократного использования.
  • Любой ключ RSA FIPS 186-4 принимается любой версией OpenSSL. Я бы не стал ставить на кон в другом направлении, но тогда редко можно импортировать ключ из OpenSSL в устройство FIPS 140. Это может быть даже запрещено в режиме FIPS, и устройству FIPS (по крайней мере, в режиме, отличном от FIPS) будет разрешено принимать любые математически достоверные данные. $д$ в том числе $d_2$, или игнорировать данный $д$.
0 + 2
poncho avatar
флаг my
poncho
Также обратите внимание, что на практике фактическое значение $d$ обычно игнорируется. Вместо этого мы обычно используем параметры CRT ($p, q, dp, dq, qinv$), и они оказываются одинаковыми независимо от того, используете ли вы $\phi(n)$ или $\operatorname{ lcm}(p-1,q-1)$ определение $d$...
3
Ответить
dave_thompson_085 avatar
флаг cn
dave_thompson_085
FWIW, FIPS186-4 (и -3) 5.1 прямо говорит, что представление CRT «разрешено»; он явно не упоминает об его использовании, но ссылается на PKCS1v2.1 и, конечно, PKCS1 до версии 1.5, по крайней мере, имеет предпочтительный CRT как для хранения, так и для операций.
1
Ответить
Рейтинг:2
avatar Crypto
флаг cn
j.p.

Насколько я понимаю, требование FIPS 186-4 использовать для вычисления закрытого ключа $д$ наименьшее общее кратное $p-1$ и $q-1$ вместо того, чтобы их продукт имел целью предотвратить атаки на мелкие $д$ нравиться Атака Винера. Среди экспертов распространено мнение, что от любого улучшения винеровской атаки можно застраховаться, если длина $д$ составляет не менее половины длины модуля $м$.

Как и все (известные) варианты атак на малый закрытый ключ $д$ работа в зависимости от размера самый маленький возможное $д$ (тот, который вычисляется с использованием наименьшего общего кратного), NIST настаивает на использовании наименьшего общего кратного, чтобы можно было проверить, что наименьшее возможное $д$ достаточно большой.

Поскольку NIST требует, чтобы $р$ и $q$ имеют примерно одинаковый размер, вы можете проверить требования к длине для $д$ также вместо того, чтобы просто проверить, что $d_p$, $d_p+p-1$, $d_q$ и $d_q+q-1$ попарно различны. Если для вас проблематичны атаки по сторонним каналам, этот тест может быть защищен гораздо проще, чем вычисление наибольшего общего делителя $p-1$ и $q-1$, который в последние годы стал объектом нескольких опубликованных атак. Который $д$ вы используете в своих расчетах, не должно иметь большого значения, так как добавление кратного $(p-1)(q-1)$ к экспоненте обычно используется в качестве контрмеры против атак по сторонним каналам.

0 + 4
fgrieu avatar
флаг ng
fgrieu
Действительно, проверка минимального $d$, сделанная в FIPS 186-4, имела бы еще меньше смысла, если бы $d$ не было указано как минимальное положительное $d$, как это есть.Но в любом случае этот тест не имеет большого смысла, поскольку (A) этот тест не проходит с незначительной вероятностью, когда используются обязательные общие методы генерации (максимум $e$ + случайные простые числа), и (B) существует множество методов для подделки ключа RSA. генератор таким образом, что это невозможно обнаружить на выходе. Среди других сложно обосновываемых тестов в FIPS 186-4 — минимальный $\lvert p-q\rvert$; но, по крайней мере, этот более поздний вариант — избыточный способ поймать застрявший генератор.
0
Ответить
флаг cn
j.p.
Небольшой $d$ может быть невинным способом «подстроить» кейген для повышения производительности (если кто-то боится атаки bellcore). Использование сита для обоих простых чисел для экономии времени (получение маленьких, ненадежных $|p-q|$) кажется менее вероятным.
0
Ответить
fgrieu avatar
флаг ng
fgrieu
FIPS 186-4 требует $n$ не менее 1024 бит, $p$ и $q$ вдвое меньше, а $e$ не более 256 бит. При этом сложно создать $p$ и $q$ с $d$ меньше половины $n$ (требуемый лимит); и я думаю, что это невозможно с $p$ и $q$ где-либо близко к случайному и независимому, даже если впоследствии будет выбрано $e$. Это сделало бы минимум $d$ релевантным только для созданных $p$ и/или $q$; но созданные простые числа опасны во многих отношениях, включая некоторые, которые могут сойти за (или даже быть) случайными неудачами. Следовательно, требование минимального $d$ имеет сомнительное обоснование.
0
Ответить
флаг cn
j.p.
Я думаю, все согласятся, что для действительно случайных $p$ и $q$, требующих $e$, не слишком долго должно быть достаточно, чтобы избежать плохих вещей. Единственный известный мне способ получить короткую $d$ (для короткой $e$) — это ввести большой общий делитель для $p-1$ и $q-1$ (что редко случается случайным выбором), поэтому я предполагаю, что некоторые из требований NIST столь же «сомнительны», как и прежнее использование «безопасных простых чисел»…
0
Ответить
флаг Moldova
Admin
Этот вопрос на других языках:

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

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