Re: CRC reverse engineering

On Wed, 2 May 2007 17:16:06 +0000 (UTC), David Wagner wrote:
mvrpfswe wrote:
There must be a more elegant way of figuring this out rather then a
brute force,

One conceptually simple thing you can try is linear algebra.

Assume that each bit of the presumed-CRC-output can be written an
(unknown) linear function data bits; write down a system of linear
equations; and then use linear algrebra (Gaussian elimination) to
solve the system of linear equations and find the linear function
(if there is one) that describes how to compute that output bit as
a function of the input bits.

Indeed, the 28 sample values you presented can all be written as
linear combinations of 8 rows, each of which has just one 1-bit
in the byte that varies:

.. . . 01 . . . 5fd6
.. . . 02 . . . 5aab
.. . . 04 . . . 5951
.. . . 08 . . . 5fa2
.. . . 10 . . . 5a43
.. . . 20 . . . 5a86
.. . . 40 . . . f4c7
.. . . 80 . . . b0da


--
To email me, substitute nowhere->spamcop, invalid->net.
.

Relevant Pages

  • Re: Simple Sagnac
    ... In the frame of the train, ... > |> There is no linear relationship between t and tau and you've ... > |> cuckoo transforms are linear? ... > | A linear function of two variables is the sum of a constant times ...
    (sci.physics.relativity)
  • Re: Regression significance conundrum
    ... >>> linearly correlated with x, then there is a linear functional ... with a "linear function model between Y and X". ... about not knowing what a linear regression model is! ... >>NOW about how you SERIOUSLY erred about what correlation measures. ...
    (sci.stat.math)
  • Re: how to find a1,a2...an for the goal value?
    ... set of parameters there is a linear function of x for which the mean ... square difference between it and gis a minimum. ... between gand a best-fitting linear function in the above sense. ...
    (comp.soft-sys.matlab)
  • Re: Why momentum is a cotangent vector?
    ... elements of fibers are called momentum vectors. ... I have no special knowledge here, but in general, co-vectors are linear ... L is a function from velocities to reals. ... To get a linear function out of it, ...
    (sci.physics)
  • Re: FIGHT! FIGHT! FIGHT!
    ... requirements of a linear function when applied to network theory." ... Linear means the graph of the function is a straight line. ... In y = mx + b, m is a constant determining the slope of the line. ...
    (rec.radio.amateur.antenna)