3

単純なハッシュ アルゴリズムを実装する必要があります。

入力データ:

  • 値 (16 ビット整数)。
  • キー (任意の長さ)。

出力データ:

  • 6 ビットのハッシュ (数字 0 ～ 63)。

要件：

  • 入力値だけがあり、キーがない場合、ハッシュ値を予測することは事実上不可能です。より具体的には、x < M の hash(x) がわかっている場合、キーを知らずに hash(M) を予測するのは難しいはずです。

可能な解決策：

  1. 完全なマッピングをキーとして保持します。したがって、キーの長さは 2^16*6 ビットです。私の場合は長すぎます。
  2. 線形コード。キーは生成行列です。長さは16×6です。しかし、いくつかの既知のハッシュ値を使用して生成行列を見つけるのは簡単です。

他の可能性はありますか？

4

2 に答える 2

5

HMACはあなたが望むもののようです。したがって、SHAベースのHMACを使用して、結果のハッシュのサブストリングを使用する可能性があります。暗号化ハッシュのビットは可能な限り独立していて予測できないため、これは比較的安全です。

ただし、環境によっては、処理に時間がかかりすぎる可能性があるため、HMACを構築するために、より単純なハッシュスキームを選択する必要がある場合があります。

元の回答コメントの議論は以下に基づいています：

とにかく暗号化プロパティを忘れることができるので（5ビットハッシュに対するブルートフォース攻撃を介して衝突を見つけるのは簡単です）、CRCやハミングコードなどを使用して無料でエラー検出を取得することもできます

于 2012-04-10T12:24:56.670 に答える
1

切り捨てられたHMACを使用するという Mensi の提案は良いものですが、非常に制約のあるシステムを使用していて、より高速または単純なものが必要な場合は、任意のブロック暗号を使用して、16 ビット値を暗号化できます (完全なブロックにパディングされます)。 ) それを使用して、結果を 6 ビットに切り捨てます。

疑似乱数関数を計算する HMAC とは異なり、ブロック暗号は疑似乱数順列であり、すべての入力が異なる出力にマッピングされます。ただし、ブロック暗号の出力の 6 ビットを除くすべてを破棄すると、残ったものは疑似乱数関数に非常によく似たものになります。繰り返される出力に対して非常に小さな偏りがありますが、(ブロック暗号のブロック サイズが 6 ビットよりもはるかに大きいと仮定すると) 検出できないほど小さいでしょう。

非常にローエンドなシステムに適したブロック暗号の選択肢は、TEAまたはその後継のXTEAとXXTEAかもしれません。これらの暗号に対する既知の攻撃がいくつかありますが、それらはすべて、アプリケーションで可能であるよりもはるかに広範な暗号へのアクセスを必要とします。

于 2013-01-21T20:34:14.190 に答える