短いハッシュを生成するハッシュ関数？

Question

これは、任意の長さの文字列を取り、サブ10文字のハッシュを生成する一方向の暗号化ですか？私は合理的にユニークなIDを生成したいが、ランダムにではなくメッセージの内容に基づいている。

私は、任意の長さの文字列が不可能な場合でも、メッセージを整数値に制限することができます。ただし、ハッシュは2つの連続した整数の場合は似ていてはなりません。

Answer 1

一般的に利用可能なハッシュアルゴリズム（SHA-1など）を使用すると、必要以上の結果が得られます。結果を目的の長さに切り捨てるだけで十分です。

たとえば、Pythonで：

>>> import hashlib 
>>> hash = hashlib.sha1("my message".encode("UTF-8")).hexdigest() 
>>> hash 
'104ab42f1193c336aa2cf08a2c946d5c6fd0fcdb' 
>>> hash[:10] 
'104ab42f11' 

Answer 2

あなたがダイジェストを考え出す内容をハッシュする必要があります。利用可能なハッシュはたくさんありますが、結果セットでは10文字がかなり小さいです。ウェイ・バックでは、33ビットのハッシュ（基本的に4文字+ 1ビット）を生成するCRC-32を使用しました。 65ビットのハッシュを生成するCRC-64もあります。同じハッシュを持つ2つのメッセージが見つかる可能性があるため、128ビットのハッシュ（16バイト/文字）を生成するMD5は暗号化目的で破損したとみなされます。任意の長さのメッセージから16バイトのダイジェストを作成すると、重複してしまうことになります。ダイジェストが短いほど、衝突のリスクが高くなります。

しかし、ハッシュが2つの連続するメッセージ（整数かどうかにかかわらず）で似ていないという懸念は、すべてのハッシュで真でなければなりません。元のメッセージの1ビットの変更でさえ、大幅に異なる結果のダイジェストを生成するはずです。

だから、CRC-64（とベース64 '結果）のような何かを使用してあなたが探している近所にあなたを取得する必要があります。

Answer 3

私に有益だった答えを要約するだけです（base-64エンコーディングの使用に関する@ erasmospunkのコメントに注意してください）。

：私の目標は、それが（受け入れ答えのように再びPythonで）任意の明白なエラーを持っている場合ので、これを修正してください、私は専門家だ...ほとんど ユニークだった短い文字列を持っている

ました

import base64 
import hashlib 
import uuid 

unique_id = uuid.uuid4() 
# unique_id = UUID('8da617a7-0bd6-4cce-ae49-5d31f2a5a35f') 

hash = hashlib.sha1(str(unique_id).encode("UTF-8")) 
# hash.hexdigest() = '882efb0f24a03938e5898aa6b69df2038a2c3f0e' 

result = base64.b64encode(hash.digest()) 
# result = b'iC77DySgOTjliYqmtp3yA4osPw4=' 

resultここでは、hash.hexdigest()を使用した場合の16進数以上の文字を使用しているため、衝突が発生しにくい（つまり、16進ダイジェストよりも安全です）。

注：UUID4（ランダム）を使用します。他のタイプについては、http://en.wikipedia.org/wiki/Universally_unique_identifierを参照してください。あなたが詳細についてなどPHPの実装を持っているhashidsライブラリは、JavaScript、Pythonのを、使用することができます

Answer 4

は、私は最近、単純な文字列リダクション機能の線に沿って何かを必要とthis link

Answer 5

をご確認ください。それはおそらく望まれるかもしれないが、それは暗号学的ハッシュ関数として使用するためのものではありませんより多くの衝突を持って

size_t ReduceString(char *Dest, size_t DestSize, const char *Src, size_t SrcSize, bool Normalize) 
{ 
    size_t x, x2 = 0, z = 0; 

    memset(Dest, 0, DestSize); 

    for (x = 0; x < SrcSize; x++) 
    { 
     Dest[x2] = (char)(((unsigned int)(unsigned char)Dest[x2]) * 37 + ((unsigned int)(unsigned char)Src[x])); 
     x2++; 

     if (x2 == DestSize - 1) 
     { 
      x2 = 0; 
      z++; 
     } 
    } 

    // Normalize the alphabet if it looped. 
    if (z && Normalize) 
    { 
     unsigned char TempChr; 
     y = (z > 1 ? DestSize - 1 : x2); 
     for (x = 1; x < y; x++) 
     { 
      TempChr = ((unsigned char)Dest[x]) & 0x3F; 

      if (TempChr < 10) TempChr += '0'; 
      else if (TempChr < 36) TempChr = TempChr - 10 + 'A'; 
      else if (TempChr < 62) TempChr = TempChr - 36 + 'a'; 
      else if (TempChr == 62) TempChr = '_'; 
      else TempChr = '-'; 

      Dest[x] = (char)TempChr; 
     } 
    } 

    return (SrcSize < DestSize ? SrcSize : DestSize); 
} 

