暗号化のお話 (1)

前へ << Java で HTTP クライアントを作ってみよう (3)

暗号化のお話 (2) >> 次へ

最終目的は SSL/TLS

ここから暗号化に関する話が始まります。 最終目標は「SSL/TLS プログラミングができるようになること」なのですが、 プログラミングのやり方だけを説明するのは嫌なので、 暗号の基礎についても解説してみました。 本を買って勉強してみたところ、これが非常におもしろい。 ついついいろんなことを書いてしまいました。

共通鍵

データを安全にやりとりするにはどうすればいいでしょうか。 そう、暗号化すればいいのです。

古来から伝わる暗号化の方式としてシーザー暗号というのものがあります。 仕組みはとても簡単で、下の表のように文字列をアルファベット順に 数個ずらすだけです。この例では A〜Z を F〜Z・A〜E と、5つずらしています。

A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

↓

↓

↓

↓

↓

↓

↓

↓

↓

↓

↓

↓

↓

↓

↓

↓

↓

↓

↓

↓

↓

↓

↓

↓

↓

↓

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

A

B

C

D

E

例えば「I LOVE YOU」というメッセージをこのシーザー暗号で 暗号化すると「N QTAJ DTZ」という暗号文になります。 暗号文を受信した側は、F〜Z・A〜E を 5つずらして A〜Z に戻せば「I LOVE YOU」という平文が手に入ります。

つまり、送信側と受信側が「アルファベットを 5つずらす」という 共通の規則を知っておけば、安全にデータのやりとりができるのです。 このような暗号化の方式を共通鍵方式と呼びます。困ったことに 以下のようにいろいろな呼び方がありますが、全て同じものを指します。

• 共通鍵暗号方式 (Common-Key Cryptography)
• 対称鍵暗号方式 (Symmetric-Key Cryptography)
• 秘密鍵暗号方式 (Secret-Key Cryptography)

このいろいろな呼び名が共通鍵方式の特徴を的確に表しています。 ということですね。

rot13

UNIX には rot13 というプログラムがあります。 これは読んで字の如く英字を 13 個ずらす (＝rotate) だけです。

% echo 'I Love You!' | rot13
V Ybir Lbh!

なぜ 13 かというと、英字は 26 個なので、もう一度 rot13 をかませば元に戻るからです。

% echo 'I Love You!' | rot13 | rot13
I Love You!

よって、暗号化や復号化を選ぶ必要はなく、とにかく rot13 をかませば暗号化あるいは復号化ができることになります。 この rot13 はシーザー暗号の一種と言えるでしょう。

単換字暗号

当然ながらシーザー暗号や rot13 はあまりにも簡単すぎます。ちょっと勘のいい人なら、 暗号文を見ただけでアルファベットをずらせばよいと気づいてしまうかもしれません。 そこで思い付くのは、 などと文字と文字の対応を決め (この対応表はランダムに決めたものです)、 その法則に従って文字を置換して暗号文を作成するものです。 これを単換字 (たんかえじ) 暗号方式と呼びます。

上記規則に従って「I Love You」を暗号化すると、 「T Oean Rei」になります。

当ページ管理人なぞこれであきらめてしまうのですが、 やはり世の中頭のいい人がいるもので、単換字暗号方式への対策はちゃんとあります。 それが「頻度分析」です。

英語であれば各文字の出現頻度は以下のようになります (FreeBSD の rot13(1) より引用)。

つまり「暗号文の中に最も多く出現してくる文字は E を指すのではないか?」 という推測が成り立つわけです。また、以下のような条件が必要です。

• 暗号文がある程度の長さを持つこと
• 既知の言語であること

もちろんこれは出現頻度の傾向でしかありませんので、本当に E が 多いかどうかはわかりません。ただし、RFC 2616 (Hypertext Transfer Protocol -- HTTP/1.1) の出現頻度を数えたところ、 一番多いのは E、二番目が T で、上記の統計どおりでした (三番目からは大はずれでしたが)。

また、頻度分析に加えて、言語特有の分析を行うことでさらに確度はあがります。 例えば、

• 1文字のアルファベットは「a」か「I」である可能性が高い。
• 3文字の頻出英単語は「the」である。
• 「2文字+3文字」の英単語であれば、「of the」「in the」「to the」の順で可能性が高い。
  (参考: 共起頻度分析ツール「ngram」)

また、解読が進めば進むほど、他の文字が推測しやすくなります。以下は解読済の文字 (18文字)を小文字、 未解読の文字 (8文字) を大文字で表記してあります。

