archivo

Archivo de la etiqueta: Criptografía


Desde los comienzos de QBlog, nos propusimos incluir no sólo información relacionada con el Sinclair QL o la retroinformática, sino que además vimos adecuado compartir cualquier otro tipo de información interesante y que nos pueda ayudar a nosotros mismos o a cualquier lector ocasional de nuestro Blog.

En este sentido, regularmente incluimos artículos genéricos como el de este post. Aunque es un poco largo lo considero muy interesante porque se adentra en la parte “oscura” para muchos de nosotros (al menos para mi) y que se refiere a términos muy actuales como la firma digital, firma de documentos, clave pública, clave privada, …

Hace algunas semanas ya presentamos una pequeña introducción, muy simple al tema de la criptografía, en esta entrada seguiremos con el tema para ya adentrarnos en conceptos más prácticos y muy de moda en los últimos tiempos.

El contenido de este post se basa en un extracto de texto (que yo tenía en algunos de mis apuntes sobre cifrado y firma de datos) tomado de un libro titulado “Camino al futuro” del año 1996 del propio Bill Gates (al menos eso decía la portada). Por desgracia no conservo ese libro, pero si mis apuntes que había tomado de ese libro.

Superado este preámbulo entremos en materia, aquí les pongo el mencionado extracto según los recogí en mis apuntes. Es un poco largo pero se lee y comprende muy bien, creo que merece la pena.

Los mensajes cifrados se están manifestando como un elemento clave en las comunicaciones por la red y por buenas razones. Sin transacciones seguras, incluyendo las transacciones financieras, es difícil imaginar que alguna red interactiva se convierta en un mercado seguro.

Cuando enviemos un mensaje en la autopista de la información “firmado” por nuestra computadora u otro dispositivo de información con una firma digital que sólo será capaz de reconocer usted y será puesta en clave de manera que sólo pueda descifrarla el receptor deseado. Enviamos un mensaje que puede ser información de cualquier clase, incluyendo video o dinero digital. El receptor verá que el mensaje es nuestro, que se envió en el momento indicado, que no se ha forzado lo más mínimo y que los demás no puede descifrarlo.

El mecanismo que hará esto posible se basa en las funciones irreversibles y en la codificación de clave pública. Voy a ocuparme sólo muy ligeramente de estos conceptos avanzados.

Para la codificación necesitamos de las funciones irreversibles, una función irreversible es algo que es mucho más fácil de hacer que deshacer (romper un cristal es una función irreversible). Pero la clase de función irreversible que sirve en la criptografía es aquella que resulta fácil de deshacer si conocemos una pieza de información extra y que es muy difícil de deshacer si no disponemos de esa información. En matemáticas hay un cierto número de tales funciones. Una de ellas utiliza los números primos. Todos los niños aprenden en la escuela lo que son los números primos. Un número primo no puede ser dividido nunca por otros números que no sean él mismo y el uno. Ente los primeros doce números, los primos son 2, 3, 5, 7 y 11. Los números 4, 6, 8 y 10 no son primos porque todos son divisibles por 2, además de por sí mismo. El número 9 no es primo porque es divisible por 3. El número de números primos es infinito y no hay ninguna regla para ellos, excepto que son primos. Cuando multiplicamos los números primos entre si obtenemos un número que sólo es divisible por ellos dos (a parte de por el uno y el propio número). Por ejemplo, 35 sólo es divisible por 5 y por 7. La búsqueda de números primos se llama descomposición factorial. Si descomponemos factorialmente el 35 obtenemos el 5 y el 7.

Resulta fácil multiplicar los números primos 11927 y 20902 y obtener el número 249301081, pero resulta más dificil hallar, a partir del producto 249310081, los dos números primos por los que es divisible. Esta función irreversible que consiste en multiplicar números primos que son difíciles de descomponer factorialmente a partir del producto, es la base de un ingenioso y sofisticado sistema de codificación. Incluso las más grandes computadoras les lleva mucho tiempo descomponer un producto verdaderamente grande en sus números primos constituyentes.

