暗号コラム①
第1回 アルゴリズムとは何か
徒然なるまゝに日ぐらし鍵盤に向かひて…
はじめまして、佐藤に引き続いて暗号コラムを書かせて頂くことになりました鈴木です。佐藤、鈴木と続いて本当にこのコラムは実在の人物が書いているのかという疑問が生じるかと思いますが佐藤、鈴木いずれも実在します。徒然なるままにキーボードに向かいつつ書いてみたいと思います。
インターネットで買い物やネットバンキングなどを行う際、「通信は暗号化されていますので安全です」とか「暗号化して通信いたします」というフレーズが目に入るかと思います。「ああ、暗号化されているから安全なのだな」と考えますが、何故暗号化されていると安全といえるのでしょうか？ 何を以って「安全です」と言っているのでしょうか？ 例えばメロンの品種の1つであるアンデスメロンは元々「安心ですメロン」から名づけられましたがそれは病気に強いという根拠を持っています。暗号も「暗い夜道でも安心できる信号」から名づけられたから安全なのです…という訳ではありません。
暗号とは秘密の通信を行うために用いられる技術です。誰かに読まれたくない文章を細工することで特定の人物以外には読めないようにします。暗号化のための細工には2つの道具が必要です。それは「鍵」と「アルゴリズム」です。
ここで「アルゴリズム」という言葉が登場しました。いったい何物でしょうか？ 大体の方はNHK Eテレで放送されている『ピタゴラスイッチ』の「アルゴリズム体操」や「アルゴリズム行進」を思い浮かべるのではないでしょうか？ この「アルゴリズム」の概念がわかれば「暗号化されていますので安全です」の根拠もわかるようになります。今回のコラムは暗号の安全性に関わる概念「アルゴリズム」について紹介していきたいと思います。
そうだ、新宿に行こう
アルゴリズムとは簡単に言うと問題を解く手順 1 のことです。ここで問題と聞くと身構える人も出てくるかもしれませんので日常にありふれた例を考えてみましょう。例えば皆さんの自宅から街まで出かけるとします。どうやって目的地まで向かいますか？電車？バス？徒歩？ヘリコプター？様々な手段がありそうです。例えば、最寄り駅が神奈川の横浜駅で東京の新宿駅の近くにある本屋に行きたい、という状況を考えて見ましょう。私はよく新宿の本屋へ出かけますのでこの問題には常日頃関わっています。手順を書いてみましょう。
1. 自宅を出る
2. 横浜駅まで歩く
3. 東急東横線・東京メトロ副都心線に乗り新宿三丁目駅まで行く
4. 新宿三丁目駅から本屋まで歩く。
この様に行動すると私は無事本屋へたどり着く事ができます。つまり、上記の流れは「自宅から新宿の本屋へ向かう」という問題を解決する手順、といえます。
「自宅から新宿の本屋へ向かう」手順は必ずしも1通りではありません。例えば
1. 自宅を出る
2. 横浜駅まで歩く
3. 京浜急行に乗り品川まで行く。
4. 品川から山手線外回りに乗り新宿へ向かう。
5. 新宿駅から本屋まで歩く。
という手順でも私は自宅から新宿へ向かうことが出来ます。極端な例では
1. 自宅を出る
2. 横浜駅のロータリーでタクシーを拾う
3. 「新宿の本屋まで」と告げる
4. 新宿付近で降りる
という手順でも新宿の本屋へ向かうことが出来ます。
このように同じ「自宅から新宿の本屋へ向かう」という問題を解決する手段は複数あること、そして何らかの優劣があります。例えばタクシーで新宿の本屋へ向かう手順はずっと座り続けることができるので身体にとっては楽ですが財布には相当やさしくない手順です。つまり、問題を解く手段にも「上手い方法」と「下手な方法」があります。
算法の出で来はじめの祖なる…
アルゴリズムはAlgorithmの訳語ですが一昔前は算法とも訳されていました。先程は日常生活の例を挙げましたが一昔前の訳語の通り数学と密接な関係にあります。世界最古のアルゴリズムは紀元前300年にギリシャの数学者Euclidの『Elements（原論）』の第7巻に登場します。2 それは2つの自然数3の最大公約数を計算するアルゴリズムです。ここで言葉の整理を行います。
・ ある自然数の約数とはその自然数を割り切る自然数4のことです。
・ 公約数とは2つ以上の自然数に共通する約数のことです。
・ 最大公約数とは2つ以上の自然数の公約数の中で最大のものです。
小学校や中学校で習った覚えがある人も多いと思います。実際に求めてみましょう。
12の約数と18の約数
12の約数、つまり12を割り切る数は1,2,3,4,6,12です。また、18の約数は1,2,3,6,9,18となります。
12と18の公約数
公約数とは2つ以上の整数に共通する約数でしたので1,2,3,6となります。
12と18の最大公約数
最大公約数とは2つ以上の整数の公約数の中で最大の数でしたので6となります。
このように最大公約数を求めるために一々約数に着目して公約数を括りだす方法は数が大きくなると大変ですね。もっと工夫をしてみましょう。ここで素因数分解という道具を用意します。素因数分解とは12 = 22 × 3のように自然数を素数の積の形で表すことです。また素数とは2や3のように1と自分自身以外に約数を持たないかつ1ではない数です。
12と18の最大公約数：素因数分解版
手順としては次のような流れになります。
1. 12を素因数分解すると12 = 22 × 31、18を素因数分解すると18 = 21 × 32となる。
2. まず素数2を見ると12の場合は2、18の場合は1が乗っているので1を選ぶ。
3. 次に素数3を見ると12の場合は1、18の場合は2が乗っているので1を選ぶ。
4. よって最大公約数は21 × 31 = 6となる。
それでは皆様もやってみましょう。
[ex1] 1071と1029の最大公約数はいくつでしょうか？
たいしたことない？ではこれは？
[ex2] 127608と116976の最大公約数はいくつでしょうか？
127608の素因数分解は大変です。
この例からわかるように、最大公約数を求めるために素因数分解を使うのは悪手です。電車で何時間もかけて行く道程を徒歩で行くようなものです。道が続いているならばいつかはたどり着きますが、やはり可能な限り効率的に行いたいものです。
ここで紀元前300年前に発見されたEuclidのアルゴリズムを紹介しましょう。一般的にはEuclidの互除法と呼ばれています。次の定理5が基礎になっています。
[Euclid] a, b(a > b)を自然数とする。またaをbで割った余りをrとする。このときa, bの最大公約数とb, rの最大公約数は等しい。
ちょっと難しいかも知れませんね！具体例を見てみましょう。
12と18の関係
18を12で割ると18 = 12 × 1 + 6となる。このとき12と6の最大公約数は6であり、18と12の最大公約数と一致する。
この例からわかるように、最大公約数を見つけるにはひたすら割り続ければよさそうということがわかります。この方法ならば先程の難問も解けそうな気がしますね！
127608と116976の最大公約数をEuclidの互除法で求める
1. 127608を116976で割った余りは127608 = 116976 × 1 + 10632より10632となります。
2. 116976を10632で割った余りは116976 = 10632 × 11 + 24より24となります。
3. 10632は24で割り切れるので余りは0となります。
4. 127608と116976の最大公約数は10632と24の最大公約数と一致します。つまり24です。
解けました！
以上の手順をまとめるとEuclidの互除法は次のような流れになります。
1. 入力をa, b (a≧b)とする。
2. もし bが0ならばaの値をa, bの最大公約数として出力する。
3. a ← b, b ← (aをbで割った余り)として.2に戻る。
ここで注目して欲しいことは、Euclidの互除法のアルゴリズムの記述には
1. 入力と出力がある（入力は2つの自然数、出力は最大公約数）
2. 手続きに曖昧さが無い（割り算）
3. 終了条件がある（手順2.に終了条件がある）
という特徴があります。この3つの要素がアルゴリズムの特徴です。
この特徴から、アルゴリズムとコンピュータの相性がとてもよいことがわかります。コンピュータは曖昧なことは苦手ですが、きっちりとした手続きは大得意です。暗号化の流れもアルゴリズムとしてきっちりとした手続きに書く事ができればコンピュータに任せる事ができます。
天は我々を見放した…のか？
最大公約数を見つけるのに素因数分解を用いるのは悪手であるといいました。本当なのでしょうか？ 実は、効率的な素因数分解のアルゴリズムは知られていません。以前、アメリカのRSA Security社が主催していた「RSA Challenge」というコンテストが存在しました。それは与えられた巨大な自然数を素因数分解するというもので、中には20万アメリカドルの懸賞金がかけられているものもありました。これが、20万ドルの賞金首の顔写真です。
25195908475657893494027183240048398571429282126204032027777137
83604366202070759555626401852588078440691829064124951508218929
85591491761845028084891200728449926873928072877767359714183472
70261896375014971824691165077613379859095700097330459748808428
40179742910064245869181719511874612151517265463228221686998754
91824224336372590851418654620435767984233871847744479207399342
36584823824281198163815010674810451660377306056201619676256133
84414360383390441495263443219011465754445417842402092461651572
33507787077498171257724679629263863563732899121548314381678998
85040445364023527381951378636564391212010397122822120720357
随分面長な顔写真ですが、それもそのはず桁数は617桁もあります 6。日本における数の単位で最大のものは無量大数ですが、1無量大数はたったの68桁しかありません。つまり、20万ドルの賞金首を呼ぶための日本語は存在せず、RSA-2048と呼ぶほかありません。この様なコンテストが存在した事実からも、如何に素因数分解という問題が難しいかというのが垣間見ることができます。
ここで重要となることはコンピュータにとって何が簡単な問題で何が難しい問題であるのかを理解することです。暗号に用いられるアルゴリズムは、鍵があれば簡単にコンピュータによって計算できて、鍵が無いと全く歯が立たないものを採用します。簡単なものを暗号のアルゴリズムとして採用してしまうといとも簡単に破られてしまいますし、 難しい事を理解しておかないと他人に安全性を説明する事ができません。
「暗号化されていますので安全です」の秘密は暗号化のためのアルゴリズムにあります。アルゴリズムがわかれば何故安全であるのかがわかります。
参考文献
- 楫元 『工科系のための初等整数論入門』 培風館 2000
1. 正しくは「Turingマシンによって計算できる問題を解く手順」ですが、説明するにはまず計算を数学的に定義する必要があります。I.J. ホップクロフト，J. ウルマン，R. モトワニ『オートマトン 言語理論 計算論』を参考にして下さい。↑
2. Euclid幾何学の原典として有名です。↑
3. ここで自然数は1から始まるものとします。↑
4. ここでは正数のみを考えます。↑
5. 定理とは簡単に言うと正しいことが客観的に示された事実のことです。↑
6. 617桁と聞くと中途半端な印象を受けますが、ビットというコンピュータで用いられる単位に直すと2048ビットとなります。2048は2の11乗なのでコンピュータにとってはキリの良い数字です。↑