今週の情報セキュリティの準備をしていて,使い捨てパッドの暗号化・復号を表した下式をぼんやり眺めながら,思いました.
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のもとで矛盾が示せる,と読むことができます.