stHtus oQ tCis mYmo

   tCis WoLumYnt spYLiQiYs Hn intYrnYt stHnWHrWs trHLk protoLol Qor tCY
   intYrnYt Lommunity, HnW rYquYsts WisLussion HnW suSSYstions Qor
   improvYmYnts.  plYHsY rYQYr to tCY LurrYnt YWition oQ tCY "intYrnYt
   oQQiLiHl protoLol stHnWHrWs" (stW 1) Qor tCY stHnWHrWizHtion stHtY
   HnW stHtus oQ tCis protoLol.  WistriBution oQ tCis mYmo is unlimitYW.

ぱっと見ただけでも

• 「oQ」は「on」か「of」では? ⇒ Q は n か f である
• 「is unlimitYW」は「is unlimited」だろう ⇒ Y は e、W は d である
• 「protoLol」は「protocol」に違いない ⇒ L は c である

などと推測できるでしょう。すると「spYLiQiYs」は「specifies」か「specinies」の いずれかであることがわかりますが、「specinies」という英単語はないので、 「specifies」が正しいと思われます。そして Q は f であることがわかります。

単換字暗号が頻度分析に弱いことが知られるにつれ、 より複雑な暗号が開発されました。 しかし昔はコンピュータなぞ存在しませんでしたので、 暗号化も復号化も人が手で行わなければなりません。 あまりにも複雑な暗号は使いこなせなかったのです。

DES

時は移ろい、コンピュータという便利なものが出現した現代。 暗号はより複雑になりました。

共通鍵方式で最も有名なのはやはり DES (Data Encryption Standard) でしょう。

なぜ DES が有名かと言うと、アルゴリズムを広く公開した初めての暗号だったからです。 暗号は戦争の道具として発展してきたという経緯があります。 ですから、1970年代、暗号アルゴリズム自体がトップシークレットでした。 しかし、異なる会社が作成した暗号では相互運用はできず、 作成者ではなくては暗号の強度を確認できず、どれが安全な暗号なのか誰も知らない、 という困った状況でした。

そんな中、1972年に米国商務省標準局 (NBS: National Bureau of Standards。現在は NIST に改称) が暗号アルゴリズムを公募しました。それに対して IBM が応募し、国家安全保障局 (NSA: National Security Agency) が手を加えて出来たものが DES です。 DES は 1977 年にアメリカの連邦情報処理標準 (FIPS: Federal Information Processing Standard) に採用されました。

DES の出現により、鍵は秘密にするけれど、 暗号アルゴリズムは広く公開するというやりかたが一般的になりました。 現代では、暗号アルゴリズムを隠す「隠蔽によるセキュリティ」 (Security through obscurity または Security of obscurity) は愚かなこととされています。

当然ながら DES はシーザー暗号よりも複雑な置き換え方法を行っています (具体的には、ローテート・排他的論理輪・転置・S ボックス…だそうです)。 どれくらい難しいかというと、当ページ管理人が理解できないくらいです。

DES の詳細を知りたいなら、以下のサイトをどうぞ。

• 暗号化技術-DES (Engineering)
• DES暗号化アルゴリズムの詳細 (Shadow Penguin Security)

DES は弱い?

「DES は解読しやすい」と聞いたことがあるかもしれません。DES の 鍵は 56bit です。つまり、鍵の種類は 2^56 (＝2の56乗、 72,057,594,037,927,936。7京2057兆) 通りということです。 言い替えると、2^56 個の鍵を地道に試せば、必ず鍵が見付かるわけです。

2^56 というのは人間が手で試すには途方もない数です。 昔のコンピュータにとっても、途方もない数でした。 では、「最近のコンピュータにとっては途方もない数か」。 RSA Security 社 が開催している 「DES Challenge」というコンテストがあります。 DES で暗号化したデータを解読した人に賞金が出る、というものです。

開催時期	コンテスト名	解読に要した時間	備考
1997年1月	DES Challenge I	96日
1998年1月	DES Challenge II-1	41日	解読したのは distributed.net という団体で、解読プログラムを配布し、 世界中のコンピュータでよってたかって解読した。 このときの distributed.net 全体の計算能力を換算すると、 「22,393 台の Intel Pentium II 333MHz マシン」に相当する。
1998年7月	DES Challenge II-2	56時間	解読したのは EFF という団体が開発した、 DES 解析ハードウェア Deep Crack 。 250,000 ドル以下の費用で製作したとか。ちなみに DES Challenge II-2 の賞金は 10,000 ドル。
1999年1月	DES Challenge III	22時間 15分	このときは distributed.net の世界中のコンピュータと、EFF の専用ハードウェアが協力。

さて、この結果をどう評価しますか?

専用ハードウェアを使うと、1日もかからないうちに解読に成功してしまいます。 ただ、少なくとも当ページ管理人は、そのハードウェアを作ることはできませんし、 買う方法も知りません。 しかし、国家や会社組織であれば、簡単に作ることができるでしょう。 ESS は Deep Crack の設計図を公開している、 らしいです (ちゃんと web を読んでないので本当かどうかは知りません)。

