Каковы наименьшие возможные закрытые и открытые ключи RSA?
Я пытаюсь понять, каковы минимально возможные открытые и закрытые ключи RSA. Когда используешь$p = 2, q = 3$, функция шифрования не выполняет шифрование. Поэтому мне нужно сместить одно простое число, чтобы получить$p = 3, q = 3$ а затем закрытый ключ $(9, 3)$ и открытый ключ также $(9, 3)$. Я знаю, что множить произведение двух равных простых чисел тривиально, и плохо иметь одинаковый закрытый и открытый ключи. Однако это самая низкая (выполнимая) пара ключей RSA, или мне что-то здесь не хватает?
Ответы
Согласно определению RSA в PKCS # 1v2.2
В действительном закрытом ключе RSA модуль RSA$n$ это продукт $u$ различные нечетные простые числа $r_i$, $i=1$, $2$,…, $u$, где $u\ge2$.
Что делает $n=3\cdot5=15$ наименьший публичный модуль.
и публичный экспонент RSA $e$ является целым числом между $3$ и $n–1$ удовлетворение $\operatorname{GCD}(e,\lambda(n))=1$, где $\lambda(n)=\operatorname{LCM}(r_1–1,\ldots,r_u–1)$
Что делает $e=3$ наименьший публичный экспонент. $(n,e)=(15,3)$ оказывается действительным открытым ключом, поскольку $\lambda(15)=4$ и $\operatorname{GCD}(3,4)=1$.
Частный показатель RSA $d$ положительное целое число меньше, чем $n$ удовлетворение $e\cdot d\equiv1\pmod{\lambda(n)}\,$.
Что делает $d=1$наименьший частный показатель. Это соответствует, например,$(n,e)=(15,5)$. Шифрование (и дешифрование) с помощью этого ключа является идентификатором, но нет никаких рецептов против этого.
Если мы запретим $d=1$, тогда $d=3$ становится наименьшей частной экспонентой, соответствующей $(n,e)=(15,3)$. В более общем смысле, разные определения RSA дают разные нижние пределы. Разрешение$u=1$, $e=1$, и сняв рецепт, $r_i$ странно, делает $(n,e,d)=(2,1,1)$приемлемо. Для FIPS 186-4 самый маленький$n$1024-битный, вероятно A $(\lfloor2^{1023/2}\rfloor+257)\cdot(\lfloor2^{1023/2}\rfloor+2^{412}+431)\,$; наименьший$e$ является $65537\,$; и самый маленький$d$это B $2^{512}+1$.
A: При вероятном предположении, что каждый из $\lfloor2^{1023/2}\rfloor+256$, $\lfloor2^{1023/2}\rfloor+258$, $\lfloor2^{1023/2}\rfloor+2^{412}+430$ и $\lfloor2^{1023/2}\rfloor+2^{412}+432$ имеет простой фактор не менее $2^{100}$, который я не проверял.
B: некоторый действительный совпадающий открытый ключ $(n,e)$существует с большой вероятностью. Выставить одну из них - довольно интересная задача.