可能な限り最小のRSA秘密鍵と公開鍵は何ですか?

Aug 18 2020

私は、RSAの公開鍵と秘密鍵が可能な限り最小のものであるかを理解しようとしています。使用する場合$p = 2, q = 3$、暗号化機能は暗号化しません。だから私は取得するために1つの素数をシフトする必要があります$p = 3, q = 3$ そして秘密鍵は $(9, 3)$ 公開鍵も $(9, 3)$。2つの等しい素数の積を因数分解するのは簡単であり、同じ秘密鍵と公開鍵を持つのは悪いことです。ただし、これは最も低い(実行可能な)RSAキーペアですか、それともここで何かが不足していますか?

回答

9 fgrieu Aug 18 2020 at 09:56

PKCS#1v2.2のRSAの定義による

では、有効な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)$。そのキーを使用した暗号化(および復号化)はIDですが、それに対する言葉による処方箋はありません。


禁止する場合 $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)$可能性が高いです。展示するのは少し面白い問題です。