Control de redundancia cíclica
De Wikipedia, la enciclopedia libre
La comprobación de redundancia cíclica (CRC) 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 ser usado para designar tanto a la función como a su resultado. Pueden ser usadas como suma de verificación para detectar la alteración de datos durante su transmisión o almacenamiento. Las CRCs son populares porque su implementación en hardware binario es simple, son fáciles de analizar matemáticamente y son particularmente efectivas para detectar errores ocasionados por ruido en los canales de transmisión. La CRC fue inventada y propuesta por W. Wesley Peterson en un artículo publicado en 1961[1] .
Tabla de contenidos |
[editar] 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 usamos conforma que el cálculo utilizado es el arrastre de un campo finito, 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 especifica el divisor que se utilizará, entre otras cosas. Aunque CRC se puede construir utilizando cualquier tipo de regla finita, todos CRC de uso común emplean una base finita binaria, esta base consta de dos elementos, generalmente el 0 y 1,El resto de este artículo se centrara en este tipo de composición, es decir el ambito binario y los principios generales de los CRC.
[editar] La Integridad de los Datos Frente a la Codificación
Mientras usemos la detección de errores, el CRC no es lo suficientemente eficiente en condiciones de seguridad para verificar plenamente [y corrección de errores la corrección de datos]. Como medida de seguridad un mensaje se supondrá falso cuando la transmisión de un mensaje y su CRC se realice por un canal abierto, para verificar su autenticidad se comprobara que la CRC coincide con el mensaje del CRC calculado, entonces el mensaje no ha sido alterado en tránsito. Esta suposición es falsa porque CRC es un mal método de cifrado de datos. De hecho, el CRC no se trata realmente de un método de cifrado, lo que realmente hace es utilizarse para el control de integridad de datos, pero en algunos casos se supone que se utilizarán para el cifrado. Cuando un CRC se calcula, el mensaje se conserva (no cifrado) y la constante de tamaño CRC se sitúa hacia el 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í múltiples códigos producirá el mismo CRC. Por supuesto, estos códigos están diseñados para ser lo suficientemente diferentes como para variar (y por lo general sólo en uno o dos bits) el cambios en la palabra clave produciría una fantástica diferencia entre CRC, y por ese motivo el error es posible detectarlo. Si la manipulación deliberada (cambios de los bits) se produce en el mensaje, entonces se tomara una nueva clave, produciendo un falso CRC el cual puede ser calculado para el nuevo mensaje y sustituir el CRC real en el final del paquete Así la CRC es confiables para verificar la integridad, pero no 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]
[editar] Cálculo de CRC
La mecánica de la informática con su lenguaje binario produce unas CRC simples. Los bits representados de entrada son alineados en una fila, y el (n +1) 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 tiene como divisor 0, no hace nada y pasar el divisor a la derecha de uno en uno. Si la entrada que está por encima de la izquierda tiene como divisor 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 elegido a menos que la especificación de algún proceso posterior lo cambie).
[editar] Matemáticas del CRC
Este apartado se refiere al análisis matemático de este proceso de división, como pone de manifiesto la manera de elegir un divisor que garantiza la detección de errores buenas propiedades. En este análisis, los dígitos de las cadenas de bits son considerados como los coeficientes de un polinomio en algunos variable x - coeficientes, que son elementos del campo finito binario en lugar de los números decimales. Este "polinomio " forma unas cadenas de bits que pueden observarse como elementos de un anillo. Un anillo es, hablando en términos generales, un conjunto de elementos, es decir como los números que pueden ser operados por una operación semejante pero no idéntica a la de la suma y además alguna otra operación semejante a la multiplicación, estas operaciones poseen muchas de las propiedades de la aritmética conmutatividad, asociativa, y distributiva.
[editar] 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 chequear 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) a el mensaje que se debe controlar ya que se cogería un polinomio que no seria el correcto para la división.Esto tiene la conveniencia de que la 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 mas 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 maquina, y cada HW 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.
[editar] Referencias
- ↑ Peterson, W. W. y Brown, D. T. (enero de 1961). "Cyclic Codes for Error Detection". Proceedings of the IRE. DOI:10.1109/JRPROC.1961.287814.
[editar] Véase también
[editar] Enlaces externos
- Easy to understand CRC32 C++ Source Code
- Free CRC Source Code from the Boost C++ Libraries
- The CRC Pitstop
- Williams, R. (1993-09) A Painless Guide to CRC Error Detection Algorithms
- Understanding Cyclic Redundancy Check
- Black, R. (1994-02) Fast CRC32 in Software; algorithm 4 is used in Linux and info-zip's zip and unzip.
- Kounavis, M. and Berry, F. (2005). A Systematic Approach to Building High Performance, Software-based, CRC generators, Slicing-by-4 and slicing-by-8 algorithms
- CRC32: Generating a checksum for a file, C++ implementation by Brian Friesen
- CRC16 to CRC64 collision research
- Reversing CRC - Theory and Practice.
- 'CRC-Analysis with Bitfilters'.
- Another Bad CRC Reading Tool, but free
- MathPages - Cyclic Redundancy Checks
- Tool for Bad CRC Reading with advanced options
- A CRC calculation utility and C source code generator written in Python. (MIT licence)
- CRC Encoding - C# Implementation by Marcel de Wijs
- Cyclic Redundancy Check: theory, practice, hardware, and software with emphasis on CRC-32. A sample chapter from Henry S. Warren, Jr. Hacker's Delight.
[editar] Herramientas Online
- Hash'em all! free online text and file hashing with different algorithms (including CRC)
- Free CRC Verilog Circuit generator
- Online CRC32 and CRC32B calculator
- Online Tool to compute common CRCs (8/16/32/64) from strings
- Online CRC calculator
- Another online CRC calculator
- Online CRC Tool: Generator of synthesizable CRC functions
- Online Char (ASCII), HEX, Binary, Base64, etc... Encoder/Decoder with MD2, MD4, MD5, SHA1+2, CRC, etc. hashing algorithms
