情報理論 第14回　共通鍵暗号

• 暗号
初回で紹介したように情報通信においては、第三者に情報を知られないようにするために暗号化の処理が行われる。暗号にかかわる用語は以下の通り。
• 平文(ひらぶん)：暗号化される前の文
• 暗号化：情報源 (送信する側) が行う、平文を暗号文に変える工程
• 復号：あて先 (受信する側) が暗号文を平文に変える工程
• 解読：第三者が暗号文を傍受して、なんらかの方法で平文を得ること

暗号には大きく分けて以下の2つがある。
• 共通鍵暗号：暗号化、復号に使う鍵が同じ。処理が速い
• 公開鍵暗号：暗号化、復号に使う鍵が異なる。処理に時間がかかる
共通鍵暗号ではあらかじめ鍵を共有するか、通信路を通して鍵を送らなければならないので、第三者に盗み取られる危険がある。
公開鍵暗号の2つの鍵は無関係ではないが、暗号化の鍵から復号の鍵を得るのは非常に難しい。
今回は共通鍵暗号の例をいくつか紹介する。


• シーザー暗号
シーザー暗号とは、平文の文字を決められた数だけずらして暗号文を作る方法のことである。「文字を何個分ずらすか」の数値がシーザー暗号の鍵にあたる。例えばアルファベットを使う場合は、鍵に応じて下図のように文字をずらす。
あて先側でこれを復号するには、暗号文の文字を鍵の分だけ前にずらす。
(下のフォームで鍵を変更すれば文字どうしをつなぐ線が変わる。また、平文に適当な英文を入れて「↓」を押すとその下に暗号文が表示され、平文の文字を消して「↑」を押せば暗号文をもとにして平文が復元される)

平文の文字

暗号文の文字

鍵
平文
暗号文

シンボルがアルファベットの26文字なら、鍵は0～25の26パターンしかなく、そのうち0では平文と暗号文が全く同じになってしまうので、実質的に鍵は25パターンだけ。
第三者はたとえ鍵を知らなくても総当たりで試せば簡単に暗号文を解読できてしまう。


• 練習問題1
以下の暗号文のもとになった英単語と、暗号化で使われた鍵を求めよ。
1. yulzcgxk
2. pumvythapvu

※ フォームの「暗号文」のところにこれらを入れて「↑」を押せばその鍵での平文が得られる。鍵を適当に変えて試せば最大25回で正しい英単語になる。

• 単一(たんいつ)換(かえ)字(じ)暗号
単一換字暗号とは、文字を下図のような対応表に応じて置き換える方法のことである。この場合は対応表が暗号化・復号の鍵にあたる。
(シーザー暗号と同様に「↓」「↑」で暗号化・復号が行われる。「鍵を変更」を押すと表がランダムに変更される)

平文の文字

暗号文の文字

鍵	平文
	暗号文





平文
暗号文

単一換字暗号のパターン数は一般に非常に多いため、シーザー暗号のように総当たりで鍵を知ることは難しい。
例えばシンボルがアルファベットの26文字なら、鍵の数はそれらの並び替えの数、つまり $26!$ $=26\times 25\times 24\times ...\times 3\times 2\times 1$ $\cong 4\times {10}^{26}$ になる。
単一換字暗号はシーザー暗号に比べれば解読されにくいが、情報源、あて先の両方がこの対応表を持っている必要があるため、今回の初めに述べた脆弱性がある。
平文が十分に長い英文の場合は、以下の手がかりから解読することができる。
• a, e, hなどは頻繁に出現し、q, zなどはめったに出てこない → 暗号文のそれぞれの文字数をカウントし、一般的な英文の出現頻度に合わせて置き換える
• 1文字だけの単語 → 一般的な英文なら「a」か「I」しかありえない
• 連続する2文字で頻繁に出てくる組み合わせ (th, he, in, er, ...) を手掛かりにする


• 練習問題2
上のフォームを使って適当な英文をもとにして暗号文を作り、復号に必要なものと揃えて提出せよ。