Descomposició de números clau contra certs codis
2011/11/01 Alberdi Celaya, Elisabete - Matematikan lizentziatua eta doktoregaia Iturria: Elhuyar aldizkaria
Si alguna vegada has accedit a una pàgina web "segura" --perquè has comprat un viatge d'avió a través d'Internet, has accedit a veure les últimes operacions del compte corrent-, la comunicació s'ha realitzat a través d'una plataforma segura, anomenada SSL, que està dins d'un protocol https (secure). En aquests casos hauràs pogut comprovar que en la barra de tasques del navegador apareix un cadenat. Indica que per a accedir a aquesta pàgina es necessita clau o clau, que ningú que no tingui clavi no pot accedir. És a dir, la comunicació és segura en la mesura en què el destinatari és l'únic que descodifica el missatge. Així que en comprar un bitllet a Ibèria, Ibèria xifra o codifica el teu número de visa. El missatge xifrat viatja per la xarxa i en arribar a Ibèria desxifren o descodifiquen el missatge xifrat. La comunicació és segura en la mesura en què l'únic que sap desxifrar el missatge és el destinatari.
La criptografia és un tècnic que utilitza diferents mètodes per a protegir un missatge. Encara que inicialment se situava en el camp de les matemàtiques, en l'actualitat també s'ha estès la informàtica i la telemàtica. No obstant això, l'ús de les tècniques de criptografia és molt antic. Les primeres civilitzacions van desenvolupar tècniques per a enviar missatges en campanyes militars. Encara que el missatger queia en mans de l'enemic, aconseguien que l'enemic no s'apropiés del missatge, ja que enviaven el missatge xifrat amb tècniques de criptografia. El destinatari del missatge en rebre'l desxifrava el missatge codificat amb l'operació inversa. En el segle V abans de Crist, l'eina utilitzada per a xifrar els missatges era l'anomenada “Escital”. En un pal s'enrotlla una cinta de cuir en la qual s'escrivia el missatge. Una vegada llevada la cinta del bastó, apareixien barrejades les lletres del missatge i només el que tenia el bastó del mateix diàmetre de l'escàndol podia desxifrar el missatge. En aquells temps, aquests bastons eren la força dels pobles, i des de llavors ve el pal que avui es lliura als alcaldes dels pobles.
Mètodes clàssics de xifrat
Els mètodes de xifrat de missatges es divideixen en dos grans blocs: clàssics i moderns. Alguns dels mètodes clàssics es basen en la substitució. Aquests mètodes substitueixen cada lletra del missatge per una altra lletra o número. Un exemple d'aquesta mena de mètodes a. C. És el cifrador que utilitzava Juli Cèsar en el segle I, en el qual cada lletra se substituïa per una lletra que en l'alfabet està tres espais més a la dreta que ella. Així, la lletra A se substituïa per D, la lletra B per E, etc. Qui rebia un missatge codificat amb la tècnica de César, substituint cada lletra per la qual estava alfabèticament 3 espais més a l'esquerra, obtenia el missatge inicial. Aquest mètode no era res segur.
El cifrador de César pot generalitzar-se substituint cada lletra per una lletra b espai més dreta que ella. En un alfabet de vint-i-set lletres hi ha 26 maneres de substituir una lletra per una altra. Provant les vint-i-sis formes s'obté el missatge. Per tant, aquest mètode generalitzat també és molt feble. A més, la prova amb totes les maneres de substituir una lletra quan s'utilitza aquest mètode no és l'única manera d'aclarir el missatge codificat. També es pot aclarir el missatge codificat coneixent l'idioma en el qual està escrit el missatge i la freqüència de les lletres en aquest idioma. Per a això, n'hi ha prou amb substituir la lletra que més apareix en el missatge codificat per la més freqüent en aquest idioma, i la distància entre totes dues lletres és la que ens indica la posició en la qual hem de moure cada lletra. Una vegada conegut el valor de b, movent cada lletra de missatge xifrat a l'esquerra l'espai b, obtindrem el missatge complet. És evident que aquest mètode no és segur.
Un xifrat més sofisticat és un xifrat afí; Ki = a . Amb l'operació La meva + b (mod27) s'aconsegueix codificar cada lletra La meva del missatge. Aquest resultat s'obté assignant un número a cada lletra i substituint el número corresponent a la lletra per aquesta fórmula. A continuació, a . El valor La meva + b es divideix per 27, sent el residu resultant el valor de Ki. Per a finalitzar s'introdueix la lletra corresponent a aquest número. Per exemple, H correspon al número 7 i per a a = 5, b = 7, Ki = 5 . Dóna 7 + 7 = 42 = 15 (mod27). Al número 15 li correspon la lletra O. Això significa que, utilitzant aquest xifrat, la lletra H es converteix en O. Encara que aquest mètode sembla més complex que l'anterior, quan el missatge codificat és llarg, utilitzant les freqüències de les lletres d'una llengua, és fàcil detectar el missatge.
Mètodes moderns de xifrat
Els moderns mètodes de xifrat poden utilitzar clau privada o clau pública. Els usuaris de clau privada poden ser de bloc o de flux. Els cifradores del bloc apliquen l'algorisme diverses vegades en un conjunt de caràcters de la informació utilitzant la mateixa clau. Exemples de cifradores en bloc són DONIS (Data Encryption Standard) i AES (Advanced Encryption Standard). En tots dos mètodes, l'algorisme és conegut i el clau, desconegut (privat). En els de flux, cada caràcter es xifra mitjançant una clau aleatòria llarga en la qual també es desconeix.
Però la modernitat tampoc ha alliberat aquests mètodes dels dits de la inseguretat. El principal desavantatge del cifrador DONIS és la petita grandària de la clau (56 bits). Això significa que hi ha 256 = 72.057.594.037.927.936 opcions per a triar la clau, i en el món dels ordinadors aquest número queda petit. Un exemple d'això és que en un DONIS challenge organitzat al gener de 1998 es va aconseguir trencar la clau en 56 hores, ja que es van utilitzar ordinadors que avaluaven 90.000 claus per segon. Per tenir una clau més llarga, de 112 bits, actualment s'utilitza més el triple DONIS, ja que ofereix 2112 opcions per a la clau. La clau del mètode AES també és més llarga: de 128, 129 i 256 bits. El desavantatge dels de flux és que el xifrat individual dels caràcters fa que la relació entre els caràcters del missatge codificat sigui feble.
Entre els mètodes que utilitzen la clau pública es troba la coneguda com RSA (Rivest, Shamir, Adleman). És un mètode fins ara segur, però com es pot aconseguir la certesa amb una clau coneguda per a tots? La clau està en la difícil operació de desxifrat.
Descomposició de números
Els éssers humans comencem a descompondre els números des de molt nen. Un dels conceptes que aprenem primer és el del número primer: El número a és el primer, només si es pot dividir per ±a i ±1. Així, els números 2, 3, 5, 7... són els primers. Quan volem descompondre un número, comencem a dividir per nombres primers menors que ell. Per exemple, el número 15 es descompon com el producte dels nombres primers 3 i 5. Quan un número no està dividit per nombres primers menors que aquell, es diu que és el primer. Per tant, anem afegint a la llista de nombres primers que hem indicat anteriorment la relació dels següents primers números: 11, 13, 17, 19, 23,...131, 137,... O bé: 244497-1, 213466917-1,... Sí, no hi ha números menors que ells que els puguin dividir.
Encara que els números petits donen treball, podem dir amb bastant facilitat si són els primers o no. Però què podem dir del número 94550!-1? És la primera? En matemàtiques hi ha diverses eines per a dir si un número és el primer o no. I si un número no és el primer, com es descompon?
Encara que existeixen algorismes eficaços per a descompondre certs números, la descomposició de qualsevol número continua sent un misteri matemàtic i el sistema RSA aprofita aquest misteri per a construir la seva codificació. Utilitzant l'RSA, el destinatari del missatge fa públics dos números: e i n El primer número, e, és el que el remitent utilitzarà per a codificar el missatge. És a dir, si x és un missatge, el remitent realitzarà la següent operació: x - e ; i aquest serà el missatge codificat que anirà per la xarxa. El destinatari, per a desxifrar el missatge codificat que ha rebut, utilitzarà el número e ', que calcularà reconeixent el número n i que compleix ( x - e ) e' = x -. D'aquesta manera, el destinatari recuperarà el missatge inicial. En el sistema RSA, el número n es tria com el producte de dos nombres primers, i el misteri que envolta la descomposició dels números fa que el número n sigui pràcticament indescomponible. En conseqüència, el número e ' necessari per a l'operació a realitzar per a aclarir el missatge pot ser obtingut per qui sap gairebé exclusivament descompondre n, és a dir, per qui ha creat el número.
Conclusions
Igual que en el seu moment els mètodes de substitució van quedar enrere, a mesura que les velocitats dels ordinadors augmentaven, les tècniques de criptografia que utilitzen les claus curtes s'han anat quedant enrere i aniran, ja que la clau llarga actual pot ser curta demà. Encara que el sistema RSA no té aquest tipus de desavantatges, depèn de la descomposició dels números; si es trobés un algorisme eficaç de descomposició de números, seria el final del sistema RSA que fins ara hem tingut com a assegurança. Si això ocorregués, necessitaríem un nou sistema de codificació. Qui donarà l'algorisme eficaç per a la descomposició de números? I qui crearà un sistema segur de xifrat que no pot dominar la velocitat dels ordinadors?
Bibliografia
