1

私のクライアントは Python プログラマーで、ライセンスの生成とチェックを含む C++ バックエンドを作成しました。安全性を高めるために、Python フロントエンドはライセンスの有効性チェックも実行します。

ただし、ライセンスの生成とチェックのアルゴリズムは、整数が固定バイト サイズであり、値をビットシフトしても整数のバイト カウントが拡張されないという事実に依存するハッシュ方法に基づいています。

これは単純化されたサンプル コードです。

unsigned int HashString(const char* str) {
    unsigned int hash = 3151;
    while (*str != 0) {
        hash = (hash << 3) + (*str << 2) * 3;
        str++;
    }
    return hash;
}

これをどのように Python に翻訳できますか? 直接翻訳すると、明らかに異なる結果が得られます。

def hash_string(str):
    hash = 3151
    for c in str:
        hash = (hash << 3) + (ord(c) << 2) * 3
    return hash

例えば：

hash_string("foo bar spam")  #  228667414299004
HashString("foo bar spam")   // 3355459964

編集：オンラインショップでも有効なライセンスを生成できるはずなので、PHPにも同じことが必要です。

4

2 に答える 2

4

ハッシュ値を次のようにマスクします&。

def hash_string(str, _width=2**32-1):
    hash = 3151
    for c in str:
        hash = ((hash << 3) + (ord(c) << 2) * 3)
    return hash & _width

これにより、ハッシュが手動でサイズに切り戻されます。結果を一度だけ制限する必要があります。これらの上位ビットが最終結果に違いをもたらすわけではありません。

デモ：

>>> hash_string("foo bar spam")
3355459964
于 2013-09-18T21:15:14.143 に答える
3

ここでの問題は、C は をunsigned int超えると自動的にロールオーバーするUINT_MAXのに対し、Pythonintは大きくなり続けることです。

最も簡単な修正は、最後に修正することです。

return hash % (1 << 32)

int非常に大きな文字列の場合、操作が遅くなる巨大な値で終わるのを避けるために、各操作の後にマスクする方が少し速いかもしれません。%しかし、より小さな文字列の場合、1 回ではなく 12 回呼び出すコストは、48 ビットの int を処理するコストを簡単に上回るため、おそらく遅くなります。

PHP にも同じ問題があるか、別の問題がある可能性があります。

PHP のデフォルトの整数型は C の long です。64 ビットの Unix プラットフォームでは、これは よりも大きいunsigned intため、Python と同じトリックを使用する必要があります (%または&のいずれか、より意味のある方)。

しかし、32 ビットの Unix プラットフォームまたは Windows では、これは同じサイズですunsigned intが、署名されているため、別のトリックが必要です。4294967293実際には、たとえば、直接表現することはできません(試してみると、-3代わりに得られます)。GMPデフォルトの型の代わりに aまたはBCMathintegerを使用することもできます-3(この場合、基本的には Python と同じです) 4294967293。

intこれは 32 ビットであり、32 または 64 のいずれかであると仮定しているだけであることに注意してください。これはlong、今日のすべての一般的なプラットフォームでたまたま当てはまるからです。しかし、C 標準では、int長さが少なくとも 16 ビットでありlong、少なくとも 32 ビットで、int. 16 ビット (または 18!) の非常に古いプラットフォームint、または 64 ビット以上になる可能性のある将来のプラットフォームを処理する必要がある場合は、コードを適切に調整する必要があります。

于 2013-09-18T21:15:21.610 に答える