Quais são as menores chaves públicas e privadas RSA possíveis?

Question

Estou tentando entender quais são as menores chaves públicas e privadas RSA possíveis. Ao usar$p = 2, q = 3$, a função de criptografia não criptografa. Então eu tenho que mudar um primo para obter$p = 3, q = 3$ e então a chave privada é $(9, 3)$ e a chave pública também é $(9, 3)$. Eu sei que é trivial fatorar o produto de dois primos iguais e é ruim ter a chave pública e privada idênticas. No entanto, é o par de chaves RSA mais baixo (viável) ou estou faltando alguma coisa aqui?

Answer 1

De acordo com a definição de RSA em PKCS # 1v2.2

Em uma chave privada RSA válida , o módulo RSA$n$ é o produto de $u$ primos ímpares distintos $r_i$, $i=1$, $2$, ..., $u$, Onde $u\ge2$.

Isto faz $n=3\cdot5=15$ o menor módulo público.

e o expoente público RSA $e$ é um número inteiro entre $3$ e $n–1$ satisfatório $\operatorname{GCD}(e,\lambda(n))=1$, Onde $\lambda(n)=\operatorname{LCM}(r_1–1,\ldots,r_u–1)$

Isto faz $e=3$ o menor expoente público. $(n,e)=(15,3)$ passa a ser uma chave pública válida, uma vez que $\lambda(15)=4$ e $\operatorname{GCD}(3,4)=1$.

O expoente privado RSA $d$ é um número inteiro positivo menor que $n$ satisfatório $e\cdot d\equiv1\pmod{\lambda(n)}\,$.

Isto faz $d=1$o menor expoente privado. Corresponde, por exemplo, a$(n,e)=(15,5)$. Criptografar (e descriptografar) com essa chave é identidade, mas não há nenhuma prescrição redigida contra isso.

---

Se proibirmos $d=1$, então $d=3$ torna-se o menor expoente privado, combinando $(n,e)=(15,3)$. De forma mais geral, diferentes definições de RSA geram diferentes limites inferiores. Permitindo$u=1$, $e=1$, e removendo a prescrição que $r_i$ é estranho, faz $(n,e,d)=(2,1,1)$aceitável. Para FIPS 186-4 , o menor$n$é de 1024 bits, provavelmente ^A $(\lfloor2^{1023/2}\rfloor+257)\cdot(\lfloor2^{1023/2}\rfloor+2^{412}+431)\,$; o menor$e$ é $65537\,$; e o menor$d$é ^B $2^{512}+1$.

---

R: Sob a suposição plausível de que cada um $\lfloor2^{1023/2}\rfloor+256$, $\lfloor2^{1023/2}\rfloor+258$, $\lfloor2^{1023/2}\rfloor+2^{412}+430$ e $\lfloor2^{1023/2}\rfloor+2^{412}+432$ tem um fator primordial pelo menos $2^{100}$, que não verifiquei.

B: Alguma chave pública correspondente válida $(n,e)$existe com alta probabilidade. É um problema ligeiramente interessante exibir um.