Un sistema de comunicación basado en la descomposición factorial utiliza dos claves diferentes de descodificación: una para cifrar un mensaje y otra diferente pero relacionada para descifrarlo. Cuando se tiene sólo la clave del cifrado es fácil codificar el mensaje, pero descodificarlo es un periodo de tiempo práctico es casi imposible. Descifrar un mensaje requiere una clave separada disponible sólo para el receptor pretendido del mensaje o más bien para la computadora receptora. La clave de codificación se basa en el producto de dos grandes números primos, mientras que la clave de descodificación se basa en los números primos en sí mismos. Una computadora puede generar un nuevo par de claves únicas en un momento porque para ella es fácil generar dos números primos grandes y multiplicarlos entre sí. La clave de codificación creada así puede hacerse pública sin riesgo aparente, por la dificultad que tiene incluso otra computadora para obtener la clave de descodificación mediante descomposición factorial.

La aplicación práctica de esta función de codificación está en el centro de varios sistemas de seguridad de la red. Podemos pensar en las futuras versiones de Internet como en una red postal en la que todo el mundo tiene un buzón que es imposible de forzar, con una cerradura imposible de abrir. Cada buzón tiene una ranura que permite a cualquiera deslizar información dentro de él, pero sólo el propietario del buzón tiene la clave para sacar la información del mismo.

La computadora de cada uno de los usuarios o cualquier otro dispositivo de información utilizará los números primos para generar una clave cifrada que aparecerá en una lista pública y una clave correspondiente para descifrarla que sólo conocerá el usuario. He aquí cómo funciona en la práctica: yo quiero enviarle a usted una información. Mi sistema informático comprueba su clave pública y la utiliza para cifrar la información antes de enviársela. Nadie puede leer el mensaje aunque su clave sea de conocimiento público, porque su clave pública no contiene la información necesaria para descifrarla. Usted recibe el mensaje y su computadora lo descifra con una clave privada que corresponde con su clave pública.

Usted quiere contestar. Su computador, o su dispositivo de información ve cuál es mi clave pública y la utiliza para codificar su respuesta. Nadie más puede leer el mensaje aunque se haya codificado con una clave totalmente pública, sólo yo puedo leerlo, ya que tengo la clave privada para descifrarlo. Esto es muy práctico porque nadie tiene que ocuparse de las claves por adelantado.

¿Qué tan grande tienen que ser los números primos y sus productos para dar lugar a una función irreversible eficaz? El concepto de cifrado mediante clave pública lo inventaron Whilfield Diffie y Martin Hellman en 1977. Otro grupo de científicos informáticos, Ron Rivest, Adi Shamir y Leonard Adelman, descubrieron pronto la noción de utilizar la descomposición factorial de los números primos como parte de lo que se conoce como el criptosistema RSA, acrónimo formado a partir de las iniciales de sus apellidos. Según sus previsiones, afirmaron que se tardaría millones de años en descomponer factorialmente un número de 130 dígitos que fuera producto de dos números primos, con independencia de la cantidad de potencia informática de que se dispusiera para la solución. Para probarlo retaron a todo el mundo a que encontrase los dos factores del siguiente número de 129 dígitos, conocido por los especialistas como el 129RSA;

114.381.625.757.888.667.669.235.779.976.146.612.010.218.296.721.
242.362.562.601.842.935.706.935.245.733.897.030.597.123.563.958.
705.058.989.075.147.599.290.026.879.543.541

Estaban seguros de que el mensaje que había codificado utilizando este número como clave pública permanecería totalmente seguro para siempre. Pero no habían tendido en cuenta todos los efectos de la Ley de Moore (la potencia de los ordenadores se multiplica cada 18 meses), que han hecho a las computadoras mucho más potentes, ni tampoco el éxito de la computadora personal, que ha incrementado enormemente el número de computadoras y de usuarios informáticos en el mundo. En 1993, un grupo de más de 600 universitarios y aficionados de todo el mundo comenzaron la labor de descifrar el número de 129 dígitos utilizando la Internet para coordinar el trabajo de varias computadoras. En menos de un año descompusieron el número en dos números primos, uno de 64 dígitos y el otro de 65:

