今週の情報セキュリティの準備をしていて，使い捨てパッドの暗号化・復号を表した下式をぼんやり眺めながら，思いました．
k XOR (k XOR m) = (k XOR k) XOR m = 0 XOR m = m
本論に進む前に，いくつか注意書きをしないといけません．上の式でmは平文，kは鍵，k XOR mは暗号文に対応します．全体としては「任意の平文mを任意の鍵kで暗号化し，暗号化と同じ鍵kで復号すると，必ず，元の平文になる」を表した式です．プリミティブな演算として見たとき，平文・鍵・暗号文はいずれも1ビットですが，これをビット列に拡張させ，ビット単位で演算を行ったと考えることもできます．XORは排他的論理和の演算子です．k XOR k = 0は，kが1ビットのとき，k=0でもk=1でも成立します．任意のビット列に拡張しても，成立しますが，その際の0は，kと同じビット長で，どのビットもゼロの値を意味します．
それで，着目したのは，k XOR (k XOR m) = (k XOR k) XOR mのところです．これは排他的論理和の結合性をもとにしています*1．
排他的論理和では結合法則が成り立つのは，真理値表を書けば当たり前，と思いながら，これまでの授業スライドを見ても，そのことは直ちには分かりません．
それと，ANDやORやXORなら結合性は大丈夫だけれど，他の基本的な論理演算で，この性質が保証されないものがあるか…と考えてみると，NANDやNORは，まずそうだなと気づきました．
あとはRubyでコーディングです．演算子をopと書き，AND，OR，XOR，NAND，NORに変えながら，x,y,z∈{0,1}に対して(x op y) op z = x op (y op z)であるかを判定します．どの組み合わせでもこの等式が成り立てば，結合的*2であり，1つでも成立しなければ，結合的でないと，出力すればいいのです．ソースはGistに置いておきます．
コーティングにおいて，各論理演算は2項演算ではなく，2以上で任意個の値に対する一括演算を行うようにしています*3．3つの値の演算結果x op y op zも，求めてみました．
結果は以下の通りです．
$ ruby assocchecker.rb [Truth table for AND] x|y|z|A|B|C|D|E 0|0|0|0|0|0|0|0 0|0|1|0|0|0|0|0 0|1|0|0|0|0|0|0 0|1|1|0|1|0|0|0 1|0|0|0|0|0|0|0 1|0|1|0|0|0|0|0 1|1|0|1|0|0|0|0 1|1|1|1|1|1|1|1 This operation is associative. [Truth table for OR] x|y|z|A|B|C|D|E 0|0|0|0|0|0|0|0 0|0|1|0|1|1|1|1 0|1|0|1|1|1|1|1 0|1|1|1|1|1|1|1 1|0|0|1|0|1|1|1 1|0|1|1|1|1|1|1 1|1|0|1|1|1|1|1 1|1|1|1|1|1|1|1 This operation is associative. [Truth table for XOR] x|y|z|A|B|C|D|E 0|0|0|0|0|0|0|0 0|0|1|0|1|1|1|1 0|1|0|1|1|1|1|1 0|1|1|1|0|0|0|0 1|0|0|1|0|1|1|1 1|0|1|1|1|0|0|0 1|1|0|0|1|0|0|0 1|1|1|0|0|1|1|1 This operation is associative. [Truth table for NAND] x|y|z|A|B|C|D|E 0|0|0|1|1|1|1|1 0|0|1|1|1|0|1|1 0|1|0|1|1|1|1|1 0|1|1|1|0|0|1|1 1|0|0|1|1|1|0|1 1|0|1|1|1|0|0|1 1|1|0|0|1|1|0|1 1|1|1|0|0|1|1|0 This operation is not associative. [Truth table for NOR] x|y|z|A|B|C|D|E 0|0|0|1|1|0|0|1 0|0|1|1|0|0|1|0 0|1|0|0|0|1|1|0 0|1|1|0|0|0|1|0 1|0|0|0|1|1|0|0 1|0|1|0|0|0|0|0 1|1|0|0|0|1|0|0 1|1|1|0|0|0|0|0 This operation is not associative.
AからEまでは，次のようになっています．
- A := x op y
- B := y op z
- C := A op z = (x op y) op z
- D := x op B = x op (y op z)
- E := x op y op z
結合性の判定は，Cの列とDの列の比較となります．どこか1つの行でも異なっていれば，結合的ではないと言えます．実際NANDとNORでは，そのような例が出現しています．
真理値表を作るのと別の方法で，それらが結合法則を満たさないことが証明できないか…検索すると，見つかりました．
NANDのほうのProof 1で，Line 2の「p∧¬r」をAssumption，すなわち仮定としているのは，上の出力のNANDの表で，xが1，zが0の行に対応します．yが0であっても1であっても，(x NAND y) NAND zは1，x NAND (y NAND z)は0と評価され，値が異なります．Proof 1に立ち返ると，結合法則が成り立つと仮定(Line 1)したとき，p∧¬rのもとで矛盾が示せる，と読むことができます．
