Números primos y criptografía

(ParteAguas, enero y julio de 2010)

 

Dice un proverbio matemático que “los números naturales fueron hechos por Dios; todo lo demás es obra del hombre”, y nos da a entender que lo más elemental de nuestro pensamiento matemático, y que es la base de todo lo que se ha hecho después, son los números naturales 1, 2, 3,… Está grabado en el cerebro de los la habilidad para contar, y los números naturales no son más que una asociación entre los grupos que formamos de un elemento, dos elementos, tres elementos, etc. La primera distinción es entre uno y muchos. El número 1 corresponde a uno, y todos los demás naturales, a muchos. La aritmética más primitiva es la que nada más distingue estas dos cantidades. Muy temprano en su historia, el hombre aprendió a distinguir dos de tres, tres de cuatro, etcétera, y este proceso milenario se repite en cada niño que aprende a contar y aprende los números.

Los pueblos antiguos tuvieron su forma, cada uno, de representar los números; la forma que utilizamos hoy en día, manejada en todo el mundo, es uno de los muchos avances matemáticos atribuidos a los árabes. La notación arábiga 1,2,3,… y la notación que utilizaban los Romanos I, II, III, IV,… no son mera cuestión de usos, o una preferencia que cualquiera de nosotros podría ejercer a favor de la numeración. Hay una diferencia enorme entre las ventajas de la numeración arábiga con respecto a la numeración romana. Si algún lector no está convencido, lo invito a que haga la multiplicación 3498×572 utilizando números romanos: MMMCDXCVIII x DLXXII. La primera prueba de esta complejidad es que ninguna calculadora hace operaciones en números romanos; la segunda, intentar hacerlo a mano.

¿Por qué es tan complicada la aritmética con los números romanos?Observemos algunas diferencias: al principio, la notación romana es más “natural”, puesto que resuelve el problema de escribir el número dos juntando el mismo símbolo utilizado para el uno, II. Con el tres, se vuelve a utilizar ese recurso: III. Esto es algo parecido a escribir palitos en el pizarrón para contar los votos de una clase: I, II, III, IIII, IIII, IIII I, etc. Es un método muy sencillo, muy poco imaginativo, e increíblemente laborioso. Con el cuatro, algunos habrán observado que en los relojes que utilizan números romanos ese número está escrito como IIII, no como IV. El cinco se escribe definitivamente con un nuevo símbolo, V. Entonces, para los primeros 5 números la numeración arábiga utiliza cinco símbolos 1,2,3,4,5 y la numeración romana utiliza nada más dos I,V; con este razonamiento, es más sencilla la notación romana. Hasta el nueve, tenemos nueve símbolos con la notación arábiga, y tres símbolos con la romana; el nuevo es X, que representa diez. Y este número mágico, el diez, aparece la diferencia sustancial entre una y otra forma: la notación romana se sigue por el camino viejo de ir creando nuevos símbolos, y la arábiga introduce el cero y la notación posicional: 10 = X. Cuando llegamos al cien, los Romanos utilizaron otro símbolo, C, y la numeración arábiga introduce otro cero: 100. ¿Cómo se escribiría 100,000,000,000 en números romanos? Yo no sé.

La idea de escribir a diez como 10 no es nada más una cuestión de notación, de llamarle John al que se llamaba Juan. Es mucho más: es la introducción del número cero, que pocos pueblos llegaron a desarrollar (por ejemplo, los mayas), y que simplificó enormemente el desarrollo posterior de todas las matemáticas. No es exagerado afirmar que no tendríamos aviones, ni computadoras, ni radios, ni concreto hidráulico, ni el Aleph de Borges, ni conoceríamos el ADN si no conociéramos el cero; todos los avances científicos están basados en las matemáticas, y una notación como la romana, que entorpece inimaginablemente las operaciones más elementales, entorpecerá todo el desarrollo de la ciencia, y por consiguiente, de la técnica. Para los incrédulos recordaremos que todas las computadoras se basan en la aritmética binaria, aquella donde todos los números se representan utilizando solamente dos símbolos: el uno y el cero, precisamente. Sin cero, no hay computadoras.

