Рейтинг:1

При чем здесь параметр безопасности $1^\kappa$?

флаг tv

Будь как будет $К$ алгоритм генерации ключей, который принимает $(к,д)$ как ввод с $к$ как битовая длина для $n=pq$ с $p,q \in \mathbb{P}$ и $d=|p-q|$ как минимальное расстояние между $р$ и $q$ (РСА).Что будет параметром безопасности $1^\каппа$?

Будет ли это $\каппа=к+д$ или только $\каппа=к$ а если бы это было так, от чего бы это зависело?

Я просмотрел следующие ссылки и не смог найти ответ на свой вопрос:

Что означает выражение $1^n$ значит как аргумент функции? Почему генерация ключей требует ввода $1^к$, и как мне это представить на практике?

fgrieu avatar
флаг ng
Для генерации ключа RSA в соответствии с [FIPS 186-4](https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-4.pdf#page=62) $k$ может составлять $3072$ (для безопасность сравнима со 128-битным симметричным ключом), а $d$ может быть $2^{k/2-100}=2^{1436}$. Добавлять такие дико разные количества не имеет смысла. Также $d$ имеет стандартное значение в RSA. А как насчет $|p-q|>2^δ$? Независимо: я не знаю математически обоснованной причины, по которой применение минимального $|p-q|$ при генерации ключа RSA улучшило бы безопасность по сравнению с тем, чтобы этого не делать. А чрезмерное увеличение $δ$ (скажем, до $8n/9$) _уменьшает_ безопасность. Так почему же $κ=k+δ$ имеет смысл?
marius avatar
флаг tv
Вопрос, имеет ли это смысл или какие другие требования безопасности будут, я специально задал в другом посте.Но может быть, например, что кто-то начинает с $int(\sqrt(n))$ при грубой факторизации $n$. Тогда такое расстояние, вероятно, имело бы смысл. Вопрос в том, влияет ли это на определение $\kappa$.
Рейтинг:1
флаг ng

По причинам в мой комментарий Я предполагаю, что мы изменим вопрос, чтобы определить $δ$ с $2^\delta<\lvert p-q\rvert$, и $\каппа=к+\дельта$. ФИПС 186-4 генерация ключей будет, например, использовать $к=3072$ и $\дельта=к/2-100=1436$.

Я не могу найти ссылки на обсуждение асимптотической безопасности RSA с такой нотацией $1^к$ которые указывают минимум $\lvert p-q\rvert$. Это потому что:

  • Увеличение $\дельта$ прошлое некоторое время заметно снижает безопасность. Например. за $к=3072$ (что дало бы 128-битную симметричную безопасность) и $δ=1912$ у нас было бы $\мин(p,q)<2^{161}$ и ЕСМ Лентры вероятно, позволит вытащить этот фактор $n$.
  • Простые аргументы, что увеличение $\дельта$ повышает безопасность, есть недостатки.
  • $\дельта=0$ считается нормально.
  • Историческая причина введения нижней границы $\lvert p-q\rvert$ заключается в том, что стоимость факторизации Ферма примерно пропорциональна $(pQ)^2/n$ умножить на некоторый многочлен от $к$, таким образом $\lvert p-q\rvert$ не должен быть слишком маленьким. От этого факта перескочили к выводу, что необходимо указать явный минимум $\lvert p-q\rvert$, хотя достаточно явно указать, что $р$ и $q$ выбираются независимо и примерно равномерно среди простых чисел в некотором интервале, подобном $[2^{(к-1)/2},2^{к/2})$ гарантировать, что факторизация Ферма безнадежна, когда бы $к$ достаточно большой, чтобы сопротивляться GNFS (или же ППМПКС, что было давно известно в 1998 году, когда спорное решение было подписано в ANS X9.31).

Как просили в комментарий Я все же предполагаю, что есть какая-то причина указать $\дельта$, и это увеличение $\дельта$ повышает безопасность в каком-то домене. Чтобы не противоречить факту в первом пункте выше, я предположу, $0\le\delta\le\alpha\,k+\beta$ для некоторых реалов $\альфа$ и $\бета$ с $\альфа\в[0,1)$. При такой гипотезе имеет смысл определить $\каппа=к+\дельта$и используйте его в качестве параметра безопасности.

Мы могли бы определить генерацию ключа RSA для постоянного нечетного целого числа $е>1$ как: на входе $1^\каппа$

  1. За полиномиальное время выберите целые числа $к$ и $\дельта$ с $\каппа=к+\дельта$ и $0\ле\дельта\ле\альфа к+\бета$ (потерпите неудачу, если это невозможно); подходящие способы включают $\delta\gets\left\lfloor\frac\alpha2\kappa\right\rfloor$ и $k\gets\каппа-\дельта$.
  2. выберите $р$ равномерно случайно среди простых чисел $р$ в $[2^{(к-1)/2},2^{к/2})$ с $\gcd(p-1,e)=1$
  3. выберите $q$ равномерно случайно среди простых чисел $q$ в $[2^{(к-1)/2},2^{к/2})$ с $\gcd(q-1,e)=1$ и $2^\delta<\lvert p-q\rvert$.
  4. Вычислить $n\получает p\,q$ и $d\gets e^{-1}\bmod\operatorname{lcm}(p-1,q-1)$, вывод открытого ключа $(п,е)$ и закрытый ключ $(н,д)$.

Вероятно, что: для любого допустимого выбора $е$ в этом алгоритме генерации ключей для любого многочлена $P$, не существует алгоритма вероятностного полиномиального времени, который при $\каппа$ растет взламывает шифрование RSA с неисчезающей вероятностью во времени $P(\каппа)$.

Эта правдоподобная гипотеза очевидным образом подразумевается общепринятой и более простой формой гипотезы RSA для фиксированного/малого публичного показателя, которая удаляет шаг (1.) и заменяет условие $2^\delta<\lvert p-q\rvert$ с $p\neq$ на шаге (3.) и использует $к$ где есть $\каппа$. У нас нет доказательств того, что гипотезы эквивалентны, но нет и веских причин полагать обратное, поэтому многие практики и большинство теоретиков используют более простую гипотезу².


¹ Набросок доказательства: мы предполагаем, что существует $е$ и алгоритм $\математический А$ который взламывает шифрование RSA с неисчезающей вероятностью за время $P(\каппа)$ при использовании генерации ключа RSA с $2^\delta<\lvert p-q\rvert$. Мы используем $\математический А$ построить алгоритм $\mathcal А'$ призывая $\математический А$ как подпрограмма, которая для того же $е$ ломает шифрование RSA с некоторой вероятностью в течение времени $П'(к)$ при использовании генерации ключа RSA с $p\neq$. Вероятность не равна нулю, потому что $р$ и $q$ выполнить условие страхования $\математический А$ работает с вероятностью, что мы можем получить нижнюю границу, и не обращается в нуль. Мы можем установить $P'$ от $P$, $\альфа$ и $\бета$, и что $P'$ по-прежнему является полиномом. $\альфа<1$ вступает в игру.

² Часто состояние $p\neq$ также удаляется, что может привести к сбою расшифровки.Это происходит при исчезающей пропорции сгенерированных ключей, но некоторые определения шифра не имеют исключений для такого крайнего случая, поэтому мы сохраняем $p\neq$.

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

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