4.490.529.510.847.650.949.147.849.619.903.898.133.417.764.638.
493.387.843.990.820.577

32.769.132.993.266.709.549.961.988.190.834.461.413.177.642.967.
992.942.539.798.288.533

El mensaje codificado dice: “las palabras mágicas son remilgadas y quebrantahuesos”.

Una de las lecciones que se pueden sacar del suceso es que esta clave pública de 129 dígitos no es lo suficientemente larga si la información que se ha codificado con ella es en verdad importante y delicada. Otra, es que nadie debería mostrarse demasiado seguro en el tema de la seguridad de la codificación.

Incrementar la clave en unos cuantos dígitos la hace mucho más difícil de descifrar. Los matemáticos creen hoy que costaría millones de años en descomponer factorialmente, con una potencia informática previsible, un número de 250 dígitos que sea producto de dos números primos. Pero, ¿quién lo sabe a ciencia cierta? Esta incertidumbre y la improbable, pero concebible posibilidad de que alguien pueda dar con una forma fácil de descomponer factorialmente grandes números primos, significa que la plataforma software para la autopista de la información tiene que diseñarse de tal manera que su esquema de codificación se pueda cambiar con rapidez.

Siempre hay algo por qué preocuparse, pero una de las cosas por la que no debemos preocuparnos es porque se acaben los números primos o por la perspectiva de que dos computadoras utilicen accidentalmente los mismos números como claves. Hay muchos más números primos de longitud adecuada que átomos en el universo, de manera que la posibilidad de que se produzcan conflictos accidentales es remota.

La codificación mediante claves permite algo más que mantener la intimidad. Puede asegurar también la autenticidad de un documento porque puede utilizarse una clave privada para codificar un mensaje que sólo puede descodificarse mediante la clave pública. Esto funciona de la siguiente manera: si tengo información que deseo firmar antes de enviarla, mi computadora utilizará mi clave privada para cifrarla. Con ello, el mensaje sólo puede leerse si se utiliza para descifrarlo mi clave pública que usted y todo el mundo conocen. Este mensaje lo puedo verificar yo, porque nadie más tiene la clave privada que podría haberlo codificado de esta manera.

Mi computadora toma este mensaje cifrado y lo cifra de nuevo, utilizando esta vez su clave pública. Luego le envía a usted este mensaje doblemente codificado a través de la autopista de la información.

Su computadora recibe el mensaje y utiliza su clave privada para descifrarlo. Esto suprime el segundo nivel de codificación, pero conserva el nivel que yo utilicé con mi clave privada. Luego, su computadora utiliza mi clave pública para volver a descifrar el mensaje. Como el mensaje procede realmente de mi, se descifra correctamente y usted sabe que es auténtico. Si se cambiase sólo un bit de información, el mensaje no se codificaría adecuadamente y se pondría de manifiesto el engaño o el error en las comunicaciones. Este extraordinario nivel de seguridad le permitirá realizar negocios con extraños, o incluso con personas de las que desconfíe, porque podrá estar seguro de que el dinero digital es válido y de que las firmas y los documentos son auténticos.

La seguridad puede incrementarse aún más incorporando a los mensajes sellos temporales. Cuando alguien trate de cambiar la fecha en que se envió o escribió supuestamente un documento, se podrá detectar el engaño. Esto rehabilitará el valor probatorio de las fotografías y de los videos que han sufrido asaltos provocados para la facilidad para efectuar retoques digitales.


Fuente:
“Camino al futuro”, 1996
Bill Gates

Anuncios

criptografia

La criptografía fue una de las primeras aplicaciones de los ordenadores. En la actualidad, elaborar y descifrar un código sencillo está al alcance de un programa de ordenador.

