PAGE TOP

取り組み

印刷する

排他的論理和と暗号

さぼ郎
排他的論理和」などと日本語で表現すると、なんだか物々しいです。一般的には「XOR」というと思います。

どういう時に使うと便利な演算子かと言うと、たとえば、信号が来ていない状態、つまり、信号が「0」の時に、信号が来出すと「1」になります。

信号を一つ前と比較すると、
0 - 0 信号が来ていない状態
0 - 1 信号が来た
1 - 1 信号が来ている
1 - 0 信号が来なくなる
信号
こんな時、信号が来た1パルスだけ、あるいは、信号が来なくなった1パルスだけを取得するのに「XOR」を使います。

例えばマウスでドラッグして、マウスボタンを離した1パルスを取得して、何か処理をする などの利用に、結構都合がいい演算子です。

【XOR】これは変わり者
0 0 = 0 0
1 0 = 1 1
0 1 = 1 0
1 1 = 0 1
【AND】これは掛け算
0 0 = 0
1 0 = 0
0 1 = 0
1 1 = 1
【OR】これは足し算
0 0 = 0
1 0 = 1
0 1 = 1
1 1 = 1
で、「NAND」が、「AND」の反対だとすると、
【NAND】これは天邪鬼
0 0 = 1
1 0 = 1
0 1 = 1
1 1 = 0

XOR」のところで「」を鍵とすると、2回「XOR」をかけると元の値に戻っています。結果は「」。

排他論理和を2回かけると元に戻る という性質は、例えばグラフィックスなどではラバーバンドに使えます。ラバーバンドというのは、クリックしたところから次にクリックするまでのマウスやデジタイザーなどのカーソルをゴムバンドのように追いかけて線を引く機能です。

一回、XORで線を引き、カーソルが移動したら、移動前のポジションにXORで線を引いてから、次の座標にXORで線を引くということを繰り返せばラバーバンドになります。

この、2回かけるともとに戻るという性質が、暗号に於いては不可欠な機能になります

BLUE BACKSの「現代暗号入門」によると、暗号の世界で「XORは、結構普通に使われているとのことでした。

暗号

バーナム暗号」というのが、平文と同じ長さの暗号キーを排他的論理和(XOR)をすることで、解くことができない暗号文にすることができる。会読は、同じく暗号キーで排他的論理和をかければいいわけです。

しかし、鍵は二度は使えないことと、暗号文を渡す前に鍵を用意しておかなければならず、強度は高いものの便利のいい暗号ではないようです。

そこで、鍵をどうやって生成するかが、その後の様々な暗号文のロジックになってきます。

鍵をロジカルに作り出せるようにすれば、ちょっとした鍵を共通で持っていれば、暗号化も復号化もできることになりますが、常に暗号は破られる宿命にあります。

まだ、そこまで読んではいないのですが、ビットコインで使われている「ハッシュ」というのは、可逆的ではないと思っています。その答えがあっているかは、同じ処理をした結果で整合か不整合かを判定するような場面での仕様になるのではないかと思います。

復元する必要がある暗号処理では、「XOR」が重要な演算子であるようです。

一般的には、暗号化された文書の文字の出現頻度から暗号化の癖をよまれるようだ。ちなみに、英文なら「e」の出現が一番多いそうです。

そこで、英文の文字の出現度を調べてみましょう。英語のwikiで「english」を調べてみました。

全部で572行、96,287文字ありました。1パラグラフ辺り168文字くらいです。圧倒的と云うほどではありませんが、たしかに「e」が一番多いようです。

一番多かったのは、半角スペースで 14,586ありましたが、これはあまり意味をなしませんが、英語なら単語の切り目が分かってしまいます。

小文字では「e」「n」「a」「i」「t」で、ビリが「z」。
大文字では「E」「A」「S」「T」「I」で、ビリが「X」。

出現頻度

暗号解読は、このような偏りを調べて解読していくのだそうです。暗号化する側は、偏りをみられないように「換字」をかけるわけです。文字の位置を変えて(転字)して、鍵で換字(XOR処理も含む)するわけですが、それでも偏りは出てしまいます。

そこで、8ビットの文字を48ビット単位に6ビットに切って、その6ビットを転字、換字することで原文をシャッフルするようです。

ただし、完全に復号できなければ意味がありませんし、処理時間がかかりすぎても処理対象の量によっては問題が起きてしまいます。

ちなみに、樋口一葉に「にごりえ」は、パラグラフが44。文字数が21,203文字。1パラグラフあたり、471文字(942バイト)でした。

半角の英文が1パラグラフあたり168文字なのに、全角の和文が1パラグラフあたり471文字というのは、一葉の文書の難解さ(一般的英文の1パラグラフあたり5.6倍のバイト数)にもつながっているような気がします。

文字数を調べるのに使ったgawkのスクリプトは、
{
ll=length($0);
for(i=1;i<ll;i++)
buff[
substr($0,i,1)]+=1;
}
END{
for(i in buff)
print i "t" buff[i];
}
配列の添字に文字を1文字ずつ入れて、各文字の出現の都度インクリメントするだけのスクリプトです。

出現頻度取得の部分は3行、出力の部分は2行だけで、文書で使われている文字の使用頻度を調べることができます。

キーワード