En detalle

La hipótesis de Riemann e Internet II


En 1977, los científicos R. Rivest, A. Shamir y L. Adleman propusieron un sistema criptográfico de clave pública llamado RSA. Este sistema utiliza algunas ideas elementales de la teoría de números.

Aunque las ideas utilizadas son elementales, esto no significa que sean triviales. De hecho, uno de los mejores matemáticos de todos los tiempos, el matemático alemán Gauss (1777-1855), creó y desarrolló la noción de congruencias que es fundamental en la codificación y decodificación de claves en el sistema RSA. Las congruencias, y el consiguiente desarrollo llamado Aritmética modular, hacen una contribución importante a la teoría de números. En particular, las cuestiones de divisibilidad, porque cuando existe la necesidad de trabajar con los restos de la división euclidiana, las congruencias son los instrumentos apropiados.

Gauss introdujo el concepto de congruencia en el primer capítulo de su trabajo "Disquisitiones Arithmeticae" publicado en 1801. Gauss introdujo, simultáneamente con el concepto de congruencia, la notación "≡", que hizo del concepto una técnica poderosa en Álgebra y Teoría de números. Vayamos a las definiciones.

Consideramos dos enteros el, b y no Un entero positivo. Si no dividir el - bentonces decimos que el es congruente con b módulo noy escribimos elb (mod no).

Por ejemplo:

37 ≡ 2 (mod 5), porque 5 divide 37 - 2 = 35,

27 ≡ 3 (mod 4), porque 4 divide 27 - 3 = 24,

7 ≡ 7 (mod 4), por lo tanto 4 divide 7 - 7 = 0.

Por lo tanto elb (mod no) significa que no dividir el - b; entonces hay un número entero k tal que el - b = kn por la definición de divisibilidad. Por ejemplo, 37 ≡ 2 (mod 5) implica que hay k (= 7) tal que 37 - 2 = 35 = 7 • 5.

Dados los enteros el y no, sabemos por el algoritmo de división que hay enteros que y r respectivamente, cociente y resto, de modo que: el = cuando + rdonde 0 ≤ r < no; pronto el - r = cuando, o sea, no dividir el - r. Por lo tanto, por la definición de congruencia elr (mod no).

El resto r puede asumir cualquier valor entre 0 y no - 1. Por lo tanto, concluimos que cada número entero el es un módulo congruente no exactamente a uno de los valores entre 0, 1, 2, ..., no - 1. El conjunto {0, 1, 2, ..., no - 1} de enteros m cuales son los restos de las divisiones del módulo no, se llama clase de desperdicio de módulo no. Si arreglamos no = 7, entonces el módulo 7 tiene exactamente 7 elementos, a saber: 0, 1, 2, ..., 6. Por lo tanto, sea cual sea el número entero, es congruente con un solo elemento del módulo 7.

Por ejemplo, 20 está representado por 6 en la clase de residuos mod 7, ya que 20 ≡ 6 (mod 7).

La idea de congruencia está presente en nuestra vida diaria si pensamos que los relojes marcan las horas del módulo 12, los días de la semana se miden el módulo 4, los meses del año siguen un patrón del módulo 12. Debido a las muchas propiedades similares entre congruencias e igualdad, Gauss eligió el Símbolo "≡" para la señal correspondiente.

Tenga en cuenta que elel (mod no) y si elb (mod no) entonces bel(mod no) Las operaciones de suma, multiplicación y potenciación se comportan de la siguiente manera.

Si elb (mod no) y cd (mod no) entonces:

el + c b + d (mod no),

el c b d (mod no),

elrbr (mod no).

El método presentado en el siguiente ejemplo es fundamental en nuestro manejo de la codificación y decodificación de claves en el sistema RSA. Además, es un ejemplo muy interesante de aplicar la noción de congruencias.

Para determinar el resto de la división de el por no es suficiente para encontrar un número entero r tal que elr (mod no) donde 0 r < no. Por ejemplo, para determinar el resto de la división de 310 por 13 hicimos 310 y luego dividirlo por 13, lo que no es fácil. Sin embargo, la noción de congruencia facilita enormemente este procedimiento. Primero notamos que:

