Re: Efficient reduction of polynoms with only one term



On 16/10/2010 11:08, Johannes Bauer wrote:

For my experiments I chose
explicitly a CRC polynomial as there are CRC generators out there (like
the said website) to verify my results. Aren't CRCs just that (i.e.
dividing some arbitrary polynomial by the CRC polynomial, yielding the
residual)?


No, for three main reasons, then a few others:

1) In CRC as used in telecom, it is customary to add at the end
of the message as many bits as the order of the generator
polynomial, before division by the generator polynomial.
That's because during verification it then becomes possible to
enter the CRC itself in the CRC checker exactly as for the message,
which is handy when the end mark is after the CRC following the
message.

2) It is customary to add an initialization pattern before the
message, with the effect that it reduces the odds that loss of
bits at start of the message remains undetected.

3) Hardware implementors want to map bits with the chronologically
first bit at the higher coefficient of polynomials, because that's
the only way to compute the CRC bit per bit; on the other hand,
ever since the telex, low order bits of characters have been
transmitted first, and that extended to 8-bit bytes. Therefore,
when computing in software a REALLY standard CRC, the low order bit
of a byte often represents a higher order polynomial coefficient
than the high order bit of that same byte; while mathematicians
and software guys want the other convention, for good reasons.


Francois Grieu
.



Relevant Pages

  • Re: CCITT-CRC16 in kernel
    ... You can reverse the convention and still have a CRC, ... It does not correspond to either your polynomials ... but the hardware did that. ... > CRC with preset to 0 and no inversion. ...
    (Linux-Kernel)
  • Re: CCITT-CRC16 in kernel
    ... You can reverse the convention and still have a CRC, ... It does not correspond to either your polynomials ... CRC with preset to 0 and no inversion. ...
    (Linux-Kernel)
  • Microcontroller Flash loader "ready", comments?
    ... of the Flash loader encryption running. ... A 32 bit CRC with a secret polynomial serves as authentication. ... any pointers where I can learn more about suitable polynomials? ... whether it would be better to combine the cipher ...
    (sci.crypt)
  • Re: Microcontroller Flash loader "ready", comments?
    ... I am working on a bootloader too but for Atmel ATmega chips. ... >A 32 bit CRC with a secret polynomial serves as authentication. ... any pointers where I can learn more about suitable polynomials? ... >don't know the effect on the cipher quality. ...
    (sci.crypt)
  • Re: reverse engineering of a CRC-16 algorithm
    ... If this were a CRC, I would have expected it to be linear, hence ... write the checksum as a polynomial c. ... highest common factor of the polynomials qand q'). ... have n known-input/output pairs, ...
    (sci.crypt)