Empreinte de Rabin

L’empreinte de Rabin est une méthode pour calculer des empreintes à l’aide de polynômes opérant sur un corps fini. Elle a été proposée par Michael O. Rabin.

Principe

À partir d’un message de n bits m₀..., m_n-1, celui-ci est traité comme un polynôme de degré n-1 sur le corps fini GF(2).

$f(x)=m_0+m_{1}x+\dots +m_{n-1}{x}^{n-1}$

Un polynôme irréductible aléatoire p(x) de degré k sur GF(2) est alors choisi, et l’empreinte du message m est définie comme le reste $r(x)$ de la division de $f(x)$ par $p(x)$ sur GF(2), qui peut être vu comme un polynôme de degré k-1 ou comme un nombre de k bits.

Applications

De nombreuses implémentations de l’algorithme de Rabin-Karp utilisent les empreintes de Rabin en interne.

Le système de fichiers de réseau bas débit (LBFS) du MIT utilise les empreintes de Rabin pour implémenter des blocs de taille variable résistants au décalage. L’idée est que le système de fichiers calcule la somme de contrôle de chaque bloc dans un fichier. Pour économiser des transferts entre client et serveur, les sommes de contrôle sont comparées, et seuls les blocs pour lesquels elles sont différentes sont transférés.

Un problème lié à ce traitement est qu’une simple insertion au début du fichier entraîne la modification de toutes les sommes de contrôle, si des blocs de taille fixe (par ex. Modèle:Unité) sont utilisés. L’idée est donc de sélectionner des blocs d’après certaines propriétés de leur contenu plutôt que d’après un décalage spécifique. LBFS réalise cela en déplaçant une fenêtre de Modèle:Unité dans le fichier et en calculant l’empreinte de Rabin de chaque fenêtre. Quand les 13 bits inférieurs de l’empreinte valent 0, LBFS appelle ces Modèle:Unité un point d’arrêt, termine le bloc actuel et en démarre un nouveau. Comme les empreintes de Rabin sont pseudo-aléatoires, la probabilité qu’un ensemble quelconque de Modèle:Unité soit un point d’arrêt est de $2^{-13}$. Cela a pour résultat des blocs de taille variable résistants au décalage. N’importe quelle fonction de hachage pourrait être utilisée pour diviser un long fichier en blocs (du moment qu’une fonction de hachage cryptographique est utilisée ensuite pour déterminer la somme de contrôle de chaque bloc) : mais l’empreinte de Rabin est une Modèle:Lien efficace, puisque le calcul de l’empreinte de Rabin d’une région B peut réutiliser une partie des calculs de l’empreinte de Rabin d’une région A, du moment que les régions A et B se chevauchent.

Notez que ce problème est similaire à celui rencontré par rsync.

Voir aussi

• Modèle:Lien
• Modèle:Lien

Liens externes

• Modèle:Ouvrage
• Modèle:Ouvrage
• Rabin fingerprint algorithm implemented in C