Construcció Merkle–Damgård
En criptografia, la construcció Merkle–Damgård o funció hash Merkle–Damgård és un mètode per construir funcions hash criptogràfiques resistents a col·lisions a partir de funcions de compressió unidireccional resistents a col·lisions.[1] :145Aquesta construcció es va utilitzar en el disseny de molts algorismes hash populars com MD5, SHA-1 i SHA-2.
La construcció Merkle–Damgård es va descriure al doctorat de Ralph Merkle. tesi l'any 1979.[2] Ralph Merkle i Ivan Damgård van demostrar de manera independent que l'estructura és sòlida: és a dir, si s'utilitza un esquema de farciment adequat i la funció de compressió és resistent a les col·lisions, la funció hash també serà resistent a les col·lisions.[3][4]
La funció hash de Merkle–Damgård aplica primer una funció de farciment compatible amb MD per crear una entrada la mida de la qual és múltiple d'un nombre fix (per exemple, 512 o 1024), això és perquè les funcions de compressió no poden gestionar entrades de mida arbitrària. Aleshores, la funció hash divideix el resultat en blocs de mida fixa i els processa un a un amb la funció de compressió, combinant cada vegada un bloc de l'entrada amb la sortida de la ronda anterior.[5] :146Per tal de garantir la construcció de la construcció, Merkle i Damgård van proposar que els missatges s'embutin amb un farciment que codifica la longitud del missatge original. Això s'anomena encoixinat de longitud o reforç Merkle-Damgård.
Al diagrama, la funció de compressió unidireccional es denota amb f, i transforma dues entrades de longitud fixa en una sortida de la mateixa mida que una de les entrades. L'algorisme comença amb un valor inicial, el vector d'inicialització (IV). El IV és un valor fix (algoritme o implementació específic). Per a cada bloc de missatges, la funció de compressió (o compactació) f porta el resultat fins ara, el combina amb el bloc de missatges i produeix un resultat intermedi. L'últim bloc s'omple de zeros segons sigui necessari i s'afegeixen bits que representen la longitud de tot el missatge. (Vegeu a continuació un exemple detallat de farciment de longitud).
Per endurir encara més el hash, l'últim resultat de vegades s'alimenta mitjançant una funció de finalització. La funció de finalització pot tenir diversos propòsits, com ara comprimir un estat intern més gran (l'últim resultat) en una mida hash de sortida més petita o garantir un millor efecte de mescla i allau en els bits de la suma hash. La funció de finalització sovint es construeix utilitzant la funció de compressió. (Cal tenir en compte que en alguns documents s'utilitza una terminologia diferent: l'acte de farciment de longitud s'anomena "finalització".
Referències
[modifica]- ↑ Goldwasser, S. and Bellare, M. "Lecture Notes on Cryptography" Arxivat 2012-04-21 a Wayback Machine.. Summer course on cryptography, MIT, 1996-2001
- ↑ R.C. Merkle. Secrecy, authentication, and public key systems. Arxivat 2018-08-14 a Wayback Machine. Stanford Ph.D. thesis 1979, pages 13-15.
- ↑ R.C. Merkle. A Certified Digital Signature. In Advances in Cryptology - CRYPTO '89 Proceedings, Lecture Notes in Computer Science Vol. 435, G. Brassard, ed, Springer-Verlag, 1989, pp. 218-238.
- ↑ I. Damgård. A Design Principle for Hash Functions. In Advances in Cryptology – CRYPTO '89 Proceedings, Lecture Notes in Computer Science Vol. 435, G. Brassard, ed, Springer-Verlag, 1989, pp. 416-427.
- ↑ Goldwasser, S. and Bellare, M. "Lecture Notes on Cryptography" Arxivat 2012-04-21 a Wayback Machine.. Summer course on cryptography, MIT, 1996-2001