No todos los números son iguales. El cero tiene la característica distintiva de que si lo sumamos con cualquier otro, conservamos el otro número: N+0 = N. El uno funciona de manera parecida, aplicando la multiplicación: Nx1 = N. La siguiente clasificación son los números primos, aquellos mayores que 1 y que solamente son divisibles entre 1 y entre ellos mismos, como 2, 3, 5, 7, 11, 13, etc. Cualquier número que pueda expresarse como factor de otros números más pequeños no puede ser primo. Por ejemplo, 4 = 2×2, 9 = 3×3, 12 = 4×3, 20 = 10×5, etc. ¿Cómo se factoriza 1000? ¿Y 1001? ¿Y 1002? Unos momentos de reflexión nos dan una pauta: 1000 y 1002 son números pares, es decir, múltiplos de 2: 1000 = 500×2, 1002 = 501×2. Pero a simple vista, 1001 no nos da una clave de sus factores. Descartamos el 2 porque no termina en número par, el 3 porque la suma de sus dígitos no es múltiplo de 3, el 5 porque no termina en 0 ó en 5, y cuando tratamos el 7, vemos que 1001 = 7×143; después de un poco de trabajo, lo resolvimos. Sin embargo, tomemos un día al azar del año 2009, consigamos en el internet el monto de la deuda pública de México, y tratemos de averiguar si es un número primo o no. Sufriremos durante un buen rato, posiblemente sin resolver el problema.

¿Por qué son tan importantes los números primos? La razón más importante es la que está expresada en el Teorema fundamental de la Aritmética: todo número natural N puede expresarse como producto de números primos, N = p1p2…pn, y esta representación es única salvo por el orden. Por ejemplo, 4 = 2×2, 12 = 2x2x3, 500 = 100×5 = 2x50x5 = 2x5x10x5 = 2x5x2x5x2 = 2x2x2x5x5. Las dos últimas expresiones son la misma, salvo el orden en que están presentados los factores primos 2 y 5. El número que factorizamos arriba, 1001 = 7×143 = 7x11x13. Con este número batallamos un poquito. ¿Y con 6901? ¿Y con 280123? En vista de las dificultades para poder factorizar un número, nos sentimos inclinados a pensar que ese teorema podrá ser todo lo fundamental que quieran los matemáticos, pero es de poca utilidad: si es tan difícil factorizar números, ¿entonces de qué nos sirve? Si alguien estuvo pensando en esta objeción, hay que felicitarlo, porque acaba de descubrir el secreto de la criptografía.

Los números primos están metidos en la lista de los números naturales de una manera azarosa. Tal parece que Dios, cuando hizo estos números, nos dejó sembradas algunas claves no obvias, para que las fuéramos descubriendo. Si hacemos una lista de los que nuestra paciencia nos permite, escribiremos algo así como 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, etc. ¿Cuántos hay? ¿Es una lista infinita la de los números primos?

Un teorema tan viejo como la cultura griega nos dice que los números primos son infinitos. La prueba es por reducción al absurdo, es decir, se supone que la lista es finita, y de ahí se argumenta para llegar a una contradicción. El argumento es sencillo: supongamos que tenemos un número finito de primos p1, p2, p3,…pN. Consideremos ahora el número M = (el producto de todos los primos) + 1 = (p1 p2 p3…pN) + 1, y cuestionemos si M es primo o si no lo es. Es claro que M es mayor que cualquiera de los números primos, puesto que el producto de dos números mayores que 1 es mayor que cualquiera de los factores. Si M fuera primo, entonces tendríamos un número primo mayor que todos los números primos, en particular mayor que sí mismo, y eso es una contradicción. Si M no es primo,

Entonces, tenemos una cantidad infinita de números especiales, los primos, distribuidos de una manera aparentemente aleatoria en la lista de todos los números naturales. Y con estos bueyes tenemos que arar, como dice el refrán mexicano. La dificultad para factorizar un número cualquiera en sus factores primos es precisamente la ventaja que utilizan los desarrolladores de algoritmos para codificar los números de tarjetas de crédito, para almacenar bases de datos encriptadas, etcétera.

