暗号化アルゴリズム

(1) 19世紀より前の暗号

本章から、データ暗号作成方法とその解読方法について紹介したいと思います
紀元前から人々は、重要な機密文書を他人に知られることなく正当な受信者だけに渡すため、様々な手段を用いてきました。当然そのような重要な秘密を暴こうと、暗号を解読する手段も開発されてきたため、暗号の作成方法とその解読手段は常にお互い進化しつづけてきたわけです。新しく強力な暗号が作られたと思ったら、それを解読するための手段が発見され、一度解読法が見つかってしまえばその暗号はもはや役に立たなくなってしまいます。現在用いられている暗号についても、いつ破られてしまうかは分かりません。そしていったん破られてしまえば、それはもはや使うことができなくなるわけです。

この章では、まず紀元前の頃から第一次大戦前までに活躍した暗号作成方法と、その解読方法について紹介したいと思います。

1) 秘密通信の方法

情報を他人に知られることなく正当な受信者に送る方法として、二つのタイプがあります。ひとつはステガノグラフィ(Steganography)で、メッセージの存在を隠すことで他人に知られないようにするやり方、もう一つはクリプトグラフィ(Cryptography)で、メッセージは隠さずにその内容を分からなくするやり方です。ステガノグラフィのわかりやすい例として「あぶり出し」がありますが、これは果汁などを使って紙にメッセージを書き、受け取った者がその紙を火にかざすことによってメッセージを読むことができるというものです。最近では画像ファイルにこの技術を使って情報を埋め込み、秘密通信に使っていたという例も報告されています。
一方のクリプトグラフィは、ある手順にしたがってメッセージを変換することによって、その手順を知らなければ読むことができないようにするやり方です。ステガノグラフィには、一度メッセージが見つけられてしまうとその内容が全て他人に知られてしまうという大きな欠点がありますが、クリプトグラフィでは変換したメッセージを元に戻す手段が分からない限り内容を理解することはできません。よくミステリー小説などで、被害者が残した謎のメッセージを解読していくようなものがありますが(最近ではダ・ヴィンチ・コードが有名でしょうか)、これも広い意味ではクリプトグラフィの一種になります。
これから紹介する暗号化手法は、クリプトグラフィの中でもメッセージ内の文字をある手続きで変換する方法だけになります。ステガノグラフィは含まれませんし、あるメッセージから連想されるパスワードを類推するような、映画などで出てくるようなものも当然含まれません。

クリプトグラフィは、さらに転置式暗号と換字式暗号の二種類に分類できます。転置式暗号はメッセージの文字を並べ替えることで他人が読めなくする方法で、換字式暗号はメッセージの文字を別の文字に置き換える方法です。まずは転置式暗号の例を紹介します。

2) 転置式暗号

転置式暗号の代表としては、スパルタで使用されていたスキュタレー(Scytale)が有名です。スキュタレーは木製の巻き軸で、これに革紐を巻き付けてメッセージを読みます。革紐には一見ランダムなメッセージが書かれていますが、これをスキュタレーに巻き付けることで一定の間隔ごとに文字が並べ替えられ、メッセージが浮かびあがる仕組みで、発信者はまずスキュタレーに巻き付けた状態でメッセージを書き、それを解いてからベルトのように見せかけて運び(一種のステガノグラフィ)、受信者は受け取った革紐を同じ太さのスキュタレーに巻き付けてメッセージを解読するといったやり取りを行っていたそうです。
日本語で書かれた小説などは通常縦書きで、一定の文字数で行が変わります。これを横から読んだとき、偶然か意図したものなのか、何らかのメッセージが表れるようなものを見掛けることがありますが、これと同じような理屈になります。

その他の転置式暗号として、レール・フェンス暗号化(Rail Fence Cipher)というものがあります。スキュタレーと原理は同じで、メッセージをある文字数分だけ縦に書いていき(この一列がフェンスになります)、フェンスの末尾まで達したら右側に新たなフェンスを書いていきます。このとき、フェンス一つあたりの文字数が、行の数(各行はレールになります)と等しくなります。最後まで書き終えたら、一番上のレールから順番に文字を並べ換えれば暗号化は完了です。

以下に例を示します。この例では、レールの本数を二本としています。また、空白文字は削除します。

メッセージ : THIS IS RAIL FENCE CIPHER

T I I R I F N E I H R
H S S A L E C C P E
↓
TIIRIFNEIHR HSSALECCPE

以下にレール・フェンス暗号化のサンプル・プログラムを示します。 
/*
  レールフェンス暗号化 : 文字列を数段に分けて交互に書いて、各段毎に出力する。

  char* src : 暗号化する対象文字列
  char* enc : 暗号化した文字列を格納するエリア
  char* enc_end : encの末尾
  unsigned int step : 分割数
  unsigned int word : 一度に入出力する文字数

  Ex. abcdefghiをstep=3,word=2で処理した場合

  ab    gh
    cd    i
      ef
      ↓
  abghcdief
*/
void rail_fence_encryption( char* src, char* enc, char* enc_end, unsigned int step, unsigned int word )
{
  unsigned int len = strlen( src ); /* srcの文字数 */
  char* src_end = src + len;        /* srcの末尾 */
  int i, j;

  if ( step == 0 || word == 0 ) return;

  for ( i = 0 ; i < step ; i++ ) {
    char* s = src + i * word;
    while ( s < src_end && enc < enc_end - 1 ) {
      for ( j = 0 ; j < word ; j++ ) {
	if ( s >= src_end || enc >= enc_end - 1 ) break;
	*enc++ = s[j];
      }
      s += step * word;
    }
    if ( enc >= enc_end - 1 ) break;
  }

  *enc = '\0';
}

/*
  分割されるグループの各サイズを求める

  unsigned int len : 文字列の長さ
  unsigned int step : 分割数
  unsigned int word : 一度に入出力する文字数
  unsigned int* group_size : 各グループのサイズを記録するエリア

  Ex. abcdfeghiをstep=3,word=2で処理した場合

  ab|cd|ef|gh|i で5回入出力されるので、各stepは
  ab,gh  cd,i  ef のグループに分割される。よって各サイズは4,3,2
*/
void calc_group_size( unsigned int len, unsigned int step, unsigned int word, unsigned int* group_size )
{
  int i;
  unsigned int group_count = len / word; /* 入出力される回数 */
  unsigned int min_group_size = ( group_count / step ) * word; /* 各グループの文字数の最小値 */

  for ( i = 0 ; i < step ; i++ )
    group_size[i] = min_group_size;

  int r = len - min_group_size * step; /* 全グループに割り当てられる分以外の端数 */

  /* 端数分を先頭のグループから順に割り当て */
  for ( i = 0 ; i < step ; i++ ) {
    if ( r <= 0 ) break;
    group_size[i] += ( ( r > word ) ? word : r );
    r -= word;
  }
}

