Encontrar el valor d en el cifrado RSA

Question

Puede que sea una pregunta estúpida, pero no consigo entenderlo, así que por favor, tened paciencia.

Estaba mirando este ejercicio de RSA, y sé que el valor correcto de d es 689. Sin embargo, no tengo ni idea de cómo obtener ese número. Leí en alguna parte que d se puede calcular usando esto:

d = e^-1 mod (p-1)*(q-1)

Estos son los valores del ejercicio:

e = 5

Los encontré yo mismo, pero creo que son correctos:

p = 43
q = 83

Así que:

d = 5^-1 mod 3444

No entiendo cómo eso podría darme 689. ¡Se agradece cualquier ayuda!

Answer 1

Si quieres utilizar estrictamente el algoritmo euclidiano extendido para resolver $$d \equiv 5^{-1} \text{ mod } 3444$$ la tabla simplificada que se obtendría sería

(Las dos primeras líneas son de inicialización, el resto se describe, por ejemplo, en http://sites.millersville.edu/bikenaga/number-theory/exteuc/exteuc.html )

Y como resultado $d \equiv 689 \text{ mod } 3444$

Answer 2

Existen procedimientos generales, como el Algoritmo Euclidiano Extendido, para encontrar inversiones modulares. Pero para la inversa modular de un número pequeño como $5$ , podemos hacerlo más o menos por inspección.

Queremos $5x\equiv 1\pmod{3444}$ . Si podemos encontrar $k$ tal que $1+3444k$ es divisible por $5$ habremos terminado, pues entonces podremos cancelar el $5$ 's.

Tenga en cuenta que $k=1$ obras. Así que queremos resolver $5x\equiv 1+3444\pmod{5}$ . Obtenemos $x=\frac{1+3444}{5}$ .