Estafas viejas y estafas modernas. El engaño de aquel que lo aborda a uno con un billete de lotería premiado que no se anima a cobrar porque le da vergüenza, seguirá existiendo mientras haya inocentes que quieran creerlo. Ahora, las estafas son más sofisticadas, se realizan con herramientas matemáticas avanzadas, y muchas veces la víctima se da cuenta hasta tiempo después. ¿Cómo se realizan? Espiando las operaciones que se realizan en el internet y apropiándose de los datos necesarios para después operar con la tarjeta de crédito de uno, con nuestras cuentas de banco.

El internet es como un quinto patio, como patio de vecindad: ahí, todo el que quiera escuchar se da cuenta de lo que le sucede al del departamento 1, a la señora del 2 que la golpea el marido, a la familia que fue abandonada por el padre, se entera de todo. ¿Cómo? Interceptando los mensajes que viajan en el internet, porque todo lo que circula ahí, teniendo el equipo adecuado, es posible interceptarlo y copiarlo, y luego dejar que siga su camino.

Es imposible crear en internet un canal de datos tan seguro que nada más los interesados puedan ver lo que circula por ahí, eso es un hecho. Lo que se hace entonces es hacer transitar por el internet, en vez del mensaje original, basura, es decir, mensajes codificados e ininteligibles, que en caso de ser interceptados, no tengan valor para el enemigo. La codificación de mensajes se puede realizar lo mismo para cartas, para transacciones comerciales individuales, para grandes operaciones entre bancos, para la voz humana. En este último caso, se distorsiona en el lado del que habla, se transmite distorsionada, y el que la recibe primero la regresa a su forma original, y luego la escucha.

Con esta Biblioteca de Babel que es el internet, que lo mismo sirve para crear enormes depósitos de información para el público (como www.wikipedia.org), sitios donde las empresas ofrecen una cara al público, correspondencia privada, chateo, y operaciones comerciales, ha sido necesario que los matemáticos y científicos que toman parte en esta guerra de proteger/interceptar mensajes, hayan estudiado muchas técnicas para volver el internet más seguro, los unos, y un botín de crackers, los otros.

Clave privada. Hasta ahora, conseguimos un método casi infalible para encriptar mensajes y mantenerlos protegidos, tomando el mensaje M, una clave C que es igual al contenido de un CD que hayamos acordado con la persona a quien le vamos a mandar el mensaje. El proceso consiste en hacer M’ = M XOR C, y es M’ lo que le enviamos al destinatario. Nuestro procedimiento es seguro, mientras nadie se entere de cuál es el CD que estamos usando.

A nivel de dos usuarios, el método es perfecto. De vez en cuando se cambia la contraseña (es decir, acordamos un nuevo CD) y todo funcionará bien mientras nuestros CD sean privados. Es decir, este método es bueno para correspondencia privada.

Este método tiene sus pros y sus contras. Es prácticamente imposible romperlo a menos que se conzca la clave, pero queda el problema de que hay que mantener en secreto a C. Cuando crece el número de personas que necesitan encriptar mensajes, este proceso se vuelve insostenible, por la dificultad práctica de poner en contacto directo a cada pareja de usuarios, para que entre ellos fijen cuál va a ser la clave C, sin que se enteren otros usuarios. Ya que la clave C se mantiene en secreto entre las partes, este método es lo que se llama de clave privada.

Es decir, toda la eficacia del método anterior radica en que los otros usuarios no se enteren de la clave. Ahora bien, ¿qué pasa cuando los usuarios ya no son individuos, sino empresas? ¿Cómo se pueden reunir y poner de acuerdo dos empresas sobre una clave? ¿Qué pasa cuando hay millones de transacciones a través del internet cada día, y todas necesitan ser protegidas? Sencillamente, el método descrito, de fijar por adelantado una clave muy grande, no puede funcionar.

