セキュリティ・キャンプ全国大会2019 暗号化通信ゼミ 応募課題
はじめに
実は，私はセキュリティ・キャンプ全国大会2019 暗号化通信ゼミに参加してまして， この記事ではその応募課題の回答を晒します．来年度以降参加される方の参考になればと思っています．なお，課題の問題文は全てこちらから引用しています． www.ipa.go.jp
https://www.ipa.go.jp/files/000073171.txt
[問1]
問題文
暗号化通信は戦争において非常に大きな役割を果たします. 実際, 第二次世界大戦中にはEnigmaのような様々な暗号が開発されては解読されていました. そこで, このEnigma暗号が解読された経緯を可能な限り詳細に書き出してみてください. また, なぜこの暗号は解読されるに至ったのかを考察してください.
回答
利便上、先にEnigma暗号とはどのようなものなのか説明した後、解読された経緯を説明する。 Enigma暗号とは、Enigmaという機械を用いた暗号の事である。Enigmaとは、元は1918年にドイツの発明家アルトゥール・シェルビウスが開発した暗号機である。 Enigmaは手前から順にプラグボード、キーボード、ランプボード、ローターが付いている。 暗号化を行うにはまず、暗号化の鍵を設定する。鍵は全部で４つある。プラグボードの配置、いくつかあるうちのローターの選び方、ローターのセットする順序、ローターの目盛り初期位置である。これらを予め定められたとおりにセットする。 次に、平文をキーボードに打ち込む。平文をキーボードで１文字入力するたびにランプボード一つが光り、それに対応する文字が暗号文となる。 ここで平文の全探索はどれくらい大変なのか考えてみる。 まず、プラグボードは３組の場合、プラグボードの配置の状態は3.5106通り存在する。 また、ローターは３つあり、３つ選択だとすると、１つあたり26通りの初期位置があり、３つだと263=17576通り、さらに３つのローターの並び順は６通りあるので、これら全てかけ算すると、一つの平文から3.5(106)175766≒36*1010通りの暗号文が出来上がることがわかる。
ドイツがエニグマを正式に軍事利用したのは1925年。その後、ドイツは主要な通信だけでなく、全ての通信をEnigmaで暗号化するようになった。そこで５年後、アメリカ・フランスなどが解読に試みるも全く太刀打ちができなかった。 1931年、フランスのスパイ、シュミット（肩書はドイツの暗号局職員）がEnigmaの鍵と操作書を盗み出した。 この情報をもとに1932年、フランスはEnigmaを復元し、解析した。主に解読作業を行っていたのはポーランド暗号局の数学者マリアン・レイェフスキである。彼は暗号解読機「ボンバ」を６台製作し、Enigmaを解読した。
Enigmaの解読の経緯としては、ここまででも問題はないのだが、Enigmaはこの後も何度か解読されるのでそちらについても記述させて頂こうと思う。
その後すぐさまドイツはローター数とプラグ数を２つ追加し、暗号を強固のものにした。これにより、ポーランド暗号局は現状のボンバでは対策のできない形となってしまった。これにより、ポーランド暗号局は復讐のようにイギリス・フランスの情報担当官にローターが３枚のEnigmaのレプリカや、ボンバの設計図など解読の成果を公開した。
1936年には、ドイツはローターの配列を８時間ごとに変更するようにし、プラグボードの数は８組に増加した。 1938年9月、アラン・チューリングはイギリスの暗号解読組織である政府暗号学校で働き始める。政府暗号学校ではエニグマの解読の為に「Ultra」というグループを立ち上げ、以下をメンバにした(他にもいた可能性がある)。「アラン・チューリング」「ゴードン・ウェルチマン」「スチュアート＝ミルナー・バリー」「ジョン・ケアンクロス」「コーネル・ヒュー・オドネル・アレグザンダー」。最初、Ultraは換字式暗号のエニグマに対し、頻度分析による解読を試みた。しかし、ローターの配列が８時間で変更されるうえ、Enigmaは同じ文字を入力しても、文字を入力するたびに暗号文字が変わってしまう為、頻度分析にほとんど意味はなかった。
そこで1939年秋、チューリングが主体となり、「bombe」という暗号解読機の製作を開始した。（※ポーランドが作った暗号解読機はbomba kryptologicznaで、チューリングが作った暗号解読機はbombaにちなんでbombeである。日本語での発音は似ているためボンバ・ボンベと区別し、さらに文章として見間違えないようにするため、本設問ではボンバとbombeで区別する。） bombeはエニグマの暗号文で使われたと考えられる正しい設定（ローターの順序、ローターの設定、プラグボードの設定など）を全探索し、その設定を決定した時の状態で暗号文を復号し、その復号文（平文）が、ドイツ語で構成されているかチェックする。 上記方法は文字にすると、少しわかりにくいので、実際に簡易プログラムを書いた。あくまでイメージであり、設定の状態が決定された状態でドイツ語か判定するプログラムなのだが、上記文章は分からずC++プログラムが読める場合はこちらの方が分かりやすいだろう。 （※こちらはURLからのみアクセス可能となっております。また、本記事は予告なく削除する場合がございます。） https://qiita.com/xryuseix/private/a640423a8e66820bcaa5
さて、このプログラムの計算量を計算する。まず、初期設定が何通りあるか考える プラグボードの組数:26C8≒1022 ローターの選び方:5C3＝10 ローターの並べ方:3!＝6 ローターの初期位置:263=17576 ドイツ語判定（判定するドイツ語の単語数をx,暗号文の単語数をyとする）:xy よって合計でxy*1028である。これは今のコンピュータでも現実的な時間で終わらない。
さて、ここまでがEnigmaが登場してからEnigmaとチューリングが出会うまでの経緯とその背景なのだが、一見解読は不可能に思えるEnigma暗号がなぜ解読されたのか。 私が思う要因は主に３つ存在する。
１つ目：チューリングの活躍 当時はまだコンピュータというものが一部の大学でしか開発されていなかったこともあり、Ultraのチューリング以外のメンバだけでなく、イギリスのEnigma暗号解読に携わった全員が「Enigmaを数学的・統計学的に解くべきだ」と主張していた。 しかし、チューリングは唯一「Enigmaは機械である。機械に人間が勝てるはずもなく、機械でのみ勝負が出来る」という思想を持っていたそうだ。幸い、チューリングは数学者だが、物理学にも精通している。さらに、チューリングは政府暗号学校へ勤務する二年前に1936年5月28日に論文、「On Computable Numbers, with an Application to the Entscheidungsproblem」を提出している。これはチューリングマシンというコンピュータでアルゴリズムを表現する方法について書かれている（※それだけではない）。 これらの事柄から言えることは、チューリングは当時のイギリスでは「コンピュータを扱うスペシャリスト」だったという訳だ。 また、チューリングはbombeの製作費用で10万ポンドを使用したそうだ（現在の日本円で1400万円なので当時の戦時下での金額に換算するとそれ以上になる）。当時イギリスは軍事費用に国家予算の４倍の金額を使っていたため、当然そんな大金は出ない。しかし、チューリングの論文が受け入れられたため、予算が下りたそうだ。 また、過去にはバベッジやノイマンのような頭の中でコンピュータの設計を行って開発する天才がいた。実際、チューリングも頭の中では設計図がある程度出来ていたが、紙で書き起こした。このおかげで、Ultraの他のメンバは「今何が完了している」「あと何を作ればいいのか」など進捗状況が明確に確認でき、長期間のプロジェクトでのモチベーション維持につながっただろう。
２つ目：ドイツの失態 当時のドイツの午前６時の暗号文の冒頭には、必ず「天気」、「ハイル ヒトラー（ドイツ語: Heil Hitler、ヒトラー万歳）」が含まれていた（これはチューリングの発見かどうかに関しての文献は見つからなかったが、映画「イミテーション・ゲーム」ではチューリングの発見ということになっている。）。ここから、前述の「復号文（平文）が、ドイツ語で構成されているかチェック」で使用されるドイツ語の候補が「天気いくつか」「ハイル」「ヒトラー」のみとなる。この方法は俗にいう枝刈り法で、このおかげで全探索が出来るようになった。
３つ目：交信解析による暗号文データベースの作成 当時、イギリス政府で働く女性は交信解析を行っていた。これは、可能な限り全ての無線交信を傍受し、記録する仕事だ。傍受された内容は暗号文だが、この仕事のおかげで前述２つ目の解読要因にたどり着くことができた。また、解読後は戦場の状態が把握することが出来、このおかげで戦争が２年早く終着したとも言われている。
以上の理由から、Enigamaは解読されるに至ったと私は判断する。
解説
ポエムでした．これは非常に長い課題なので，まず構成を考えましょう．私の場合は
- Enigma暗号の説明(時系列順にすることでさらに整理)
- 解読された原因1
- 解読された原因2
- 解読された原因3
はい．で，まずEnigma暗号の説明(時系列順にすることでさらに整理)何ですが，これは結構適当だったりします．なぜならエニグマ(こっからはこう呼ぶ)はイギリスの完全い軍事機密で，公開されたのが199*年くらいだったような〜〜って感じだからです．もちろん，当時の文献の多くは焼滅してしまい，今では憶測の記事ばかりが残っています．その中でカンペ時に正しい回答を出すことはできません．そこで，正確性はおいておいて，Overviewだけはちゃんと説明するようにしました．今だから言えるんですが，解読された原因はこれだけじゃない（ちょっと間違ってる）んですよね．まあそれでも受かったから良かったんですけど．
問2
問題文
暗号化通信プロトコルのさきがけとして有名なものの一つにDiffie-Hellman鍵交換アルゴリズムがあります. このプロトコルは上述のEnigma暗号やその他の従来の暗号化通信に用いられた技術とは決定的に異なる性質を持っています. それは現在公開鍵暗号と呼ばれる技術であり, 今日の暗号化通信技術には欠かせない技術になっています. (1) このDiffie-Hellman鍵交換アルゴリズムとはどのようなアルゴリズムかを解説してください. 余裕があれば, その攻撃についても考察してください.
回答
まず、Diffie-Hellman鍵交換アルゴリズムを説明する以前に、暗号化方式について説明させていただく。 暗号化方式には大きく二つに分類される。一つは共通鍵暗号方式である。共通鍵暗号方式は情報の送信者と受信者で同じ鍵を利用する暗号化方式である。例えば、シーザー暗号の場合は、平文をn文字ずらしたものが暗号文になるのだが、このnが鍵となる。 共通鍵暗号方式は暗号化と復号に同じ鍵が必要である。そのため、最初はどうやって鍵を安全に受け渡すのかという問題が発生する。他にも鍵の管理に問題が発生する。鍵は送信者と受信者のペアの数必要であり、一般にn人の間では鍵はn*(n-1)/2個の鍵を生成する必要がある。 この現実を踏まえ、1976年ウィットフィールド・デフィーとマーティン・ヘルマンが公開鍵暗号に関する世界最初の論文を発表した。 公開鍵暗号方式とは、共通鍵暗号方式とは違い、暗号化に使用する鍵と復号に使用する鍵が異なる暗号化方式である。 詳しいアルゴリズムは後ほど述べるので、まずは大まかな理論について述べさせていただく。 １、送信者・受信者はそれぞれ公開鍵と秘密鍵を用意する。これは個人が持つ鍵であり、通信する相手によって変えるものではない。また、送信者・受信者ともに公開鍵をインターネット上に公開する。 ２、送信者は受信者の公開鍵を使って暗号化し、送信する。 ３、受信者は受信者の秘密鍵を使って復号する。
ここで、公開鍵によって暗号化された暗号文は公開鍵では復号できない。なぜならば、公開鍵で暗号化する際に、離散対数問題など一方通行関数を利用しているためだ。詳細に関してはこちらも後ほど説明する。
Diffie-Hellman鍵交換アルゴリズムとは、公開鍵暗号方式の理論を利用して、安全に鍵を交換するアルゴリズムである。具体的には、共通鍵暗号方式を利用する際に、その鍵の配送（共有）利用されることが多い。Diffie-Hellman鍵交換アルゴリズムは離散対数問題を利用し安全に鍵を交換している。 一旦、離散対数問題に関して説明する。 xy=z mod pという式があった場合、x,y,pが与えられた時にzを求めるのは容易である。 例えば、x=2,y=5,p=7の場合、25=4 mod 7である。しかし、x,z,pが与えられた時にyを求めるのはどうだろうか。これは実際に手を動かして試してみて頂きたいのだが、とても難しい。 実際、数学的にも「pが大きな素数のときはスーパーコンピュータを用いても非常に難しい」ということは証明されている（本課題では、証明に関しては省略させていただく）。 このような関数の非対称性から特定の値を導き出すことが難しいということを離散対数問題という。 では、これらの話を踏まえて、本題のDiffie-Hellman鍵交換アルゴリズムの仕組みに入る。 １、送信者は生成元Gと大きな素数Pを求める。生成元とは、GA mod Pを計算したとき、Aを変化させると周期がPとなるGである。具体的には、P＝13、G=11の時、Aを1~12と変化させるとGA mod Pは{11,4,5,3,7,12,2,9,8,10,6,1}となり、全て異なる値なので11は生成元となりうる。 ２、送信者はGとPを受信者へ送る。 ３、送信者は乱数A(1<=A<=P-2)、受信者は乱数B(1<=B<=P-2)を求める。 ４、送信者はGAmod P、受信者はGB mod Pをお互い交換する。 ５、送信者は(GB mod P)Aを、受信者は(GA mod P)Bを計算する ６、(GB mod P)A =(GA mod P)B=GBA mod Pなので、この値を共通鍵とする。
ここで、盗聴者が見ることが出来る内容はP,G, GA mod P, GB mod Pのみである。離散対数問題の困難性より、これらの内容からA,Bを見るけることは困難な為、鍵を盗聴することはできない。仮に、P,G, GA mod P, GB mod Pのいずれかを改ざんした場合、送信者が暗号文を受信者に送った時点で復号出来ないことが分かるので、再度(1)からやり直す。なお、改ざんしたとしてもA,Bが定まることはない。
さて、ここで一つ問題がある。それは「そもそも受信者は本物なのか」ということである。だれかが受信者となりすますことによって、送信者と盗聴者の間の共通鍵が生成され、内容を傍受されてしまう可能性がある。 また、離散対数問題に関しても問題がある。「鍵を見つけるのは困難」と前述したが、それはスーパーコンピュータの話であり、2011年に発表された「D-Wave」をはじめとする量子コンピュータでは簡単に見つけることが可能だと言われている。
解説
まず．「余裕があれば」の内容はちゃんと書きましょう．こっちは１ヶ月くらい調べる時間があるのですから，ちゃんと調べれば余裕はあるはずです． 今回も長そうなので方針を先に立てました．
- 暗号化方式の説明
- DH鍵交換の背景
- 離散対数問題の話
- 実際にDH鍵交換で暗号化を行う
- DH鍵交換の攻撃
1~4まではググれば普通に出てきます．一応文献は３つ以上読んでください．この問題の場合は違ったことを言うと致命的です．多分．いや，僕も間違っているかもしれませんが． 5についてなんですが，
さて、ここで一つ問題がある。それは「そもそも受信者は本物なのか」ということである。だれかが受信者となりすますことによって、送信者と盗聴者の間の共通鍵が生成され、内容を傍受されてしまう可能性がある。
これは有名な話だと思うのですが，「攻撃」と定義していいのかかなり不安でした．「攻撃」というば「ブルゥゥゥゥトゥフォオオオオオオオオスッ」(※ブルートフォース攻撃)のような直接解読できるようなものを想像するじゃないですか．そこで，一度立命館大学の暗号理論を専門とされている教授に質問しました．「こうゆう問題でこうこう答えようと思っているのですが，これは答えになってますか」って．大丈夫って言われました．やったね！ で，提出したわけってばよ．このように詳しい人に質問するのもありです．
問2
問題文
(2) 問1で触れたEnigma暗号の解読は, Diffie-Hellman鍵交換アルゴリズムを用いることで阻止できますか. 考察し, 理由を書いてみてください.
回答
Enigma暗号の解読は, Diffie-Hellman鍵交換アルゴリズムを用いることで阻止できない。なぜなら、Diffie-Hellman鍵交換アルゴリズムは共通鍵生成アルゴリズムであり、「盗聴の対策」を可能にするアルゴリズムなのである。Enigmaは全探索の枝刈りで解読されたので、Diffie-Hellman鍵交換アルゴリズムとの関係はない。
解説
いや，DHとEnigma関係ないやろwwwって２日間くらい考えました．考えた結果，「ありません，それはそうです」みたいなことを書きました．こうゆうこともあります．
[問3]
問題文
あなたが今回このゼミで開発したいと思う暗号化通信プロトコルについて, 詳細を述べてください. [問3 注意点] * 本当に, どうしても, 応募期限ギリギリまで考えてもわからないところがあれば, そこはわからないと書いてよいです. わからないことは恥でもなにもありません. ゼミ中に解決していきましょう. * 論文やRFC等, 参考にしたものがあればそれは参考文献として書いてください.
回答
私は今回のゼミの為に新たな暗号化アルゴリズムを考えたので、このアルゴリズムに通信プロトコルを付け加えることによって暗号化通信プロトコルを実現したいと思う。 以下、暗号化アルゴリズムの紹介をする。なお、図は全てこちら https://qiita.com/xryuseix/private/a640423a8e66820bcaa5#3cubing暗号の図 （↑そのうち消えているかもしれません．提出当時はちゃんと存在してました） に記載されている。 また、仕組みはこちらから動画でも確認する事ができる。こちらの方が視覚的に理解しやすいだろう。 （※この動画はHatenaBrogの記事では公開しません）
＊名称：cubing暗号 ＊暗号方式：共通鍵暗号方式・転置鍵暗号方式 ＊転置鍵：”１”,”２”,”３”の三種類の文字から成る文字列 ＊概要 まず、平文を図１の二次元配列に格納する。ここでは平文を 「kokaikagiangouhousikihaRSAangougayumeidesu(公開鍵暗号方式は RSA 暗号が有名です。)」とする。余ったセルには＊印を格納する。また、図１の６番のセルに関しては図２参照。 ここで、転置鍵を利用してルービックキューブのように文字列操作をする。転置鍵は”１”,”２”,”３”の三種類の文字から成る文字列であればいくら長くても構わない。 転置鍵の 3n+1(n=0,1,2…)文字目は方向、3n+2 文字目は列、3n 文字目は回数を表す。 方向は上記図３のように縦方向右…１、横方向…２、回転方向…３とする。 列は図４の通りである。 このようなルールで文字を転置するのだが、文章で文字が変わるのか説明するのが困難な為、図３で分からなければ上記動画を見ていただきたい。 このようにして、文字を転置した後、図５の数字の順で文字列に復元する。すると、暗号文が出来上がる。
最後に 上記URLから参照できるサイトはコメント可能となっている。Youtubeに関しては承認済みコメントのみ表示する形となっている。もし、本課題を書いている私とYoutube、Qiitaのアカウントが同一人物でない場合があると判断された場合、そちらのコメントにて私しか知りえない情報（例えば本課題の問３の最初の１行は何が書かれているか、など）を質問して頂きたい。
解説
高校生の時考えた「ぼくの かんがえた さいきょうの あんごう」を提示してみました．正直，講師の方が強強の暗号CTFプレイヤーとわかっていたので，「瞬殺，やるだけ〜」と思われても仕方ないと思っていたのですが，意外にも高評価をいただきました．どうやら，採用基準は「問１，問２がきちんと書けてる」「問３がすごい！」だったそうです．
付録
作問者Shiho Midorikawa(@eliptic_shiho)さんのDMから引用した，講評です．Shiho Midorikawaさんには掲載許可をいただきました．
問１
実は, 僕はあんまりその辺りの厳密な記述は気にせずに評価しています. というのも, 戦争により資料が散逸し, その後まとめられた資料でもバラバラな値になることが多いこと, そもそも未だに公開されていない情報もある可能性がある(*)ことという2点から, その正確さよりもどれだけ読んだものを自分の言葉で再構成し, まとめられているかという点, 一次資料にどれぐらい近い資料なのかというようなその辺りを見ていました.
例えば, RSA暗号がRivestらにより開発される前に既に発見されていたEllis / CocksによるRSA暗号とほぼ同じ内容を記述した発明に関しては, GCHQの機密事項とされ, 1997年まで表には出ていませんでした
しかももう1段トラップがあって, Enigmaは「戦時中に知られている解読法では解読できないとしても, その後の研究によりうまく枝刈りしたり計算機パワーで殴ると現代の計算量的には全く安全ではない暗号であることがわかっている暗号」なんですよね. なので, 戦時中の情報だけ見てこれは解読不可能!という結論を出す人がいるのも想定範囲で, 正直そこまで出来ていれば問題ないと判断していました.
戦時中にわかっていたかどうかを無視した文章であれば85点, というところでしょうか. 「戦時中の仮定ならばこれはかなり困難になると思われるが, 現代的においては安全ではない. 」までがあれば100点で良いと思います
問２
ということでDiffie-HellmanにおいてEnigmaは防げるか, という問題について想定回答っぽいものを. これは解ける解けないで言えば解けるが正解で, 安全ではないです. DHが担保するのは盗聴に対して安全な鍵交換だけで, 暗号本体が脆弱(史実ではKnown Plaintext Attackですね)な場合にはこれを使用してもさほどの安全性向上効果を与えません. また, Man-in-the-MiddleのようなDHそのものの問題点についても注意が必要で, その意味では相手の信頼性を担保できない戦時下のような状況ではDHは無力だ, という感じですね
DHとEnigmaは意図的に無関係なものを合わせています. 先程僕が書いたとおり「脆弱な共通鍵暗号」と「安全な鍵交換を実現するアルゴリズム」の2つを組み合わせるサンプルとしてあえて一般に知られていない組み合わせを選びました. なのでその意味では地味にむずかしめの設問だったと言えますね
最後に
雑でごめんなさい．本記事は論文が終わらないので息抜きで書いてました．後，僕の課題の回答はいくつか間違っている箇所があるので，「引用」や「参考文献」として本記事の回答は使わないでください．あくまで雰囲気の参考です． また，何かあればいろんな手段でご連絡いただけると幸いです．課題をやってあげるわけにはいきませんが，セキュキャンに関する質問などをお気軽にどうぞ．
