Verificación de redundancia cíclica

La verificación por redundancia cíclica[1]​ (CRC) es un código de detección de errores usado frecuentemente en redes digitales y en dispositivos de almacenamiento para detectar cambios accidentales en los datos.[1]​ Los bloques de datos ingresados en estos sistemas contiene un valor de verificación adjunto, basado en el residuo de una división de polinomios; el cálculo se repite y la acción de corrección puede tomarse contra los datos presuntamente corruptos en caso de que el valor de verificación no concuerde. Este código es un tipo de función que recibe un flujo de datos de cualquier longitud como entrada y devuelve un valor de longitud fija como salida. El término suele usarse para designar tanto a la función como a su resultado. Pueden usarse como suma de verificación para detectar la alteración de datos durante su transmisión o su almacenamiento. El CRC es popular porque su implementación en hardware binario es simple, es fácil de analizar matemáticamente y es particularmente efectiva para errores ocasionados por ruido en los canales de transmisión. El CRC fue inventado y propuesto por W. Wesley Peterson en un artículo publicado en 1961.[2]​

Introducción

El CRC es un código de detección de error cuyo cálculo es una larga división de computación en el que se descarta el cociente y el resto se convierte en el resultado, con la importante diferencia de que la aritmética que se usa conforma que el cálculo utilizado es el arrastre de un campo; en este caso, los bits. El tamaño del resto es siempre menor que la longitud del divisor, que, por lo tanto, determina el tamaño del resultado. La definición de un CRC específica el divisor que se utilizará, entre otras cosas. Aunque un CRC se puede construir utilizando cualquier tipo de regla finita, todos los CRC de uso común emplean una base finita binaria que consta de dos elementos, generalmente el 0 y el 1. El resto de este artículo se centrará en este tipo de composición, es decir, el ámbito binario y los principios generales de los CRC.

La integridad de los datos frente a la codificación

El CRC es útil para detección de errores, pero, en condiciones de seguridad, no se puede confiar en que el CRC puede verificar plenamente que los datos son los correctos en el caso de que se hayan producido cambios deliberados y no aleatorios. A menudo se piensa que si, cuando llega un mensaje, este y su CRC coinciden, quiere decir que el mensaje no ha podido ser alterado durante su transmisión, aunque se haya transmitido por un canal abierto. Esta suposición es falsa porque el CRC es un mal método de cifrado de datos. De hecho, no se trata realmente de un método de cifrado; lo que realmente hace es controlar la integridad de los datos, pero en algunos casos se supone que se utilizará para el cifrado.

Cuando un CRC se calcula, el mensaje se conserva (no cifrado) y la constante de tamaño CRC se sitúa al final (es decir, el mensaje puede ser tan fácil como leer antes de la posición que ocupa el CRC). Además, la longitud del CRC es por lo general mucho más pequeña que la longitud del mensaje; es imposible para una relación de 1:1 entre la CRC y el mensaje. Así, numerosos códigos producirán el mismo CRC.

Por supuesto, estos códigos están diseñados para ser lo suficientemente diferentes como para variar (y por lo general solo en uno o dos bits). Pequeños cambios en la palabra clave producirían una gran diferencia entre un CRC y otro; por ese motivo, es posible detectar el error.

Si la manipulación del mensaje (cambios de los bits) es deliberada, entonces se tomará una nueva clave, produciendo un falso CRC que puede calcularse para el nuevo mensaje y sustituir al CRC real en el final del paquete; esta modificación no podrá detectarse.

El CRC sirve para verificar la integridad, pero no para saber si el mensaje es correcto.

Por el contrario, un medio eficaz para proteger a los mensajes contra la manipulación intencional es el uso de un código de autenticación de mensajes como HMAC.

Cálculo de CRC

La mecánica de la informática con su lenguaje binario produce unos CRC simples.

Los bits representados de entrada se alinean en una fila y el (n + 1), que representa el patrón de bits del divisor CRC (llamado polinomio), se coloca debajo de la parte izquierda del final de la fila. Aquí está la primera de ellas para el cálculo de 3 bits de CRC: 

