A criptografía ven definida no diccionario da RAG como a arte de escribir textos dun modo enigmático, en cifra. Engloba un conxunto de técnicas intimamente relacionadas cos algoritmos (e coas Ciencias da Computación en xeral), tendo sido un dos motores de desenvolvemento dos mesmos ao longo da Historia da Humanidade. Empezando con Xulio César e o seu sistema de cifrado de mensaxes, pasando polas máquinas mecánicas de encriptación, como a utilizada polos nazis na II Guerra Mundial, a máquina Enigma , e a loita por descifrala (hackearla), e chegando hoxe en día á seguridade en Internet e á criptografía cuántica.
Os problemas de codificación e cifrado, xunto á realidade tecnolóxica do momento son moi apropiados para someterse a un enfoque de resolución algorítmica, tipo ensaio e erro mediante bucles iterativos. Algoritmos como a da busca binaria poden aplicarse en criptografía como exemplos de forza bruta.
No apartado Papel recomendamos unha maravillosa novela, Criptonomicón de Neal Stephenson, e un ensaio de divulgación: Matemáticas, espías y piratas informáticos de Joan Gómez. E no apartado de Fotogramas: filmes un par de películas relacionadas coa máquina Enigma.
A diferenza entre cifrar e codificar
Aínda que adoitamos utilizalos como sinónimos, deberiamos falar de codificar cando collemos información nunha lingua natural, como o galego falado ou escrito, e a transformamos cunha serie de reglas e protocolos (que veñen sendo algoritmos) para poder comunicala no tempo (ou sexa, almacenala) ou no espazo (a distancia). Os problemas de codificado adoitan ser de tipo "tecnolóxico" ou físico (por exemplo, usar algoritmos de compresión para que un ficheiro ocupe menos espazo, como JPG en imaxes ou MP3 en audio). Estas regras e protocolos poden ser segredos, privados ou coñecidos, públicos e libres. Por exemplo, cando utilizamos un programa como Word codificamos con protocolo segredo ao gardar un ficheiro, namentres que con LibreOffice utilizamos un algoritmo libre, público. Moitas persoas (entre elas, moito profesorado) aínda non entende que o uso de algoritmos privativos, segredos, vai en contra da estandarización das comunicacións (é dicir, dificulta o proceso comunicativo ao resto da poboación e ao software e o hardware que non pode ler ese algoritmo segredo, e por iso é algo insolidario) e que polo tanto non deberiamos utilizalos se temos opcións libres.
Con cifrar podemos referirnos a codificar caracteres ou palabras cun algoritmo para intentar preservar a confidencialidade da mensaxe. O tipo de problema adoita ser de tipo lóxico (que algoritmo aplico para garantir a confidencialidade?). Por exemplo se mercamos por internet ou poñemos un contrasinal é fundamental ter un algoritmo de cifrado. Como norma xeral temos unha clave ou chave para almacenar a información cifrada, protexida ou pechada, e o receptor terá que ter coñecemento desa clave para descrifrar, abrir a mensaxe.
Segundo sexa a clave ou chave falamos de dous grandes tipos de cifrado:
- Simétrico: cando o emisor usa unha clave e o receptor ten que ter a mesma para descrifrar.
- Asimétrico: cando o emisor usa unha clave e o receptor pode usar outra (¿?). Este é o tipo de cifrado predominante en Internet.
Cifrado Simétrico
O cifrado simétrico é o cifrado clásico, onde o emisor usa un algoritmo segredo (que tamén sabe o receptor) para xerar unha clave coa que cifra a mensaxe, tendo que ter ambos a mesma clave e algoritmo para cifrar e descifrar. Existen moitas técnicas e algoritmos, pero a día de hoxe a maioría delas se consideran febles dende un punto de vista técnico, descifrables cun ordenador medio por calqera hacker medianamente competente. Aínda así segue a utilizarse en moitos procesos cotiás.
Dende un punto de vista histórico e técnico podemos falar das técnicas de cifrado simétrico por trasposición e por substitución (non son únicas, existen outras).
Cifrado por transposición: A Escítala
Neste cifrado collemos a mensaxe e modificamos a posición dos caracteres ou das palabras seguindo unha regla predeterminada, que deberá saber o receptor.
Por exemplo podemos coller o mensaxe a cifrar: ALGORITMIA e aplicarlle unha trasposición acordada co emisor; no noso exemplo que a última letra se intercambia coa primeira, a penúltima coa segunda, etc... A mensaxe cifrada quedaría como AIMTIROGLA.
Por sinxelo que pareza esta técnica utilizouse dende a Antigüidade co soporte de artefactos mecánicos, que axudaban a facer máis complexa a tarefa do cifrado.
É moi coñecida por simple e efectiva a Escítala do espartanos: A mensaxe cifrada aparece nunha tira de coiro e para descifrala é necesario envolver a tira nunha vara dun diámetro dado e cun determinado número de voltas, pactada polo emisor e o receptor.
En moitas novelas, películas e videoxogos podemos atopar un cifrado por transposición. Sen ir máis lonxe, en Viaxe ao centro da terra de Jules Verne ou no famoso Kama_Sutra.
Se a trasposición é moi complexa ou azarosa (por exemplo, sorteando que letra é transposta con outra) parece imposible de descifrar agás que apresemos a un inimigo. O problema é que se complicamos o cifrado complicamos o descifrado. Para descrifralo teríamos que mandar a clave non cifrada, e aí está a debilidade do sistema.
O cifrado de trasposición pode utilizarse en clase de programación ou matemáticas utilizando matrices, e aplicando algoritmos ou fórmulas de transposición, que se estudan en 2º Bach.
Cifrado por substitución: Cifrado César
Ao tempo que se empregaron sistemas de trasposición decidiron utilizarse e desenvolverse sistemas de substitución que facilitaban o envío de mensaxes a moitas personas, como no caso das ordes militares. No de substitución cada caracter é substituído por outro seguindo un algoritmo, pero cada caracter queda no seu sitio, non hai transposición.
O cifrado utilizado por Xulio César é un dos máis coñecidos e sinxelo de explicar. Colles cada letra da mensaxe e a substitúes pola letra do alfabeto que está 3 posicións máis adiante:
A nosa mensaxe de exemplo, ALGORITMIA, quedaría cifrada como VGDMOFQHGV (usando o alfabeto galego con 23 letras).
Como faría un espía dos galos para descifrar a mensaxe?. Pois coñecendo o algoritmo de partida sería sinxelo, tan só tería que probar, se o alfabeto ten n letras, n posibilidades. Aínda así o método debeu considerarse seguro para que fose utilizado en moitos exércitos e eṕocas diferentes, con variantes.
Cifrado César e aritmética modular
Dado que os módulos son unha operación ben importante en programación, compre mencionar a íntima relación co cifrado por substitución. Un cifrado como o de César pode formalizarse a nivel matemático do seguinte xeito:
- Damos un valor numérico a cada letra do alfabeto e do alfabeto cifrado (lembremos que a clave é 3 neste caso).
| Valor | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 |
| Alfabeto orixinal (galego) | A | B | C | D | E | F | G | H | I | L | M | N | Ñ | O | P | Q | R | S | T | U | V | X | Z |
| Alfabeto cifrado | V | X | Z | A | B | C | D | E | F | G | H | I | L | M | N | Ñ | O | P | Q | R | S | T | U |
- Agora se x é a letra a cifrar, podemos calcular a letra cifrada coa función:
C(x) = (x + 3) mod(23)
- En xeral se temos unha clave k, e un número de letras n, a fórmula do cifrado por substitución será:
C(x) = (x+k) mod n
O método de substitución foise mellorando con diversas técnicas, como o polialfabeto (usar varios alfabetos cifrados á vez), o disco de Alberti (usado na guerra de Secesión polos conferederados), o cadrado de Vigenère (que foi descifrado por Charles Baggage, inventor do ordenador mecánico) e outros, ata chegar ao século XX con máquinas tan complexas como a famosa ENIGMA dos nazis na II Guerra Mundial, que aínda así foi descifrada por un exercito de matemáticAs coordinadas por Alan Turing.
Unha das técnicas básicas para descifrar o algoritmo de substitución, o análise de frecuencias (inventado en Bagdad no século IX polo sabio al_Kindi), pode ser utilizado en programación, tal e como contamos na páxina de Python: Codificar e Decodificar.
O algoritmo de substitución tamén aparece en gran cantidade de referencias culturais, sendo algunha das máis famosas O escarabello de ouro, de Allan Poe, ou contos de Sherlock Holmes, onde o detective fai uso da análise de frecuencias.
Cifrado asimétrico
Calquera algoritmo simétrico, por complexo que sexa (e algúns son realmente complexos) afronta o chamado en Criptografía problema da distribución da clave: como emisor e receptor teñen que ter a mesma clave, o momento delicado é cando distribuímos a clave, non cando enviamos a mensaxe cifrada. Por exemplo, o exército nazi distribuía cada semana miles de libros coas novas claves de ENIGMA, convertindo o seu sistema en algo máis vulnerable se eran interceptadas.
Por sorprendente que pareza, e grazas ao traballo de varios intrépidos matemáticos, temos unha maneira de evitar o envío das claves privadas, usando a cambio cifrado con claves públicas, o cal é máis eficaz, tanto que é o que utilizamos para pagar en Internet ou cifrar comunicacións confidenciais. E só temos que saber aritmética modular e número primos (¡!)
Algoritmo Diffie- Hellman: a maxia da aritmética modular
Como podemos cifrar unha mensaxe sen ter que enviar unha clave privada (que non estará cifrada, e polo tanto é vulnerable), ou enviando só claves públicas, que poda vela calquera?. Co seguinte algoritmo:
- PASO 1:Emisor e receptor xeran un número cada un, N1 e N2, que permanece segredo.
- PASO 2: Con eses números aplican unha función do tipo f(x) = ax mod p, sendo p un primo moi grande e x o número xerado. Esa función ten que estar compartida previamente entre eles.
- PASO 3: O emisor obtén o número f(N1) e o receptor f(N2). Eses números son a clave pública e poden enviarse sen cifrar.
- PASO 4: Cando reciben a clave pública, cada un ten que resolver a ecuación C = (clave recibida clave xenerada ) mod p.
(ta-ta-ta-chán!!! que diría o gran Tamariz): Por sorprendente que pareza, ambos obteñen o mesmo valor de C: C1 = (f(N2))N1 mod p = C2 = (f(N1))N2 mod p
C será a clave privada para cifrar e descifrar. Ambos teñen C sen ter intercambiado esa clave. Cousa de meigas?. O mellor é que un posible espía ou cracker, que teña acceso ás claves públicas e á función pactada, pero non aos números xenerados, teno casi imposible para calcular C, supoñendo que o número primo p sexa suficientemente grande. Maxia da aritmética modular.
Algoritmo RSA: todavía máis difícil
O algoritmo asimétrico visto antes é marabilloso, pero aínda ten o problema de que emisor e receptor teñen que poñerse dacordo para crear dous números e intercambiar información. Este problema solucionouse co algoritmo RSA (acrónimo dos seus autores e difundido por Martin Gardner en 1977).
Con RSA o emisor dispón de 2 claves: unha para cifrar e outra para descifrar, que son distintas (nos casos anteriores, as claves tiñan que ser iguais). A de cifrado é pública e pode enviarse tranquilamente para que quen queira enviar algo poda cifralo. Cando se recibe a mensaxe cifrada pode descifrarse coa outra clave. A día de hoxe é o algoritmo utilizado para cifrar comunicacións, ventas por internet, etc...E todo grazas á maxia dos números primos.
Non imos explicar a matemática subxacente, aínda que recomendamos ler sobre ela. A nivel cualitativo chega con saber o que é a función de Euler e algúns teoremas matemáticos, como o pequeno teorema de Fermat (se p é primo e a > 0 entón a p-1 = 1 mod p).
O único que indicamos é a seguridade do algoritmo. A clave pública ven sendo o produto de 2 números primos moi grandes (de máis de 100 cifras cada un). Para descifralo teriamos que factorizar ese número, o cal é virtualmente imposible polo tamaño dos mesmos. De aquí que a obtención de novos números primos grandes sexa moi importante para as comunicacións e a economía dixital.
Autenticación de mensaxes e función hash
En internet non todo ten por que ser confidencial, tan só ten que ser dunha fonte fiable (por exemplo, saber que un mail ven do emisor previsto. E resulta que podemos usar o algoritmo RSA (ou sexa, o cifrado de clave pública) para acreditar a orixe dunha mensaxe.
O truco é debido a unha simetría de RSA: podemos cifrar coa clave privada e descifrar coa clave pública. Isto obviamente non ten seguridade pero si fiabilidade: se recibimos unha mensaxe cifrada coa nosa clave, podemos fiarnos máis do emisor. O proceso que autentificar con seguridade é o seguinte:
- O emisor cifra coa clave pública do receptor. Isto asegura a confidencialidade.
- O emisor cifra de novo coa súa clave privada. A mensaxe queda autentificada, ou asinada.
- O receptor usa a clave pública do emisor para descifrar a mensaxe cifrada no paso anterior. Isto é verificar.
- E por último o receptor usa a súa clave privada para descifrar o cifrado do primeiro paso.
Isto funciona cun alto nivel de efectividade, as nosas comunicacións e compras por internet están máis a salvo do que a xente pensa (agás cando deixamos entrar no ordenador a crackers e virus que rouban as nosas claves, en xeral por que usamos software privativo como o de Microsoft, moi inseguro), pero a cambio consume moitos recursos computacionais. De xeito práctico moitas veces o proceso se simplifica con algoritmos ou funcións hash. Funciona así:
- O emisor ten unha mensaxe e xenera unha cadena de bits curta (sobre 160 normalmente) que serán función da mensaxe (é decir, cada mensaxe xenera unha cadea de bits distinta). Isto é o hash, e ten a propiedade de que garante a integridade dunha mensaxe, pois no momento en que modifiquemos unha mínima parte da mensaxe a cadena varía completamente (exemplo: as palabras 'OLA' e 'HOLA' producirían un hash moi distinto).
- O emisor cifra o hash coa clave privada e acompaña á mensaxe cifrada.
- O receptor descifra o hash coa clave pública do emisor.
- Como coñece o algoritmo para xenerar o hash compara o hash recibido co que pode xenerar el aplicando o algoritmo á mensaxe. Se conciden isto garantiza que a mensaxe non foi modificada e é fiable, garantiza a identidade do emisor.
Isto é o que usamos para verificar a fiabilidade dun ficheiro. Por exemplo, se tomamos a sabia decisión de baixar unha distribución de software libre como MiniNo (creada por GALPÓN) dende a súa páxina, cando imos a descargas ademáis do ficheiro atopamos unha serie de códigos para cada ficheiro, md5, que garante a integridade e fiabilidade do ficheiros a descargar, e que non deixa de ser unha cadena hash.
