XOR（eXclusive OR：排他的論理和）は、2つの入力ビットから1つの出力ビットを生成する論理演算です。
「排他的」という名前の通り、2つの入力が異なる場合のみ1を出力し、同じ場合は0を出力します。
この性質により、暗号化と復号で同じ演算を使用できるため、ワンタイムパッドなどの暗号方式で重要な役割を果たします。
| 入力A | 入力B | 出力 （A ⊕ B） |
説明 |
|---|---|---|---|
| 0 | 0 | 0 | 同じ値なので0 |
| 0 | 1 | 1 | 異なる値なので1 |
| 1 | 0 | 1 | 異なる値なので1 |
| 1 | 1 | 0 | 同じ値なので0 |
A ⊕ B ⊕ B = A
0 ⊕ 0 = 0（同じ値なので結果は0）
XORはビット演算であるため、ハードウェア実装との相性が非常に良い特徴があります。
XORゲートは基本的な論理ゲートの組み合わせで実現でき、回路が単純で高速です。
ハードウェアレベルでの並列処理が可能で、大量のデータを高速に処理できます。
シンプルな回路のため、消費電力が少なく効率的です。
XORゲートは2つの入力を受け取り、それらが異なる場合のみ1を出力します。
このシンプルな構造により、CPUやFPGA、専用チップなどで効率的に実装できます。
A ⊕ B = B ⊕ A
入力の順序を変えても結果は同じ
(A ⊕ B) ⊕ C = A ⊕ (B ⊕ C)
複数の値をXORする際、計算順序は関係ない
A ⊕ 0 = A
任意の値と0をXORしても元の値のまま
A ⊕ A = 0
同じ値同士をXORすると0になる
| 演算 | 記号 | 0,0 | 0,1 | 1,0 | 1,1 | 特徴 |
|---|---|---|---|---|---|---|
| AND | ∧ | 0 | 0 | 0 | 1 | 両方が1の時のみ1 |
| OR | ∨ | 0 | 1 | 1 | 1 | どちらかが1なら1 |
| XOR | ⊕ | 0 | 1 | 1 | 0 | 異なる時のみ1（排他的） |
| NAND | ↑ | 1 | 1 | 1 | 0 | ANDの否定 |
XORの独特さ: XORは唯一「可逆性」を持つ基本論理演算です。この性質が暗号での応用を可能にしています。
ワンタイムパッド（OTP）の特性と脆弱性を実験を通して学習します。
各実験では、OTPの数学的性質や、なぜ「一度だけ使用」が重要なのかを体験的に理解できます。
XORゲートは基本的な論理ゲート（NOT、AND、OR）の組み合わせで作ることができます。
XOR演算の等価式:
A ⊕ B = (A ∧ ¬B) ∨ (¬A ∧ B)
これは「Aが1でBが0、またはAが0でBが1の場合に1を出力」を意味します。
| A | B | ¬A | ¬B | A∧¬B | ¬A∧B | 結果 (A⊕B) |
|---|---|---|---|---|---|---|
| 0 | 0 | 1 | 1 | 0 | 0 | 0 |
0 ⊕ 0 = 0 (NOT(0)=1, NOT(0)=1, 0∧1=0, 1∧0=0, 0∨0=0)
同じ鍵で2つの平文を暗号化すると、暗号文から平文の情報が漏洩することを実証します。
暗号化:
C₁ = P₁ ⊕ KC₂ = P₂ ⊕ K
問題: 暗号文同士のXOR
C₁ ⊕ C₂ = (P₁ ⊕ K) ⊕ (P₂ ⊕ K) = P₁ ⊕ P₂
⚠️ 鍵Kが相殺され、平文同士のXORが得られてしまいます！
平文の一部分（1ビットでも）がわかれば、対応する鍵ビットが確定的に求まることを実証します。
XORの性質を利用:
C = P ⊕ K から K = P ⊕ C
平文の断片がわかれば、対応する暗号文ビットから鍵ビットを逆算できます。
ただし、OTPでは各鍵は一度だけ使用されるため、将来のメッセージには影響しません。
XORは基本的な論理演算の組み合わせで構成でき、ハードウェア実装が容易です。
鍵の再利用は致命的な脆弱性を生み出します。OTPでは絶対に鍵を再利用してはいけません。
平文の断片が漏洩すると対応する鍵も漏洩しますが、OTPでは使い捨てなので将来のセキュリティには影響しません。