11010011101100 <--- entrada
1011           <--- divisor (4 bits) 
-------------- 
01100011101100 <--- resultado

Si la entrada que está por encima del extremo izquierdo del divisor es 0, no se hace nada y se pasa el divisor a la derecha de uno en uno. Si la entrada que está por encima de la izquierda del divisor es 1, el divisor es Or exclusiva en la entrada (en otras palabras, por encima de la entrada de cada bit el primer bit conmuta con el divisor). El divisor es entonces desplazado hacia la derecha, y el proceso se repite hasta que el divisor llega a la derecha, en la parte final de la fila de entrada. Aquí está el último cálculo: 

00000000001110 <--- resultado de la multiplicación de cálculo 
          1011 <--- divisor 
-------------- 
00000000000101 <--- resto (3 bits)

Desde la izquierda se divide por cero todos los bits de entrada, cuando este proceso termina el único bits en la fila de entrada que puede ser distinto de cero es n bits más a la derecha, en la parte final de la fila. Estos n bits son el resto de la división, y será también el valor de la función CRC (es el CRC escogido a menos que la especificación de algún proceso posterior lo cambie).

Matemáticas del CRC

El análisis matemático de este proceso similar a la división pone de manifiesto la manera de elegir un divisor que garantiza buenas propiedades de detección de errores. En este análisis, los dígitos de las cadenas de bits son considerados como los coeficientes de un polinomio en alguna variable x: coeficientes que son elementos del cuerpo finito GF(2) (los enteros módulo 2, es decir, un cero o un uno) en lugar de los números decimales. El conjunto de polinomios con coeficientes binarios es un anillo en el sentido matemático.

Especificación de un CRC

El CRC se utiliza como una detección de errores de código, el cual tiene una serie de aplicaciones usadas cuando se implementa mediante normas, convirtiéndolo así en un sistema práctico.

Estas son algunas de las aplicaciones:

  • Se usa un patrón de prefijos de bit para comprobar su autenticidad. Esto es útil cuando la trama podría tener errores en los bits de delante de un mensaje, una alteración que, de otro modo dejaría sin cambios al CRC. A veces un envío agrega n bits (n es el tamaño de la CRC) al mensaje que se debe controlar ya que se tomaría un polinomio que no sería el correcto para la división. Esto tiene la conveniencia de que el CRC del mensaje original con el CRC adjunto es exactamente cero, por lo que el CRC se puede comprobar simplemente por la división polinómica y comparando con el resto cero. A veces se realiza una implementación del CRC con OR exclusivos en el resto de la división polinómica.
  • Orden de los bits: en ocasiones, el orden en el que se envían las tramas de datos no corresponden exactamente con la posición que tendrán los bits en la división polinómica; es decir, que puede que el primer bit enviado sea el de más peso o viceversa. Este convenio tiene sentido cuando las tramas a enviar se envían por puertos series ya que el CRC es comprobado por el hardware de cada máquina, y cada uno tendrá un convenio conjunto de lectura y posicionamiento de paquetes para el envió a la capa siguiente.
  • Omisión del orden del bit de más peso del polinomio divisor: algunos escritores proponen omitir esto, puesto que el bit mayor peso es siempre 1, y ya que el bit CRC debe ser definido por un (n + 1) bits del divisor, es innecesario mencionar el divisor mayor peso en el mensaje y en el CRC.

Referencias

  1. ↑ a b «verificación por redundancia cíclica». Diccionario Español de Ingeniería (1.0 edición). Real Academia de Ingeniería de España. 2014. Consultado el 9 de septiembre de 2014. 
  2. ↑ Peterson, W. W. y Brown, D. T. (enero de 1961). «Cyclic Codes for Error Detection». Proceedings of the IRE. ISSN 0096-8390. doi:10.1109/JRPROC.1961.287814. 

Véase también

Enlaces externos

Herramientas en línea