Hi ha un programari basat en codi 100% segur? Aquesta qüestió ha estat fonamental en la criptografia durant milers d’anys i se situa al centre dels esforços per obtenir informació privada a internet. En un nou treball de recerca, investigadors de Cornell Tech van identificar una clau sobre las vulnerabilitat del xifratge conjuntament amb la connexió d'un concepte matemàtic que pretén definir i mesurar l’atzar.
Aquest resultat no només mostra que la criptografia té un problema natural 'mare', sinó que també mostra una profunda connexió entre dues zones ben diferenciades de les matemàtiques i la informàtica , la criptografia i la teoria algorísmica de la informació.
El resultat, és que un problema natural computacional introduït als anys seixanta a la Unió Soviètica caracteritza la viabilitat de la criptografia bàsica (xifrat en clau privada, signatures digitals i autenticació.
Durant mil·lennis, la criptografia s'ha considerat un cicle: Algú va inventar un codi, el codi va ser efectiu fins que algú el va vulnerar. A la dècada del 1970, els investigadors que buscaven una millor teoria de la criptografia van introduir el concepte de la funció unidireccional: una tasca o problema què és fàcil de resoldre en una direcció, però impossible en l'altra.
La idea era, si es tingués una funció tan única, potser podria ser un molt bo punt de partida per entendre la criptografia. Xifrar el missatge, és molt fàcil. I si es disposa de la clau, també es pot desxifrar. Però algú que no sap la clau hauria, l'hauria de crear per poder descodificar el missatge.
Però els investigadors no han pogut demostrar l’existència d’una funció unidireccional. El candidat més conegut, que també és la base dels esquemes de xifratge més utilitzats a Internet, es basa en la factorització entera. És fàcil multiplicar dos nombres primers aleatoris, per exemple, 23 i 47, però és molt difícil trobar aquests dos factors si només es dóna el seu producte, 1.081.
Es creu que no existeix cap algorisme de factorització eficient per a un gran nombre, tot i que els investigadors encara no han trobat els algorismes adequats.
La pregunta que cal fer-se és si existeix. Hi ha algun problema natural que caracteritzi l'existència de funcions unidireccionals?" Si no hi ha, això és la clau de tots els problemes, i si hi ha una manera de resoldre aquest problema, es pot vulnerar totes les presumptes funcions d'un sol sentit. en cas contrari, es pot dir que és possible obtenir una criptografia segura.
Mentrestant, els matemàtics dels anys seixanta van identificar el que es coneix com la complexitat de Kolmogorov, que es refereix a quantificar la quantitat d’atzar o patró d’una cadena de números. La complexitat de Kolmogorov d'una cadena de números es defineix com la longitud del programa informàtic més curt que pot generar la cadena; per a algunes cadenes, com ara:121212121212121212121212121212, hi ha un programa curt que el genera: 1s i 2s alternatius. Però, per a les cadenes de nombres més complicades i aparentment aleatòries, com ara 37539017332840393452954329, pot ser que no existeixi un programa inferior a la longitud de la cadena.
El problema ha interessat durant molt de temps als matemàtics i als informàtics, entre ells Juris Hartmanis, professor emèrit d’informàtica i enginyeria. Com que el programa informàtic que intenta generar el nombre podria trigar milions o fins i tot milers de milions d’anys, els investigadors de la Unió Soviètica a la dècada dels 60, així com Hartmanis i altres a la dècada dels 80, van desenvolupar la complexitat de Kolmogorov limitada en el temps, un programa amb la durada curta que pot emetre una cadena de números en un cert temps.
Es va demostrar que si la complexitat de Kolmogorov té una limitació temporal en el temps, és difícil què existeixen funcions unidireccionals.
Tot i que la seva cerca és teòrica, té implicacions potencials en la criptografia, inclosa la seguretat a Internet.
Si es pot trobar un algorisme per resoldre el problema de complexitat del temps de Kolmogorov, es pot vulnerar tots els criptes, tots els esquemes de xifratge, totes les signatures digitals. Tanmateix, si no hi ha cap algorisme el suficientment eficient per resoldre aquest problema, es pot dir que és possible obtenir una funció unidireccional i, per tant, és pot afirmar que es possible obtenir xifratge i signatures digitals, etc.
Font: Cornell Tech
Cap comentari:
Publica un comentari a l'entrada