10

可変長の文字列から8バイトのダイジェストを抽出する必要があるため、c /c++で実装するようなアルゴリズムを探しています。これはマイクロコントローラーのデジタル署名手順の一部になるため、次のようにする必要があります。

  • ファームウェアをできるだけ少なくする必要があるため、数行のコードで記述できます。
  • リソース消費量が少なく、特にRAM（100バイト未満が望ましい）。
  • 文字列の任意のポイントで1つの文字を変更すると、ダイジェスト全体が変更されるほど十分に強力です。

crc64などの既存のアルゴリズムを調べましたが、プラットフォームには重すぎるようです。

4

4 に答える 4

10

64ビットでセキュアハッシュを実行する機会はありません。160ビットのSHA-1でさえ、理論的には壊れていると見なされます。安全なデジタル署名を本当に気にする場合は、SHA2-256を使用する必要があります。セキュリティを気にせず、非敵対的な衝突を回避するハッシュ関数が必要な場合は、次を使用するだけで問題ありません。

constexpr uint64 P1 = 7;
constexpr uint64 P2 = 31;

uint64 hash = P1;
for (const char* p = s; *p != 0; p++) {
    hash = hash * P2 + *p;
}
于 2012-11-10T19:12:45.030 に答える
4

AndrewTomazos- Fathomlingが言ったように、64ビットで安全なハッシュを行うことは不可能なので、それがあなたの意図であるなら、私のアドバイスはやめて、本を手に取り、暗号的に安全なハッシュについて読んでください。

これを安全なハッシュとして使用する予定がなく、衝突や攻撃を気にしない場合は、彼の答えは問題なく機能し、必要に応じて素数P1とP2を微調整できます。タグ付きハッシュを実行し、物事をさらに混乱させる別の方法を紹介します。

// Disclaimer: I make no claims about the quality of this particular hash - it's 
// certainly not a cryptographically secure hash, nor should it *ever* be 
// construed as such. 

unsigned long long quickhash64(const char *str, unsigned long long mix = 0)
{ // set 'mix' to some value other than zero if you want a tagged hash          
    const unsigned long long mulp = 2654435789;

    mix ^= 104395301;

    while(*str)
        mix += (*str++ * mulp) ^ (mix >> 23);

    return mix ^ (mix << 37);
}
于 2012-11-10T21:40:24.010 に答える
3

これは、古いソースファイルで見つけた32ビットバージョンの修正バージョンです。

static unsigned long long llhash(const char *str)
{
    unsigned long long hash = 5381;
    int c;

    while (c = *str++)
        hash = ((hash << 5) + hash) + c;

    return hash;
}

ただし、ハッシュは常に衝突を引き起こします。もちろん、一部のアルゴリズムは他のアルゴリズムよりも優れています。

編集： 32ビットバージョンのソースを見つけました：http ：//www.cse.yorku.ca/~oz/hash.html

于 2012-11-10T19:17:49.917 に答える
2

私はまったく同じ要件を持っていて、SIPハッシュ（ここでbloombergによって実装された）を却下した後、 FNV-1Aに落ち着きました。

私はここでFNVの実装を見つけました：

https://github.com/foonathan/string_id/blob/master/hash.hpp

これは：

constexpr uint64_t fnv_basis = 14695981039346656037ull;
constexpr uint64_t fnv_prime = 1099511628211ull;

// FNV-1a 64 bit hash of null terminated buffer
uint64_t fnv1a_hash(const char* str, uint64_t hash = fnv_basis)
{
    return *str ? fnv1a_hash(str + 1, (hash ^ *str) * fnv_prime) : hash;
}

彼は末尾再帰を使用してループしているようです。そして停止条件はnullバイトです。（私が推測するチェーンの各要素である
ブースト使用。）hash_rangehash_combining

ライセンスはzlibで、著作権はJonathanMüllerです。私は、ワンライナーが他の人による研究を実施する場合、合法的に認可されることができるとは確信していませんが（Fowler-Noll-Vo）。

于 2018-04-19T09:13:53.077 に答える