Toda nuestra comunicación con los demás está codificada. Tanto el habla como el lenguaje escrito son inteligibles sólo si la persona que recibe el mensaje conoce el código del comunicante. Lo mismo sucede con nuestras conversaciones con los ordenadores. La mayoría de los ordenadores personales se comunican por medio de una versión del BASIC para ser accesibles a la mayoría de la gente, pero nosotros sabemos que la máquina no emplea este leguaje para realizar sus funciones: ella debe primero interpretar las sentencias en BASIC en una forma puramente numérica que después utiliza para establecer la secuencia de conmutaciones definidas en el programa y, de este modo, producir los resultados deseados. Los códigos de este tipo (lenguajes humanos y lenguajes de programación) son de fácil acceso en nuestra vida cotidiana. Con un poco de esfuerzo y voluntad, cualquiera puede aprender francés, alemán, BASIC o Fortran.

Pero existe otro tipo de codificación (o criptografía, para usar la palabra adecuada) que tiene por objetivo lo contrario de la comunicación; su finalidad consiste en evitar que lo comprendan todos, a excepción de un reducido grupo al cual está destinado el mensaje. Hasta la segunda mitad del siglo XX, la transmisión de información en una forma ininteligible para el público en general era privativa de los gobiernos y de alguno que otro asunto industrial importante. Pero más recientemente la criptografía se ha convertido en algo cotidiano.

Las claves y los códigos oscilan desde los muy simples (la suma o la resta de un valor determinado a cada byte, o la sustitución según el formato de un carácter por otro cada vez que éste aparece) hasta las claves en extremo complejas por las que se encaminan los más recientes avances de la teoría de los números. Estas claves no contienen ningún elemento de repetición y, por consiguiente, no son descifrables con los tradicionales métodos de decodificación por análisis de frecuencia.

Quizás la más sencilla de todas las técnicas significativas de criptografía sea la “clave del César” (que tal vez se utilizó por primera vez en la época del Imperio romano). Para descifrar la clave del César sólo se necesita el mensaje y un conocimiento de la clave, de modo que no hay que consultar voluminosos libros de códigos ni documento alguno, ni se necesita unas máquinas especiales. He aquí un breve mensaje escrito en clave del César:

AYJYZNXNQ W BPYENLCQ

Podemos aventurar algunas suposiciones acerca de estas palabras crípticas, a tenor de la forma en que se separan los grupos cifrados (aunque, por supuesto, ¡esto se podría haber hecho para crear mayor confusión¡). Lo más obvio a que destaca a simple vista es que el mensaje consta de 3 palabras; la primera posee 9 letras, la segunda posee 1 y la última 8. También es claro que la primera y la tercera palabra terminan con la misma letra. Aquí la última letra final común (Q) es, asimismo, una de las tres letras del mensaje que se repiten con mayor frecuencia (las otras dos son la Y y la N). Para el criptoanalista esta observación tiene un valor considerable (al menos, cuando sabe en qué idioma está trabajando). En castellano, las letras que se presentan con mayor frecuencia son la A y la E entre las vocales, y la S entre las consonantes; esta última, dado que con ella se forma el plural, suele hallarse al final de las palabras.

Con una muestra tan reducida como la que tenemos aquí (un total de 18 letras, cifra que todo estadístico considera muy insuficiente para buscar en ella cualquier análisis), es probable que nuestros resultados sean fiables. Pero, aun así, vamos a probar con la sustitución de frecuencia y veremos si los resultados obtenidos tienen algún significado. En primer lugar vamos a reemplazar la Q por la S, por ser aquella la última letra de las dos palabras más largas.

AYJYZNXNs W BPYENLCs

El mensaje aún no tiene significado, pero existen otras pistas. ¿Qué hay de la relación entre la letra original y la letra por la cual la hemos sustituido? En el alfabeto, la Q está dos lugares antes que la S. ¿Qué sucederá si sometemos el resto del mensaje a la misma transformación? Dos lugares después de la Y (la otra de nuestras letras que aparece con mayor frecuencia) está la A (si consideramos el alfabeto como una cadena ininterrumpida), así que vamos a intentar agregar esta información.

AaJaZNXNs W BPaENLCs

