我正在学习,试图了解 CRC 背后的想法。我在任何地方都找不到 CRC128 和 CRC256 代码。如果你们中的任何人有他们的 C++ 或 C# 代码,请与我分享。还提供网站的在线链接。我是一个新手,根本不会自己编码,也不能将理论和数学转换为编码。所以我向你寻求帮助。为我提供正确而简单的代码,您会非常高兴。如果有人向我提供这些代码,请同时提供 CRC 表生成器功能。谢谢你。
4 回答
我同意你的看法,但对于 32 位和 64 位 CRC,意外碰撞率分别高于 2^32 中的 1 或 2^64 中的 1。
我编写了一个应用程序,通过它们的 CRC 值来跟踪事物以跟踪项目。我们需要跟踪潜在的数百万个项目,我们从 CRC32 开始,在现实世界的实践中,它的碰撞率约为 2^16 分之一,这是一个令人不快的惊喜。然后,我们重新编码以使用 CRC64,它在 2^23 中的实际碰撞率约为 1。在我们开始使用 32 位的令人不快的惊喜之后,我们对此进行了测试,并接受了 64 位的小错误率。
我无法真正解释预期碰撞率背后的统计数据,但你会比位的宽度更快地经历碰撞是有道理的。就像一个哈希表......一些哈希桶是空的,而另一些则有多个条目......
即使对于 256 位 CRC,前 2 个 CRC 也可能是相同的……这几乎令人难以置信,但却是可能的。
CRC-128 和 CRC-256 仅在以下三点为真时才有意义:
- 您的 CPU 受到限制,以至于加密哈希会显着减慢您的速度
- 统计上绝对不会发生意外碰撞,2^64 中有 1 个仍然太高
- OTOH故意碰撞不是问题
2 和 3 一起成立的典型情况是,如果意外碰撞会造成仅影响数据发送者而不影响平台的数据丢失。
虽然定义了 CRC-128 和 CRC-256,但我不知道有谁真正使用过它们。
大多数时候,认为他们想要 CRC 的开发人员应该真正使用加密哈希函数,它已经在许多应用程序中成功地使用了 CRC。CRC-128 或 CRC-256 甚至比损坏的 MD5 更胜一筹的情况确实很少见,更不用说 SHA-2 系列了。
这是我最近编写的用于玩 CRC 的 Java 类。请注意,更改位顺序仅适用于按位计算。
/**
* A CRC algorithm for computing check values.
*/
public class Crc
{
public static final Crc CRC_16_CCITT =
new Crc(16, 0x1021, 0xffff, 0xffff, true);
public static final Crc CRC_32 =
new Crc(32, 0x04c11db7, 0xffffffffL, 0xffffffffL, true);
private final int _width;
private final long _polynomial;
private final long _mask;
private final long _highBitMask;
private final long _preset;
private final long _postComplementMask;
private final boolean _msbFirstBitOrder;
private final int _shift;
private final long[] _crcs;
/**
* Constructs a CRC specification.
*
* @param width
* @param polynomial
* @param msbFirstBitOrder
*/
public Crc(
int width,
long polynomial)
{
this(width, polynomial, 0, 0, true);
}
/**
* Constructs a CRC specification.
*
* @param width
* @param polynomial
* @param msbFirstBitOrder
*/
public Crc(
int width,
long polynomial,
long preset,
long postComplementMask,
boolean msbFirstBitOrder)
{
super();
_width = width;
_polynomial = polynomial;
_mask = (1L << width) - 1;
_highBitMask = (1L << (width - 1));
_preset = preset;
_postComplementMask = postComplementMask;
_msbFirstBitOrder = msbFirstBitOrder;
_shift = _width - 8;
_crcs = new long[256];
for (int i = 0; i < 256; i++)
{
_crcs[i] = crcForByte(i);
}
}
/**
* Gets the width.
*
* @return The width.
*/
public int getWidth()
{
return _width;
}
/**
* Gets the polynomial.
*
* @return The polynomial.
*/
public long getPolynomial()
{
return _polynomial;
}
/**
* Gets the mask.
*
* @return The mask.
*/
public long getMask()
{
return _mask;
}
/**
* Gets the preset.
*
* @return The preset.
*/
public long getPreset()
{
return _preset;
}
/**
* Gets the post-complement mask.
*
* @return The post-complement mask.
*/
public long getPostComplementMask()
{
return _postComplementMask;
}
/**
* @return True if this CRC uses MSB first bit order.
*/
public boolean isMsbFirstBitOrder()
{
return _msbFirstBitOrder;
}
public long computeBitwise(byte[] message)
{
long result = _preset;
for (int i = 0; i < message.length; i++)
{
for (int j = 0; j < 8; j++)
{
final int bitIndex = _msbFirstBitOrder ? 7 - j : j;
final boolean messageBit = (message[i] & (1 << bitIndex)) != 0;
final boolean crcBit = (result & _highBitMask) != 0;
result <<= 1;
if (messageBit ^ crcBit)
{
result ^= _polynomial;
}
result &= _mask;
}
}
return result ^ _postComplementMask;
}
public long compute(byte[] message)
{
long result = _preset;
for (int i = 0; i < message.length; i++)
{
final int b = (int) (message[i] ^ (result >>> _shift)) & 0xff;
result = ((result << 8) ^ _crcs[b]) & _mask;
}
return result ^ _postComplementMask;
}
private long crcForByte(int b)
{
long result1 = (b & 0xff) << _shift;
for (int j = 0; j < 8; j++)
{
final boolean crcBit = (result1 & (1L << (_width - 1))) != 0;
result1 <<= 1;
if (crcBit)
{
result1 ^= _polynomial;
}
result1 &= _mask;
}
return result1;
}
public String crcTable()
{
final int digits = (_width + 3) / 4;
final int itemsPerLine = (digits + 4) * 8 < 72 ? 8 : 4;
final String format = "0x%0" + digits + "x, ";
final StringBuilder builder = new StringBuilder();
builder.append("{\n");
for (int i = 0; i < _crcs.length; i += itemsPerLine)
{
builder.append(" ");
for (int j = i; j < i + itemsPerLine; j++)
{
builder.append(String.format(format, _crcs[j]));
}
builder.append("\n");
}
builder.append("}\n");
return builder.toString();
}
}