/*
  レールフェンス復号化

  char* enc : 暗号化した文字列
  char* src : 復号化した文字列を格納するエリア
  char* src_end : srcの末尾
  unsigned int step : 分割数
  unsigned int word : 一度に入出力する文字数
*/
void rail_fence_decryption( char* enc, char* src, char* src_end, unsigned int step, unsigned int word )
{
  unsigned int len = strlen( enc ); /* encの文字数 */
  unsigned int group_size[step];    /* 各step毎の文字数 */
  int i, j;

  if ( step == 0 || word == 0 ) return;

  calc_group_size( len, step, word, group_size );
  for ( i = 0 ; i < step ; i ++ ) {
    char* e = enc; /* 現stepの暗号文字列先頭ポインタ */
    enc += group_size[i]; /* encは現stepの末尾を指すようにする */
    char* s = src + i * word; /* 現stepを復号化する先頭位置 */
    while ( e < enc && s < src_end ) {
      for ( j = 0 ; j < word ; j++ ) {
	if ( e >= enc || s + j >= src_end ) break;
	s[j] = *e++;
      }
      s += step * word;
    }
  }
  char* s = src + len;
  if ( s >= src_end ) s = src_end - 1;
  *s = '\0';
}

上の例では、レールの本数をstep、一度に読み込む文字数をwordで指定することで、さらに複雑なパターンで暗号化と復号化を行えるようになっています。先の例をstep=3、word=2で行った場合、

メッセージ : THIS IS RAIL FENCE CIPHER

TH RA NC HE
IS IL EC R
IS FE IP
↓
THRANCHE ISILECR ISFEIP

と暗号化されます。暗号化の場合は文字列の先頭から各レールに並ぶ文字コードを抽出するだけで簡単にできますが、復号化では各レールごとの区切り位置をチェックしないとうまく処理することができないため、レールごとの文字数を計算してから復号化処理を行っています。この計算処理はcalc_group_sizeで行っています。

転置式暗号は、元の文字列に含まれる文字コード自体が変わるのではなく、その並びが変わるだけです。それぞれが異なる3つの文字からなる文字列を並べ替える組合せは6通りしかありませんが、アルファベット全ての文字ひとつずつからなる文字列を並べる組合せを考えると約4X1026通りにもなります。ちなみに一億は1X108なので、一億の一億倍の一億倍よりも大きいということになります。この組合せを全てチェックするには膨大な時間が必要になり、解読することなど不可能に見えます。
しかし、完全にランダムな並べかえをしてしまえば、復号化もできなくなるため、実際には上記のようなある規約に基づいて並べ替えを実施することになります。レールフェンス暗号化の場合、もし処理の方法が分かってしまえば、キーとなるパラメータはstepとwordの二種類の数値だけになるため、いくつかのパラメータを試してみれば容易に解読できてしまいます。

3) 換字式暗号

前述の通り、換字式暗号はメッセージの各文字を他の文字に置き換えて暗号化する方法で、特に有名なものとして「カエサル暗号(Caesar cipher)」があります。カエサル暗号では、メッセージ内のそれぞれのアルファベットを、それより三つ後ろにあるアルファベットに置き換えます。最後の三文字分はそれより後側の文字は存在しないため、先頭の三文字に置換することになります。
カエサル暗号は、ローマの政治家「ユリウス・カエサル」が実際に使ったことからその名が付けられましたが、シフトする文字数は必ず三つとする必要はなく、アルファベットを置換する場合なら一文字から二十五文字まで変化させることができます。よって、このように任意の文字数だけシフトさせる方法による暗号化もカエサル暗号と呼ばれています。

以下にカエサル暗号化のサンプル・プログラムを示します。 
/*
  文字列から指定した文字コードの位置を検出して返す

  char* s : 文字列
  char c : 文字コード

  戻り値 : 文字の位置(見つからなかった場合は負数)
*/
int find_code( char* s, char c )
{
  if ( ! isprint( c ) ) return( -1 );
  char* cp = strchr( s, c );
  if ( cp == NULL ) return( -1 );

  return( cp - s );
}

/*
  カエサル暗号化

  char* src : 暗号化を行う文字列
  char* enc : 暗号化した結果を格納するエリアへのポインタ
  char* encEnd : encの末尾(番人)
  char* plain : 平文文字コード
  unsigned int shift : シフト量
*/
void caesar_cipher_encode( char* src, char* enc, char* encEnd, char* plain, unsigned int shift )
{
  int len = strlen( plain );

  for ( ; *src != '\0' ; src++ ) {
    if ( enc >= encEnd - 1 ) break;
    int i = find_code( plain, *src );
    if ( i >= 0 )
      *enc++ = plain[(i + shift) % len];
  }
  *enc = '\0';
}

/*
  カエサル復号化

  char* enc : 暗号化した文字列
  char* src : 復号化した結果を格納するエリアへのポインタ
  char* srcEnd : srcの末尾(番人)
  char* plain : 平文文字コード
  unsigned int shift : シフト量
*/
void caesar_cipher_decode( char* enc, char* src, char* srcEnd, char* plain, unsigned int shift )
{
  int len = strlen( plain );

  for ( ; *enc != '\0' ; enc++ ) {
    if ( src >= srcEnd - 1 ) break;
    int i = find_code( plain, *enc );
    if ( i >= 0 ) {
      i -= shift;
      if ( i < 0 ) i += len;
      *src++ = plain[i];
    }
  }
  *src = '\0';
}

サンプル・プログラム中の平文文字コードplainには、置換対象の文字コードがあらかじめ登録されているものとします。元の文字列から読み込んだ一文字をplain内より探し、その位置からさらに任意の数だけシフトした位置の文字を使って暗号化を行います。復号化では、暗号化した文字列から読み込んだ一文字をplainから探索して、今度は逆方向に同じ数だけシフトすれば、元の文字列を得ることができます。

