Criptografía hasta Siglo XVI

Criptografía por transposición

En la guerra del Peloponeso que enfrentó a Espartanos y Atenienses (431 a.C-404 a.C).
Se usaban cintas para escribir los mensajes, el mensaje se enrrollaba en una escitala o bastón de un grosor determinado, se escribía el mensaje y luego se desenrrollaba la cinta, quedando un texto sin sentido, éste se enviaba y el receptor solo tenía que enrrollar de nuevo la cinta en otra escitala del mismo grosor para descifrar el mensaje.
Este método consiste en transponer los caracteres en el texto cifrado.
Para un texto de n caracteres existe n! posiblidades de ordenación.
Por ejemplo, para un texto de 3 caracteres existirían 3! = 3*2*1 = 6 maneras de organizarlos.


Escitala

Cifrado César

Con los romanos, continuó la búsqueda de un algoritmo más seguro que el de transposición, empezaron los cifrados de sustitución.
Cada letra del texto original era sustituída por la que le seguía 3 posiciones más adelante, así la A se cifraba con la D, la G con la L…(Téngase en cuenta el alfabeto romano). Posteriormente a todo cifrado en el que la letra original se ha sustituído por otra desplazada un número fijo de posiciones (no necesariamente 3) se denomina: cifrado César.

Este cifrado es vulnerable al criptoanálisis por análisis de frecuencia, a causa del número reducido de claves. Como la sustitución se hace en orden alfabético solo podría haber 21 claves de cifrado diferentes, teniendo en cuenta que el alfabeto romano tiene 21 caracteres. Sin embargo si eliminamos las restricciones de orden alfabético obtenemos 21! =51.090.942.171.709.440.000 posibles claves de cifrado.
Aunque sigue siendo vulnerable al criptoanálisis por análisis de frecuencia.

Cifrados polialfabéticos

En 1460 Leon Battista Alberti propuso un cifrado que consistía en añadir al alfabeto cifrado convencional un segundo alfabeto cifrado.


Así, para cifrar un mensaje se van alternando uno y otro alfabeto por ejemplo, la palabra CASA, la C la cifraríamos con el primer Alfabeto Cifrado quedando una B, la A la cifrariamos con el segundo Alfabeto Cifrado quedando la G, obteniendo de resultado BGRG
En el siglo XVI Vigenère creó el cifrado que se basa en el cuadro de Vigenère, basado en la aportación de Alberti pero en vez de con 2 alfabetos cifrados, con 27 (igual que letras tiene el alfabeto castellano)

El procedimiento sería el mismo que con el cifrado propuesto por Alberti pero utilizando tantos alfabetos cifrados, como letras tenga el alfabeto.

Máquina de Turing

Número computable

Son los números reales que pueden ser calculados con la precisión que se desee por un algoritmo finito. Un número computable es aquel para el que hay una máquina de Turing dado n su cinta inicial termina con el n-esimo digito de ese número

Por ejemplo tenemos un número con infinitos decimales como π , hay un algoritmo que te permite calcular un numero finito de decimales de π , por lo que π sería computable.

Problemas de decisión

Un problema de decisión es una pregunta que tiene una respuesta verdadera o falsa.
Por ejemplo: ¿Es 11 número primo?

Church y Turing demostraron en 1936 que no hay un algoritmo general capaz de decidir si una fórmula es un teorema.

Un problema de decisión puede tener una solución si la maquina de Turing se para y da un resultado, de lo contrario si la máquina no se para y sigue hasta el infinito no tendrá solución.

Máquina de Turing

Consta de una cinta infinita con cuadros, cada cuadro es capaz de almacenar un simbolo de un conjunto de símbolos definidos (en este caso: espacio en blanco,0 y 1). La cinta esta en un estado inicial con unos simbolos pertenecientes al conjunto.

Tiene un cabezal que esta en un estado inicial que lee el simbolo que se encuentra en ese cuadro, según el simbolo que lea y como este programada la máquina borrara el simbolo o lo mantendrá o escribirá un espacio en blanco y se desplazará a izquierda o derecha y cambiará de estado.



Enlaces de interés:

Puedes comprobar como funciona la máquina de Turing en el siguiente enlace, tienes programas de prueba.
http://morphett.info/turing/turing.html

Computadoras en los Años 70

En la década de los 70 los ordenadores eran muy grandes y no tenían pantalla por lo que el resultado de los cálculos los daban por impresora. Lo mas habitual es que los programas se escribieran en tarjetas perforadas, en cada tarjeta perforada cabían 80 caracteres por lo que un programa podría necesitar cientos de tarjetas perforadas.

Disponían de varios módulos:
1- Módulo para perforar tarjetas.
2- Módulo lector de tarjetas perforadas.
3- Unidad central, con teclado para introducir comandos por consola y lector de disco.
4- Módulo de Impresora, por donde salen los resultados.

El procedimiento para hacer un programa era:
1- Se escribian las sentencias en una hoja de codificación.
2- Se pasaba el código a tarjetas perforadas.
3- Una vez escrito el programa se ponían las tarjetas en orden para que el ordenador las fuera leyendo.
4- Una vez acabada la ejecución del programa salían los resultados por la impresora.

Los programas que contenian funciones útiles para los cálculos se podían pasar a disco magnético. Los discos tenian 512KB de capacidad y median unos 45cm de diametro.
Los lenguajes que se utilizaban para programar estas tarjetas eran FORTRAN y COBOL o directamente en ensamblador.

Tarjeta perforada
Perforador de tarjetas
Unidad central IBM 1130
Módulo de Impresora

(Fotos en El Museo Nacional de las Computadoras, Inglaterra)