Arbre de Merkle

Arbre de Merkle
Un arbre de Merkle binaire.

En informatique et en cryptographie, un arbre de Merkle ou arbre de hachage est une structure de données contenant un résumé d'information d'un volume de données, généralement grand (comme un fichier).

Les arbres de hachage ont été inventés par Ralph Merkle en 1979[1].

Fonctionnement

Le principe d'un arbre de hachage consiste à décomposer les données d'entrée en un ensemble de blocs de tailles identiques. Ces blocs sont les feuilles de l'arbre. Ils sont généralement complétés avec des valeurs neutres, comme des zéros, de façon à obtenir des blocs de la taille souhaitée.

Les nœuds de niveau supérieur sont ensuite obtenus en compressant les nœuds du niveau courant à l'aide d'une fonction de hachage/compression jusqu'à n'obtenir qu'un nœud : la racine.

Utilisations

Actuellement, les arbres de hachage sont très utilisés dans les réseaux pair à pair, car ils permettent de vérifier l'intégrité d'une partie d'un fichier. En effet, il suffit alors de connaître le bon nœud se situant à la hauteur nécessaire dans l'arbre, sans nécessairement devoir posséder tout le fichier.

Ils sont également très utilisés dans les fonctions de hachage cryptographique, comme MD6, car ils sont intrinsèquement parallélisable, et permettent donc à ces algorithmes de tirer parti du parallélisme présent dans les ordinateurs modernes.

Les arbres de Merkle sont aussi utilisés dans le système de fichiers ZFS[2], dans le protocole Google Wave ou dans le système de monnaie virtuelle bitcoin.

Références

  1. ↑ R. C. Merkle, A digital signature based on a conventional encryption function, Crypto '87
  2. ↑ Jeff Bonwick's Blog ZFS End-to-End Data Integrity
v · Fonctions de hachage cryptographiques
Algorithmes APR1 · AR · Boognish · FFT-hash · HAS-160 · Haval · MD2 · MD4 · MD5 · MD6 · N-hash · PANAMA · RIPEMD · RIPEMD-128 · RIPEMD-160 · RIPEMD-256 · Famille SHA (SHA-0 · SHA-1 · SHA-224 · SHA-256 · SHA-384 · SHA-512) · Snefru · StepRightUp · Tiger · VSH · Whirlpool
Cryptanalyse Paradoxe des anniversaires · Linéaire · Différentielle · Attaque par force brute · Effet avalanche · Pseudo-collision
Architecture Remplissage · Fonction de compression · Construction de Merkle-Damgård · Construction de Miyaguchi-Preneel · Construction de Matyas-Meyer-Oseas · Construction de Davies-Meyer

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Arbre de Merkle de Wikipédia en français (auteurs)

Игры ⚽ Нужно сделать НИР?

Regardez d'autres dictionnaires:

  • Ralph Merkle — Ralph C. Merkle (né le 2 février 1952), cryptographe américain et chercheur en nanotechnologie. Il est l un des pionniers de la cryptographie asymétrique avec Martin Hellman et Whitfield Diffie. En 1974, il a créé les puzzles de Merkle, la… …   Wikipédia en Français

  • MD6 — L algorithme MD6, pour Message Digest 6, est une fonction de hachage cryptographique qui permet d obtenir l empreinte numérique d un fichier (on parle souvent de message). MD6 a été développée par un groupe[1] mené par Ronald L. Rivest,… …   Wikipédia en Français

  • Message Digest 6 — MD6 L algorithme MD6, pour Message Digest 6, est une fonction de hachage cryptographique qui permet d obtenir l empreinte numérique d un fichier (on parle souvent de message). MD6 a été développée par un groupe[1] mené par Ronald L. Rivest,… …   Wikipédia en Français

  • Bitcoin — sur Ubuntu …   Wikipédia en Français

  • Probleme du sac a dos — Problème du sac à dos Le problème du sac à dos : quelles boîtes choisir afin de maximiser la somme emportée tout en ne dépassant pas les 15 kg autorisés ? Le problème du sac à dos, noté également KP (en anglais, Knapsack Problem) est un …   Wikipédia en Français

  • Problème du sac à dos — Le problème du sac à dos : quelles boîtes choisir afin de maximiser la somme emportée tout en ne dépassant pas les 15 kg autorisés ? En algorithmique, le problème du sac à dos, noté également KP (en anglais, Knapsack Problem) est un… …   Wikipédia en Français

  • Austro-bavarois — Bavarois Pour les articles homonymes, voir Bavarois (homonymie). Austro bavarois Bairisch Österreichisch Parlée en Allemagne, Autriche, Italie, Suisse République tchèque, Hongrie Région …   Wikipédia en Français

  • Bavarois — Pour les articles homonymes, voir Bavarois (homonymie). Austro bavarois Bairisch Österreichisch Parlée en Allemagne, Autriche, Italie, Suisse République tchèque, Hongrie Nombre de locuteu …   Wikipédia en Français

  • Cuisine Allemande — Saucisses, chou et pomme de terre La cuisine allemande est une cuisine riche en diversité. Au delà des stéréotypes concernant la consommation de bière, de porc, de choux et de pommes de terre, elle développe une cuisine inventive, aux ingrédients …   Wikipédia en Français

  • Cuisine allemande — Saucisses, chou et pomme de terre La cuisine allemande est une cuisine riche en diversité. Au delà des stéréotypes concernant la consommation de bière, de porc, de choux et de pommes de terre, elle développe une cuisine inventive, aux ingrédients …   Wikipédia en Français

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”