一方、22,000 台の Pentium II 300MHz で 41日で解読できるということは、 (Pentiun4 3GHz が Pentium II 300MHz の 10倍の計算能力を持つと仮定すると) 2,200 台の Pentium4 3GHz で 41日で解読できるということです。 当ページ管理人は PC を 2,200 台買うことはできませんが、 国家や会社組織であれば、簡単に入手できるでしょう。

つまり、そこらへんの人が「ちょっと DES を解読してみようか」 と思っても、そう簡単にはできません。しかし、金と知識を持っている組織が 本気で解読しようとすると、非常に簡単、というわけです。

ただし「DES が弱い」のは「共通鍵方式だから弱い」のではありません。 単に 56bit という鍵長が少なすぎただけなのです。 どんな暗号方式でも、全ての鍵を総あたりで解読しようとすればいつかは 正解にたどり着きます。総あたりしか解読方法がない DES というのは、 むしろ優秀な暗号方式と言えます。

2DES

DES は 56bit だから弱い。「じゃあ鍵を 2つ用意して、DES で 2回暗号化すれば強くなるのでは?」 ということで出てきたのが 2DES です。「ダブル DES」と呼びます。 56bit の倍の 112bit の鍵長を持たせるのが目的で、確かに総当たり攻撃に対しては 112bit 分の強さがあったのですが、中間一致攻撃 (Meet-in-the-Middle) という攻撃に弱いことがわかりました。

中間一致攻撃は多量のメモリを必要とするため、そう簡単にできる攻撃ではないのですが、 とにかくこの攻撃を使うと 57bit 分の探索で解読できてしまうのです (56bit×2 の鍵空間 = 57bit 分の鍵空間)。

2DES は使うべきではありません。 まぁ 2DES を実装しているソフトウェア・ハードウェアを見たことがないので、 使いたくても使えないかもしれませんが。

3DES

2回でダメなら 3回暗号化してしまえ、というのが 3DES です。 トリプル DES と読みます。DES3 と書く場合もあります。

3DES には、鍵を 2つ使う方法と、鍵を 3つ使う方法があります。

• 鍵を 2つ: 「鍵 A で暗号化 → 鍵 B で復号化 → 鍵 A で暗号化」
• 鍵を 3つ: 「鍵 A で暗号化 → 鍵 B で復号化 → 鍵 C で暗号化」

いずれも「暗号化 → 暗号化 → 暗号化」ではなく、 「暗号化 → 復号化 → 暗号化」となっていることに注意してください。 これを EDE (Encrypt-Decrypt-Encrypt) と言います。DES なら DES-EDE などと書きます。

暗号強度については、EDE と EEE (Encrypt-Encrypt-Encrypt) は同じ強さです。 しかし EDE の利点として「鍵 A と鍵 B に同じ鍵を使うと、結局は 1つの鍵で暗号化したのと 同じ結果が得られる」ということがあげられます。特に暗号化処理をハードウェアで実装した場合、 DES 用と 3DES 用の実装を全く同一にすることができるわけですね。

「そもそも鍵 B で暗号化していないデータに対して、鍵 B で復号化してよいのか?」 と思うかもしれませんが、復号化は「暗号化の際に行った操作を逆に行う」 というだけの処理なので、問題ありません。 シーザー暗号で例えるなら、

• 暗号化: 右に n 個ずらす   復号化: 左に n 個ずらす
• 暗号化: 左に n 個ずらす   復号化: 右に n 個ずらす

のいずれを選んでも同じ、ということです。

2つの鍵を使う 3DES・3つの鍵を使う 3DES いずれも 総当たり攻撃に対しては 168 bit 分の強さがありますが、 中間一致攻撃に対しては 112bit 相当の暗号強度になります。 なお、2つの鍵を使う 3DES については 攻撃方法があるようなので (ちゃんと読んでません)、3つの鍵を使った方がよいでしょう。 2003 年現在では 3DES の暗号強度は「悪くはない」と見なされています。

ただし 3DES はかなり遅いです。 DES の暗号化・復号化はそれほど速くない上に、それを 3回も繰り返すのですから、 当然とも言えます。

AES

最近出てきた暗号として、AES (Advanced Encryption Standard) があります。 アメリカの NIST (米国商務省標準技術局) が DES に代わる暗号を公募しました。 世界中から多くの暗号が集まり、 世界中の暗号学者・数学者が暗号の強度を検討した結果、 結局 Rijndael (レインドール) という暗号が AES に選ばれました。

暗号強度以外にも、

• 鍵長が 128bit、192bit、256bit から選択可能なこと
• 速度が速いこと
• AES に選ばれた場合は、特許を放棄すること

などの条件が求められました。

これを勝ち抜いたのが Rijndael だったのです。 AES 選定にまつわる話は すずきひろのぶ 氏の

