Una història del hash

Una funció hash genèrica és un tipus especial de funció de programació que s’utilitza per assignar dades de mida arbitrària a dades de una mida fixa. Les funcions Hash es van originar en la necessitat de comprimir dades per reduir la quantitat de memòria necessària per emmagatzemar fitxers grans. El cas d’ús més popular per a una funció hash és per a una altra estructura de dades específica anomenada a taula de hash, que s’utilitza àmpliament per a la cerca ràpida de dades. Les funcions de hash ajuden a accelerar la cerca de taules o bases de dades mitjançant la detecció de dos hash iguals.

També ajuden a minimitzar les etiquetes de fitxers enormes com ara fitxers mp3, PDF o imatges per tal de fer més fàcil treballar amb aquests tipus de fitxers força grans. Per a una identificació ràpida, un requisit clau de les funcions de hash és que aquestes emet una cadena de caràcters alfanumèrics de longitud fixa.

Tot i que la raó fonamental de la creació d’una funció de hash provenia de la necessitat de comprimir el contingut, un benefici secundari aviat es va convertir en un element bàsic del hash: identificadors singulars. L’ideal seria que, quan es mostressin diversos missatges, cap missatge diferent no ha de tornar mai el mateix hash. Es denomina a dos missatges de resum diferenciats que donen lloc al mateix resum de sortida col·lisió.

Des de la perspectiva de la gestió de bases de dades, això significaria que dos objectes diferents acaben emmagatzemats a la mateixa cel·la; no serveix de res si es busca definir identificadors únics. Si considerem una funció hash amb entrades infinites (és a dir, podem hash qualsevol cadena), podem derivar exactament per què de fet són les col·lisions inevitable.

Principi del colomar

Dins de la criptografia matemàtica existeix un concepte anomenat principi del colomar que afirma que si encaixem (n) elements en (m) espais on n > m, llavors, per principi, existeix almenys un espai (m) ocupat per més de dos elements (n).

Per exemple, cinc individus es comproven els abrics en un dels tres armaris disponibles. Segons el principi del forat, ja que el nombre de capes emmagatzemades (n) és superior al cubbies disponible (m), es garanteix que, com a mínim, un cabot conté més d’una capa.

Normalment, els enginyers de programari estan interessats en funcions de resum amb un domini infinit (és a dir, prenen com a cadenes d’entrada de totes les longituds possibles) i a rang finit. Un cop més, seguint el principi del forat, ja que el nostre rang (n) és més petit que el nostre domini (m), se segueix que a ha d’existir almenys una col·lisió. Per tant, una funció de hash eficaç només busca minimitzar el nombre de col·lisions: per què això es farà més clar en un moment, però, de moment, tornem a la història dels hash.

Tot i que les funcions de hash es van originar estrictament en el manteniment de la base de dades & les necessitats de gestió, que afavoria sobretot la velocitat, la seva utilitat va evolucionar ràpidament. Una branca especial de funcions de hash que afavoria la privadesa i la seguretat, & aviat va entrar la transparència al camp; una branca de funcions de hash que seguirà sent el focus d’aquest article: funcions de resum criptogràfic.

Hashing criptogràfic

Les funcions de resum criptogràfic, com bé indica el nom, afavoreixen la preservació de missatges absolutament ininterromputs. Tot i que minimitzar les col·lisions és una bona pràctica per a altres funcions de hash, per a funcions específicament criptogràfiques, és mínim minimitzar les col·lisions requisit. En lloc de maximitzar la utilitat per a una base de dades ràpida o un escenari de cerca de taules, les funcions de resum criptogràfic es creen tenint en compte un escenari contradictori: aquell en què un interruptor de codi (criptoanalista) intenta activament provocar una col·lisió. Ara definirem les notacions de funció hash estàndard & establir principis de funció hash dins de la perspectiva de la criptografia.

Notació de funció hash

Una funció de hash criptogràfic genèrica té dues entrades: el missatge que comprimirà o hash (x) & una clau pública que representa la sortida de longitud fixa del nostre hash en caràcters alfanumèrics. El nostre resultat resum es denomina resum de missatges o simplement resum (x *). Això té el següent aspecte:


H (s, x) = x *

Passem per alt aquesta notació caminant per un exemple de la vida real que hashing una cadena mitjançant una funció de hashing anteriorment estàndard anomenada MD5. Suposem que volem fer servir l’MD5 per generar un hash “Hello World!” corda. També sabem que per defecte MD5 sempre genera una cadena de 128 bits (0’s) & 1). Aquesta notació tindria el següent aspecte:

H (128, x) = ed076287532e86365e841e92bfc50d8c

De fet, si segueixes endavant & proveu de proporcionar la funció de hash MD5 “Hello World!” hauríeu de veure el mateix hash resultant. Impressionant. Ara anem a establir la notació per a una col·lisió; a més de les variables anteriors H, s, x, & x * ara introduïm un segon missatge (x ’). Numèricament, es produeix una col·lisió quan es mostren dos missatges diferents (x & x ’) dóna com a resultat el mateix resum de missatges (x *):

Si H (128, x) = H (128, x ’), es diu que la nostra funció de hash (H) té una col·lisió a x & x ’.

Ara hem definit la notació per a l’estàndard actual de la criptografia de funció hash; si un adversari pot provocar una col·lisió (parlant computacionalment), una funció de hash ja no es considera pràcticament segura.

Pensaments de clausura fins a la propera vegada

L’última definició matemàtica és on viu el fascinant catch-22 per a la pràctica de la funció hash. Les funcions Hash es van originar en la necessitat de comprimir & ofereixen dades uniformes estandarditzades per comoditat d’emmagatzematge, el que significa que escupen cadenes pseudoreatorials de longitud fixa. No obstant això, per tal de crear un fitxer totalment resistent a les col·lisions funció hash, cada missatge (x) hauria de tenir una sortida hash del fitxer la mateixa longitud que l’entrada. Sense hash d’una longitud fixa, perdem la nostra capacitat d’utilitzar-los com a estructura de dades convenient, tot i que assignant una longitud fixa, fem que la nostra funció hash no estigui totalment lliure de col·lisions..

PS: estic segur que alguns de vosaltres, les galetes intel·ligents, van notar que al nostre exemple MD5 hem notat una funció de resum que retorna una cadena de longitud 128, tot i així, el nostre “Hello World!” hash ha retornat a 32 cadena de caràcters alfanumèrics. Torneu la propera vegada & aprofundirem en les funcions de hash per explicar d’on va sorgir aquesta diferència.

Mike Owergreen Administrator
Sorry! The Author has not filled his profile.
follow me