c++ - 特定の長さの文字列のハッシュ

Question

ハッシュ自体が特定の長さになるように、文字列のハッシュを生成する方法はありますか? 41 バイトのハッシュ (SHA-1) を生成する関数がありますが、最大 33 バイトにする必要があります (特定のハードウェア制限のため)。41 バイトのハッシュを 33 に切り詰めると、おそらく (確実に!) 一意性が失われます。

または、実際には、あなたの助けを借りて C コードを見つけることができれば、MD5 アルゴリズムがうまく適合すると思います。

編集: 迅速で知識豊富な回答に感謝します。私は MD5 ハッシュを使用することにしましたが、それは私の目的にぴったりです。一意性は重要な問題ですが、特定の時点でこれらのハッシュの数が非常に多くなるとは思いません。これらのハッシュはホーム LAN 上のソフトウェアサーバーを表すため、最大で 5 つ、おそらく 10 が実行されます。

score 7 · Accepted Answer

41 バイトのハッシュを 33 に切り詰めると、おそらく (確実に!) 一意性が失われます。

今、自分が独自性を持っていると思う理由は何ですか? はい、41 バイトではなく 33 バイトだけで遊んでいる場合、明らかに衝突の可能性が高くなりますが、ハッシュを使用することが理にかなっている状況では、衝突が発生する可能性は低く、不可能ではないことを十分に認識する必要があります。そもそも。41 バイトを超えるデータをハッシュしている場合、利用可能なハッシュよりも明らかに多くの組み合わせが可能です。

SHA-1 ハッシュを切り詰めた方がよいのか、MD5 などの短いハッシュを使用した方がよいのかはわかりません。ハッシュ全体を保持する場合は、より一般的に自信があると思いますが、MD5 には既知の脆弱性があり、特定のアプリケーションにとって問題になる場合とそうでない場合があります。

score 5 · Accepted Answer

残念ながら、ハッシュが計算される方法は不可能です。ハッシュ長を 33 バイトに制限するには、それをカットする必要があります。より多くの情報を保持できるため、最初と最後の 33 バイトを xor することができます。しかし、33 バイトであっても、衝突の可能性はそれほど大きくありません。

md5: http://www.md5hashing.com/c++/

ところで。md5 は 16 バイト、sha1 は 20 バイト、sha256 は 32 バイトですが、16 進文字列として、サイズはすべて 2 倍になります。バイトを格納できる場合は、sha256 を使用することもできます。

score 4 · Accepted Answer

ハッシュアルゴリズムの設計方法により、substring(sha_hash, 0, 33) との衝突の可能性は、長さが 33 バイトの他のハッシュと比べて高くありません (エントロピーは結果の文字列に均等に分散されます)。

score 3 · Accepted Answer

MD5 や SHA-X の代わりに、 Elf ハッシュ(<- C コードを含む) またはそのような他の単純なハッシュ関数を使用できます。安全ではありませんが、必要な長さに調整できます

/*****Please include following header files*****/
// string
/***********************************************/

/*****Please use following namespaces*****/
// std
/*****************************************/

static unsigned int ELFHash(string str) {
    unsigned int hash = 0;
    unsigned int x = 0;
    unsigned int i = 0;
    unsigned int len = str.length();

    for (i = 0; i < len; i++)
    {
        hash = (hash << 4) + (str[i]);
        if ((x = hash & 0xF0000000) != 0)
        {
            hash ^= (x >> 24);
        }
        hash &= ~x;
    }

    return hash;
}

例

string data = "jdfgsdhfsdfsd 6445dsfsd7fg/*/+bfjsdgf%$^";
unsigned int value = ELFHash(data);

出力

248446350

score 2 · Accepted Answer

ハッシュは、定義上、少量のデータに対してのみ一意です (それでも保証されません)。魔法のように情報を取り除いて後で元に戻すことはできないため、大量の情報を少量の情報に一意にマッピングすることは不可能です。これは圧縮が行われていないことに注意してください。

個人的には、この状況では MD5 (テキストで保存する必要がある場合)、または SHA256 などの 256b (32B) ハッシュ (バイナリで保存できる場合) を使用します。別のハッシュアルゴリズムを 33B に切り捨てても機能し、ハッシュの衝突が発生する可能性が高くなる場合があります。それはアルゴリズムに大きく依存します。

また、それを設計した人々による MD5 のさらに別の C 実装。

score 1 · Accepted Answer

MD5 ハッシュアルゴリズムの結果は 32 桁の数字になると思いますので、そのほうが適しているかもしれません。

編集: MD5 機能にアクセスするには、openssl ライブラリにフックできる必要があります。ただし、ハードウェアの制限について言及したため、これは不可能な場合があります。

score 1 · Accepted Answer

33 バイトの衝突の確率は 1/2^132 です (誕生日のパラドックスによる)

したがって、一意性が失われる心配はありません。

更新: SHA1 の実際のバイト長は確認していません。関連する計算は次のとおりです。32 ニブルの衝突 (33 バイトの 16 進数 - 1 終了文字) は、ハッシュされた文字列の数が約 sqrt(2^(32*4)) = 2^64 になった場合にのみ発生します。

score 1 · Accepted Answer

1

これは C でのMD5の実装です。

于 2008-10-07T06:21:56.620 に答える

score 0 · Accepted Answer

Apache の DigestUtils を使用します。

http://commons.apache.org/codec/api-release/org/apache/commons/codec/digest/DigestUtils.html#md5Hex(java.lang.String)

ハッシュを 32 文字の 16 進文字列に変換します。

c++ - 特定の長さの文字列のハッシュ

9 に答える 9

Related

Reference