Descomposición de números crave contra certos códigos
2011/11/01 Alberdi Celaya, Elisabete - Matematikan lizentziatua eta doktoregaia Iturria: Elhuyar aldizkaria
Si algunha vez accediches a unha páxina web "segura" --porque compraches unha viaxe de avión a través de Internet, accediches a ver as últimas operacións da conta corrente-, a comunicación realizouse a través de una plataforma segura, chamada SSL, que está dentro dun protocolo https (secure). Nestes casos poderías comprobar que na barra de tarefas do navegador aparece un cadeado. Indica que paira acceder a esta páxina necesítase clave ou clave, que ninguén que non teña clave non pode acceder. É dicir, a comunicación é segura na medida en que o destinatario é o único que descodifica a mensaxe. Así que ao comprar un billete en Iberia, Iberia cifra ou codifica o teu número de visa. A mensaxe cifrada viaxa pola rede e ao chegar a Iberia descifran ou descodifican a mensaxe cifrada. A comunicación é segura na medida en que o único que sabe descifrar a mensaxe é o destinatario.
A criptografía é un técnico que utiliza diferentes métodos paira protexer unha mensaxe. Aínda que inicialmente situábase no campo das matemáticas, na actualidade tamén se estendeu a informática e a telemática. Con todo, o uso das técnicas de criptografía é moi antigo. As primeiras civilizacións desenvolveron técnicas paira enviar mensaxes en campañas militares. Aínda que o mensaxeiro caía en mans do inimigo, conseguían que o inimigo non se apropiase da mensaxe, xa que enviaban a mensaxe cifrada con técnicas de criptografía. O destinatario da mensaxe ao recibilo descifraba a mensaxe codificado coa operación inversa. No século V antes de Cristo, a ferramenta utilizada paira cifrar as mensaxes era a chamada “Escital”. Nun pau enrólase una cinta de coiro na que se escribía a mensaxe. Una vez quitada a cinta do bastón, aparecían mesturadas as letras da mensaxe e só o que tiña o bastón do mesmo diámetro do escándalo podía descifrar a mensaxe. Naqueles tempos, estes bastóns eran a forza dos pobos, e desde entón vén o pau que hoxe se entrega aos alcaldes dos pobos.
Métodos clásicos de cifrado
Os métodos de cifrado de mensaxes divídense en dous grandes bloques: clásicos e modernos. Algúns dos métodos clásicos baséanse na substitución. Estes métodos substitúen cada letra da mensaxe por outra letra ou número. Un exemplo deste tipo de métodos a. C. É o cifrador que utilizaba Xullo César no século I, no que cada letra se substituía por unha letra que no alfabeto está tres espazos máis á dereita que ela. Así, a letra A substituíase por D, a letra B por E, etc. Quen recibía unha mensaxe codificado coa técnica de César, substituíndo cada letra pola que estaba alfabeticamente 3 espazos máis á esquerda, obtiña a mensaxe inicial. Este método non era nada seguro.
O cifrador de César pode xeneralizarse substituíndo cada letra por unha letra b espazo máis dereita que ela. Nun alfabeto de vinte e sete letras hai 26 formas de substituír una letra por outra. Probando as vinte e seis formas obtense a mensaxe. Por tanto, este método xeneralizado tamén é moi débil. Ademais, a proba con todas as formas de substituír una letra cando se utiliza este método non é a única maneira de aclarar a mensaxe codificado. Tamén se pode aclarar a mensaxe codificado coñecendo o idioma no que está escrito a mensaxe e a frecuencia das letras nese idioma. Paira iso, basta con substituír a letra que máis aparece na mensaxe codificado pola máis frecuente nese idioma, e a distancia entre ambas as letras é a que nos indica a posición na que debemos mover cada letra. Una vez coñecido o valor de b, movendo cada letra de mensaxe cifrada á esquerda o espazo b, obteremos a mensaxe completa. É evidente que este método non é seguro.
Un cifrado máis sofisticado é un cifrado afín; Ki = a . Coa operación A miña + b (mod27) conséguese codificar cada letra A miña da mensaxe. Este resultado obtense asignando un número a cada letra e substituíndo o número correspondente á letra por esta fórmula. A continuación, a . O valor O meu + b divídese por 27, sendo o residuo resultante o valor de Ki. Paira finalizar introdúcese a letra correspondente a este número. Por exemplo, H corresponde ao número 7 e paira a = 5, b = 7, Ki = 5 . Dá 7 + 7 = 42 = 15 (mod27). Ao número 15 correspóndelle a letra Ou. Isto significa que, utilizando este cifrado, a letra H convértese en Ou. Aínda que este método parece máis complexo que o anterior, cando a mensaxe codificado é longo, utilizando as frecuencias das letras dunha lingua, é fácil detectar a mensaxe.
Métodos modernos de cifrado
Os modernos métodos de cifrado poden utilizar clave privada ou clave pública. Os usuarios de clave privada poden ser de bloque ou de fluxo. Os cifradores do bloque aplican o algoritmo varias veces nun conxunto de caracteres da información utilizando a mesma clave. Exemplos de cifradores en bloque son DEAS (Data Encryption Standard) e AES (Advanced Encryption Standard). En ambos os métodos, o algoritmo é coñecido e a clave, descoñecido (privado). Nos de fluxo, cada carácter cífrase mediante unha clave aleatoria longa na que tamén se descoñece.
Pero a modernidade tampouco liberou estes métodos dos dedos da inseguridade. A principal desvantaxe do cifrador DEAS é o pequeno tamaño da clave (56 bits). Isto significa que hai 256 = 72.057.594.037.927.936 opcións paira elixir a clave, e no mundo dos computadores ese número queda pequeno. Un exemplo diso é que nun DEAS challenge organizado en xaneiro de 1998 conseguiuse romper a clave en 56 horas, xa que se utilizaron computadores que avaliaban 90.000 claves por segundo. Por ter una clave máis longa, de 112 bits, actualmente utilízase máis o triplo DEAS, xa que ofrece 2112 opcións paira a clave. A clave do método AES tamén é máis longa: de 128, 129 e 256 bits. A desvantaxe dos de fluxo é que o cifrado individual dos caracteres fai que a relación entre os caracteres da mensaxe codificado sexa débil.
Entre os métodos que utilizan a clave pública atópase a coñecida como RSA (Rivest, Shamir, Adleman). É un método até agora seguro, pero como se pode conseguir a certeza cunha clave coñecida paira todos? A clave está na difícil operación de descifrado.
Descomposición de números
Os seres humanos empezamos a descompor os números desde moi neno. Uno dos conceptos que aprendemos primeiro é o do número primeiro: O número a é o primeiro, só se se pode dividir por ±a e ±1. Así, os números 2, 3, 5, 7... son os primeiros. Cando queremos descompor un número, empezamos a dividir por números primos menores que el. Por exemplo, o número 15 descomponse como o produto dos números primos 3 e 5. Cando un número non está dividido por números primos menores que aquel, dise que é o primeiro. Por tanto, imos engadindo á lista de números primos que indicamos anteriormente a relación dos seguintes primeiros números: 11, 13, 17, 19, 23,...131, 137,... Ou ben: 244497-1, 213466917-1,... Si, non hai números menores que eles que os poidan dividir.
Aínda que os números pequenos dan traballo, podemos dicir con bastante facilidade se son os primeiros ou non. Pero que podemos dicir do número 94550!-1? É a primeira? En matemáticas hai varias ferramentas paira dicir se un número é o primeiro ou non. E se un número non é o primeiro, como se descompón?
Aínda que existen algoritmos eficaces paira descompor certos números, a descomposición de calquera número segue sendo un misterio matemático e o sistema RSA aproveita este misterio paira construír o seu codificación. Utilizando a RSA, o destinatario da mensaxe fai públicos dous números: e e n O primeiro número, e, é o que o remitente utilizará paira codificar a mensaxe. É dicir, se x é unha mensaxe, o remitente realizará a seguinte operación: x - e ; e ese será a mensaxe codificado que irá pola rede. O destinatario, paira descifrar a mensaxe codificado que recibiu , utilizará o número e ', que calculará recoñecendo o número n e que cumpre ( x - e ) e' = x -. Deste xeito, o destinatario recuperará a mensaxe inicial. No sistema RSA, o número n elíxese como o produto de dous números primos, e o misterio que rodea a descomposición dos números fai que o número n sexa practicamente indescomponible. En consecuencia, o número e ' necesario paira a operación a realizar paira aclarar a mensaxe pode ser obtido por quen sabe case exclusivamente descompor n, é dicir, por quen creou o número.
Conclusións
Do mesmo xeito que no seu día os métodos de substitución quedaron atrás, a medida que as velocidades dos computadores aumentaban, as técnicas de criptografía que utilizan as claves curtas fóronse quedando atrás e irán, xa que a clave longa actual pode ser curta mañá. Aínda que o sistema RSA non ten este tipo de desvantaxes, depende da descomposición dos números; se se atopase un algoritmo eficaz de descomposición de números, sería o final do sistema RSA que até agora tivemos como seguro. Se isto ocorrese, necesitariamos un novo sistema de codificación. Quen dará o algoritmo eficaz paira a descomposición de números? E quen creará un sistema seguro de cifrado que non pode dominar a velocidade dos computadores?
Bibliografía
