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

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

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

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

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

По причинам в мой комментарий Я предполагаю, что мы изменим вопрос, чтобы определить $δ$ с $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$.