Clave pública / privada. Toda la dificultad radica en compartir la clave. Para sortear este problema, en la década de los setentas se les ocurrió a dos matemáticos, W, Diffie y M. Hellman, la idea de hacer una clave compuesta de dos claves, digamos C = C1 ¤ C2, donde el símbolo ¤ indica una manera de relacionar ambas claves (todavía indefinida), de tal manera que sea necesario disponer de las dos para completar el proceso de desencriptar. Podría enviarse una de las dos claves en forma pública, conservar la otra para usarla en privado, y se tendría entonces la seguridad deseada. Este esquema de compartir a medias una clave C, se llama (en forma muy adecuada) de clave pública  / privada, y es el que se utiliza en la mayoría de las transacciones comerciales, como transferencias de fondos realizadas por particulares, compras con tarjetas de crédito en el internet, etc.

Se puede sospechar que con estas condiciones, las claves C1, C2 no pueden ser muy independientes, algo así como que cada quien diga el número que está pensando, sino que deben de tener alguna relación estrecha entre ellas. Efectivamente, el método que vamos a ver produce ambas claves C1, C2 en una forma que las relaciona, que es un procedimiento simple en principio (la dificultad para factorizar en números primos) pero que es laborioso para números muy grandes. Analizaremos las matemáticas que se usan para esto.

La mayoría de los matemáticos consideran que Carl Friedrich Gauss ha sido el más grande matemático de todos los tiempos. Una memoria y una inteligencia prodigiosas, alguien brillantísimo que surgió de la nada, puesto que su padre era un trabajador manual y sus genes no se habían cultivado durante generaciones, como en el caso de J.S.Bach, de la familia Bernoulli, o de Mozart. Hizo muchos descubrimientos matemáticos, aplicó la geometría al cálculo de superficies grandes y otros muchos en diversas ramas de las matemáticas. Veremos ahora uno de los más sencillos, aunque ha probado ser de mucha importancia. Es la llamada aritmética modular. Todos tenemos experiencia con ella, por la división del día en 24 horas. Supongamos que son las 9 de la noche en México, y queremos conocer la hora en China. ¿Cómo le hacemos? Lo primero es ver que aquí manejamos la franja horaria GMT-6 = hora del meridiano de Greenwich -6, y que en China tienen GMT + 8; nosotros vamos retrasados 6 horas con respecto a la de Greewich, y los chinos van adelantados 9 horas. La diferencia entre nosotros será 6 + 9 = 15 horas. Entonces, a las 21 horas (9 de la noche) le sumamos 15, y obtenemos las 36 horas, que es una hora inexistente: nunca pasamos de 24. ¿Qué hacemos? Sencillamente, restamos 36-24 = 12, y eso quiere decir que cuando aquí son las 9 de la noche del 7 de mayo, en China son las 12 del día del 8 de mayo. Esta operación, que es familiar para todos nosotros, se escribe así:

21 + 15 ≡ 12 (mod 24)

y se lee “módulo 24”. El número 24 no tiene nada de particular. Puede hacerse aritmética modular con cualquier número n > 1. Otro candidato es el 12. Si estamos a las 11 de la mañana, y calculamos que nos faltan 4 horas para terminar el trabajo, entonces rápidamente hacemos la cuenta 11 + 4 ≡ 3 mod (12), sin tener que pensar en Gauss. La aritmética modular, como se llama esta forma de sumar, es muy sencilla de entender y ha tenido muchas aplicaciones interesantes en la matemática. Seguramente Gauss nunca imaginó que hoy servirían sus descubrimientos para encriptar mensajes, pero así resultó.

Una propiedad importante de esta aritmética modular es que limita el universo de los números con los que está uno trabajando: en vez de ser un número infinito, quedan nada más n números, porque después del número que tomamos como referencia, se vuelve a  iniciar la cuenta. Por ejemplo, tomando en cuenta el 12, todos los números que se requieren son 0, 1, 2, 3,…10, 11. Si usáramos el 24, la cuenta empezaría en 0 y terminaría en 23, y así sucesivamente.

