Comentarios

La hipótesis de Riemann e Internet- III


El matemático alemán C. F. Gauss introdujo el concepto de congruencia en el primer capítulo de su trabajo "Disquisitiones Arithmeticae", publicado en 1801. Este concepto es fundamental en la codificación y decodificación de claves en el sistema RSA. El criptosistema de clave pública, llamado RSA, fue desarrollado por los científicos R. Rivest, A. Shamir y L. Adleman.

Para codificar un texto de acuerdo con el sistema RSA necesita:

(1) un gran número Nque es el producto de dos números primos distintos p y que, o sea, N = p۰que.

(2) un entero E, conocida como clave de codificación, que satisface las siguientes propiedades:

el divisor común máximo (MDC) entre E y el producto (p - 1)۰(que -1) es 1, y el MDC

en el medio E y N también es 1.

Para decodificar un texto, de acuerdo con el sistema RSA, necesita:

(3) un entero D, conocida como clave de descifrado, que satisface la condición:

E۰D ≡ 1 (mod (p -1)۰(que - 1)).

La relación entre E y D es simétrico, es decir, si D es la clave de descifrado para Eentonces E es la clave de descifrado para D.

En la columna anterior codificamos el mensaje CLAVE PUBLICA utilizando el sistema RSA con

N = 2.537 = 43•59, p = 43, que = 59 y con la clave de cifrado E = 13.

Primero, observamos que N = 2.537 tiene 4 dígitos y dividimos el texto en pares de letras: PU BL IC KE Y y complete el último bloque con la letra C obteniendo: PU BL IC KE YC.

Usando la tabla de conversión que asocia los números naturales con las letras del alfabeto, los bloques convertidos del mensaje son: 1520 0111 0802 1004 2402. De esta manera, el receptor recibirá el mensaje cifrado: 0095 1648 1410 1299 0811.

Nuestro objetivo es tomar los pasos necesarios para decodificar este mensaje de acuerdo con el criptosistema RSA. Para descifrar este mensaje necesitamos la clave pública D de decodificación

¿Hay un método para determinar Dsi E, p y que son conocidos Sin embargo, si p y que no se conocen D No se puede determinar. La seguridad del criptosistema RSA reside en este hecho.

Si p y que son extremadamente grandes, por ejemplo, mayores de 10200luego determine estos números primos en un tiempo razonable, que es equivalente a factorizar N = p۰que,puede estar más allá de la capacidad de las supercomputadoras más rápidas.

Nuestro objetivo es determinar Dtal que E۰D ≡ 1 (mod (p - 1)۰(que - 1)), en otras palabras D es el inverso de E módulo (p - 1)۰(que - 1).

El método consiste en utilizar el algoritmo de Euclides aplicado a la clave E codificación y número (p - 1)۰(que - 1) Como E y (p - 1)۰(que - 1) son primos entre sí, el MDC entre ellos es 1. Primero, pasamos por todos los pasos del Algoritmo de Euclides para determinar el MDC que en este caso es 1.

Por el algoritmo euclidiano tenemos que

(p - 1)۰(que - 1) = que1۰E+ r2, 0 ≤ r2< E.

¿Cómo sabemos que MDC ((p - 1)۰(que - 1), E) = 1, continuamos aplicando el Algoritmo Euclidiano hasta que el resto de la división sea igual a 1. Por lo tanto, realizamos la división de E por r2 y así sucesivamente hasta obtener el resto de 1:

E = que2۰ r2 + r3, 0 ≤ r3< r2

r2 = que3۰ r3+ r4,0 ≤ r4< r3

rn-4 = quen-3۰ rn-3 + rn-2,0 ≤ rn-2 < rn-3

rn-3 = quen-2۰ rn-2 + rn-1,0 ≤ rn-1 < rn-2

rn-2 = quen-1۰ rn-1 + 1,0 ≤ 1< rn-1.

Ahora usando el algoritmo euclidiano en reversa podemos calcular D tal que

E۰D ≡ 1 (mod (p -1)۰(que - 1)).

Por lo tanto D Es la clave de descifrado.

Tenga en cuenta que:

<>

1 = rn-2 - quen-1۰<>

r<>

n-1<>

(1)

<>

r<>

n-1<>

= rn-3 - quen-2۰<>

r<>

n-2<>

(2)

<>

r<>

n-2 <>

= rn-4 - quen-3۰<>

r<>

n-3<>

(3)

r4 = r2-que3۰ r3 (no - 3)

r3= E - que2۰ r2, (no - 2)

r2 = (p - 1)۰(que - 1) - que1E (no - 1)

Anular el valor de rn-1 de (2) a (1) obtenemos

1 = (1 + quen-1۰quen-2rn-2 - quen-1۰rn-3

y sustituyendo en esta igualdad el valor de rn-2 de (3) obtenemos

rno = - (quen-3 + quen-1۰quen-2۰quen-3 + quen-1rn-3 + (1 + quen-1۰quen-2rn-4.

Entonces procedemos sucesivamente hasta obtener el número entero al final D tal que

E۰D ≡ 1 (mod (p -1)۰(que - 1)).

En nuestro ejemplo tenemos:

N = 2.537 = 43۰59, p = 43, que = 59 y (p - 1)۰(que - 1) = 42۰58 = 2,436 y E = 13.

Usando el algoritmo de Euclides para determinar el MDC entre (p - 1)۰(que - 1) = 2,436 y E = 13 obtenemos:

2.436 = 187۰13 + 5, 13 = 2۰5 + 3, 5 = 1۰3 + 2, 3 = 1۰2 + 1.

Ahora, usando el algoritmo de Euclides a la inversa, obtenemos:

1 = 3 - 1۰2, 2 = 5 - 1۰3, 3 = 13 - 2۰5, 5 = 2436 - 187۰13

Por lo tanto, sustituyendo como se explicó anteriormente, tenemos:

1 = 3 - 1۰2 = 3 - 1۰( 5 - 1۰3) = 3 - 1۰5 + 1۰3 = - 5 + 2۰3;

1 = - 5 + 2۰3 = - 5 + 2۰( 13 - 2۰5) = - 5 + 2۰13 - 4۰5 = 2۰13 - 5۰5;

1 = 2۰13 - 5۰5 = 2۰13 - 5۰( 2.436 - 187۰13) = 2۰13 - 5۰2.436 + 935.۰13 =

= 937۰13 - 5۰2.436.

Así obtenemos 1 = 937۰13 - 5۰2.436 que implica 937۰13 = 5۰2.436 +1.

Por lo tanto, 13۰937 ≡ 1 (mod 2.436), es decir E37937 ≡ 1 (mod (p -1)۰(que - 1)).

Concluimos que D = 937.

En la siguiente columna decodificaremos el mensaje.

Volver a las columnas

<