¿Cómo puedo adivinar un algoritmo de suma de comprobación?

Question

¿Alguien sabe cómo descubrir el algoritmo CRC si se da un código dado + cadena CRC?

Tengo varias cadenas que consisten en código + CRC que coinciden, pero no sé cómo calcular el CRC en cuestión para poder producir más cadenas de código. He aquí algunos ejemplos de código de 16 bits (4 bits CRC +):

 
0010101000011101 + 0000 
0010101000011111 + 0001 
1000110011101101 + 0001 
0000000000000100 + 0010 
0011100011001110 + 0011 
1000110011101110 + 0100 
0001011110101100 + 0100 
0010101000011110 + 0101 
0011100011001101 + 0110 
0001011110101111 + 0111 
0011100011001100 + 1001 
0011100011001111 + 1010 
0001011110101101 + 1011 
0000000000001000 + 1011 
0000111100001101 + 1100 
0000000000001100 + 1100 
1111111111111111 + 1101 
1000110011101111 + 1101 
1000110011101100 + 1110 
0001011110101110 + 1110 
1111111100001101 + 1110 
0010101000011100 + 1111 

Estos códigos proceden de un emisor RF (433 MHz) como los productos X10.

No estoy seguro de si esto es un CRC o qué es, pero al menos se calculó de alguna manera fuera de las cadenas de código.

¿Alguien puede ayudar?

actualizaciones:

RE: encontrar las especificaciones también creo que sería la mejor solución, pero ya que esta es otra opción que necesito la fuerza bruta del cálculo de comprobación de alguna manera.

Este es el problema, no tengo las especificaciones y no puedo conseguirlas en ninguna parte. He intentado varios métodos de cálculo de suma de comprobación diferentes sin resultado, ¿no hay una manera de comparar las cadenas de entrada descubriendo lo que tienen en común y de esta manera obtener el algoritmo

Answer 1

Adivinar es la palabra correcta. Si este dispositivo de RF no es propietario, intente leer las especificaciones ! Esta sería la forma más fácil de hacerlo.

Adivinar todos los algoritmos CRC (o Hashing) posibles no parece demasiado optimista. Solo mira here.

Una tercera posibilidad es realizar una ingeniería inversa del código que está utilizando para generar las sumas de comprobación.

buena suerte :)

Answer 2

Hay demasiadas posibilidades algoritmo CRC de adivinar de manera eficaz. Puede tomar el enfoque fácil, que es encontrar una especificación para su dispositivo. O puede tomar el método de la fuerza bruta, que es calcular el CRC para cada entrada posible y crear un algoritmo que genere el mismo resultado.

Answer 3

Puede probar algunos métodos comunes de CRC y esperar tener suerte, pero la respuesta de Mana (en busca de especificaciones) sería la mejor opción.

Answer 4

¿Qué te hace pensar que es un CRC? Por lo general, los CRC no se utilizan para datos tan pequeños.

Para mí esto parece un tipo de paridad, ECC (en realidad FEC) o código Reed-Solomon. Puede ser Hamming Code - Hamming ampliamente utilizado en la industria, en las telecomunicaciones.

Answer 5

El punto entero en un buen algoritmo de suma de comprobación es que no tiene nada en común con el texto de entrada. Puedes cambiar un solo caracter en la entrada. y toda la suma de comprobación de cambiará. Entonces la única manera de ir por el otro lado es, sí, adivinar. Si sabe cuáles son las cadenas de entrada y salida, puede probar algunos algoritmos de suma de comprobación comunes y ver si alguno de ellos proporciona el resultado correcto. Aparte de eso, no, no es posible.

Alternativamente, como han sugerido otros, puede que no sea una suma de comprobación en absoluto, sino algún tipo de código de redundancia/corrección de errores, y que podría ser más fácil de descifrar.

Answer 6

Probablemente no es un CRC, pero todavía no logro encontrar el algoritmo de corrección/redundancia de errores.

Answer 7

@mecki puede ser correcto, pero es difícil de saber. Puede intentar Data format for X-10 wireless units y X-10 FAQ.

Answer 8

A juzgar por la longitud de las cadenas frente a la longitud de la suma de comprobación, diría que se trata de una simple suma de comprobación de corrección de 1 error. Es probable que sea uno de los simples que utilizan distancias Hamming. No puedo recordar de primera mano cómo funcionó, y no tengo ninguna teoría de la información/libros de texto de álgebra lineal sobre mí.

Answer 9

['0010101000011101', '0000', '0'] ['0010101000011110', '0101', '5'] [1, 3] 
['1000110011101101', '0001', '1'] ['1000110011101110', '0100', '4'] [1, 3] 
['0000000000000100', '0010', '2'] ['0000000000001000', '1011', 'b'] [0, 3] 
['0011100011001110', '0011', '3'] ['0011100011001101', '0110', '6'] [1, 3] 
['0001011110101100', '0100', '4'] ['0001011110101111', '0111', '7'] [2, 3] 
['0011100011001100', '1001', '9'] ['0011100011001111', '1010', 'a'] [2, 3] 
['0001011110101101', '1011', 'b'] ['0001011110101110', '1110', 'e'] [1, 3] 
['1000110011101111', '1101', 'd'] ['1000110011101100', '1110', 'e'] [2, 3] 

resultados de diferencial "análisis", esto no se parece a CRC, referencia: http://www.cosc.canterbury.ac.nz/greg.ewing/essays/CRC-Reverse-Engineering.html

Dudo que sea código de Hamming o bien, como 4 bits de paridad sólo permiten a los bits 11 de datos, no 16.