Olası en küçük RSA özel ve genel anahtarları nelerdir?

Question

Olası en küçük RSA genel ve özel anahtarlarının ne olduğunu anlamaya çalışıyorum. Kullanırken$p = 2, q = 3$şifreleme işlevi şifreleme yapmaz. Bu yüzden bir üssü kaydırmam gerekiyor$p = 3, q = 3$ ve sonra özel anahtar $(9, 3)$ ve genel anahtar da $(9, 3)$. İki eşit asalın çarpanını çarpanlarına ayırmanın önemsiz olduğunu ve aynı özel ve genel anahtara sahip olmanın kötü olduğunu biliyorum. Ancak en düşük (uygulanabilir) RSA anahtar çifti mi yoksa burada bir şey mi eksik?

Answer 1

PKCS # 1v2.2'deki RSA tanımına göre

Bir de geçerli RSA özel anahtarla , RSA modül$n$ ürünüdür $u$ farklı garip asal sayılar $r_i$, $i=1$, $2$,…, $u$, nerede $u\ge2$.

Bu yapar $n=3\cdot5=15$ en küçük genel katsayı.

ve RSA genel üssü $e$ arasında bir tamsayıdır $3$ ve $n–1$ doyurucu $\operatorname{GCD}(e,\lambda(n))=1$, nerede $\lambda(n)=\operatorname{LCM}(r_1–1,\ldots,r_u–1)$

Bu yapar $e=3$ en küçük halk üssü. $(n,e)=(15,3)$ geçerli bir genel anahtar olur, çünkü $\lambda(15)=4$ ve $\operatorname{GCD}(3,4)=1$.

RSA özel üssü $d$ şundan küçük pozitif bir tamsayıdır $n$ doyurucu $e\cdot d\equiv1\pmod{\lambda(n)}\,$.

Bu yapar $d=1$en küçük özel üs. Örneğin karşılık gelir$(n,e)=(15,5)$. Bu anahtarla şifreleme (ve şifre çözme) kimliktir, ancak buna karşı yazılı bir reçete yoktur.

---

Yasaklarsak $d=1$, sonra $d=3$ en küçük özel üs olur, eşleşen $(n,e)=(15,3)$. Daha genel olarak, farklı RSA tanımları farklı alt sınırlar sağlar. İzin verme$u=1$, $e=1$ve bu reçetenin kaldırılması $r_i$ garip, yapar $(n,e,d)=(2,1,1)$kabul edilebilir. İçin FIPS 186-4 , en küçük$n$1024 bit, muhtemelen ^A $(\lfloor2^{1023/2}\rfloor+257)\cdot(\lfloor2^{1023/2}\rfloor+2^{412}+431)\,$; en küçük$e$ dır-dir $65537\,$; ve en küçüğü$d$olan ^B $2^{512}+1$.

---

C: Mantıklı varsayım altında her birinin $\lfloor2^{1023/2}\rfloor+256$, $\lfloor2^{1023/2}\rfloor+258$, $\lfloor2^{1023/2}\rfloor+2^{412}+430$ ve $\lfloor2^{1023/2}\rfloor+2^{412}+432$ en azından bir asal faktöre sahiptir $2^{100}$, ki ben kontrol etmedim.

B: Bazı geçerli eşleşen genel anahtar $(n,e)$yüksek olasılıkla var. Birini sergilemek biraz ilginç bir problem.