Resolución de RSA para $p$ y $q$ conociendo $\phi(pq)$ y $n$

Question

Quiero determinar $p$ y $q$ en RSA.

Sé que $n = 172451$ y $\phi(n) = 171600$ .

$$171600 = pq - (p+q) + 1 = 172451 -(p + q) + 1$$ $$p + q = 172451-171600+1 = 852$$ $$(p-q)^2 = (p+q)^2-4pq = (852)^2 - 4(172451) = 36100$$

Ahora estoy atascado en este punto y no entiendo cómo puedo obtener $p$ y $q$ .

Si alguien quiere explicarlo.

P.D. - Ya he mirado otras respuestas publicadas aquí en math.stackexchange.com pero no unsertand

Answer 1

Ya casi has terminado. Ya hemos $(p-q)^2=36100$ . Sin pérdida de generalidad, podemos suponer que $p\ge q$ . Así que $p-q=190$ (sacamos la raíz cuadrada).

Ahora sabemos $p+q$ y $p-q$ . Sumando, encontramos $2p$ y por lo tanto $p$ .

Answer 2

Ya sabes \begin{equation*} p q = n \end{equation*} y \begin{equation*} \varphi(n) = (p-1)(q-1) = pq - p - q + 1 = n - (p+q) + 1. \end{equation*} Así que \begin{equation*} p + q = n + 1 - \varphi(n). \end{equation*}

Ahora recordemos que en una ecuación cuadrática \begin{equation*} x^2 - b x + c = 0, \end{equation*} el coeficiente $b$ es la suma de las dos raíces, y $c$ es su producto. De ello se deduce que puede encontrar $p$ y $q$ como raíces de la ecuación \begin{equation*} x^2 - (n + 1 - \varphi(n)) x + n = 0. \end{equation*}