Tal vez simplemente no lo esté viendo, pero CRC32 parece innecesariamente complicado o no está suficientemente explicado en cualquier lugar que pueda encontrar en la web.
Entiendo que es el resto de una división aritmética no basada en acarreo del valor del mensaje, dividido por el polinomio (generador), pero se me escapa la implementación real.
He leído Una guía indolora de algoritmos de detección de errores de CRC , y debo decir que no fue indoloro. Repasa bastante bien la teoría, pero el autor nunca llega a un simple "esto es". Dice cuáles son los parámetros para el algoritmo estándar CRC32, pero se olvida de exponer claramente cómo se llega a él.
La parte que me atrapa es cuando dice "esto es todo" y luego agrega, "oh, por cierto, se puede revertir o comenzar con diferentes condiciones iniciales", y no da una respuesta clara de cuál es la forma final de calcular una suma de comprobación CRC32 dados todos los cambios que acaba de agregar.
- ¿Existe una explicación más sencilla de cómo se calcula CRC32?
Intenté codificar en C cómo se forma la tabla:
for (i = 0; i < 256; i++)
{
temp = i;
for (j = 0; j < 8; j++)
{
if (temp & 1)
{
temp >>= 1;
temp ^= 0xEDB88320;
}
else {temp >>= 1;}
}
testcrc[i] = temp;
}pero esto parece generar valores inconsistentes con valores que he encontrado en otros lugares de Internet. Yo podría utilizar los valores que encontré en línea, pero quiero entender la forma en que fueron creados.
Cualquier ayuda para aclarar estos números increíblemente confusos sería muy apreciada.
0xEDB88320también se puede escribir msbit-first ( normal ) como0x04C11DB7. ¿Los valores de la tabla que encontró en otro lugar se generaron utilizando el mismo polinomio CRC?Respuestas:
El polinomio de CRC32 es:
O en hexadecimal y binario:
El término más alto (x 32 ) generalmente no está escrito explícitamente, por lo que se puede representar en hexadecimal como
Siéntase libre de contar los 1 y 0, pero encontrará que coinciden con el polinomio, donde
1está el bit 0 (o el primer bit) y elxbit 1 (o el segundo bit).¿Por qué este polinomio? Porque debe haber un polinomio estándar dado y el estándar fue establecido por IEEE 802.3. Además, es extremadamente difícil encontrar un polinomio que detecte diferentes errores de bits de manera efectiva.
Puede pensar en el CRC-32 como una serie de "Aritmética binaria sin acarreos", o básicamente "operaciones XOR y de desplazamiento". Esto se denomina técnicamente aritmética polinomial.
Para entenderlo mejor, piense en esta multiplicación:
Si asumimos que x es base 2, obtenemos:
¿Por qué? Debido a que 3x ^ 3 es 11x ^ 11 (pero solo necesitamos 1 o 0 dígitos previos), trasladamos:
Pero los matemáticos cambiaron las reglas para que sea el mod 2. Entonces, básicamente, cualquier polinomio binario mod 2 es simplemente una suma sin acarreo ni XOR. Entonces nuestra ecuación original se ve así:
Sé que esto es un acto de fe, pero está más allá de mi capacidad como programador de línea. Si eres un estudiante de informática o un ingeniero empedernido, reto a desglosar esto. Todos se beneficiarán de este análisis.
Entonces, para resolver un ejemplo completo:
Ahora dividimos el Mensaje aumentado por el Poli usando aritmética CRC. Esta es la misma división que antes:
La división produce un cociente, que desechamos, y un resto, que es la suma de comprobación calculada. Esto finaliza el cálculo. Por lo general, la suma de verificación se agrega al mensaje y se transmite el resultado. En este caso la transmisión sería: 11010110111110.
Solo use un número de 32 bits como divisor y use toda su transmisión como dividendo. Deseche el cociente y conserve el resto. Marque el resto al final de su mensaje y tendrá un CRC32.
Revisión de chico promedio:
(Tenga en cuenta que el flujo debe poder dividirse en 32 bits o debe rellenarse. Por ejemplo, un flujo ANSI de 8 bits debería rellenarse. También al final del flujo, la división se detiene).
fuente
x^6 + x^5 + x^4 + 3*x^3 + x^2 + x^1 + x^0 ... If we assume x is base 2 then we get: x^7 + x^3 + x^2 + x^1 + x^0. No es así como funcionan las matemáticas. Los coeficientes del polinomio son mod (2) o GF (2), las x se dejan solas, lo que da como resultado x ^ 6 + x ^ 5 + x ^ 4 + x ^ 3 + x ^ 2 + x ^ 1 + x ^ 0 (ya que 3 mod (2) = 1).Tack the remainder on the end of your message- técnicamente, el resto se resta de los 0 bits que se agregaron al mensaje, pero como se trata de matemáticas mod (2), tanto la suma como la resta son iguales que XOR, y los bits cero XOR'ed con el resto son iguales como el resto.Why did you append four 0s though?- los algoritmos de software para calcular crc agregan efectivamente los 0, aunque no sea evidente. Si se muestra el cálculo de CRC usando la división de mano larga, entonces se deben agregar 0 para que el ejemplo de división aparezca correctamente.Para IEEE802.3, CRC-32. Piense en todo el mensaje como un flujo de bits en serie, agregue 32 ceros al final del mensaje. A continuación, DEBE invertir los bits de CADA byte del mensaje y complementar los primeros 32 bits con un 1. Ahora divida por el polinomio CRC-32, 0x104C11DB7. Finalmente, debe complementar a 1 el resto de 32 bits de esta división, invertir cada uno de los 4 bytes del resto. Esto se convierte en el CRC de 32 bits que se agrega al final del mensaje.
La razón de este extraño procedimiento es que las primeras implementaciones de Ethernet serializarían el mensaje un byte a la vez y transmitirían primero el bit menos significativo de cada byte. El flujo de bits en serie luego pasó por un cálculo de registro de desplazamiento CRC-32 en serie, que simplemente se complementó y se envió por cable después de que se completó el mensaje. La razón para complementar los primeros 32 bits del mensaje es para que no obtenga un CRC completamente cero, incluso si el mensaje fue solo ceros.
fuente
Un CRC es bastante simple; toma un polinomio representado como bits y los datos, y divide el polinomio en los datos (o representa los datos como un polinomio y hace lo mismo). El resto, que está entre 0 y el polinomio es el CRC. Su código es un poco difícil de entender, en parte porque está incompleto: temp y testcrc no están declarados, por lo que no está claro qué se está indexando y cuántos datos se están ejecutando a través del algoritmo.
La forma de entender los CRC es tratar de calcular algunos utilizando un fragmento de datos corto (16 bits más o menos) con un polinomio corto, quizás 4 bits. Si practica de esta manera, realmente comprenderá cómo podría hacerlo para codificarlo.
Si lo hace con frecuencia, un CRC es bastante lento de computar en software. La computación por hardware es mucho más eficiente y requiere solo unas pocas puertas.
fuente
Además de la verificación de redundancia cíclica de Wikipedia y los artículos de Computación de CRC , encontré un artículo titulado Reversing CRC - Theory and Practice * como una buena referencia.
Básicamente, existen tres enfoques para calcular un CRC: un enfoque algebraico, un enfoque orientado a bits y un enfoque basado en tablas. En Reversing CRC - Theory and Practice * , cada uno de estos tres algoritmos / enfoques se explica en teoría acompañado en el APÉNDICE por una implementación para el CRC32 en el lenguaje de programación C.
* PDF Link
Reversing CRC - Teoría y práctica.
Informe público de HU Berlín
SAR-PR-2006-05 de
mayo de 2006
Autores:
Martin Stigge, Henryk Plötz, Wolf Müller, Jens-Peter Redlich
fuente
Pasé un tiempo tratando de descubrir la respuesta a esta pregunta, y finalmente publiqué un tutorial sobre CRC-32 hoy: Tutorial de hash de CRC-32 - AutoHotkey Community
En este ejemplo, demuestro cómo calcular el hash CRC-32 para la cadena ASCII 'abc':
fuente
^? stackoverflow.com/questions/62168128/…Luego siempre está el Código Rosetta, que muestra crc32 implementado en docenas de lenguajes de computadora. https://rosettacode.org/wiki/CRC-32 y tiene enlaces a muchas explicaciones e implementaciones.
fuente
Para reducir crc32 a aceptar el recordatorio, debe:
En código esto es:
donde reminderIEEE es el recordatorio puro en GF (2) [x]
fuente