：基本的には、コードは次の（先にC/C++コード）のようなものが見えました。衝突が多すぎると、さまざまな乗数を試すことができます（つまり、37を別の素数に変更する）。このスニペットの興味深い特徴の1つは、SrcがDestよりも短い場合、Destは入力文字列がそのまま存在することです（0 * 37 + value = value）。プロセスの最後に「読み取り可能な」ものが必要な場合、ノーマライズは変換されたバイトを調整して、衝突を増加させます。

出典：あなたは意図的な変更に強いのアルゴリズムを必要としない場合

https://github.com/cubiclesoft/cross-platform-cpp/blob/master/sync/sync_util.cpp

Answer 6

、私はかなり短い（〜8文字）の結果を生成adler32と呼ばれるアルゴリズムを発見しました。それを試してみるためにここにドロップダウンからそれを選択します。

http://www.sha1-online.com/

Answer 7

あなたはMD5（128ビット）またはSHA1（160）のような短いものを、生産する既存のハッシュアルゴリズムを使用することができます。その後、ダイジェストのセクションを他のセクションと排他的論理和（XOR）することで、さらに短くすることができます。これにより、衝突の可能性は増しますが、単純にダイジェストを切り捨てるほど悪くはありません。

また、よりユニークなものにするために、元のデータの長さを結果の一部として含めることもできます。たとえば、MD5ダイジェストの前半を後半にXORすると、64ビットになります。データの長さに32ビットを追加します（長さが常により少ないビットに収まることがわかっている場合は、それを低くします）。その結果、96ビット（12バイト）の結果となり、24文字の16進文字列に変換されます。代わりに、ベース64エンコーディングを使用してさらに短くすることもできます。

Answer 8

あなたが"sub-10-character hash" が必要な場合は、8文字のハッシュ（32ビット）、CRC-32またはアドラー-32を生成フレッチャー-32アルゴリズムを使用することができます。

CRC-32は、Adler32よりも20％〜100％遅いです。

Fletcher-32はAdler-32よりも少し信頼性が高いです。これは、Adlerチェックサムより低い計算コスト：Fletcher vs Adler comparisonを持っています。いくつかのフレッチャー実装と

サンプルプログラムは、以下に与えられる：

#include <stdio.h> 
    #include <string.h> 
    #include <stdint.h> // for uint32_t 

    uint32_t fletcher32_1(const uint16_t *data, size_t len) 
    { 
      uint32_t c0, c1; 
      unsigned int i; 

      for (c0 = c1 = 0; len >= 360; len -= 360) { 
        for (i = 0; i < 360; ++i) { 
          c0 = c0 + *data++; 
          c1 = c1 + c0; 
        } 
        c0 = c0 % 65535; 
        c1 = c1 % 65535; 
      } 
      for (i = 0; i < len; ++i) { 
        c0 = c0 + *data++; 
        c1 = c1 + c0; 
      } 
      c0 = c0 % 65535; 
      c1 = c1 % 65535; 
      return (c1 << 16 | c0); 
    } 

    uint32_t fletcher32_2(const uint16_t *data, size_t l) 
    { 
     uint32_t sum1 = 0xffff, sum2 = 0xffff; 

     while (l) { 
      unsigned tlen = l > 359 ? 359 : l; 
      l -= tlen; 
      do { 
       sum2 += sum1 += *data++; 
      } while (--tlen); 
      sum1 = (sum1 & 0xffff) + (sum1 >> 16); 
      sum2 = (sum2 & 0xffff) + (sum2 >> 16); 
     } 
     /* Second reduction step to reduce sums to 16 bits */ 
     sum1 = (sum1 & 0xffff) + (sum1 >> 16); 
     sum2 = (sum2 & 0xffff) + (sum2 >> 16); 
     return (sum2 << 16) | sum1; 
    } 

    int main() 
    { 
     char *str1 = "abcde"; 
     char *str2 = "abcdef"; 

     size_t len1 = (strlen(str1)+1)/2; // '\0' will be used for padding 
     size_t len2 = (strlen(str2)+1)/2; // 

     uint32_t f1 = fletcher32_1(str1, len1); 
     uint32_t f2 = fletcher32_2(str1, len1); 

     printf("%u %X \n", f1,f1); 
     printf("%u %X \n\n", f2,f2); 

     f1 = fletcher32_1(str2, len2); 
     f2 = fletcher32_2(str2, len2); 

     printf("%u %X \n",f1,f1); 
     printf("%u %X \n",f2,f2); 

     return 0; 
    } 

出力：

4031760169 F04FC729                                                        
4031760169 F04FC729                                                        

1448095018 56502D2A                                                        
1448095018 56502D2A                                                        

はTest vectorsと一致する：

"abcde" -> 4031760169 (0xF04FC729) 
"abcdef" -> 1448095018 (0x56502D2A) 

アドラー-32用の弱点を有していますこれらのメッセージのチェックサムはcovが悪いため、数百バイトの短いメッセージ利用可能な32のビットの誤り。これを確認してください：

The Adler32 algorithm is not complex enough to compete with comparable checksums