Ayúdame a explicar el principio del algoritmo RSA.
Primero, encuentre tres números, p, q, r.
Entre ellos, pyq son dos números primos diferentes, y r es igual a (p-1)( q -1) Números relativamente primos
Los tres números p, q, r son claves privadas
Luego, encuentra m tal que rm == 1 mod (p-1 )(q -1
Esta m debe existir, porque r y (p-1)(q-1) son primos relativos, lo que se puede obtener mediante el método de división euclidiana.
Nuevamente, calcule n = pq
m, los dos números n son la clave pública
El proceso de codificación es, si los datos son a, tratarlos como un entero grande, asumiendo un lt ; /p>
Si a gt; = n, expresa a como s carry (s lt; = n, generalmente s = 2^t),
Entonces cada número de dígitos es menor que n. , y luego codificación segmentada
A continuación, calcule b == a^m mod n, (0 lt; = b lt; n),
b son datos codificados
El proceso de decodificación consiste en calcular c == b^r mod pq (0 lt; = c lt; pq),
Luego, se completa la decodificación, etc. Se demostrará que c y a. son en realidad iguales :)
Si un tercero escucha a escondidas, obtendrá varios números: m, n(=pq), b
Si quiere decodificar, debe encontrar un manera de obtener r. Por lo tanto, primero debe factorizar n en factores primos.
Para evitar que se descomponga, la forma más efectiva es encontrar dos números primos muy grandes p, q,
. Hace que sea difícil para un tercero factorizar
lt; Teorema gt;
Si p y q son números heterogéneos, rm == 1 mod (p-1)(q-1). ),
a es cualquier entero positivo, b == a^m mod pq, c == b^r mod pq,
Entonces c == a mod pq
El proceso de demostración utilizará el pequeño teorema de Fermat, que se describe a continuación:
m es cualquier número primo, n es cualquier número entero, entonces n^m == n mod m
(En otras palabras, si n y m son mutuamente primos, entonces n^(m-1) == 1 mod m)
Utilizando algunos conocimientos básicos de teoría de grupos, puedes probar fácilmente la teoría de Fermat. Pequeño teorema
lt; prueba gt;
Porque rm == 1 mod (p-1 )(q-1), entonces rm = k(p-1)(q- 1) 1, donde k es un número entero
Porque el módulo conserva la multiplicación
( x == y mod z and u == v mod z =gt; xu == yv mod z ),
Entonces, c == b^r == (a^m)^r == a^(rm) == a^(k(p-1)(q-1) 1 ) mod pq
1 Si a no es múltiplo de p o q,
Entonces a^(p-1) == 1 mod p (Pequeño teorema de Fermat) =gt. ; a^(k(p-1)(q-1)) == 1 mod p
a^(q-1) == 1 mod q (Pequeño teorema de Fermat)
=gt; a^(k(p-1)(q-1)) == 1 mod q
Entonces, p y q pueden dividir a^(k(p-1)(q-1). )) - 1 =gt; pq | a^(k(p-1)(q-1)) - 1
Es decir, a^(k(p-1)(q-1) ) = = 1 mod pq
=gt; c == a^(k(p-1)(q-1) 1) == a mod pq
2. a es cuando es múltiplo de p, pero no múltiplo de q,
entonces a^(q-1) == 1 mod q (Pequeño Teorema de Fermat)
=gt; a^( k(p-1)(q-1)) == 1 mod q
=gt; c == a^(k(p-1)(q-1) 1) = = a mod q
=gt; q | c - a
Porque p | 1)( q-1) 1) == 0 mod p
=gt; p | c - a
Por lo tanto, pq | mod pq
3. Si a es múltiplo de q, pero no múltiplo de p, la prueba es la misma que la anterior
4. y q,
Entonces pq | a
=gt; c == a^(k(p-1)(q-1) 1) == 0 mod pq
=gt; pq | c - a
=gt; c == a mod pq
Q.E.D
Este teorema muestra que cuando a se codifica en b y luego se decodifica en c, a == c mod n (n = pq)
Pero cuando codificamos y decodificamos, limitamos 0 lt = a lt; = c lt; n,
Entonces esto significa que a es igual a c, por lo que este proceso de hecho puede realizar la función de codificar y decodificar