前へ << Java で HTTP クライアントを作ってみよう (3) | 暗号化のお話 (2) >> 次へ |
古来から伝わる暗号化の方式としてシーザー暗号というのものがあります。 仕組みはとても簡単で、下の表のように文字列をアルファベット順に 数個ずらすだけです。この例では 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つずらす」という 共通の規則を知っておけば、安全にデータのやりとりができるのです。 このような暗号化の方式を共通鍵方式と呼びます。困ったことに 以下のようにいろいろな呼び方がありますが、全て同じものを指します。
% echo 'I Love You!' | rot13 V Ybir Lbh!なぜ 13 かというと、英字は 26 個なので、もう一度 rot13 をかませば元に戻るからです。
% echo 'I Love You!' | rot13 | rot13 I Love You!よって、暗号化や復号化を選ぶ必要はなく、とにかく rot13 をかませば暗号化あるいは復号化ができることになります。 この rot13 はシーザー暗号の一種と言えるでしょう。
A → H B → B C → L D → W E → Y F → Q |
G → S H → C I → V J → O K → N L → D |
M → G N → T O → K P → R Q → M R → U |
S → J T → F U → P V → E W → A X → Z |
Y → I Z → X |
上記規則に従って「I Love You」を暗号化すると、 「T Oean Rei」になります。
当ページ管理人なぞこれであきらめてしまうのですが、 やはり世の中頭のいい人がいるもので、単換字暗号方式への対策はちゃんとあります。 それが「頻度分析」です。
英語であれば各文字の出現頻度は以下のようになります (FreeBSD の rot13(1) より引用)。
E 13% T 10.5% A 8.1% O 7.9% N 7.1% R 6.8% |
I 6.3% S 6.1% H 5.2% D 3.8% L 3.4% F 2.9% |
C 2.7% M 2.5% U 2.4% G 2% P 1.9% Y 1.9% |
W 1.5% B 1.4% V 0.9% K 0.4% X 0.15% J 0.13% |
Q 0.11% Z 0.07% |
また、頻度分析に加えて、言語特有の分析を行うことでさらに確度はあがります。 例えば、
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.
ぱっと見ただけでも
単換字暗号が頻度分析に弱いことが知られるにつれ、 より複雑な暗号が開発されました。 しかし昔はコンピュータなぞ存在しませんでしたので、 暗号化も復号化も人が手で行わなければなりません。 あまりにも複雑な暗号は使いこなせなかったのです。
共通鍵方式で最も有名なのはやはり 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 の詳細を知りたいなら、以下のサイトをどうぞ。
2^56 というのは人間が手で試すには途方もない数です。 昔のコンピュータにとっても、途方もない数でした。 では、「最近のコンピュータにとっては途方もない数か」。 RSA Security 社 が開催している 「DES Challenge」というコンテストがあります。 DES で暗号化したデータを解読した人に賞金が出る、というものです。
開催時期 | コンテスト名 | 備考 | |
---|---|---|---|
DES Challenge I | 96日 | ||
1998年1月 | DES Challenge II-1 | 41日 | 解読したのは distributed.net という団体で、解読プログラムを配布し、 世界中のコンピュータでよってたかって解読した。 このときの distributed.net 全体の計算能力を換算すると、 「22,393 台の Intel Pentium II 333MHz マシン」に相当する。 |
1998年7月 | 56時間 | 解読したのは EFF という団体が開発した、 DES 解析ハードウェア Deep Crack 。 250,000 ドル以下の費用で製作したとか。ちなみに DES Challenge II-2 の賞金は 10,000 ドル。 | |
1999年1月 | DES Challenge III | このときは 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 というのは、 むしろ優秀な暗号方式と言えます。
中間一致攻撃は多量のメモリを必要とするため、そう簡単にできる攻撃ではないのですが、 とにかくこの攻撃を使うと 57bit 分の探索で解読できてしまうのです (56bit×2 の鍵空間 = 57bit 分の鍵空間)。
2DES は使うべきではありません。 まぁ 2DES を実装しているソフトウェア・ハードウェアを見たことがないので、 使いたくても使えないかもしれませんが。
3DES には、鍵を 2つ使う方法と、鍵を 3つ使う方法があります。
暗号強度については、EDE と EEE (Encrypt-Encrypt-Encrypt) は同じ強さです。 しかし EDE の利点として「鍵 A と鍵 B に同じ鍵を使うと、結局は 1つの鍵で暗号化したのと 同じ結果が得られる」ということがあげられます。特に暗号化処理をハードウェアで実装した場合、 DES 用と 3DES 用の実装を全く同一にすることができるわけですね。
「そもそも鍵 B で暗号化していないデータに対して、鍵 B で復号化してよいのか?」 と思うかもしれませんが、復号化は「暗号化の際に行った操作を逆に行う」 というだけの処理なので、問題ありません。 シーザー暗号で例えるなら、
同様に、DES の操作も「閉じている」のでしょうか? もし DES が「閉じている」のなら、何回 DES で暗号化したところで、 一度で解読できるような鍵を見付ければ済みます。 しかし 1992年に「DES は閉じていない」ことが数学的に証明されました。 つまり、DES で 3回暗号化したものは 必ず 3 回復号化しなければならないということです。
ただし 3DES はかなり遅いです。 DES の暗号化・復号化はそれほど速くない上に、それを 3回も繰り返すのですから、 当然とも言えます。
暗号強度以外にも、
これを勝ち抜いたのが Rijndael だったのです。 AES 選定にまつわる話は すずきひろのぶ 氏の
で読むことができます。ちなみに非常におもしろく・わかりやすく書かれているので、 ぜひ一読されることをおすすめします。RSA Security 社は、RC5 という暗号化方式の鍵長 64bit の堅固さをアピールするため、RC5-64 Challenge というコンテストを開催し、 解読までに 1,757 日を要しました。現在は、鍵長 72bit をクラックする RC5-72 Challenge を開催中です。
開催時期 | コンテスト名 | 備考 | |
---|---|---|---|
1,757日 | 解読したのは distributed.net | ||
?日 | 現在進行中 |
鍵長が 56 bit である DES の解読時間と比べると、 鍵長の長さはとても重要ということがわかっていただけると思います。
今では openssl コマンドを使うのが一番よいでしょう。 openssl というと apache と組み合わせて SSL の鍵管理に使うもの、 と思っている人もいるかもしれませんが、 コマンドラインでの暗号化・復号化機能も充実しています。
% openssl enc -h options are -inplain.txt を DES で暗号化し、crypted に出力します。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
% openssl enc -e -des -in plain.txt -out crypted復号化する場合は以下のようにします。
% openssl enc -d -des -in crypted -out plain.txt.decodedDES でなく AES 256bit で暗号化します。
% openssl enc -e -aes256 -in plain.txt -out crypted
直接会ってこっそり耳打ちする…というのも悪くないですが、 直接会えない状況というのもあります。
例えばあなたは web 上のショップでよさそうな本を見付けました。 購入するため、住所・氏名・クレジット番号などの個人情報を送信したいとします。 ネットワークを誰かが盗聴しているかもしれませんので、 データを暗号化して送信したいとします。 しかし、あなたと web ショップは初めて出会ったわけなので、 共通鍵を知りません。
ネットワーク上に共通鍵を流したら、盗聴者に鍵を入手されてしまいます。 電話で伝えようと思っても、電話が盗聴されているかもしれません。 手紙で伝えようと思っても、手紙が途中で開封されてしまうかもしれません。
これを「鍵配送問題」と言います。共通鍵を使う以上、 鍵をどうやって相手に伝えるかは永遠の課題だったのです。
それを解決したのが、次節で解説する公開鍵暗号方式です。
前へ << Java で HTTP クライアントを作ってみよう (3) | 暗号化のお話 (2) >> 次へ |
ご意見・ご指摘は Twitter: @68user までお願いします。