33 ≡ 1 (mod 13), ¡esto es fácil!

Ahora, al elevar todo al cubo, obtenemos

(33)3 ≡ (1)3 mod 13 es decir 39 ≡ 1 (mod 13).

Si multiplicamos ambos lados de la congruencia por 3, entonces obtenemos 310 ≡ 3 (mod 13).

Las computadoras de hoy han alcanzado niveles tan sofisticados que cualquier sistema criptográfico debe ser lo suficientemente robusto como para resistir los ataques de las personas que desean romper la seguridad de sus transacciones.

En 1975, los matemáticos W. Diffie y M. Hellman propusieron un sistema de cifrado completamente nuevo: la criptografía de clave pública. En este método de codificador se utilizan dos teclas: una para codificar y otra para decodificar. Se desarrollaron algunos métodos específicos para implementar las ideas de Diffie y Hellmann. Sin embargo, el método más compatible que sigue siendo el predeterminado es el sistema RSA.

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

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

(2) un entero E, conocida como clave de codificación, que satisface las siguientes propiedades: el máximo común divisor (MDC) entre E y el producto (p - 1) (que - 1) es 1, y el MDC entre 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)).

Observamos que 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.

Codifiquemos el mensaje CLAVE PUBLICA utilizando el sistema RSA con N = 2537 y clave de cifrado E = 13. Primero, notamos que N = 43.59 donde 43 y 59 son números primos.

Por lo tanto, MDC (13, (43 - 1) • (59 - 1)) = MDC (13, 42 • 58) = 1, ya que el entero 13 no divide 42 ni 58; MDC (13, 2537) = 1, porque 13, 43 y 59 (2537 = 43 • 59) son números primos. Ahora convertimos el texto usando la tabla de correspondencia de letras y números:

A = 00, B = 01, C = 02, D = 03,…, X = 23, Y = 24, Z = 25.

Como N = 2537 contiene 4 dígitos, envolvemos el texto en pares de letras:

PU BL IC KE Y

y completa el último bloque con la letra C conseguir

<>

PU BL IC KE YC<>

.

Usando la tabla de conversión anterior, los 5 bloques de mensajes convertidos son:

1520 0111 0802 1004 2402.

Llamaremos a B el bloque de cuatro dígitos. El siguiente paso es calcular el valor de cada uno de los bloques de cuatro dígitos elevados al exponente 13 (mod 3127), es decir, dado un bloque B, queremos determinar C de modo que C = P13 (mod 2537).

Por ejemplo, cuando codificamos el primer bloque, tenemos que resolver C ≡ 152013 r (mod 2537). Luego procedemos de la siguiente manera:

<>

15202 = 2.310.400 = 910 • 2537 + 1730 ≡ 1730 (mod 2537);

<>

15204 = 17302 = 2,992,900 = 1179 • 2537 + 1777 ≡ 1777 (mod 2537);

<>

15208 = 17772 = 3.157.729 = 1244 • 2537 + 1701 ≡ 1701 (mod 2537);

<>

152012 = 15208.• 15204 = 1701 • 1777 = 3.022.677 = 1191 • 2537 + 1110 =

<>

= 1110 (mod 2537);

152013 = 152012 • 1520 = 1110 • 1520 = 1,687.200 = 665 • 2537 + 95 = 95 (mod 2537).

Por lo tanto, la codificación de 1520 es 0095.

Los otros bloques de mensajes están codificados de la misma manera, es decir, cada bloque consta de cuatro dígitos que se elevan a la potencia 13 (mod 2537). Por lo tanto, el receptor recibirá el mensaje cifrado:

0095 1648 1410 1299 0811.

Tenga en cuenta que no podemos convertir este mensaje en letras, ya que algunos pares de dígitos constituyentes de bloque son mayores que 25. En la siguiente columna tomaremos los pasos para decodificar mensajes de acuerdo con el sistema RSA y decodificar el mensaje de este ejemplo.

Volver a las columnas

<