stringtranslate.com

Suma de comprobación

Efecto de una función de suma de comprobación típica (la cksumutilidad Unix)

Una suma de comprobación es un bloque de datos de tamaño pequeño derivado de otro bloque de datos digitales con el fin de detectar errores que puedan haberse introducido durante su transmisión o almacenamiento . Por sí mismas, las sumas de comprobación se utilizan a menudo para verificar la integridad de los datos , pero no se confía en ellas para verificar su autenticidad . [1]

El procedimiento que genera esta suma de comprobación se denomina función de suma de comprobación o algoritmo de suma de comprobación . Según sus objetivos de diseño, un buen algoritmo de suma de comprobación suele generar un valor significativamente diferente, incluso para pequeños cambios realizados en la entrada. [2] Esto es especialmente cierto en el caso de las funciones hash criptográficas , que pueden utilizarse para detectar muchos errores de corrupción de datos y verificar la integridad general de los datos ; si la suma de comprobación calculada para la entrada de datos actual coincide con el valor almacenado de una suma de comprobación calculada previamente, existe una probabilidad muy alta de que los datos no se hayan alterado o corrompido accidentalmente.

Las funciones de suma de comprobación están relacionadas con las funciones hash , las huellas dactilares , las funciones de aleatorización y las funciones hash criptográficas . Sin embargo, cada uno de esos conceptos tiene diferentes aplicaciones y, por lo tanto, diferentes objetivos de diseño. Por ejemplo, una función que devuelve el comienzo de una cadena puede proporcionar un hash apropiado para algunas aplicaciones, pero nunca será una suma de comprobación adecuada. Las sumas de comprobación se utilizan como primitivas criptográficas en algoritmos de autenticación más grandes. Para sistemas criptográficos con estos dos objetivos de diseño específicos [ aclaración necesaria ] , consulte HMAC .

Los dígitos de control y los bits de paridad son casos especiales de sumas de comprobación, apropiados para pequeños bloques de datos (como números de la Seguridad Social , números de cuentas bancarias , palabras de computadora , bytes individuales , etc.). Algunos códigos de corrección de errores se basan en sumas de comprobación especiales que no solo detectan errores comunes, sino que también permiten recuperar los datos originales en ciertos casos.

Algoritmos

Byte de paridad o palabra de paridad

El algoritmo de suma de comprobación más simple es el llamado control de paridad longitudinal , que divide los datos en "palabras" con un número fijo n de bits y luego calcula la operación exclusiva o (XOR) de todas esas palabras. El resultado se agrega al mensaje como una palabra adicional. En términos más simples, para n = 1 esto significa agregar un bit al final de los bits de datos para garantizar que haya un número par de "1". Para verificar la integridad de un mensaje, el receptor calcula la operación exclusiva o de todas sus palabras, incluida la suma de comprobación; si el resultado no es una palabra que consta de n ceros, el receptor sabe que ocurrió un error de transmisión. [3]

Con esta suma de comprobación, cualquier error de transmisión que invierta un solo bit del mensaje, o un número impar de bits, se detectará como una suma de comprobación incorrecta. Sin embargo, no se detectará un error que afecte a dos bits si esos bits se encuentran en la misma posición en dos palabras distintas. Tampoco se detectará el intercambio de dos o más palabras. Si los bits afectados se eligen de forma independiente al azar, la probabilidad de que no se detecte un error de dos bits es 1/ n .

Complemento de suma

Una variante del algoritmo anterior consiste en sumar todas las "palabras" como números binarios sin signo, descartando los bits de desbordamiento y añadiendo el complemento a dos del total como suma de comprobación. Para validar un mensaje, el receptor suma todas las palabras de la misma manera, incluida la suma de comprobación; si el resultado no es una palabra llena de ceros, debe haberse producido un error. Esta variante también detecta cualquier error de un solo bit, pero la suma modular pro se utiliza en SAE J1708 . [4]

Dependiente de la posición

Las sumas de comprobación simples descritas anteriormente no detectan algunos errores comunes que afectan a muchos bits a la vez, como cambiar el orden de las palabras de datos o insertar o eliminar palabras con todos los bits configurados en cero. Los algoritmos de suma de comprobación más utilizados en la práctica, como la suma de comprobación de Fletcher , Adler-32 y las comprobaciones de redundancia cíclica (CRC), abordan estas debilidades al considerar no solo el valor de cada palabra sino también su posición en la secuencia. Esta característica generalmente aumenta el costo de calcular la suma de comprobación.

Suma de comprobación difusa

La idea de la suma de comprobación difusa se desarrolló para la detección de correo no deseado mediante la creación de bases de datos cooperativas de varios ISP de correo electrónico sospechoso de ser spam. El contenido de dicho spam a menudo puede variar en sus detalles, lo que haría que la suma de comprobación normal fuera ineficaz. Por el contrario, una "suma de comprobación difusa" reduce el texto del cuerpo a su mínimo característico y luego genera una suma de comprobación de la manera habitual. Esto aumenta en gran medida las posibilidades de que correos electrónicos spam ligeramente diferentes produzcan la misma suma de comprobación. El software de detección de spam de ISP, como SpamAssassin , de ISP cooperadores, envía sumas de comprobación de todos los correos electrónicos al servicio centralizado como DCC . Si el recuento de una suma de comprobación difusa enviada excede un cierto umbral, la base de datos señala que esto probablemente indica spam. Los usuarios del servicio ISP generan de manera similar una suma de comprobación difusa en cada uno de sus correos electrónicos y solicitan al servicio una probabilidad de spam. [5]

Consideraciones generales

Un mensaje de m bits de longitud puede considerarse como una esquina del hipercubo de m dimensiones . El efecto de un algoritmo de suma de comprobación que produce una suma de comprobación de n bits es asignar cada mensaje de m bits a una esquina de un hipercubo más grande, con dimensión m + n . Las 2 m + n esquinas de este hipercubo representan todos los mensajes recibidos posibles. Los mensajes recibidos válidos (aquellos que tienen la suma de comprobación correcta) comprenden un conjunto más pequeño, con solo 2 m esquinas.

Un error de transmisión de un solo bit corresponde entonces a un desplazamiento desde una esquina válida (el mensaje correcto y la suma de comprobación) a una de las m esquinas adyacentes. Un error que afecta a k bits mueve el mensaje a una esquina que está a k pasos de distancia de su esquina correcta. El objetivo de un buen algoritmo de suma de comprobación es dispersar las esquinas válidas lo más lejos posible entre sí, para aumentar la probabilidad de que los errores de transmisión "típicos" terminen en una esquina no válida.

Véase también

Tema general

Corrección de errores

Funciones hash

Sistemas de archivos

Conceptos relacionados

Referencias

  1. ^ "Definición de CHECKSUM". Merriam-Webster . Archivado desde el original el 2022-03-10 . Consultado el 2022-03-10 .
  2. ^ Hoffman, Chris (30 de septiembre de 2019). "¿Qué es una suma de comprobación (y por qué debería importarte)?". How-To Geek . Archivado desde el original el 9 de marzo de 2022. Consultado el 10 de marzo de 2022 .
  3. ^ Fairhurst, Gorry (2014). "Sumas de comprobación y comprobaciones de integridad". Archivado desde el original el 8 de abril de 2022. Consultado el 11 de marzo de 2022 .
  4. ^ "SAE J1708". Kvaser.com. Archivado desde el original el 11 de diciembre de 2013.
  5. ^ "IXhash". Apache. Archivado desde el original el 31 de agosto de 2020. Consultado el 7 de enero de 2020 .

Lectura adicional

Enlaces externos