Apa kunci privat dan publik RSA sekecil mungkin?

Question

Saya mencoba memahami apa kunci publik dan privat RSA sekecil mungkin. Ketika menggunakan$p = 2, q = 3$, fungsi enkripsi tidak mengenkripsi. Jadi saya harus menggeser satu bilangan prima untuk mendapatkannya$p = 3, q = 3$ dan kemudian kunci privatnya adalah $(9, 3)$ dan kunci publiknya juga $(9, 3)$. Saya tahu bahwa adalah sepele untuk memfaktorkan produk dari dua bilangan prima yang sama dan buruk untuk memiliki kunci privat dan publik yang identik. Namun apakah itu pasangan kunci RSA terendah (layak) atau saya melewatkan sesuatu di sini?

Answer 1

Sesuai definisi RSA di PKCS # 1v2.2

Dalam kunci pribadi RSA yang valid , modulus RSA$n$ adalah produk dari $u$ bilangan prima aneh yang berbeda $r_i$, $i=1$, $2$,…, $u$, dimana $u\ge2$.

Itu membuat $n=3\cdot5=15$ modulus publik terkecil.

dan eksponen publik RSA $e$ adalah bilangan bulat antara $3$ dan $n–1$ memuaskan $\operatorname{GCD}(e,\lambda(n))=1$, dimana $\lambda(n)=\operatorname{LCM}(r_1–1,\ldots,r_u–1)$

Itu membuat $e=3$ eksponen publik terkecil. $(n,e)=(15,3)$ kebetulan menjadi kunci publik yang valid, sejak $\lambda(15)=4$ dan $\operatorname{GCD}(3,4)=1$.

Eksponen pribadi RSA $d$ adalah bilangan bulat positif kurang dari $n$ memuaskan $e\cdot d\equiv1\pmod{\lambda(n)}\,$.

Itu membuat $d=1$eksponen pribadi terkecil. Ini sesuai misalnya dengan$(n,e)=(15,5)$. Enkripsi (dan dekripsi) dengan kunci itu adalah identitas, tetapi tidak ada resep yang melarang itu.

---

Jika kami melarang $d=1$, kemudian $d=3$ menjadi eksponen privat terkecil, cocok $(n,e)=(15,3)$. Secara lebih umum, definisi RSA yang berbeda menghasilkan batas bawah yang berbeda. Mengizinkan$u=1$, $e=1$, dan menghapus resep itu $r_i$ aneh, membuat $(n,e,d)=(2,1,1)$dapat diterima. Untuk FIPS 186-4 , yang terkecil$n$adalah 1024-bit, kemungkinan ^A $(\lfloor2^{1023/2}\rfloor+257)\cdot(\lfloor2^{1023/2}\rfloor+2^{412}+431)\,$; Terkecil$e$ adalah $65537\,$; dan yang terkecil$d$adalah ^B $2^{512}+1$.

---

J: Dengan asumsi yang masuk akal bahwa masing-masing $\lfloor2^{1023/2}\rfloor+256$, $\lfloor2^{1023/2}\rfloor+258$, $\lfloor2^{1023/2}\rfloor+2^{412}+430$ dan $\lfloor2^{1023/2}\rfloor+2^{412}+432$ memiliki faktor prima setidaknya $2^{100}$, yang tidak saya periksa.

B: Beberapa kunci publik yang cocok dan valid $(n,e)$ada dengan kemungkinan tinggi. Ini masalah yang agak menarik untuk dipamerkan.