Dentro de los números, los más importantes son los números primos. La aritmética modular para los números primos puede entenderse mejor haciendo un contraste con el caso que ya conocemos, módulo 24. Las 24 horas del día se dividen de forma natural en dos relojes de 12 horas, y de hecho, así son las carátulas de casi todos los relojes. Sabemos que “cada 12 horas” se junta un día, es decir 12 + 12 ≡ 0 (mod 24). En el caso de 24 horas, también contando de 2 en 2, de 3 en 3, de 4 en 4, y de 6 en 6 podemos juntar exactamente un día. Por ejemplo 6 + 6 + 6 + 6  ≡ 0 (mod 24). ¿Qué tiene de particular el 24 para que se pueda contar de esta manera? Es fácil averiguarlo, escribiendo la última operación como una multiplicación: 6 ∙ 4  = 24, y por lo tanto, 6 ∙ 4  ≡ 0 (mod 24), es decir, hemos factorizado a 24 como el producto de 6 y 4. Y esa es toda la cuestión: si podemos hallar factores del número n que estamos tomando para operar módulo n, eso quiere decir que el reloj de n horas puede ser dividido, así como dividimos el reloj del día en dos relojes de 12 horas.

Ahora vamos a verlo al revés: consideremos un número que no tiene divisores, es decir, consideremos un número primo p, por ejemplo el 23. Si nuestro día tuviera 23 horas en vez de 24, entonces no podríamos dividir el día en “medio día”, no habría un “mediodía”, una hora exacta que fuera la mitad del día. Más aún, con un día de 23 horas no podríamos dividirlo de manera regular en 3 ni en 4 ni en ningún otro número. No habría forma de poner tres turnos de x horas para otras tantas jornadas de trabajo, etc.

Como un ejemplo, vamos a formar una tabla con la suma módulo 7. El lector podrá comprobar personalmente los resultados que presentamos.

+ 0 1 2 3 4 5 6
0 0 1 2 3 4 5 6
1 1 2 3 4 5 6 0
2 2 3 4 5 6 0 1
3 3 4 5 6 0 1 2
4 4 5 6 0 1 2 3
5 5 6 0 1 2 3 4
6 6 0 1 2 3 4 5

Los números en la columna de la izquierda, y los de la fila superior, son los sumandos de la operación que queremos hacer, semejante a encontrar la distancia entre dos ciudades que viene en la Guía Roji Nacional. Por ejemplo 4 + 5 ≡20 (mod 7), leyendo el resultado en la fila del 4, cruzada con la columna del 5. Esta tabla se conoce como el grupo aditivo de los enteros módulo 7, y se utiliza el símbolo Z7.

La tabla de Z4 y de Z12 son las siguientes:

+ 0 1 2 3
0 0 1 2 3
1 1 2 3 0
2 2 3 0 1
3 3 0 1 2
+ 0 1 2 3 4 5 6 7 8 9 10 11
0 0 1 2 3 4 5 6 7 8 9 10 11
1 1 2 3 4 5 6 7 8 9 10 11 0
2 2 3 4 5 6 7 8 9 10 11 0 1
3 3 4 5 6 7 8 9 10 11 0 1 2
4 4 5 6 7 8 9 10 11 0 1 2 3
5 5 6 7 8 9 10 11 0 1 2 3 4
6 6 7 8 9 10 11 0 1 2 3 4 5
7 7 8 9 10 11 0 1 2 3 4 5 6
8 8 9 10 11 0 1 2 3 4 5 6 7
9 9 10 11 0 1 2 3 4 5 6 7 8
10 10 11 0 1 2 3 4 5 6 7 8 9
11 11 0 1 2 3 4 5 6 7 8 9 10

La característica del número 12 que hemos analizado, que puede descomponerse en factores más pequeños, está representada por la presencia del cero en la diagonal, correspondiente a la suma 6 + 6 ≡ 0 (mod 12). En cambio, en Z7 no existe ningún cero en la diagonal, ni lo vamos a encontrar en la diagonal de ningún Zp donde p es un número primo. En cambio, en la tabla de Z4 encontramos el 0 en la diagonal, correspondiendo a 2 + 2, y precisamente, 4 no es primo.