カエサル暗号は、作成できる暗号の種類が最大二十五種類と少ないため、いったんカエサル暗号を使用していることが分かってしまえば、解読することは非常に容易になります。しかし、それぞれの文字コードを変換する組み合わせを完全に任意とした場合、その組み合わせは約4 X 1026にもなります。たとえ換字型暗号を利用していることが判明したとしても、どのような組合せで並べ変えを行ったのかが分からない限りは、全ての組合せを一つずつ試しながら解読を行うことになり、事実上解読は不可能なように見えます。

以下に換字型暗号のサンプル・プログラムを示します。 
/*
  文字列から指定した文字コードの位置を検出して返す

  char* s : 文字列
  char c : 文字コード

  戻り値 : 文字の位置(見つからなかった場合は負数)
*/
int find_code( char* s, char c )
{
  if ( ! isprint( c ) ) return( -1 );
  char* cp = strchr( s, c );
  if ( cp == NULL ) return( -1 );

  return( cp - s );
}

/*
  キーコードの重複を除外する

  char* code : キーコード
*/
void ex_dup_code( char* code )
{
  char* current = code + 1;
  if ( *code == '\0' || *current == '\0' ) return;

  while ( *current != '\0' ) {
    char* c;
    for ( c = current - 1 ; c >= code ; c-- )
      if ( *c == *current ) break;
    if ( c >= code ) {
      c = current;
      do {
	*c = *( c + 1 );
	c++;
      } while ( *c != '\0' );
    } else {
      current++;
    }
  }
}

/*
  キーコードに含まれない文字を平文文字コードから暗号文字コードへコピーする

  char* plain : 平文文字コード
  char* plain_end : 平文文字コードの末尾(NULL時は平文文字コードの末尾チェックを行わない)
  char** cipher : 暗号文字コード
  char* cipher_end: 暗号文字コードの末尾
  char* keyword : キーコード
*/
void move_code( char* plain, char* plain_end, char** cipher, char* cipher_end, char* keyword )
{
  char* c;

  for ( ; *plain != '\0' ; plain++ ) {
    if ( plain_end != NULL && plain >= plain_end ) break;

    /* 文字がキーコードに含まれるかをチェックして、含まれていなければ暗号文字コードにコピー */
    for ( c = keyword ; *c != '\0' ; c++ )
      if ( *c == *plain ) break;
    if ( *c == '\0' )
      *( ( *cipher )++ ) = *plain;
    if ( *cipher >= cipher_end - 1 )
      break;
  }
}

/*
  キーコードを元に暗号文字コードを作成する
  キーコードを先頭に並べ、キーコードの末尾の次の文字から順にキーコードに含まれない文字を追加する

  char* plain : 平文文字コード
  char* cipher : 作成する暗号文字コードへのポインタ
  char* cipher_end : 暗号文字コードの末尾
  char* keyword : キーコード
*/
void create_cipher_code( char* plain, char* cipher, char* cipher_end, char* keyword )
{
  char* p;
  char* c = cipher;

  ex_dup_code( keyword );
  if ( strlen( keyword ) > cipher_end - c ) return;
  strcpy( c, keyword );
  c += strlen( keyword );

  /* キーコードの末尾の文字と一致するものを平文文字コードから探す */
  for ( p = plain ; *p != '\0' ; p++ )
    if ( *( c - 1 ) == *p ) break;

  if ( *p != '\0' ) {
    p++;
    /* 一致した文字が見つかったらその次の文字からコピー */
    move_code( p, NULL, &c, cipher_end, keyword );
    /* 次に先頭から残りをコピー */
    move_code( plain, p, &c, cipher_end, keyword );
  }

  *c = '\0';
}

/*
  単一換字式暗号化/復号化

  char* src : 暗号化/復号化を行う文字列
  char* enc : 暗号化/復号化した結果を格納するエリアへのポインタ
  char* enc_end : encの末尾(番人)
  char* plain : 平文文字コード
  char* cipher : 暗号文字コード
*/
void substitution( char* src, char* enc, char* enc_end, char* plain, char* cipher )
{
  for ( ; *src != '\0' ; src++ ) {
    int j = find_code( plain, *src );
    if ( j >= 0 ) {
      if ( enc >= enc_end ) break;
      *enc++ = cipher[j];
    }
  }
  *enc = '\0';
}

上記サンプル・プログラムでは、元の文字列にあるそれぞれの文字コードが平文文字コード(plain)上のどの位置にあるかを探索し、暗号文字コード(cipher)の同じ位置にある文字コードに置き換えることで暗号化処理を行っています。暗号文字コードの作成処理はcreate_cipher_codeで行っていますが、ただ単純に平文文字コードに対してスクランブル処理を掛けて作成した場合、メッセージを読んでほしい相手にまで解読できないような暗号メッセージができあがってしまうため、ある特定のキーワードから暗号文字コードが作成できるようにして、そのキーワードさえ覚えていれば解読できるようにしておきます。キーワードから暗号文字コードを作成する手順は以下の通りです。

  1. キーワードから重複する文字コードを取り除く

  2. 暗号文字コードの先頭から重複文字を取り除いたキーワードを並べる

  3. キーワードの末尾にある文字コードの次の位置にある文字を平文文字コードから探索する

  4. 探索した位置から順番に残りの文字コードを暗号文字コードへコピーする

キーワードをcaesarcipher(カエサル暗号)として、アルファベットを使って暗号文字コードを作成する例を以下に示します。

キーワードcaesarcipher
平文文字コードabcdefghijklmnopqrstuvwxyz
暗号文字コード

キーワードcaesriph
平文文字コードabcdefghijklmnopqrstuvwxyz
暗号文字コード

キーワードcaesriph
平文文字コードabcdefghijklmnopqrstuvwxyz
暗号文字コードcaesriph

キーワードcaesriph
平文文字コードabcdefghijklmnopqrstuvwxyz
暗号文字コードcaesriphjklmnoqtuvwxyzbdfg

この暗号文字コードによって、暗号化したいメッセージの中の文字コード'a'は'c'へ、'b'は'a'へ、といった具合に換字暗号処理ができます。この処理を行っている箇所がsubstitutionになります。
復号化は、暗号文字コードと平文文字コードを逆にして暗号化と同じ処理を行うことでできてしまいます。

以下は、換字暗号化を利用して、ある有名なメッセージを暗号化した例です。解読することはできるでしょうか?

