algorithm - inverso - RSA: Cálculo de clave privada con algoritmo euclidiano extendido

el inverso multiplicativo de 17

Question

Soy un estudiante de preparatoria escribiendo un artículo sobre RSA, y estoy haciendo un ejemplo con algunos números primos muy pequeños. Entiendo cómo funciona el sistema, pero no puedo, por mi vida, calcular la clave privada utilizando el algoritmo euclidiano extendido.

Esto es lo que he hecho hasta ahora:

• He elegido los números primos p = 37 y q = 89 y calculé N = 3293
• He calculado (p-1) (q-1) = 3168
• He elegido un número e para que e y 3168 sean relativamente primos. Lo estoy comprobando con el algoritmo euclidiano estándar, y eso funciona muy bien. Mi e = 25

Ahora solo tengo que calcular la clave privada d, que debería satisfacer ed = 1 (mod 3168)

Usando el algoritmo euclídeo extendido para encontrar d tal que de + tN = 1 obtengo -887 • 25 + 7 • 3168 = 1. Tiro el 7 y consigo d = -887. Intentando descifrar un mensaje, sin embargo, esto no funciona.

Sé por mi libro que d debería ser 2281, y funciona, pero no puedo averiguar cómo llegan a ese número.

¿Alguien puede ayudar? He intentado resolver este problema durante las últimas 4 horas y he buscado una respuesta en todas partes. Estoy haciendo el Algoritmo Euclidiano Extendido a mano, pero como el resultado funciona, mis cálculos deberían ser correctos.

Gracias por adelantado,

Mads

Answer 1

Estás tan cerca que te vas a patear.

3168-887 = 2281.

Específicamente, si tiene un mod x, entonces A debe satisfacer 0<=a<x . Si no es así, sume o reste x tantas veces como sea necesario hasta que esté en este rango. Esto se llama aritmética modular.

Es posible que desee leer sobre congruencias lineales y teoría de números. Estos temas son las matemáticas a nivel de grado en el Reino Unido (lo que llamarías universidad, supongo), así que no te preocupes si parece un poco extraño. Una congruencia lineal simplemente dice que -887 mod 3168 y 2281 mod 3168 son en realidad lo mismo porque son parte de la misma clase, la clase que resulta como 2281 mod 3168 en el rango requerido. 2281+3168 mod 3168 también estaría en esa clase.

¡Que te diviertas!

PS PARI / GP es un número de utilidad que los teóricos usan para los cálculos. Podría valer la pena un vistazo.