Para mandar un mensaje secreto se nececita una "llave", es decir un método para codificar el mensaje, y después un método para decodificar (o decifrar) el mensaje codificado. La criptología es el arte de construir llaves efectivas: que sean fáciles de usar y difíciles de "romper" (decifrar el texto codificado sin la llave). La historia de la criptología de divide en dos épocas: hasta el año 1976, y despues del 1976. Hasta el 1976 solo se conocían llaves "privadas"; es decir, el método de codificación se debería de mantener en secreto, para mantener la seguridad del mensaje. En 1976, basado en el trabajo de matématicos del siglo 18 (Fermat y Euler), en área que pareciá hasta entonces no tener nada que ver con la criptología, tres científicos (Rivet, Shamir, Adelman) introdujeron un nuevo método de codificación que revolucionó el mundo de la criptología: el método de la "llave publica", Según esto, el método de codificación de un mensaje codificado es público, y sin embargo nadie puede decifrar el mensaje, a menos que tenga otra llave, la llave de decodificación. ¿Cómo es posible? En este taller conoceremos todos estos conceptos de cerca.
A -> D, B -> E, ..., V -> Z, W -> A, X -> B, Y -> C(las letras al final del alfabeto regresan al principio). Así, el texto "MI MENSAJE SECRETO" se codifica como "QM QIRWDNI WIGVIXS", o incluso mejor "QMQIRWDNIWIGVIXS" (quitando los espacios), para que sea mas difícil de romper.
Conociendo la llave de codificación ("avanza 3 lugares a la derecha"), se deduce fácilmente la llave de decodificación ("avanza 3 lugares a la izquierda").
HOLAB CDEFG IJKMN PQRST UVXYZ(una letra no aparece, la W; en lugar de ella podemos usar la V). Luego cada par de letras se substituye por otro par según las siguientes reglas:
(1) si el par está en columnas y filas distintas, se forma un cuadrado con este par como vértices opuestos, y se cambia este par por el otro par de vértices opuestos. Así, CT --> GP, PO --> QH (¡cuidado con el orden de las letras!)
(2) Si el par está en la misma fila, se avanza cada letra del par un lugar a la derecha. (Si se sale de la fila se regresa al principio). Así, HO se cambia por OL, EC por FD,IN por JI.
(3) De manera similar, si el par está en la misma columna, se avanza un lugar hacia abajo (regresando arriba se sale por abajo).
(4) Letra doble (como LL o RR) se le agrega primero una X entre las dos letras antes de codificar.
(5) Si el número de letras en el texto es impar se agrega una X al final del mensaje.
Ejemplo:
texto original : MI LLAVE SECRETA se convierte primero en: MI LX LA VE SE CR ET AX y se codifica como : NJ EL AB XD RF EP GR LYEs fácil decifrar el mensaje con la palabra clave ("HOLA" en nuestro ejemplo).
texto: NOSVEMOSALASOCHO llave: PEHUCGFVELUBXIZYy ahora combinamos el texto y la llave según una regla simple. Podemos asignar un valor númerico a cada letra, de 1 hasta 26:
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26y después "sumar" el texto y la llave, modulo 26. Así, N+P=D, ya que N=14, P=16, 14+16=30=4 (mod 26) y D=4. En el ejemplo arriba el texto codificado que obtenemos es
DSAQ...Para decifrar, simplemente hay que "restar" la llave del texto codificado (modulo 26). Si no se vuelve a usar la llave no hay manera de decifrar el mensaje sin la llave, ya que cada letra del texto tiene su propia llave y no hay ningun patron en el texto que puede ayudarnos en descubrir el texto original. Esto es el método de criptología más seguro que existe, pero claro, tiene su costo: la llave es muy "cara", tiene que ser tan larga como el texto original, y se puede usar solamente una vez.
hola (la llave) 2431 (el orden) MIME NSAJ ESEC RETOEn la segunda fila, abajo de "HOLA", denotamos abajo de cada letra el orden que aparecen estas letras en el alfabeto: A aparece primera así que escribimos 1 abajo de ella, luego H con 2 abajo de ella etc. (Si en la palabra clave aparece una letra mas que una vez, las ordenamos en el orden que aparecen, así que LLAVE se transforma en 34152). Para codificar, copiamos las columnas del texto en el orden dictado por la palabra clave. En el ejemplo de arriva, el texto codificao es
EJCOMNERMAETISSEEn caso que la última fila del mensaje no está llena en la tabla podmeos llenarla con X, o mejor aun, dejar la incompleta, y "bajar" de la tabla columnas de texto de tamaño variable. De todos modos, es fácil decifrar el mensaje dada la palabra clave (¿cómo?).
Ejemplo: digamos que el texto que queremos codificar es "MIMENSAJESECRETO". Escogimos primero un par de palabras clave, digamos "amigo bueno" (la primera palabra no debe tener letras repetidas, como en la palabra "amiga"). Luego, usamos la primera palabra para construir una tabla de 6 por 6, de manera similar a la tabla de la práctica núm. 2; primero la palabra clave, luego el resto de las letras y las 10 cifras:
ADFGVX A amigob D cdefhj F klnpqr G stuvwx V yz0123 X 456789Con esta tabla, substituimos cada letra del texto (o cifra, en caso que contenga el mensaje) por un par de letras del conjunto de las 6 letras ADFGVX. En nuestro ejemplo obtenemos "AD AF AD DF FF GA AA DX DF GA DF DA FX DF GD AV". El siguiente paso es usar la segunda palabra clave para "revolver" las letras de este texto , como hemos hecho en la práctica anterior:
bueno 15234 ADAFA DDFFF GAAAD XDFGA DFDAF XDFGD AVSe obtiene entonces el texto
ADGXDXAAFAFDFFFAGAGAFDAFDDDADFDV
Pero es peligroso mandar este número 17 por internet, ya que alguien lo puede interceptar y luego puede entrar a la cuenta del cliente indebidamente. Ni el cliente ni el banco quieren que pase esto. Hay que ocultar, o codificar, esta información. Entonces el banco le da al cliente (o mas bien a su PC) las siguientes instrucciones para codificar su mensaje:
Ahora, ¿cómo recupera el banco, desde el mensaje codificado (8), el mensaje original del cliente (17)?
Para esto el banco tiene una ``potencia decodificadora'': el número 23. El banco calcula el residuo modulo 55 de 8 elevado a la 23ava potencia, y le sale 17. O sea, multiplicando 8 por su mismo 23 veces y dividir el resultado entre 55, lo que sobra es 17, el mensaje original del cliente.
Ahora el banco puede verificar si el cliente mandó la contraseña correcta y decidir si le deja entrar a su cuenta.
En fórmulas: M=17 (el mensaje secreto del cliente), N=55 y c=7 (los números que el banco manda, publicamente al cliente para codificar su mensaje, el ``modulus'' y la ``llave pública''). C= Mc(mod N)=8 (el mensaje codificado que manda el cliente al banco). El banco recupera el mensaje secreto del cliente al usar d=23 (la potencia decodificadora, o la ``llave privada'') y calcula M= Cd (mod N).
El punto de todo esto es que las instrucciones para el cliente, incluyendo los números N y c, son públicas; por ejemplo, pueden aparecer en la misma página internet del banco. Solo la ``potencia decodificadora'' d (en nuestro caso 23) es secreta, sin ella es practicamente imposible recuperar el mensaje original M (el número 17 en nuestro caso), aun si el metodo de codificacion, incluso la N y la c, son conocidos. Ahora claro, con números pequeños (55,7,23,...) el metodo no es seguro. Pero cuando son grandes (N tiene tipicamente en aplicaciones entre 100 y 200 digitos) es muy seguro.
Para entender esto mejor, tenemos que entender la manera en que el banco diseña los números N, c y d. La receta es la siguiente: escoje dos primos p y q (5 y 11 en nuestro caso, pero en realidad tienen que ser muchos mas grande, con cientos de dígitos). Define N=pq (55 en nuestro caso) y f=(p-1)(q-1) (40 en nuestro caso). Escoje ahora c entre 1 y f que no tenga factor común con f (7 en nuestro caso, no tiene factor común con 40). Encuentra un d entre 1 y f tal que cd= 1 (mod f) (23 en nuestro caso, ya que 7 x 23 =161= 1 (mod 40). Los números N y c son públicos. El resto, p, q, f y d, son secretos. El exito de este sistema está basado en que la única manera (que conocemos ahora) de decodificar el mensaje C es encontrar los factores primos p y q de N, para luego poder determinar el f (esto es fácil) y luego d (tambien fácil). Pero resulta que si p y q son muy grandes (digamos de 200 dígitos cada uno), es practicamente imposible (hoy en día) de encontrar los factores p y q de N=pq.