XOR論理演算と解読不可能な可逆暗号「使い捨てパッド暗号」

最近、セキュリティの基礎の勉強をしています。その中で、基礎の基礎であるXOR論理演算について学びました。

XORは排他的論理和のことで、与えられた二つの命題のうちに、どちらか一つだけが真のときに真となる論理演算のことです。

この論理演算の持つ面白い性質として、

a ^ b = c

とした時、

c ^ b = a

となることがあるようです。
つまり、暗号化したいデータと同じ長さのバイト列を持つ、ランダムなバイト列を（使い捨ての）「鍵」として用意すれば、あとはそれに対してXOR演算をかけることで極簡単な暗号化が可能になるというわけですね。

極めて原始的な可逆暗号なわけですけども、この方式を「使い捨てパッド暗号（One Time Pad)」といい、（鍵が流出しない限りは）実質的に解読が不可能であることが数学的に証明されているようです。
詳しい説明は省きますが、仮にブルートフォースで一つづつ復号化を試したとして、どのバイト列が正解であるかと判別できないために解読が不可能だとされています。

「じゃあこの暗号化を使えば常に最強じゃねえか」と思わなくもないわけなんですが、色々な観点から現代では使い捨てパッド暗号は「実用的ではない（汎用性がない）」とされています。
その理由については次以降、あるいは結城浩先生の「暗号化技術入門」あたりを読むといいとおもいます。僕も今「暗号化技術入門」を読んで暗号化技術に入門しています。

新版暗号技術入門 秘密の国のアリス

入門として、過不足なく基礎を解説してくれている良書じゃないかとおもいます。

とはいえ、本を読むだけではアレがソレなので実際にコードを書いて動かして確認してみます。

実装例

せっかくなので、ブラウザで実行して結果をみれるようにしたいとおもったので言語はJavaScriptを使うことにしました。
ということで、せっかくだしHaxeを使います（唐突）。どうせこの程度ならどの言語を使おうが大差ないだろうし。

OneTimePadというクラスが暗号化処理の中枢にあたります。

package ;

import haxe.io.Bytes;
import haxe.extern.EitherType;

import js.Browser;
import js.html.InputElement;

using Std;
using StringTools;


class OneTimePad {

  public var words(default, null): Bytes;
  // ascii = 127
  public var mask(default, null): Bytes;

  var _enctypted(default, null): Bytes;

  public function new(words: String) {
    this.words = Bytes.ofString(words);
    var _len = this.words.length;
    var _buf = Bytes.alloc(_len);
    for (i in 0..._len) {
      _buf.set(i, Std.random(128));
    }
    this.mask = _buf;
  }

  private static function _mask(val: Bytes, mask: Bytes): Bytes {
    var len = val.length;
    var buf = Bytes.alloc(len);
    for (i in 0...len) {
      buf.set(i, val.get(i) ^ mask.get(i));
    }
    return buf;
  }

  public function encrypt(): Bytes {
    if (this._enctypted != null) { return this._enctypted; }
    var enc = _mask(this.words, this.mask);
    this._enctypted = enc;
    return enc;
  }

  public function decrypt(): Bytes {
    var dec = _mask(this._enctypted, this.mask);
    return dec;
  }
}


class Main {
  // 以下、画面で動作させるためのコード
  public static function main() {
    var binWordsField: InputElement = untyped Browser.document.querySelector('#bin-words');
    var maskField: InputElement = untyped Browser.document.querySelector('#maskbit');
    var maskedField: InputElement = untyped Browser.document.querySelector('#masked');
    var unmaskedBitField: InputElement = untyped Browser.document.querySelector('#unmaskedbit');
    var unmaskedField: InputElement = untyped Browser.document.querySelector('#unmasked');
    Browser.document.querySelector('#words').addEventListener('change', function(ev) {
      var value = ev.target.value;
      if (value == '' || value == null) return;
      var pad = new OneTimePad(value);
      binWordsField.value = untyped parseInt(pad.words.toHex(), 16).toString(2);
      maskField.value = untyped parseInt(pad.mask.toHex(), 16).toString(2);
      maskedField.value = untyped parseInt(pad.encrypt().toHex(), 16).toString(2);
      var dec = pad.decrypt();
      unmaskedBitField.value = untyped parseInt(dec.toHex(), 16).toString(2);
      unmaskedField.value = dec.toString();
    });
  }
}

色々とアナはありそうですが、とりあえずはこんな感じで動くんじゃあないかとおもいます。
探した感じ、Haxeは2進数表記とかを簡単に扱うAPIがなかったので冗長な変換 & インラインでJavaScriptを書いたりとかしてます。これなら生でJavaScript書いたほうが楽だったのでは

実例

GistsのHTMLコードを表示してくれるらしいサービス bl.ocks.org - about を利用させてもらいました。
先ほど存在を知ったのでどこまで信用していいのかはわからないけど……

めんどいので基本的にはASCII文字のことだけを考えて実装してます。（一文字づつ暗号化処理をかけているのでこの実装では汎用性に欠けるのでは？）

http://bl.ocks.org/hachibeeDI/raw/0a00abd18117541cb849/

どうでもいいですけど、これだとブラウザの結果をみただけじゃインチキしてるんだかないんだかわかんないですね。コードを合わせてみてください。

元の文字列 -> ランダムに生成した鍵による暗号化 -> 同じ鍵による復号化

ができていることが確認出来るかとおもいます。
もちろん、文字だけじゃなくて画像だとかのデータにも応用できますよ。運用、汎用性の問題さえカバー出来れば実装も簡単ですし、最強の暗号化といってもさしつかえないんじゃないでしょうかね。

まとめ

サーバを実装したときも感じたけど、Haxeでビット演算はしんどいのでは。

XOR演算の、簡単にランダムなデータを作れ、復号化出来るという性質は現代のほとんどの暗号方式の基礎となっています。
というわけで、次回（気が向いたら）はXORを応用したブロック暗号方式のひとつである「DES」とそのアルゴリズムである「ファイステルネットワーク」の実装をしたいとおもいます。

が、ファイステルネットワークってアルゴリズムの仕組み自体はすごくシンプルで簡単なんですけど、実用的に実装しようとすると色々とめんどくさそう……というか、暗号化技術入門の解説だと色々と省略されているわけで、調査したりする気力が湧くまでちょっとかかりそうですね？
アルゴリズムがシンプルでも、実運用を考えた瞬間に実装がダルくなるのはどの世界でもままあることなんですね。

以上！

---

ちなみに暗号化技術入門は、シーザー暗号やエニグマから現代の暗号技術にいたるまでを網羅的に解説してくれていて、例えば日頃暗号系のAPIを叩くときになんとなくで指定していた引数の値だとか方式の違いなんかも一通りわかるようになるわけで、多少なりともセキュリティと関わるプログラマーであれば一冊は手元に置いておきたい書籍だとおもいました！ 結城先生の本は間違いないですねー。

新版暗号技術入門 秘密の国のアリス

暗号と名探偵 (Little Selectionsあなたのための小さな物語)