4

一方向ハッシュ アルゴリズム (衝突なし) を使用して、32 ビット整数を 36 ビット整数に変換したいと考えています。

誰もそれを行う方法を説明できますか?

4

2 に答える 2

8

「一方向」とは、xがハッシュ結果h（x）をどのように与えたかを理解するのが「難しい」ことを意味します。「ハード」という用語は明確に定義されていないため、一方向性関数とは何かについても明確に定義されていません。

「衝突なし」とは、xとyのすべてのペアでh（x）がh（y）と異なることを意味します。ここで、xはyとは異なります。これは明確な定義ですが、h（x）が本当に一方向の関数であるかどうかを証明するのは困難です。2つの32ビット数のすべてのペアのハッシュ結果を比較し、それらが異なるかどうかをテストする必要があります。

これを行う最良の方法は、可能なすべてのh（x）を計算し、それらをxと一緒に配列に格納することです。次に、配列をh（x）で並べ替えてから、このリストを調べて、2つの隣接する配列が同じh（x）を持っているかどうかをテストします。同一の隣接関数が見つからない場合、ハッシュ関数に衝突はありません。

しかし、これが本当にできるのであれば、関数を一方向性関数にすることはできません。衝突のないことを証明するために生成したリストは、各hのxを見つけることができる非常に高速なルックアップテーブルだからです。 （x）log（n）の検索時間。これは、xからのh（x）の計算よりも高速である可能性があります。

では、これに実際にかかる時間を把握しましょう

32ビット整数は0から4294967295までの数値です。xからh（x）を計算するのに0.1ミリ秒かかるとしましょう。ハッシュアルゴリズムにもよりますが、これは安価なノートブックでも現実的です。したがって、1秒で10,000個のハッシュ番号を取得し、1日で864,000,000個の番号を取得します。考えられるすべての数値を計算してディスクに保存するには、わずか5日かかります。

各エントリには、32ビット番号用に4バイト、36ビットハッシュ用に5バイトがあります。9バイトになります。したがって、完全なテーブルには38,654,705,664バイトが含まれます。これは38GBです。これは、すべての低予算のノートブックに保存できます。このテーブルの並べ替えには数分かかりますが、計算に必要な5日にはカウントされません。

したがって、このテーブルを中古の200ドルで作成する-ノートブックはまったく問題ありません。一度取得すると、本当に衝突がないかどうかを証明するのは非常に簡単ですが、このテーブルを作成することで、一方向性関数ではないことも証明しました。

では、最善の解決策は何ですか？

  1. 4,294,967,296個のランダムな36ビット番号のリストを生成し、すべてのエントリに、エントリの行番号（0から始まる）である32ビット番号を追加します。
  2. リストを並べ替えます。
  3. did-change-a-number-flagをリセットします
  4. リストをウォークスルーします。実際のエントリを前のエントリと比較します。それらが異なる場合は、手順7に進みます。
  5. 36ビット番号を新しいランダムな36ビット番号に置き換えます
  6. did-change-a-number-flagを設定します
  7. リストの最後に到達した場合：フラグは設定されていますか？その場合は、手順2に進みます。
  8. リストを32ビット番号（前の行番号）で並べ替えます

ステップ1の後、リストには衝突の6.25％（約2億6,840万回の衝突）が含まれます。各反復で、衝突の数を16番目の部分に減らします。すべての衝突を排除するには、約8回の反復が必要です。

この38GBのテーブルは、超高速で完全に衝突のないハッシュ関数になりました。また、32〜36ビットのハッシュ関数と同じように一方向です。意味：与えられたh（x）に対してxを見つけるのが難しい他の衝突のないハッシュ関数はあり得ません。

于 2012-07-24T07:48:30.153 に答える
3

38 GB が小さく聞こえない場合は、36 ビット ブロックでLuby-Rackoff 構造を使用できます。

まず、32 ビット入力を 36 ビットにパディングします。

次に、一連の独立したランダム キーを生成しますKi。必要なだけ大きくします。たとえば、80 っぽいビットです。これらKiは「ハッシュ」するたびに使用するため、安全な場所に保管してください。

ラウンド関数では、 18 ビットに切り捨てられたものをF(Ki,x)使用します。SHA1(Ki . x)

これの 4 つのラウンドはうまくいくはずです。Ki. _

(ええ、「独自の暗号を発明してはいけません」。しかし、32 ビットの入力しかないので、誰が気にしますか?)

于 2012-07-27T03:01:03.047 に答える