El esquema de huellas dactilares de Rabin (también conocido como huellas dactilares polinomiales ) es un método para implementar huellas dactilares utilizando polinomios sobre un cuerpo finito . Fue propuesto por Michael O. Rabin . [1]
Dado un mensaje de n bits m 0 ,..., m n -1 , lo vemos como un polinomio de grado n -1 sobre el campo finito GF(2) .
Luego elegimos un polinomio irreducible aleatorio de grado k sobre GF(2), y definimos la huella digital del mensaje m como el resto después de la división de por sobre GF(2), que puede verse como un polinomio de grado k − 1 o como un número de k bits.
Muchas implementaciones del algoritmo Rabin-Karp utilizan internamente huellas dactilares de Rabin.
El sistema de archivos de red de bajo ancho de banda (LBFS) del MIT utiliza huellas dactilares de Rabin para implementar bloques resistentes a cambios de tamaño variable. [2] La idea básica es que el sistema de archivos calcula el hash criptográfico de cada bloque de un archivo. Para ahorrar en transferencias entre el cliente y el servidor, comparan sus sumas de comprobación y solo transfieren los bloques cuyas sumas de comprobación difieren. Pero un problema con este esquema es que una sola inserción al principio del archivo hará que cada suma de comprobación cambie si se utilizan bloques de tamaño fijo (por ejemplo, 4 KB). Por lo tanto, la idea es seleccionar bloques no en función de un desplazamiento específico, sino más bien en función de alguna propiedad del contenido del bloque. LBFS hace esto deslizando una ventana de 48 bytes sobre el archivo y calculando la huella dactilar de Rabin de cada ventana. Cuando los 13 bits inferiores de la huella dactilar son cero, LBFS llama a esos 48 bytes un punto de interrupción y finaliza el bloque actual y comienza uno nuevo. Dado que la salida de las huellas dactilares de Rabin es pseudoaleatoria, la probabilidad de que 48 bytes dados sean un punto de interrupción es (1 en 8192). Esto tiene el efecto de bloques de tamaño variable resistentes al desplazamiento. Se podría utilizar cualquier función hash para dividir un archivo largo en bloques (siempre que se utilice una función hash criptográfica para encontrar la suma de comprobación de cada bloque): pero la huella dactilar de Rabin es un hash rotativo eficiente , ya que el cálculo de la huella dactilar de Rabin de la región B puede reutilizar parte del cálculo de la huella dactilar de Rabin de la región A cuando las regiones A y B se superponen.
Tenga en cuenta que este es un problema similar al que enfrenta rsync . [ ejemplo necesario ]