Si el lector se da cuenta, no estamos más que diciendo “4 no es primo porque se puede factorizar como 22”, y “como podemos factorizar a 4 = 22, entonces 4 no es primo”. Es decir, estamos diciendo lo mismo con diferentes palabras. Una buena parte de las matemáticas no es más que esto, decir lo mismo con otra formulación. Es como decir piropos a una mujer: no se le puede decir siempre “qué hermosa eres”, porque ella terminará por fastidiarse de uno, hay que decirle lo mismo, pero con otras palabras. Pero sugiero usar con precaución variaciones extremas como “la simetría de tu rostro me recuerda la belleza de  Z12”, corremos el peligro de ser incomprendidos.

Para los que son alérgicos a los números, hay una manera gráfica de entender este asunto, analizando las gráficas de estrellas. Seguramente todos hemos formado una estrella de 5 puntas con uno solo trazo de lápiz, sin levantarlo y sin salirnos de la estrella. Es muy fácil: en un círculo ponemos los cinco puntos que corresponden a los vértices de la estrella, y los numeramos 0, 1, 2, 3, 4. Ponemos el lápiz en el vértice 0, y lo unimos con una recta con el vértice 2. Luego unimos el 2 con el 4, el 4 con el 3, y terminamos uniendo el 3 con el 0.

Ahora bien, tratemos de hacer lo mismo con una estrella de 6 puntas, y aquí no es posible formarla con un solo trazo, sin despegar el lápiz ni poner rectas que no estén uniendo un vértice con otro. Lo que aquí podemos obtener, lo mejor que puede resultar en este caso, es la estrella de 6 puntas, la Estrella de David, símbolo de Israel.

Ensayemos el caso n = 7. Como le hicimos con 5, indicaré nada más la secuencia de vértices, que gráficamente consistirá en “brincar dos vértices” para formar la recta correspondiente: 0, 3, 6, 2, 5, 1, 4, 0. Probablemente el lector ya sospecha que con n = 8 no se puede, y tampoco con n = 10, y después de un rato de trabajo, vemos que  con n = 9 sí es posible, haciendo saltos de 2 en 2: 0, 2, 4, 6, 8, 1, 3, 5, 7, 0.

El caso n = 8 no puede resolverse de esta manera. ¿Será cuestión de tomar un número impar? Sugerimos al lector intentarlo por sí mismo. Puede tratar por separado los casos pares e impares, y los de un número primo.

 

Pierre Fermat fue un abogado que vivió en Francia de 1601 a 1665. Se interesó por las matemáticas cuando ya estaba en los treintas y siempre se acercó a ella como pasatiempo; sin embargo, los pasatiempos de los genios son superiores a toda una vida de dedicación de gentes menos dotadas. Trabajó mucho con Teoría de los Números, una rama de las matemáticas que podemos identificar con la Aritmética, en particular con los relojes de Gauss, y realizó algunos descubrimientos importantes. Por ejemplo el siguiente, que usaremos más adelante:

Pequeño Teorema de Fermat. Supongamos que a es un número natural, y que p es un número primo que no es un divisor de a, es decir, no es parte de sus factores primos. Entonces sucede que

p divide a ap-1-1 (1)

Vamos a ilustrarlo con un ejemplo. Necesitamos dos números a, p, tales que p sea primo que no aparece en la factorización de a. Tomemos a = 8 = 222, y p = 5, que no es factor de 8. En este caso ap-1 – 1 = 85-1 – 1 =  84 -1 = 4096 – 1 = 4095, que efectivamente es divisible entre 5. Y cualquier combinación de números que satisfagan las condiciones exigidas, se cumplirá la consecuencia. Por ejemplo, podemos tomar a = 123457, p = 29, y sin necesidad de hacer operaciones horrorosas, sabemos que 1235729-1 = 1235728 es divisible entre 29.

