Empreinte de Rabin

À 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).

${\displaystyle f(x)=m_{0}+m_{1}x+\ldots +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 ${\displaystyle r(x)}$ de la division de ${\displaystyle f(x)}$ par ${\displaystyle p(x)}$ sur GF(2), qui peut être vu comme un polynôme de degré k-1 ou comme un nombre de k bits.

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[2]. 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. 4 ko) 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 48 octets 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 48 octets 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 48 octets soit un point d’arrêt est de ${\displaystyle 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 fonction de hachage déroulante (en) 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.

• W-shingling (en)
• Rolling hash (en)

• Andrei Z. Broder, Some applications of Rabin's fingerprinting method, 1993 (lire en ligne)
• David Andersen, Exploiting Similarity for Multi-Source Downloads using File Handprints, 2007 (lire en ligne)
• Rabin fingerprint algorithm implemented in C

• Portail de l'informatique théorique