2

我正在学习，试图了解 CRC 背后的想法。我在任何地方都找不到 CRC128 和 CRC256 代码。如果你们中的任何人有他们的 C++ 或 C# 代码，请与我分享。还提供网站的在线链接。我是一个新手，根本不会自己编码，也不能将理论和数学转换为编码。所以我向你寻求帮助。为我提供正确而简单的代码，您会非常高兴。如果有人向我提供这些代码，请同时提供 CRC 表生成器功能。谢谢你。

4

4 回答 4

4

我同意你的看法，但对于 32 位和 64 位 CRC，意外碰撞率分别高于 2^32 中的 1 或 2^64 中的 1。

我编写了一个应用程序，通过它们的 CRC 值来跟踪事物以跟踪项目。我们需要跟踪潜在的数百万个项目，我们从 CRC32 开始，在现实世界的实践中，它的碰撞率约为 2^16 分之一，这是一个令人不快的惊喜。然后，我们重新编码以使用 CRC64，它在 2^23 中的实际碰撞率约为 1。在我们开始使用 32 位的令人不快的惊喜之后，我们对此进行了测试，并接受了 64 位的小错误率。

我无法真正解释预期碰撞率背后的统计数据，但你会比位的宽度更快地经历碰撞是有道理的。就像一个哈希表......一些哈希桶是空的，而另一些则有多个条目......

即使对于 256 位 CRC，前 2 个 CRC 也可能是相同的……这几乎令人难以置信，但却是可能的。

于 2014-01-06T21:25:02.227 回答
3

CRC-128 和 CRC-256 仅在以下三点为真时才有意义：

  1. 您的 CPU 受到限制，以至于加密哈希会显着减慢您的速度
  2. 统计上绝对不会发生意外碰撞，2^64 中有 1 个仍然太高
  3. OTOH故意碰撞不是问题

2 和 3 一起成立的典型情况是，如果意外碰撞会造成仅影响数据发送者而不影响平台的数据丢失。

于 2012-02-07T11:24:41.997 回答
3

虽然定义了 CRC-128 和 CRC-256，但我不知道有谁真正使用过它们。

大多数时候，认为他们想要 CRC 的开发人员应该真正使用加密哈希函数，它已经在许多应用程序中成功地使用了 CRC。CRC-128 或 CRC-256 甚至比损坏的 MD5 更胜一筹的情况确实很少见，更不用说 SHA-2 系列了。

于 2010-08-23T18:41:02.967 回答
3

这是我最近编写的用于玩 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();
}
}
于 2010-08-23T21:46:26.547 回答