:NKcROIKTYKYcLUXcSUYZcYULZ]GXKcGXKcJKYOMTKJcZUcZGQKcG]G_c_U[XcLXKKJUScZUcYNGXKcGTJcINGTMKcOZqcc(_cIUTZXGYZncZNKc-4; c-KTKXGRc6[HROIc2OIKTYKcOYcOTZKTJKJcZUcM[GXGTZKKc_U[XcLXKKJUScZUcYNGXKcGTJcINGTMKcLXKKcYULZ]GXKooZUcSGQKcY[XKcZNKcYULZ]GXK cOYcLXKKcLUXcGRRcOZYc[YKXYqcc:NOYc-KTKXGRc6[HROIc2OIKTYKcGVVROKYcZUcSUYZcULcZNKc,XKKc9ULZ]GXKc,U[TJGZOUThYcYULZ]GXK cGTJcZUcGT_cUZNKXcVXUMXGSc]NUYKcG[ZNUXYcIUSSOZcZUc[YOTMcOZqccj9USKcUZNKXc,XKKc9ULZ]GXKc,U[TJGZOUTcYULZ]GXKcOYcIU\KXKJcH_ cZNKc-4;c2KYYKXc-KTKXGRc6[HROIc2OIKTYKcOTYZKGJqkcc?U[cIGTcGVVR_cOZcZUc_U[XcVXUMXGSYncZUUq

4) ヴィジュネル暗号

前章で紹介した換字暗号化は、一つの平文文字コードを一つの暗号文字コードに置き換えて換字しているため、単アルファベット換字式暗号(Monoalphabetic Substitution Cipher)と呼ばれています。この方法は使用方法が簡単な上、組み合わせの多様性により鍵となるキーワードやキーフレーズさえ知られなければ暗号を破ることは不可能とされていたため、長い間利用されてきました。しかし、この方法は本当に安全で解読不可能なのでしょうか。
データ圧縮法の紹介の時にも書いたように、データ列には冗長性があり、ハフマン符号化ではデータ出現頻度の差を利用することで圧縮が可能となっています。このデータ出現頻度を利用することで暗号解読ができることが、九世紀頃、アラビアの科学者たちによって発見されました。英文の場合、最も使用頻度の高い英単語は'e'で全体の13%、その後't'、'a'、'o'、'n'の順に並び、最も使用頻度の低いアルファベットは'z'になります。単アルファベット換字式暗号では、同じ文字コードはある一つの同じ文字コードに暗号化されるため、各文字の使用頻度はそのまま保持されます。従って、暗号文にある各文字の使用頻度を調べることによって、復号化したときの文字を推測することができるようになります。

アルファベットだけに着目しても頻度にバラツキがあるため、解読に充分役立ちそうですが、単アルファベット換字式暗号の場合は文字コードと同様、同じ単語は必ず同じ文字列で暗号化されるという致命的な弱点があります。よって使用頻度の高い単語に着目するとさらに解読がしやすくなります。例えば、上に示した暗号文では'cZNKc'という単語がいくつか見つかりますが、'ZNK'を使用頻度の高い'the'と予想して、さらにその両端が空白文字であると見なした場合、暗号文は以下のようになります。

:he ROIeTYeY LUX SUYt YULt]GXe GXe JeYOMTeJ tU tGQe G]G_ _U[X LXeeJUS tU YhGXe GTJ IhGTMe Otq (_ IUTtXGYtn the -4; -eTeXGR 6[HROI 2OIeTYe OY OTteTJeJ tU M[GXGTtee _U[X LXeeJUS tU YhGXe GTJ IhGTMe LXee YULt]GXeootU SGQe Y[Xe the YULt]GXe OY LXee LUX GRR OtY [YeXYq :hOY -eTeXGR 6[HROI 2OIeTYe GVVROeY tU SUYt UL the ,Xee 9ULt]GXe ,U[TJGtOUThY YULt]GXe GTJ tU GT_ UtheX VXUMXGS ]hUYe G[thUXY IUSSOt tU [YOTM Otq j9USe UtheX ,Xee 9ULt]GXe ,U[TJGtOUT YULt]GXe OY IU\eXeJ H_ the -4; 2eYYeX -eTeXGR 6[HROI 2OIeTYe OTYteGJqk ?U[ IGT GVVR_ Ot tU _U[X VXUMXGSYn tUUq

暗号平文
c空白文字
Ke
Nh
Zt

ここで'ee'を末尾に持つ単語がいくつか表れました。四文字の英単語としては'tree'や'free'などを思い浮かべることができます。また、M[GXGTteeは末尾が'tee'で、三文字めと五文字目が同じアルファベットである九文字の単語であることがわかるので、候補はかなり絞りこむことができます。おそらく'guarantee'ではないでしょうか。これを当てはめてみると次のようになります。

:he ROIenYeY LUr SUYt YULt]are are JeYOgneJ tU taQe a]a_ _Uur LreeJUS tU Yhare anJ Ihange Otq (_ IUntraYtn the -4; -eneraR 6uHROI 2OIenYe OY OntenJeJ tU guarantee _Uur LreeJUS tU Yhare anJ Ihange Lree YULt]areootU SaQe Yure the YULt]are OY Lree LUr aRR OtY uYerYq :hOY -eneraR 6uHROI 2OIenYe aVVROeY tU SUYt UL the ,ree 9ULt]are ,UunJatOUnhY YULt]are anJ tU an_ Uther VrUgraS ]hUYe authUrY IUSSOt tU uYOng Otq j9USe Uther ,ree 9ULt]are ,UunJatOUn YULt]are OY IU\ereJ H_ the -4; 2eYYer -eneraR 6uHROI 2OIenYe OnYteaJqk ?Uu Ian aVVR_ Ot tU _Uur VrUgraSYn tUUq

暗号平文
c空白文字
Ga
Ke
Mg
Nh
Tn
Xr
Zt
[u

ここまでくると、かなり解読しやすくなります。LUr→for、aRR→all、anJ→andなど、一つ一つアルファベットを組み換えていくと、以下のように解読することができました。

:he licenses for most software are designed to take away your freedom to share and change itq (y contrastn the -4; -eneral 6ublic 2icense is intended to guarantee your freedom to share and change free softwareooto make sure the software is free for all its usersq :his -eneral 6ublic 2icense applies to most of the ,ree 9oftware ,oundationhs software and to any other program whose authors commit to using itq j9ome other ,ree 9oftware ,oundation software is co\ered by the -4; 2esser -eneral 6ublic 2icense insteadqk ?ou can apply it to your programsn tooq

暗号平文
c空白文字
Ga
Hb
Ic
Jd
Ke
Lf
Mg
Nh
Oi
Qk
Rl
Sm
Tn
Uo
Vp
Xr
Ys
Zt
[u
]w
_y

まだ途中までしか解読していませんが、ある程度の内容は充分に判読ができるようになりました(ちなみにこのメッセージはGNU GENERAL PUBLIC LICENSEの一部です)。また、暗号文字コードと平文文字コードの対応表から、ほとんどの単語は一定の文字数分シフトしただけであるように見えます。おそらく、Pはjに、Wはqに変換することが可能でしょう。
このように最初のいくつかの単語が正しく置換できれば、解読がそれほど難しくないことがこれで理解できると思います。もっとも、この例では空白文字がそのまま含まれていたため単語の区切りがすぐに推測できるようになっていました。通常は空白文字を除くなどして、各単語の区切りが分かりにくくなっているでしょう。また、文字の出現頻度に比例した数だけの暗号文字コードを各平文文字コードに割り当てて(例えばeの出現頻度は約13%なので、13個の暗号文字コードを割り当てるなど)、その中からランダムに選んで暗号化を行うことで、出現頻度を均一にする手法(ホモフォニック換字式暗号 Homophonic Substitution Cipher)などを利用することで、安全性を高めることも可能です。しかし、これも英語などで見られるような、他の文字との出現順番に見られる特徴(連接特徴 ; 例えば、qの後には必ずuが続くという特徴)を利用することで、解読は可能になるため、素人には解読できなくても、暗号解読のプロなどにかかれば安全とは言えなくなります。

暗号文字コードが一種類である限り、同じ単語は同じ文字列で暗号化され、文字コードの出現頻度や文字列の同じパターンから解読を行うことができます。しかし、暗号文字コードを複数用意して使い分けを行うことで、同一の文字コードが異なる文字に変換され、文字列のパターンを生み出さないようにすることができます。最初にこのことに気づいたのはレオン・バッティスタ・アルベルティ(Leon Battista Alberti)で、彼は二組の暗号文字コードを用意して、それを交互に使うことで、単アルファベット換字式暗号の弱点が克服できることを発見しました。このように、暗号文字コードを複数用いた換字式暗号を、多アルファベット換字式暗号(Polyalphabet Substitution Cipher)と呼びます。
ちなみに、ホモフォニック換字式暗号では一つの文字コードに対する暗号文字コードが複数になるだけであるため、単アルファベット換字式暗号に分類されます。決定的な違いは、一つの暗号文字コードに対しては平文文字コードがただ一つに決まってしまうというところです。多アルファベット換字式暗号では、そのようなことにはなりません。

多アルファベット換字式暗号を発展させた人物として、ヨハネス・トリテミウス(Johannes Trithemius)、ジョバンニ・バッティスタ・デラ・ポルタ(Giovanni Battista Della Porta)、そしてブレーズ・ド・ヴィジュネル(Blaise de Vigenere)の三名が挙げられます。トリテミウスは、カエサル暗号で行った文字のシフトを一文字分ずつ変化させながら行った26種類の暗号アルファベットを縦に並べ、上から順番に使用しながら暗号化を行う方法を考案しました。これをトリテミウスの多表式暗号と呼びます。

トリテミウスの多表式暗号表
平文ABCDEFGHIJKLMNOPQRSTUVWXYZ
Aabcdefghijklmnopqrstuvwxyz
Bbcdefghijklmnopqrstuvwxyza
Ccdefghijklmnopqrstuvwxyzab
Ddefghijklmnopqrstuvwxyzabc
Eefghijklmnopqrstuvwxyzabcd
Ffghijklmnopqrstuvwxyzabcde
Gghijklmnopqrstuvwxyzabcdef
Hhijklmnopqrstuvwxyzabcdefg
Iijklmnopqrstuvwxyzabcdefgh
Jjklmnopqrstuvwxyzabcdefghi
Kklmnopqrstuvwxyzabcdefghij
Llmnopqrstuvwxyzabcdefghijk
Mmnopqrstuvwxyzabcdefghijkl
Nnopqrstuvwxyzabcdefghijklm
Oopqrstuvwxyzabcdefghijklmn
Ppqrstuvwxyzabcdefghijklmno
Qqrstuvwxyzabcdefghijklmnop
Rrstuvwxyzabcdefghijklmnopq
Sstuvwxyzabcdefghijklmnopqr
Ttuvwxyzabcdefghijklmnopqrs
Uuvwxyzabcdefghijklmnopqrst
Vvwxyzabcdefghijklmnopqrstu
Wwxyzabcdefghijklmnopqrstuv
Xxyzabcdefghijklmnopqrstuvw
Yyzabcdefghijklmnopqrstuvwx
Zzabcdefghijklmnopqrstuvwxy

これを利用して例えばhello worldを暗号化した場合、最初の暗号アルファベットは平文アルファベットと同じなのでhのまま、次のeは一文字シフトした暗号アルファベットを利用するのでfとなり、以下暗号化を進めるとhfnos buytmに変換されます。ここでhelloの中のllが暗号化された文字列ではnoと異なった文字コードに変換されていることがわかると思います。よって文字の出現頻度を利用した解析や、同じパターンの文字列を利用した類推などは一切できなくなります。
なお、復号する場合は、暗号文のアルファベットから平文アルファベットをたどることで行います。例えば例に示した暗号文二文字目のfは、二行目の暗号アルファベットでは左から五番めにあたる列Eに位置しているため、eに変換されます。

ポルタは、ダイグラフィック暗号(Digraphic Cipher)を考案しました。トリテミウスの多表式暗号とは異なり、二文字ずつペアで変換します。

ダイグラフィック暗号表
平文ABCDEFGHIJKLMNOPQRSTUVWXYZ
Antotptqtrtstttutvtwtxtytztatbtctdtetftgthtitjtktltmt
Bnsospsqsrssstsusvswsxsyszsasbscsdsesfsgshsisjskslsms
Cnrorprqrrrsrtrurvrwrxryrzrarbrcrdrerfrgrhrirjrkrlrmr
Dnqoqpqqqrqsqtquqvqwqxqyqzqaqbqcqdqeqfqgqhqiqjqkqlqmq
Enpopppqprpsptpupvpwpxpypzpapbpcpdpepfpgphpipjpkplpmp
Fnooopoqorosotouovowoxoyozoaobocodoeofogohoiojokolomo
Gnnonpnqnrnsntnunvnwnxnynznanbncndnenfngnhninjnknlnmn
Hnmompmqmrmsmtmumvmwmxmymzmambmcmdmemfmgmhmimjmkmlmmm
Inlolplqlrlsltlulvlwlxlylzlalblcldlelflglhliljlklllml
Jnkokpkqkrksktkukvkwkxkykzkakbkckdkekfkgkhkikjkkklkmk
Knjojpjqjrjsjtjujvjwjxjyjzjajbjcjdjejfjgjhjijjjkjljmj
Lnioipiqirisitiuiviwixiyiziaibicidieifigihiiijikilimi
Mnhohphqhrhshthuhvhwhxhyhzhahbhchdhehfhghhhihjhkhlhmh
Nngogpgqgrgsgtgugvgwgxgygzgagbgcgdgegfggghgigjgkglgmg
Onfofpfqfrfsftfufvfwfxfyfzfafbfcfdfefffgfhfifjfkflfmf
Pneoepeqereseteuevewexeyezeaebecedeeefegeheiejekeleme
Qndodpdqdrdsdtdudvdwdxdydzdadbdcdddedfdgdhdidjdkdldmd
Rncocpcqcrcsctcucvcwcxcyczcacbcccdcecfcgchcicjckclcmc
Snbobpbqbrbsbtbubvbwbxbybzbabbbcbdbebfbgbhbibjbkblbmb
Tnaoapaqarasatauavawaxayazaaabacadaeafagahaiajakalama
Unzozpzqzrzsztzuzvzwzxzyzzzazbzczdzezfzgzhzizjzkzlzmz
Vnyoypyqyrysytyuyvywyxyyyzyaybycydyeyfygyhyiyjykylymy
Wnxoxpxqxrxsxtxuxvxwxxxyxzxaxbxcxdxexfxgxhxixjxkxlxmx
Xnwowpwqwrwswtwuwvwwwxwywzwawbwcwdwewfwgwhwiwjwkwlwmw
Ynvovpvqvrvsvtvuvvvwvxvyvzvavbvcvdvevfvgvhvivjvkvlvmv
Znuoupuqurusutuuuvuwuxuyuzuaubucudueufuguhuiujukulumu

ダイグラフィック暗号表を使ってhello worldを暗号化する場合、二文字ずつのペアhe、ll、ow、or、ldに分解して、それぞれのペアに該当する暗号アルファベットのペアを表から抽出します。heの場合は列H、行Eに位置する文字upを選択します。この操作により、upyib xbcyqと変換されることになります。なお、ダイグラフィック暗号表では平文アルファベットのペアと暗号アルファベットのペアが可逆的に変換できるように並んでいます。例えば平文アルファベットのペアheにあたる暗号アルファベットのペアupに対して、平文アルファベットのペアupにあたる暗号アルファベットのペアはheになります。従って復号する場合も、暗号化の時と全く同じ操作でできます。
このように、複数の文字を一度に変換する方式をポリグラフィック換字暗号(Polygraphic Substitution Cipher)と言います。

アルベルティ、トリテミウス、ポルタの三人はそれぞれ、多アルファベット換字式暗号の発展に貢献してきたのですが、最終形として完成させたのはヴィジュネルでした。ヴィジュネルは、トリテミウスの多表式暗号表を利用して、あるキーワードに従って行を切り替えるという手法を考案しました。これをヴィジュネル暗号(Vigenere Cipher)と言います。トリテミウスは単純に、最上位の行から順番に暗号アルファベットを利用していましたが、行自体にスクランブルを掛けることによって、さらに解読の難しい、強力な暗号を作成することができるわけです。トリテミウスの多表式暗号表はヴィジュネル暗号で利用する場合、ヴィジュネル方陣とも呼ばれています。

hello worldを、キーワードvigenereを使ってヴィジュネル暗号化する場合、最初のhはキーワードの最初の文字vにあたるヴィジュネル方陣上の下から五行目の行を利用して、cと変換されます。次の文字eはキーワードの二番めの文字iにあたる行を利用してmになります。キーワードの最後の文字まで使いきった場合は最初の文字に戻り、同じ操作を繰り返します。以下、変換を続けると暗号はcmrpb afvglになります。
復号する場合、トリテミウスの多表式暗号と同様に、暗号文のアルファベットから平文アルファベットをたどる形になります。当然、暗号アルファベットはキーワードに従って切り替える必要があります。

以下にヴィジュネル暗号のサンプル・プログラムを示します。 
/*
  文字列から指定した文字コードの位置を検出して返す

  char* s : 文字列
  char c : 文字コード

  戻り値 : 文字の位置(見つからなかった場合は負数)
*/
int find_code( char* s, char c )
{
  if ( ! isprint( c ) ) return( -1 );
  char* cp = strchr( s, c );
  if ( cp == NULL ) return( -1 );

  return( cp - s );
}

/*
  ヴィジュネル暗号化

  char* src : 暗号化を行う文字列
  char* enc : 暗号化した結果を格納するエリアへのポインタ
  char* enc_end : encの末尾(番人)
  char* plain : 平文文字コード
  char* key : キーコード
*/
void vigenere_cipher_encode( char* src, char* enc, char* enc_end, char* plain, char* key )
{
  char* key_buf = key;
  unsigned int len = strlen( plain );

  while ( *src != '\0' ) {
    if ( enc >= enc_end - 1 ) break;
    int k = find_code( plain, *key_buf );
    int s = find_code( plain, *src++ );
    if ( k >= 0 && s >= 0 ) {
      *enc++ = plain[( s + k ) % len ];
      if ( *(++key_buf) == '\0' ) key_buf = key;
    }
  }
  *enc = '\0';
}

/*
  ヴィジュネル復号化

  char* enc : 暗号化した文字列
  char* src : 復号化した結果を格納するエリアへのポインタ
  char* src_end : srcの末尾(番人)
  char* plain : 平文文字コード
  char* key : キーコード
*/
void vigenere_cipher_decode( char* enc, char* src, char* src_end, char* plain, char* key )
{
  char* key_buf = key;
  unsigned int len = strlen( plain );

  while ( *enc != '\0' ) {
    if ( src >= src_end - 1 ) break;
    int k = find_code( plain, *key_buf );
    int e = find_code( plain, *enc++ );
    if ( k >= 0 && e >= 0 ) {
      if ( e < k ) e += len;
      *src++ = plain[e - k];
      if ( *(++key_buf) == '\0' ) key_buf = key;
    }
  }
  *src = '\0';
}

ヴィジュネル暗号を手で行うのはかなり大変な作業になります。またホモフォニック換字式暗号などにより、単アルファベット換字式暗号でもある程度強力な暗号が作成できることもあって、かなり強力な暗号が作成できるにも関らず、誕生してから約200年もの間ほとんど利用されなかったそうです。しかしプログラム上では非常に簡単な処理で行うことができます。
サンプル・プログラムでは、キーコードkey及び暗号化を行う文字列src上の現在の文字が、平文文字コードplainの中のどの位置にあるかをチェックして、その位置をそれぞれ変数k、sに格納しています。plain[k]はk行目の暗号文字コードを表し、そこからs番めの文字が暗号文字コードになるため、plain[( s + k ) % strlen( plain ) ]が求める暗号化した文字になります。
復号化のときは、plain[-k]が暗号文字コードを平文文字コードに戻す操作と同じ意味になるため、暗号文字列enc上の現在の文字が、平文文字コードplainの中のどの位置にあるかをeで表したとき、plain[e - k]が求める復号化した文字になります。

ヴィジュネル暗号を利用して、換字暗号化を行った時と同じメッセージを暗号化した例です。今度は解読が可能でしょうか? 

 N_KRc/Kh?KmKLi>eg;YnKYi2Zq-X_KGl1e^1Yc3T_0en;en-Q_KGq-_yEUo>e`>K_0UgKZiKYb-X_KGh0e]4Gh3Ky5Z(Ke<Ee];Tn>Gm@qy@N
_K-H!eA1T_>GfK6o.Rc/eF5I_:Y_KOmKOh@Kh0K^KZiKMo-X[:Z_1es;[lKLl1K^;Sy@Uy?N[>Ky-T^KIb-Ta1e`>K_KYi2Zq-X_Xrn;eg-Q_KYo>K
y@N_KYi2Zq-X_KOmKLl1Ky2UlKGf8ec@YyAY_>Y(KeN4OmK-_:Kl-Ry{[\8O]K2c/Kh?Ky-Vj8O_?en;eg;YnKU`KZb1e@>K_K9i2Zq-X_K,iAT^-Z
c;T!?em;LnCGl1e[:Jy@Uy-TsKUn4KlKVl;Ml-SyCNi?Ky-[n4Ul?e];Sg5Zy@UyAYc:My5Z(Ke"~Ug1ei@N_>e@>K_K9i2Zq-X_K,iAT^-Zc
;Ty?U`@][>Ky5Yy/Up1X_0e\Een4Kyr4OK2_?Y_>eA1T_>GfK6o.Rc/eF5I_:Y_KOh?Z_-J(Tey%UoKI[:e[<VfEec@en;es;[lKVl;Ml-SmWen;U(

5) ヴィジュネル暗号の解読とワンタイムパッド

ヴィジュネル暗号は、頻度分析を不可能にし、暗号メッセージ上の同じパターンから単語を類推することを防ぐこともできるため、しばらくの間は「解読不能の暗号」とされていましたが、この暗号にも大きな弱点があることが19世紀の科学者チャールズ・バベッジ(Charles Babbage)によって発見されてしまいます。

バベッジは、当時まだ人手で作成していた数表(三角関数や対数など関数で計算した値を表にまとめたもの)を機械で計算させることで、誤りのない高精度の数表を作成することを考案し、階差機関(Difference Engine)を設計したことで有名な科学者です。しかし、この階差機関の第一号は失敗に終わり、第二号の作成も政府の助成金打ち切りにより完成しませんでした。バベッジはさらに、機械により汎用的な計算を行うための解析機関(Analytical Engine)を設計したのですが、この装置には「入出力装置」としてパンチカードとプリンタ、曲線プロッタ、ベルなどを使用し、「記憶装置」や「演算装置」を備えていました。さらに条件分岐やループ制御を持つプログラミング言語も備えていたため、現在のコンピュータの雛型とも見なされていますが、階差機関のプロジェクトが失敗したことにより、残念ながら試作機が作成されただけで、完全な形で実現することはできませんでした。
ちなみに、ラブレース伯爵夫人のエイダ・キング(Ada King)はバベッジの解析機関に興味を持ち、イタリア人数学者のルイジ・メナブレア(Luigi Menabrea)が出版したバベッジの講演記録を英語に翻訳し、その中でベルヌーイ数を求めるための世界初のプログラムコードを掲載しています(実際にはバベッジが書いたというのが定説になっているようですが、エイダとバベッジが交わした書簡の中で明らかにエイダ自身が書いたとされるプログラムもあるそうです)。このため、彼女を世界初のプログラマとする者もおり、プログラミング言語のAdaは彼女の名前を元に名付けられました。

ヴィジュネル暗号では、キーコードによって暗号アルファベットを切り替えていました。例えば、KEYをキーコードとしてtを暗号化する場合、キーワードの中で使用される文字によって、次のように変換されます。

ある単語が暗号化されるとき、最初の文字を暗号化するときに使われるキーコード内の文字の位置によって結果は異なりますが、その組合せはキーコードの文字数に等しくなります。例えば、上記キーコードでtheを暗号化した場合、次のように変換されることになります。

メッセージの中に同じ単語theがいくつもある場合、キーコードの文字数分だけのパターンの変換結果が出現することになります。よって暗号メッセージ内に同じパターンが出現した場合、稀な例外もありますが、通常は同じ単語が同じキーコードを使って変換された結果だと推測することができます。特に一致したパターンが長ければ、その確率は高くなります。

ヴィジュネル暗号で暗号化した先のメッセージを見ると、いくつかの同じパターンが見つかります。

 N_KRc/Kh?KmKLi>eg;YnKYi2Zq-X_KGl1e^1Yc3T_0en;en-Q_KGq-_yEUo>e`>K_0UgKZiKYb-X_KGh0e]4Gh3Ky5Z(Ke<Ee];Tn>Gm@qy@N
_K-H!eA1T_>GfK6o.Rc/eF5I_:Y_KOmKOh@Kh0K^KZiKMo-X[:Z_1es;[lKLl1K^;Sy@Uy?N[>Ky-T^KIb-Ta1e`>K_KYi2Zq-X_Xrn;eg-Q_KYo>K
y@N_KYi2Zq-X_KOmKLl1Ky2UlKGf8ec@YyAY_>Y(KeN4OmK-_:Kl-Ry{[\8O]K2c/Kh?Ky-Vj8O_?en;eg;YnKU`KZb1e@>K_K9i2Zq-X_K,iAT^-Z
c;T!?em;LnCGl1e[:Jy@Uy-TsKUn4KlKVl;Ml-SyCNi?Ky-[n4Ul?e];Sg5Zy@UyAYc:My5Z(Ke"~Ug1ei@N_>e@>K_K9i2Zq-X_K,iAT^-Zc
;Ty?U`@][>Ky5Yy/Up1X_0e\Een4Kyr4OK2_?Y_>eA1T_>GfK6o.Rc/eF5I_:Y_KOh?Z_-J(Tey%UoKI[:e[<VfEec@en;es;[lKVl;Ml-SmWen;U(

他にもあると思いますが、ざっと眺めただけでKYi2Zq-X、eA1T_>GfK6o.Rc/eF5I_:Y_KO、e@>K_K9i2Zq-X_K,iAT^-Zc;Tの三つのパターンが見つかりました。次に、このパターンが何文字おきに出現しているのかを確認してみます。

文字パターン出現間隔
KYi2Zq-X180, 27
eA1T_>GfK6o.Rc/eF5I_:Y_KO372
e@>K_K9i2Zq-X_K,iAT^-Zc;T108

この内容から、キーコードは27、108、180、372文字ごとに文字の位置が元に戻っているということが分かります。これらの公約数は1を除くと3のみになるため、キーコードの文字数は3であると推測することができます。
キーコードの文字数が判明すれば、キーコード内のそれぞれの文字で変換された場所ごとに分解された暗号メッセージは単純なカエサル暗号による変換結果と同等になります。単純にシフト位置を変換しながら調べても、メッセージが分解されているため意味のあるメッセージを得ることはできませんが、ここからは単アルファベット換字式暗号の解読手段が利用できるため、文字コードの出現頻度を調べることによりシフト位置を推測することは充分可能です。

上記の例では、キーワードの文字数が非常に短かったため、同じパターンがいくつも見つかってしまいました。しかし、キーワードが充分に長ければ、解読はかなり難しくなり、メッセージとキーワードが同じ長さになれば、この方法での解読は不可能になります。
メッセージと同程度の文字数のキーワード、例えば百文字のメッセージに対して百文字のキーワードを作成しようとすると、例えば何かの文献にある文章を利用したり、国名や動物の名前などを並べてみたりすることになると思います。しかし、キーワード自体に何らかのパターンがある場合、頻繁に利用される単語を平文文字コードに当てはめてみて、これが暗号化された場合のキーワードを類推することで、キーワードを特定することも不可能ではありません。例えば、暗号メッセージの先頭三文字が復号化されたときはTheになると仮定して、そのように暗号化されるにはどんなキーワードを使えばいいのかを求めてみます。この時のキーワードが何らかの単語の一部と推測できたら、その仮定が正しいとして単語の残りを補ってみて、復号化を試みます。これを繰り返すことにより、解読を行うことは(かなり難しいですが)不可能ではありません。

キーワードに何らかのパターンが存在すれば、安全性は保証できないことになりますが、キーワードを完全にランダムなものにすると、キーワードを類推することすら不可能になります。ランダムな文字コードから成るキーワードを使った暗号処理を「ワンタイムパッド(One Time Pad, OTP)」暗号化と言います。ワンタイムパッドでは、一度使ったキーワードは捨てられるため、このような名前が付けられました。
クロード・シャノン(Claude Elwood Shannon)は、ワンタイムパッドが情報理論的に解読不可能な唯一の暗号であることを数学的に証明しました。ちなみにシャノンは、スイッチの直列接続がAND、並列接続がORを示すことから、あらゆる論理演算がスイッチ回路で実現可能であることを示し、現在のコンピュータの発展に大きな影響を与えた人物です。

ワンタイムパッドを使えば解読不可能な暗号を作ることが可能になりますが、問題はどうやって完全にランダムなキーワードを作成するかです。現在のコンピュータで作成できる乱数は疑似乱数と呼ばれるもので、本当の乱数ではありません。暗号用に乱数を作成する場合、物理現象を使うことが多いようですが、それが理想的な乱数になっているとは限らないため、後で加工する必要もあります。つまり、キーワードの作成にはかなりの手間と時間がかかってしまうということです。さらに、作成したキーワードを、暗号を受け取る相手にも配送しなければなりません。これもかなり大変な作業になり、さらに他人の手に渡ってしまう危険性もあります。
使用済みのキーワードを再利用するなどというのは絶対にしてはいけないことです。もし、同じキーワードを利用した二つの暗号メッセージが手に入れば、片方のメッセージに良く利用する単語を当てはめてキーワードを求め、それを使ってもう一方のメッセージを復号し、意味のある部分を調べるという操作を繰り返すことで、正しいキーワードを見つけることができてしまいます。アメリカのVENONA作戦で旧ソ連のワンタイムパッド暗号が解読されたのは、同じキーワードを利用した暗号メッセージが存在したことが原因でした。

ワンタイムパッド暗号として有名なものに、バーナム暗号(Vernam Cipher)があります。Gilbert Sandford VernamとJoseph Mauborgneが考案したこの暗号法では、充分に長いランダムなキーワードを使い、平文との排他的論理和を計算することで暗号化を行います。キーワードの長さが平文のそれ以上であれば解読不可能な暗号となります(但し、乱数の生成方法にも依存し、疑似乱数を使っているような場合は絶対安全であるという保証はありません)。

今回のサンプル・プログラムのソースをアップロードしておきます。御自由にお使い下さい。

zip形式(cryptography.zip)

tar-gzip形式(cryptography.tar.gz)

動作確認はVine Linux 4.0上で行いました。特殊なライブラリは使用していないため、どんな環境でもビルド・動作は可能だと思います。

<参考文献>
  1. 「暗号解読」 サイモン・シン著 (新潮社)
  2. Wikipedia

[Go Back]前に戻る [Back to HOME]タイトルに戻る

inserted by FC2 system