15

一方向ハッシュを実行したい 128 ビット ID がありますが、入力メッセージに対して同じダイジェストを取得したくありません。sha-1または代替が、出力ダイジェストサイズ未満の一連のメッセージに対して衝突を生成しないことが保証されているかどうかは誰にもわかりませんか? これは少なくとも理論的には可能です...

また、RSA を使用し、秘密鍵を破棄して一方向の暗号化を行うことも検討しましたが、結果を 32 文字の DB フィールドに格納する必要があり、利用可能な暗号化スキームでは十分に小さいものは生成されません。

元の値の決定論的で可逆的で衝突のない変換を生成する別の方法の提案は大歓迎です。

4

9 に答える 9

7

暗号化ハッシュは、特定の入力に対して非常に適切な乱数の近似値を提供します。では、同じ 160 ビットを取得するまでに、部屋でいくつのランダム ハッシュが必要になるでしょうか? 平方根についてです (免責事項: 私は統計学者ではありません)。そのため、約 80 ビットで衝突が発生することが予想されます。

実用性ということは、宇宙線がいつ衝突よりも大きな問題になるかを知っておくべきだということだと思います.

于 2010-07-01T13:47:13.513 に答える
6

128 ビットから 128 ビットへの秘密順列を計算する場合、単純な解決策の 1 つは、AES のような 128 ビットのブロック暗号を固定の秘密鍵で使用することです。もちろん、鍵を永遠に秘密にしておくことができなければなりません。

于 2010-07-01T23:36:10.827 に答える
4

ID は一意で、128 ビットです。

あなたのコメントは、IDをそのまま使用できないことを説明しています。

おそらく一意であるだけでなく、一意である必要があります。したがって、ハッシュは使用できません。

両方の世界を持つことはできません。元に戻せない 1:1 マッピングを持つことはできません。それは不可能です。

暗号化 - 全単射操作であるため、衝突は発生しません。秘密鍵を使用した ID では、ID を元に戻して元の値を特定することが非常に困難になります。

AES は 128 ビットの優れたブロック長を持ち、128 ビットの入力から 128 ビットの出力を生成し、古いアルゴリズム (!) よりも高速で、ほとんどのプラットフォームと言語で広く利用できます。目的に合わせて AES を使用することをお勧めします。

于 2010-07-01T13:50:44.873 に答える
2

どのハッシュ関数が衝突を回避するかはわかりませんが、ここで答えが見つからない場合は、ウィキペディアの完全なハッシュ関数から始めることをお勧めします。そのページから：

セットSの完全なハッシュ関数は、衝突なしでSの個別の要素を個別の整数にマップするハッシュ関数です。

そのページには、役立つと思われる詳細情報へのリンクがいくつかあります。

そうは言っても、なぜ完璧な機能が必要なのか教えていただけますか？そのプロパティを必要とせずにあなたがやりたいことを達成する他の方法があるかもしれません、そしてここの誰かが提案をすることができるかもしれません。

于 2010-07-01T13:57:35.000 に答える
2

sha-1または代替が衝突を起こさないことが保証されているかどうかは誰にも分かりますか?

ハッシュ関数は衝突を起こさないように設計されていますが、何も「保証」されていません。逆に、可能なハッシュの数は限られていますが、メッセージ スペースは実質的に不定であるため、衝突が発生することが保証されています。

ただし、SHA-1 は耐衝突性であることが証明されており、期待できる最高のものです。

于 2010-07-01T13:49:10.150 に答える
2

十分に大きなビットサイズの場合、離散累乗は 1:1 関数だと思いますが、反転は計算上実行不可能です。ただし、「大」がどの程度必要かはわかりません。使用できないほど遅い (ただし、概念的には理解できる) 実装のコード:

unsigned long spin_once(unsigned long dat)
{
  もし (日付 & 1)
    戻ります (dat >> 1);
  return (dat >> 1) ^ SomeMagicNumber;
}

unsigned long hash (unsigned long dat)
{
  unsigned long i,ret;

  もし (dat == 0xFFFFFFFF)
    0 を返します。
  ret = 1;
  for (i=0; i < dat; i++)
    ret = spin_once(ret);
}

このプログラムは、dat の多くの値のハッシュを計算するために何十億ものステップを必要としますが、よりトリッキーなコードを使用すると、妥当な時間でジョブを実行できます。もちろん、32 ビット ハッシュは暗号学的に価値がありませんが、このアプローチは任意のサイズに容易に拡張できます。

于 2010-07-01T15:28:17.570 に答える
1

ハッシュによって重複が生成される可能性は「ほとんどありません」が、保証はありません。一方、対称暗号化スキームは、128 ビットの入力に対して 128 ビットの出力を生成し、重複がないことを保証します。

一方、ハッシュが一意であることに依存している場合、私の直感では、何か間違ったことをしているということです。たとえば、パスワードを難読化するためにハッシュを使用している場合は、ハッシュされたパスワードを事実上のパスワードにしないように注意する必要があります。

于 2010-07-02T00:38:31.303 に答える
0

この記事http://www.debian-administration.org/users/dkg/weblog/48によると、

米国政府の連邦機関は、2010 年末までに SHA-1 への依存をすべて停止するように指示されました。

しかし、私の知る限り、まだ衝突は見つかっていません。つまり、一生懸命頑張った人でも衝突は見つかっていません。したがって、衝突は起こらないと仮定するのが妥当と思われます (高度なセキュリティ データを扱っていない場合)。

于 2010-07-01T14:18:28.910 に答える
0

一方向ハッシュのポイントは、(一般的に) ハッシュ値から元のデータを復元できないことではないでしょうか? では、ハッシュ関数を設計する人が、小さな入力の衝突を防ぐためにわざわざ尽力するのはなぜでしょうか?

代わりに、データを隠したいように見えますが、これは目的によっては問題ありません。公開鍵暗号化を使用することが実用的でない場合は、独自の関数を作成することもできます。

于 2010-07-01T14:15:17.390 に答える