El esquema de huellas dactilares de Rabin es un método para implementar huellas dactilares utilizando polinomios en un campo finito . Fue propuesto por Michael O. Rabin . [1]
Esquema
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 dactilar 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.
Aplicaciones
Muchas implementaciones del algoritmo Rabin-Karp utilizan internamente huellas dactilares de Rabin.
El sistema de archivos de red de ancho de banda bajo (LBFS) del MIT usa 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 en un archivo. Para ahorrar en transferencias entre el cliente y el servidor, comparan sus sumas de comprobación y solo transfieren 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). Entonces, la idea es seleccionar bloques que no se basen en un desplazamiento específico, sino en alguna propiedad del contenido del bloque. LBFS hace esto deslizando una ventana de 48 bytes sobre el archivo y calculando la huella digital de Rabin de cada ventana. Cuando los 13 bits bajos de la huella digital 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 cualquiera de los 48 bytes sea un punto de interrupción es(1 en 8192). Esto tiene el efecto de bloques de tamaño variable resistentes a los cambios. Cualquier función hash podría usarse para dividir un archivo largo en bloques (siempre que se use 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 rodante 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 .
Ver también
Referencias
- ^ Michael O. Rabin (1981). "Toma de huellas dactilares por polinomios aleatorios" (PDF) . Centro de Investigación en Tecnología Informática, Universidad de Harvard. Informe técnico TR-CSE-03-01 . Consultado el 22 de marzo de 2007 . Cite journal requiere
|journal=
( ayuda ) - ^ Athicha Muthitacharoen, Benjie Chen y David Mazières "Un sistema de archivos de red de ancho de banda bajo"
enlaces externos
- Andrei Z. Broder (1993). "Algunas aplicaciones del método de huellas dactilares de Rabin" . Consultado el 12 de septiembre de 2011 . Cite journal requiere
|journal=
( ayuda ) - David Andersen (2007). "Aprovechamiento de la similitud para descargas de múltiples fuentes utilizando huellas de archivos" . Consultado el 12 de abril de 2007 . Cite journal requiere
|journal=
( ayuda ) - Ross N. Williams (1993). " Una guía indolora para los algoritmos de detección de errores CRC ".