En la primera palabra tenemos ahora dos vocales intercaladas, que en castellano es una construcción válida. Además, la letra final es una S, hecho que en esta lengua es de común ocurrencia, de modo que tal vez estemos en el camino correcto. Vamos a someter el resto del mensaje a la misma transformación. Dos lugares tras de la A se encuentra la C; dos lugares después de la J está la N; aplicando la misma correspondencia, la Z de convierte en B, la N en O y la X en Z… De esta forma llegamos a la solución “calabozos y dragones”, un atractivo juego de aventuras.

La clave del César es, pues, un código de sustitución que se basa en “deslizar” el alfabeto hacia atrás o hacia adelante según un número que es secreto y que nos dará el nuevo valor de cada carácter. Sin utilizar las frecuencias, el mensaje puede simplemente construirse según una serie clave de transformaciones: 24225, por ejemplo. En este caso la primera letra se desplazaría dos lugares, la segunda cuatro, la tercera dos y así sucesivamente. Cuando se llega al último número de la serie clave la volveremos a iniciar. Con esta serie clave, el mensaje de muestra “calabozos y dragones” quedaría:

AWJYWNVNQ T BÑYERKLAQ

En este caso, el análisis de frecuencia sería inútil, pues no hay uniformidad en las sustituciones: una letra tendrá distintas sustituidas según su posición en el mensaje global. Otra clave sencilla auto contenido es el mismo mensaje en estos términos:

CBSDOAAOO RGNSLZYAE

Si observamos atentamente, podemos ver que esta serie de caracteres es en realidad un anagrama de “calabozos y dragones”, completo y con los dos espacios entre las palabras. Aquí simplemente estamos tratando de determinar el algoritmo criptográfico, a parir de ejemplos tanto de texto llano como de texto cifrado, un procedimiento sorprendentemente común. Si la clave ha de ser comprensible al destinatario del mensaje, entonces la combinación de las letras debe ser predecible de alguna forma. Esta clave particular, conocida como “bar fence”, también requiere que el decodificador la conozca; en este caso es 3. Vamos a tomar los cinco primeros caracteres y escribirlos con tres espacios de por medio:

C***B***S * D***O

¿Reconoce algo? Entonces probemos con esto: escriba el mensaje de texto llano en tres líneas, yendo de arriba y hacia abajo entre ellas, de la siguiente manera:

C   B   S   D   O
 A A O O *Y* R G N S
  L   Z       A   E

Los asteriscos representan los espacios entre las palabras; el método criptográfico es llano.

Los ejemplos que hemos citado hasta el momento han sido todos cifras, definidas como un método de escritura secreta que utiliza la sustitución o transformación de letras de acuerdo a una clave. Los códigos son algo diferente, en el sentido de que tienden a reemplazar bloques enteros por otros bloques, normalmente más pequeños (permitiendo, de este modo, al mismo tiempo, comprimir los datos). Su inconveniente es que exigen que ambas partes posean un libro de códigos para que se puedan comunicar mensajes. Un ejemplo de esta técnica emplea una novela, un periódico u otro texto que se pueda conseguir con facilidad, e indica las palabras del mensaje dando el número de secuencia en que se producen. Un texto como:

“Maigret leyó con atención el aviso: Por favor, al objeto de favorecer el tráfico, permanezca al volante, no baje del coche. Sonrió. Ahora comprendía por qué en su momento el cadáver de Smith no fue identificado”.

podría ser la clave para el código 4, 6, 7, 17, 2.

Un ordenador de cualquier clase puede ser de enorme valor al intentar cifrar o descifrar mensajes criptográficos. Un requisito primordial de la clave del César, por ejemplo, es la capacidad de desplazamiento a través de una serie alfanumérica, sumando o restando una variable al valor ASCII de cada carácter, que se puede entonces imprimir. Dicha constante ha de ser susceptible de modificarse cuando se ejecuta el programa, y debe hacer que el alfabeto se “enrolle” (es decir, una A, cuando la clave fuera uno, debería dar Z).

(Fuente: Enciclopedia Mi Computer)