排他的論理和の移項も排他的論理和

「使い捨てパッド*1における暗号化の操作とは，ビット単位で，平文と鍵との排他的論理和を求めることです．復号の操作は，これまたビット単位で，暗号文と鍵との排他的論理和を求めることです．『排他的論理和』については論理回路の授業で学習してきたと思いますが，使い捨てパッドの暗号化・復号そして解読に用いられる諸性質を，ここで確認しておきます．
　まず論理演算（ビット演算）ということで，真理値表をつくることができます．2つの変数xとyは，ここでは1ビットの値をとることとし，その排他的論理和xyについて，xとyの値がともに0のとき，00は0です．x＝0でy＝1のとき，01は1です．x＝1でy＝0のとき，10は1です．最後にxとyの値がともに1のとき，11は0です．
　これをもとに，真理値表の下に書いた式が成り立つことが言えます．なお，これらの変数x, y, zについて，1ビットに限らず，式ごとに同じ長さの任意のビット列とし，排他的論理和の演算をビットごとに行うと拡張しても，成立します．
まずは『可換性』あるいは『可換律』『交換法則』と呼ばれる関係式，xy＝yxです．真理値表から，1ビットの演算でこれが成り立つのは，分かりますね．
　次に知っておいてほしい等式は，xx＝0です．これも1ビットの演算については，真理値表を見ます．x＝0のときは，00で0となり，x＝1のときは，11で0となります．
　数学的には，排他的論理和という2項演算において，xの逆元はxそのものだと言えます．それとかつて，Z80というCPUで，CPU内の変数に相当するアキュムレータというのの，値を0にしたいとき，0を代入せよというよりも，アキュムレータそのものとの排他的論理和を求めてそれをアキュムレータの値にせよという演算の方が，日本語で言うと長いのですが，コードサイズも演算時間も小さくなるので好まれた，なんて話もあります．
　3番目に挙げたのは，『結合性』で，『結合律』『結合法則』とも呼ばれます．3つの変数そしてカッコを用いた等式ですが，その意味合いはというと，『xyz』と式を書いてみたとき，先にxyを計算して，その結果zを計算するのも，先にyzを計算して，xその結果を計算するのも，答えは同じになるということです．x, y, zが0と1のいずれをとっても成立するというのは，2の3乗で8通りすべてで，両辺の値が同じになるのを確認すればいいのです．
　2番目と3番目の性質から，4番目に書いたxyy＝xが導けます．その理由は一つ前のスライドに書きましたので，ここには載せていません*2．この式において，xとyを同じ長さのビット列とし，xを平文，yを鍵と見なすと，xyが暗号文に対応しまして，（xy）yは，暗号文に，暗号化に使用したのと同じ鍵を使ってビットごとの排他的論理和を求めるという操作で，元の平文xが得られることを，表すことになります．
　箇条書きの下から2番目の式は，中学1年で学習した等式の性質，すなわち両辺に同じ値を加えても等式が維持される，というのと関連します．単純な足し算のところを，排他的論理和に置き換えても，0と1との間の演算としては，成立するのです．『x＝yならばxz＝yz』は，x, y, zが1ビットであれば結合性で述べたのと同じく2の3乗の8通りの組み合わせについて，この論理式が成り立つことを確認すればいいのです．ここで『PならばQ』の命題において，Pが偽（たとえばx＝0でy＝1）のとき，Qの真偽を考えることなく『PならばQ』は真になることも使用します．
　最後の性質は，排他的論理和の『移項』と呼べるものです．中学1年では，z＝x＋yあるいはx＋y＝zであるとき，x＝z−yと変形できます．左右の両辺で同じもの（ここではy）を引くことから，この移項の概念は説明できるのですが，一方の辺に出現する『＋y』という，項の足し算を消すとなると，もう一方の辺に『−y』とすればいい，と言うこともできます．
　さて，排他的論理和には，マイナスは出現しませんが，その代わりの演算は，排他的論理和そのものです．式で表すと，『z＝xyならば，x＝zy』であり，『z＝xyならば，y＝xz』となります．一つ上の性質と同じく，x, y, zが1ビットであれば2の3乗の8通りの組み合わせについて，それぞれ確認ができ，それは任意のビット長に拡張できます．
　『z＝xyならば，x＝zy』においてxを平文，yを鍵，zを暗号文と見なすと，鍵と暗号文のペアがあるとき，それらについてビット単位で排他的論理和の演算を行えば，元の平文が得られることを意味します．『暗号化と復号の関係』を別の形で表したものと，見ることもできます．
　あとのスライドでまた述べますが，同じ変数の割り当てで『z＝xyならば，y＝xz』という式は，平文と暗号文のペアがあるときには，それらについてビット単位で排他的論理和の演算を行えば，鍵が得られると解釈できます．解読*3も，排他的論理和なのです．なのですが，その操作で得られた鍵が，過去あるいは未来の暗号文の復号に使われることのないよう，鍵は真の乱数として生成し『使い捨て』とします．このことが，『使い捨てパッド』の語源となっているのです」

中学1年の「移項」って?

　中学校学習指導要領解説：文部科学省の中学校学習指導要領解説数学編 pp.71, 72-73*4より：

Twitter上の「移項」って?

• 「移項」とは一方の辺の項を符号を逆にして他の辺に移すこと　←何だこれ？ - Togetter

　コメントで興味深かったのは，「移項については中学校学習指導要領本文第2章第3節(数学) 第2-2-(A)に〔用語・記号〕に明記されている」という指摘に対し「「移項」の定義はどこにも書かれていない」と言及しているところです．「ご飯論法」を彷彿とさせます．
　その分野（数学教育学）に携わってこなかった者こそ，謙虚に，その分野で使われてきた用語や概念を学ばなければと，思わずにいられなかったやりとりでした．

*1:wikipedia:ワンタイムパッド

*2:スライドでは明示していませんが，「xyy」と書いたら「（xy）y」を意味すること（「4÷2÷2」は「（4÷2）÷2」であって「4÷（2÷2）」ではないのと同じように）と，x0＝xすなわち0が排他的論理和の単位元であることも，使用しています．ここで「0」について，1ビットでない場合は，全ビットが0となるビット列を表します．

*3:暗号文から平文を求める「暗号文単独攻撃」ではなく，平文と暗号文のペアを入手できそこから鍵を求める「既知平文攻撃」や「選択平文攻撃」を念頭に置いています．

*4:画像の2枚目と3枚目はページをまたいで段落を構成しています．最初の画像の箱囲みは，（解説でない）中学校学習指導要領の記載を意味します．