La expresión (1) es un poco incómoda, y se puede decir de otra manera, utilizando los relojes de Gauss; observemos que (1) es lo mismo que decir que para algún número b, tenemos que pb = ap-1-1, y por lo tanto pb +1 = ap-1, y aquí aplicamos la aritmética módulo p, porque pb ≡ 0 (mod p), y por lo tanto pb +1 ≡ ap-1 (mod p), y entonces 0 +1 ≡ ap-1 (mod p), o lo que es lo mismo, ap-1 ≡ 1 (mod p). Reformulamos entonces

Pequeño Teorema de Fermat. Supongamos que a es un número natural, y que p es un número primo que no es un divisor de a, es decir, no es parte de sus factores primos. Entonces sucede que

ap-1 ≡ 1 (mod p) (1bis)

Fermat tenía la mala costumbre de no probar muchas de sus afirmaciones. El resultado que mencionamos fue probado tiempo después por Euler, pero otro de sus teoremas sobrevivió varios siglos sin tener una prueba, y es el que se conoce como el Gran Teorema de Fermat: si n es un entero > 2, entonces no hay tres enteros positivos a, b, c que satisfagan la ecuación an + bn = cn . Este resultado fue probado hasta 1995, aunque había sido conjeturado desde 1637.

La Teoría de Números es una parte de las matemáticas muy especial: muchos de sus resultados son fáciles de comprender cuando se enuncian; sin embargo, las pruebas duran a veces tres siglos y medio, como en el que acabamos de mencionar.

Números primos. La manera de averiguar que un número N es primo es muy sencilla en teoría: vemos si tiene divisores diferentes de 1. En la práctica, como sucede muy seguido con las Matemáticas, es bastante más difícil. En el artículo pasado vimos algunos ejemplos de números y la dificultad de hacerlo con una calculadora. Podríamos pensar que ya con computadoras, cualquier cálculo numérico puede hacerse en un instante, pero tampoco es cierto. El enfoque de fuerza bruta para ver si un número N es primo es buscar todos los primos hasta antes de √N para ver si dividen a N. Así, probaríamos con 2, 3, 5, 7, 11, 13, 17, etc., hasta llegar a √N. Con las actuales computadoras, este procedimiento tardaría años para ver si un número relativamente grande, digamos de unas 200 cifras, es primo o no es primo. No hay negocio, ni proyecto, ni experimento científico que tenga paciencia de años nada más para averiguar si N es primo.

Los matemáticos se fijaron en un caso particular del Pequeño Teorema de Fermat, cuandoa = 2. En este caso, cualquier primo p > 2 no será un factor de 2 (los factores de cualquier número tienen que ser menores que ese número), y por lo tanto se tiene que cumplir que2p-1 ≡ 1 (mod p). Razonando a la inversa, si tenemos que no es cierto que 2p-1 ≡ 1 (mod p),entonces p no puede ser primo. Y resulta que este es un cálculo bastante más sencillo que los anteriores, entonces puede servir para descartar en algunos casos que p sea primo. Y en el caso que se cumple  2p-1 ≡ 1 (mod p), no es suficiente para decidir. Por ejemplo, p =  341 = 11 31, no es un primo y sin embargo cumple la condición mencionada.

El Pequeño Teorema de Fermat nos da una condición que todos los primos deben de satisfacer; sin embargo, no es suficiente, porque hay otros números que la cumplen, y que no son primos. Es como decir “Los pájaros tienen alas y vuelan”. Sirve para desechar algunos casos, digamos a las gallinas, que tienen alas pero no vuelan, no pueden ser pájaros. Pero los aviones también tienen alas y vuelan, y no son pájaros.

La conclusión de los dos párrafos anteriores es sencilla: es difícil averiguar si un número es primo, y es todavía más difícil descomponerlo como un producto de primos. Aquel teorema de Euclides, tan apreciado por los matemáticos teóricos, es el campo de batalla en donde luchan los criptógrafos de uno y otro bando: los que codifican mensajes, y los que tratan de romper la seguridad.

