2

私は学んでおり、CRC の背後にある考えを理解しようとしています。CRC128 および CRC256 コードがどこにも見つかりません。誰かが C++ または C# コードを持っている場合は、私と共有してください。Web サイトへのオンライン リンクも提供します。私は初心者で、自分でコーディングすることはまったくできません。また、理論や数学をコーディングに変換することもできません。だから私はあなたに助けを求めます。適切で簡単なコードを提供してくれると、とてもうれしいです。誰かが私にこれらのコードを提供する場合は、CRC テーブル ジェネレータ関数も提供してください。ありがとうございました。

4

4 に答える 4

4

32 ビットおよび 64 ビット CRC の場合、偶発的な衝突率がそれぞれ 2^32 分の 1 または 2^64 分の 1 よりも高いことを除いて、私はあなたに同意します。

アイテムを追跡するために、CRC 値によって物事を追跡するアプリを作成しました。潜在的に何百万ものアイテムを追跡する必要があり、CRC32 から始めましたが、現実世界の慣例では衝突率が 2^16 あたり約 1 であり、不愉快な驚きでした。次に、実際の衝突率が 2^23 分の 1 である CRC64 を使用するように再コーディングしました。最初の 32 ビットの不愉快な驚きの後にこれをテストし、64 ビットの小さなエラー率を受け入れました。

予想される衝突率の背後にある統計を実際に説明することはできませんが、ビット幅よりもはるかに早く衝突が発生することは理にかなっています。ハッシュテーブルと同じように...いくつかのハッシュバケットは空で、他のハッシュバケットには複数のエントリがあります....

256 ビット CRC の場合でも、最初の 2 つの CRC が同じである可能性があります...ほとんど信じられないことですが、可能です。

于 2014-01-06T21:25:02.227 に答える
3

CRC-128とCRC-256が定義されていますが、実際にそれらを使用している人は誰も知りません。

ほとんどの場合、CRCが必要だと考える開発者は、実際には暗号化ハッシュ関数を使用する必要があります。これは、多くのアプリケーションでCRCに成功しています。実際、CRC-128またはCRC-256が壊れたMD5よりも優れた選択肢であり、SHA-2ファミリよりもはるかに優れているというのはまれなケースです。

于 2010-08-23T18:41:02.967 に答える
3

CRC-128およびCRC-256は、次の3つの点が当てはまる場合にのみ意味があります。

  1. 暗号化ハッシュが大幅に遅くなる点までCPUに制約があります
  2. 偶発的な衝突は統計的に決して起こらないはずです、2^64の1はまだ高すぎます
  3. OTOHの意図的な衝突は問題ではありません

2と3が一緒に真になる可能性がある典型的なケースは、偶発的な衝突によってデータの送信者にのみ影響し、プラットフォームには影響しないデータ損失が発生する場合です。

于 2012-02-07T11:24:41.997 に答える
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 に答える