1. ホーム
  2. cryptography

[解決済み] なぜ、ハッシュを組み合わせるのにXORがデフォルトなのですか?

2022-04-24 19:35:02

質問

2つのハッシュがあるとする H(A)H(B) で、それらを結合したいとします。2つのハッシュを結合する良い方法は、次のようなものだと読んだことがあります。 XOR を、例えば XOR( H(A), H(B) ) .

私が見つけた最も良い説明は、このページで簡単に触れています。 ハッシュ関数ガイドライン :

ほぼランダムに分布する2つの数値をXORすると、やはりほぼランダムに分布する*が、今度はその2つの数値に依存する別の数値が得られる。

...

* つまり、50%の組み合わせで1が出力されます。つまり、2つの入力ビットがそれぞれ0か1になる確率がほぼ半々であれば、出力ビットも同じように半々になる。

ハッシュ関数を組み合わせる際に、なぜORやANDではなくXORをデフォルトの操作とすべきなのか、その直感や数学的背景を説明してもらえますか?

どのように解決するのですか?

一様乱数(1ビット)の入力を仮定すると、AND関数の出力確率分布は75%になります。 0 と25%です。 1 . 逆に、OR は 25% です。 0 と75%です。 1 .

XOR関数は50%です 0 と50 1 したがって、一様な確率分布を組み合わせるのに適しています。

これは真理値表を書き出すとわかる。

 a | b | a AND b
---+---+--------
 0 | 0 |    0
 0 | 1 |    0
 1 | 0 |    0
 1 | 1 |    1

 a | b | a OR b
---+---+--------
 0 | 0 |    0
 0 | 1 |    1
 1 | 0 |    1
 1 | 1 |    1

 a | b | a XOR b
---+---+--------
 0 | 0 |    0
 0 | 1 |    1
 1 | 0 |    1
 1 | 1 |    0

演習:2つの1ビット入力の論理関数はいくつあるか ab は、このように一様な出力分布を持つのでしょうか?なぜXORが質問にある目的に最も適しているのでしょうか?