Codificación. Cualquier archivo de computadora y cualquier mensaje que circula por el internet, no es más que una lista de bits y bytes; por lo tanto, puede interpretarse como número. Quizá el número es muy grande, pero sigue siendo un número. Resultó más sencilla para su desarrollo la codificación de mensajes, si nos olvidamos del significado original del mensaje y lo pensamos como un número. Probablemente varios números, no uno solo: un mensaje muy largo puede componerse de muchas “cifras”, digamos si organizamos los bytes del mensaje en grupos de 8, de 16, 32 o 64. La manipulación de estos mensajes, su encriptamiento y se desencriptamiento, serán entonces operaciones con números.

Ya sabemos que no basta con volver muy incomprensible un mensaje, necesitamos regresarlo a su estado original. Las operaciones que re realizan con los mensajes, pensados como números, son casi siempre multiplicaciones. La razón es que la suma es demasiado sencilla para producir un buen nivel de seguridad. Si vamos a multiplicar un mensaje M (considerado como número) por otro número C,  M’ = MC, después tendremos que dividir entre C para regresar al mensaje original. Aquí es donde aparecen los números primos, porque con ellos es relativamente más sencillo operar.

Lo que sucede en el internet. Con los conceptos que hemos visto, ya podemos dar una idea de cómo se realizan la protección de transacciones en el internet. En el cuadro que sigue, A es un usuario de internet, digamos alguien que va a pagar un boleto de avión con tarjeta de crédito, y B es la línea aérea que recibe la transacción. M es el mensaje, donde se codificarán el nombre del usuario, número de tarjeta, dígitos de verificación y la cantidad objeto de la operación.

Cada renglón del siguiente cuadro es una etapa en la operación.

Etapa Participantes Evolución del mensaje
1Escritura del mensaje A entra al sitio de Lufthansa y busca un boleto México-Frankfurt. Juan Pérez, 12.9.2010, México-Frankfurt, 22:00, $2,500USDlls.La información está localmente, en la máquina de Juan
2Justificación (padding) del mensaje M’ = M rellenado para que tenga una longitud adecuada Juan Pérez, 12.9.2010, México-Frankfurt, 22:00, $2,500USDlls.010101EL mensaje justificado se interpreta como número, es decir, nada más binario
3Encriptamiento del mensaje B proporciona una clave C =  C1 ∙ C2, que es el producto de dos números primos muy grandes Se encripta el mensaje anterior comoΓ = M’ ∙ C

El mensaje encriptado es simplemente un número.

4Circulación en internet El mensaje viaja de México, DF, a Frankfurt, sede de Lufthansa Lo que viaja por la red es el mensaje encriptado Γ
5Opcional: un enemigo intercepta el mensaje El enemigo intercepta Γ.Para desencriptar Γ, hay que encontrar (o tener por anticipado, o robar) los factores primos de C, que son C1 y C2. Toda la seguridad del internet radica en la esperanza de que el enemigo se tarde lo suficiente para volver inútil la información robada.
6El mensaje encriptado llega a b B realiza el proceso inverso de encriptamiento M’ = Γ/CM se obtiene después de quitar la justificación del paso 2.

Futuro. La guerra de codificadores vs. Intrusos es tan vieja como el hombre; desde la antigüedad ha habido, y seguirá habiendo, información que algunas personas no quieren que las sepan otras. El internet, con su enorme crecimiento en los últimos treinta años, ha sido un detonador para crear programas cada vez más sofisticados que protejan o que expongan la información.

En este momento se está descansando en la inhabilidad de las computadoras actuales, con los algoritmos actuales, para encontrar rápidamente los factores primos de números muy grandes. Si se descubriera un método para factorizar extremadamente rápido, la seguridad actual de internet se volvería inútil. Entonces, los de RSA y otras empresas que protegen información rezan porque no aparezca un genio que les rompa su código, y que si aparece, sea uno de ellos mismos.

[i]


[i] El autor agradece la revisión del trabajo por parte de Rodrigo Gómez C., y la colaboración artística de Fernando Ortiz Gómez.


Comments

Números primos y criptografía

Hacer un comentario: