Cyclic Redundancy Check

The cyclic redundancy check (CRC) is an error detection code frequently used in digital networks and storage devices to detect accidental changes in data. in these systems it contains an adjoint check value, based on the remainder of a division of polynomials; the calculation is repeated, and corrective action can be taken against the suspected corrupted data in case the check value does not match. This code is a type of function that takes a data stream of any length as input and returns a fixed-length value as output. The term is usually used to designate both the function and its result. They can be used as a checksum to detect data tampering during transmission or storage. CRCs are popular because their implementation in binary hardware is simple, they are easy to analyze mathematically, and they are particularly effective for errors caused by noise in transmission channels. The CRC was invented and proposed by W. Wesley Peterson in an article published in 1961.

Introduction

The CRC is an error detection code whose calculation is a computational long division in which the quotient is discarded and the remainder becomes the result, with the important difference that the arithmetic we use makes the calculation used is the dragging of a field, in this case the bits. The size of the remainder is always less than the length of the divisor, which therefore determines the size of the result. The definition of a CRC specifies the divisor to be used, among other things. Although a CRC can be constructed using any type of finite rule, all commonly used CRCs use a binary finite base, this base consists of two elements, usually 0 and 1. The rest of this article will focus on this type of composition., that is, the binary scope and the general principles of CRCs.

Data integrity vs. encryption

This is useful for error detection, but in safety we can't rely on the CRC to fully verify that the data is correct in case of deliberate rather than random changes.

It is often thought that if, when a message arrives, it and its CRC match, it means that the message could not have been altered during its transmission, even though it was transmitted over an open channel.

This assumption is false because CRC is a bad data encryption method. In fact, the CRC is not really an encryption method, what it actually does is used for data integrity checking, but in some cases it is supposed to be used for encryption.

When a CRC is computed, the message is preserved (not encrypted) and the CRC-size constant is placed toward the end (ie, the message can be as easy as reading before the CRC position).

Also, the length of the CRC is usually much smaller than the length of the message, making it impossible for a 1:1 relationship between the CRC and the message.

Thus, many codes will produce the same CRC.

Of course, these codes are designed to be different enough to vary (and usually only by one or two bits). Small changes to the keyword would make a big difference between one CRC and another; for that reason it is possible to detect the error.

If message tampering (bit changes) is deliberate, then a new key will be taken, producing a false CRC which can be computed for the new message and substitute the real CRC at the end of the packet and this modification it will not be able to be detected.

The CRC is used to verify the integrity, but not to know if the message is correct.

In contrast, an effective means of protecting messages against intentional tampering is the use of a message authentication code such as HMAC.

CRC calculation

The mechanics of computing with its binary language produces simple CRCs. The input represented bits are row aligned, and the (n + 1) representing the CRC divisor bit pattern (called a polynomial) is placed below the left end of the row. Here's the first one for the 3-bit CRC calculation:

11010011101100 Δ-
1011;- divisor (4 bits)
-...
01100011101100 Δ- result

If the entry above the left end of the divisor is 0, do nothing and pass the divisor to the right one by one. If the input above the left of the divisor is 1, the divisor is exclusive-OR on the input (in other words, each bit above the input the first bit toggles with the divisor). The divider is then moved to the right, and the process is repeated until the divider reaches the right, at the end of the input row. Here is the latest calculation:

00000000001110 Δ- result of calculation multiplication
1011.
-...
00000000000101 Δ--- rest (3 bits)

From the left all input bits are divided by zero, when this process finishes the only bit in the input row that can be non-zero is n bits further to the right, at the end of the row. These n bits are the remainder of the division, and will also be the value of the CRC function (it is the chosen CRC unless some downstream specification changes it).

CRC Math

CRC Math

This section deals with the mathematical analysis of this division process, as evidenced by the way to choose a divider that guarantees good error detection properties. In this analysis, the digits of the bit strings are considered as the coefficients of a polynomial in some x/coefficient variables, which are binary finite field elements rather than the decimal numbers. This "polynomial" forms bit strings that can be seen as elements of a ring. A ring is, generally speaking, a set of elements. That is to say, as the numbers that can be operated by an operation similar but not identical to that of addition and also some other operation similar to multiplication. These operations have many of the properties of arithmetic: commutative, associative, and distributive.

Specifying a CRC

CRC is used as a code error detection, which has a number of applications used when implemented by standards, making it a practical system.

These are some of the applications:

• A bit prefix pattern is used to check its authenticity. This is useful when the plot could have bugs in the bits in front of a message, an alteration that would otherwise leave CRC unchanged. Sometimes a shipment adds n bits (n is the size of the CRC) to the message that should be controlled as a polynomial would be taken that would not be correct for the division. This has the convenience that CRC of the original message with the attached CRC is exactly zero, so CRC can be simply checked by the polynomial division and compared to the remaining zero. Sometimes a CRC implementation is carried out with exclusive RW in the rest of the polynomial division.

• Order of bits: Sometimes the order in which the data plots are sent does not correspond exactly to the position that the bits will have in the polynomial division; that is, that the first bit sent may be the most weighted or vice versa. This agreement makes sense when the plots to send are sent by serial ports as the CRC is checked by the hardware of each machine, and each one will have a joint agreement reading and positioning packages for it sent to the next layer.

• Omission of the most weight bit of the divisor polynomial: some writers propose to omit this, since the greater bit weight is always 1, and since the CRC bit should be defined by a (n + 1) bits of the divisor, it is unnecessary to mention the divisor greater weight in the message and in the CRC.