Una clave RSA con especial números primos

Question

$(N,5)$ es una clave pública RSA con números primos $p,q$ tal que $N =pq, q = 2p-3$$p>5$. Demostrar que:

1. $p \equiv 3 \mod 5$
2. $(N,d)$ $d =\frac{1}{5} (1+(p-1)(q-1))$ es válido clave privada RSA de clave pública $(N,5)$.

Aquí está mi intento de prueba para el punto 2:

Sabemos que (a partir de la construcción de la criptosistema RSA)

$$d \cdot e ≡ 1 \mod \varphi(N)$$

Desde $\varphi(N) = (p-1)(q-1)$$e=5$, tenemos que resolver

$$d \cdot 5 ≡ 1 \mod (p-1)(q-1)$$

para $d$ que es el mismo que

$$d \cdot 5 ≡ 0 \mod ((p-1)(q-1)+1)$$

y podemos ver directamente que

$$d =\frac{1}{5} (1+(p-1)(q-1))$$

lo que demuestra el punto 2.

Es correcto y ¿alguien puede ayudarme con el punto 1?

Answer 1

Punto 1. Observar los valores de $r=p\bmod 5.$ Si $r=0$ $p$ no es primo. Si $r=1$ o $r=2$ ( $q\bmod 5=1$ ) ha $\phi \bmod 5 = 0$ y no hay inversa. $r=4$ implica que el $q$ hay prime porque $q\bmod 5=0$.

Así que si su sistema RSA es válido, que necesariamente tienen $p\equiv 3 \pmod 5$, y a partir de la definición de $q\equiv 3 \pmod 5.$

Artículo 2. A partir del 1 tenemos $\phi = (p-1)(q-1)\equiv 2\times 2\equiv 4 \pmod 5.$ Esto significa que el $\phi+1$ es un múltiplo de a $5$. Deje $$d = \frac{\phi+1}{5}=\frac{(p-1)(q-1)+1}{5}$$ A continuación, $$5d=5\frac{\phi+1}{5}=\phi+1 \equiv 1 \pmod {\phi},$$ es decir, $d\,$ es el inverso multiplicativo de a $5$ modulo $\phi$ y un documento de la clave privada para $(N,5).$

Nota: Como ya se mencionó en un comentario, este sistema RSA es inseguro, porque usted puede fácilmente factor de $N$. Usted obtiene una ecuación cuadrática en números enteros de $N=p(2p-3)$ $$2p^2-3p-N=0$$ con la solución positiva $$p=\frac{3+\sqrt{8N+9}}{4}$$

Answer 2

1. Para $(N,5)$ a calificar como una clave pública RSA, debemos tener $\gcd(\varphi(N),5)=1$.

   Como $\varphi(N)=(p-1)(q-1)$, esto significa que $\gcd(p-1,5)=\gcd(q-1,5)=1$, lo $p$ $q$ debe ser igual a $0,2,3,$ o $4 \bmod 5$. $p$ y $q$ es de los primeros, y se nos dice que $p > 5$$q=2p-3$, lo $p$ $q$ debe ser distinto de cero $\bmod 5$. Esto deja a $2,3,$ $4$ como posibles valores de $p \bmod 5$$q \bmod 5$.

   Ahora para cada uno de estos posibles valores de $p \bmod 5$, el uso de $q=2p-3$ para encontrar el valor correspondiente de $q \bmod 5$. ¿Cuáles son las permitidas pares de $(p \bmod 5,q\bmod 5)$?

2. De $$d \cdot 5 ≡ 0 \mod ((p-1)(q-1)+1)$$ you can't conclude that $$d =\frac{1}{5} (1+(p-1)(q-1))$$

   Tiene un enfoque diferente:

   • mostrar (utilizando parte 1) $d=\frac{1}{5} (1+(p-1)(q-1))$ es un número entero;
   • mostrar que $5d = 1 \bmod \varphi(N)$.