• AES Conference / CRYPTO 98 訪問記
• AESファイナリストをめぐって 〜暗号最新動向〜

で読むことができます。ちなみに非常におもしろく・わかりやすく書かれているので、 ぜひ一読されることをおすすめします。

その他の共通鍵暗号方式

他にも RC2、RC5、RC6、Blowfish、IDEA、TwoFish など多くの共通鍵の暗号化方式があります。

RSA Security 社は、RC5 という暗号化方式の鍵長 64bit の堅固さをアピールするため、RC5-64 Challenge というコンテストを開催し、 解読までに 1,757 日を要しました。現在は、鍵長 72bit をクラックする RC5-72 Challenge を開催中です。

開催時期	コンテスト名	解読に要した時間	備考
1997年11月〜2002年7月	RC5-64 Challenge	1,757日	解読したのは distributed.net
2002年12月〜	RC5-72 Challenge	?日	現在進行中

鍵長が 56 bit である DES の解読時間と比べると、 鍵長の長さはとても重要ということがわかっていただけると思います。

UNIX における共通鍵

昔は crypt あるいは enigma というコマンドがありました (今でもありますが)。 これは今となっては弱すぎる暗号方式です。

今では openssl コマンドを使うのが一番よいでしょう。 openssl というと apache と組み合わせて SSL の鍵管理に使うもの、 と思っている人もいるかもしれませんが、 コマンドラインでの暗号化・復号化機能も充実しています。

% openssl enc -h
options are
-in      input file
-out     output file
-pass     pass phrase source
-e             encrypt
-d             decrypt
-a/-base64     base64 encode/decode, depending on encryption flag
-k             key is the next argument
-kfile         key is the first line of the file argument
-K/-iv         key/iv in hex is the next argument
-[pP]          print the iv/key (then exit if -P)
-bufsize    buffer size
-engine e      use engine e, possibly a hardware device.
Cipher Types
-aes-128-cbc               -aes-128-cfb               -aes-128-ecb
-aes-128-ofb               -aes-192-cbc               -aes-192-cfb
-aes-192-ecb               -aes-192-ofb               -aes-256-cbc
-aes-256-cfb               -aes-256-ecb               -aes-256-ofb
-aes128                    -aes192                    -aes256
-bf                        -bf-cbc                    -bf-cfb
-bf-ecb                    -bf-ofb                    -blowfish
-cast                      -cast-cbc                  -cast5-cbc
-cast5-cfb                 -cast5-ecb                 -cast5-ofb
-des                       -des-cbc                   -des-cfb
-des-ecb                   -des-ede                   -des-ede-cbc
-des-ede-cfb               -des-ede-ofb               -des-ede3
-des-ede3-cbc              -des-ede3-cfb              -des-ede3-ofb
-des-ofb                   -des3                      -desx
-desx-cbc                  -rc2                       -rc2-40-cbc
-rc2-64-cbc                -rc2-cbc                   -rc2-cfb
-rc2-ecb                   -rc2-ofb                   -rc4
-rc4-40                    -rc5                       -rc5-cbc
-rc5-cfb                   -rc5-ecb                   -rc5-ofb

plain.txt を DES で暗号化し、crypted に出力します。

% openssl enc -e -des -in plain.txt -out crypted

復号化する場合は以下のようにします。

% openssl enc -d -des -in crypted -out plain.txt.decoded

DES でなく AES 256bit で暗号化します。

% openssl enc -e -aes256 -in plain.txt -out crypted

共通鍵方式の弱点

非常にわかりやすい共通鍵方式ですが、残念ながら弱点があります。 いったいどうやって共通鍵 (たとえば「アルファベットを 5つずらす」という 規則) をお互いに伝えあえばいいのでしょうか。

直接会ってこっそり耳打ちする…というのも悪くないですが、 直接会えない状況というのもあります。

例えばあなたは web 上のショップでよさそうな本を見付けました。 購入するため、住所・氏名・クレジット番号などの個人情報を送信したいとします。 ネットワークを誰かが盗聴しているかもしれませんので、 データを暗号化して送信したいとします。 しかし、あなたと web ショップは初めて出会ったわけなので、 共通鍵を知りません。

ネットワーク上に共通鍵を流したら、盗聴者に鍵を入手されてしまいます。 電話で伝えようと思っても、電話が盗聴されているかもしれません。 手紙で伝えようと思っても、手紙が途中で開封されてしまうかもしれません。

これを「鍵配送問題」と言います。共通鍵を使う以上、 鍵をどうやって相手に伝えるかは永遠の課題だったのです。

それを解決したのが、次節で解説する公開鍵暗号方式です。

前へ << Java で HTTP クライアントを作ってみよう (3)

暗号化のお話 (2) >> 次へ