XOR演算の仕組み

ホームC#入門講座第4章:簡易暗号化アルゴリズム > XOR演算の仕組み

XOR演算の仕組み

2進法の仕組み

XOR演算の仕組みの前に、2進法を理解する必要があります。ところで問題です。

(例題)
以下の2進法の数を10進法で表せ。ただし、符号は常に正とし、符号ビットは存在しないものとする。
1) 1010
2) 1111

高校数学で習ったと思いますが、「2進法の数 abcd」を10進法に直す場合、「2のべき乗」を使うのでした。それを思い出しながら、実際に計算すると以下のようになります。

(解) 最初の恒等式の左辺のみ2進法で記述する
1)
1010 = 1 * 23 + 0 * 22 + 1 * 21 + 0 * 20
     = 8 + 0 + 2 + 0
     = 10

2)
1111 = 1 * 23 + 1 * 22 + 1 * 21 + 1 * 20
     = 8 + 4 + 2 + 1
     = 15

では、ついでに16進法も計算しましょう。

(問) 16進法の数 "E0" を10進法で表せ。

(解)
0 = 0, 1 = 1, ・・・, 9 = 9, 10 = A, 11 = B, 12 = C, 13 = D, 14 = E, 15 = F より
E0 = 15 * 161 + 0 * 160
   = 224

ステップアップC#の背景色は「#E0E0E0」であり、これは(赤,緑,青) = (224,224,224)の割合で混ぜた色(光)を意味します。16進法で表せる2桁の数で最も大きいのは「FF」(255)であり、こ れが3種類あるので、背景色は約1677万色作れます。

排他的論理和

2進法を学んだとろこで、XOR、つまり「排他的論理和」について学びましょう。その前に、すこしコンピュータから離れて話をします。

「排他的」とは、恋愛のようなものです。たとえば、「桜子さん(女)」と「若葉ちゃん(男)」と「欧介さん(男)」がいるとします。また、カップル が成立しうる状態を「true」と表現し、カップルが成立しえない状態を「false」と表現することにします。なお、女性同士のカップルは考えないこと とします。

現在、「桜子さん」は「欧介さん」が好きです。このカップルを「ナナコカップル」と名付けると、「ナナコカップル」は「true」です。また、「若 葉ちゃん」も「欧介さん」が好きです。このカップルを「アキコカップル」と名付けると、「アキコカップル」は「true」です。

(ナナコカップル) : 桜子さん × 欧介さん = true
(アキコカップル) : 若葉ちゃん × 欧介さん = true

ここに存在するカップルはふたつとも true です。カップルはいずれも「成立しそう」です。個別に見た場合、カップルが成立しない状態である「false」を見出すことはできません。しかし、実際は 違います。恋愛は「排他的」なのです。この両カップルを「排他的論理和」してみます。排他的論理和を示す演算子は「^」です。

ナナコカップル「true」 ^ アキコカップル「true」 = false

欧介さんは両者の板ばさみになり、排他的論理和の結論はfalseです。つまり、カップルは成立しないという結論に達します。実際に4通りすべて列挙してみれば、恋愛を論理的に解明することができます。

ナナコカップル「true」 ^ アキコカップル「true」 = false
ナナコカップル「true」 ^ アキコカップル「false」 = true
ナナコカップル「false」 ^ アキコカップル「true」 = true
ナナコカップル「false」 ^ アキコカップル「false」 = false

どちらにも好かれない場合はカップルは成立しません。これは当然です。ですが、両方に好かれたとしてもカップルは成立しません。これが排他的論理和 の結論です。よって、「二兎追う者は一兎を得ず」というということわざの信憑性が実証され、不倫・二股の危険性を証明することができました。

これが排他的論理和の全貌です。これを2進法に適用してみます。1は「true」を、0は「false」を表していると考え、15と10を排他的論理和してみます。

1 0 1 0 = 10
1 1 1 1 = 15
------------
0 1 0 1 = 0 * 23 + 1 * 22 + 0 * 21 + 1 * 20
        = 0 + 4 + 0 + 1
        = 5

よって、
    10 ^ 15 = 5
が成立する

各ビットを縦に見てください。そして、2つの数字でカップルが成立するかどうかを判断します。そして計算すると、「10と15の排他的論理和は5」 という結論が出ました。これは、本来「true」と「false」に限られていた排他的論理和の概念を拡張し、整数に適用した結論です。もとが 「true」と「false」なので、排他的論理和の理解には2進法の理解が必要になります。

排他的論理和の性質

排他的論理和は「XOR」と呼ばれます。これからはXORと記述します。

XORにはある面白い特徴があります。それは、このようなものです。

A ^ B = C
が成立するとき、
A ^ C = B
B ^ C = A
も成立する

上の例で試してみましょう。A = 10, B = 15, C = 5 を代入して、確かめてみます。

(10 ^ 5)
1 0 1 0 = 10
0 1 0 1 = 5
------------
1 1 1 1 = 15

(15 ^ 5)
0 1 0 1 = 5
1 1 1 1 = 15
------------
1 0 1 0 = 10

これは論理的に考えれば当然です。ですが、この性質を使って、以下のような等式も成立させることができます。

平文 ^ パスワード = 暗号 (暗号化・エンコード)
暗号 ^ パスワード = 平文 (復号化・デコード)

実に単純な論理ですが、「ニイタカヤマノボレ」よりはハイテクな暗号システムだと思いませんか? これがXOR演算による暗号化アルゴリズムです。普通は「暗号化」と「復号化」は逆のベクトルで処理しますが、XORは全く同じプログラムで奇数回処理す るか偶数回処理するかで変わるという興味深い性質があるのです。

ポイントになるのはデータを整数で表すことです。もし、データを整数で表すためにさらに別のアルゴリズムを習得する必要があるなら、これはお手軽な サンプルではありません。しかし、コンピュータは幸いにもすべてのデータをビットで表すので、データから整数を得るのは実に簡単です。それを次回にやるこ とにします。

今回はソースコードが出てきませんでしたが、これがいわゆる「アルゴリズム」を学ぶことです。小手先のプログラミングテクニックではなく、目の前の 世界そのものを動かすような、「概念」を学ぶのです。普通の人は一生知らないであろうXORと恋愛との関係や暗号との関係に付いて学び、なんらかの考えを 持ったはずです。これこそが真のプログラミングであると私は思うのです。