暗号・符号理論と情報セキュリティ

コース情報

評価方法

詳細情報

スケジュール

1. ガイダンス，および暗号理論(１) 暗号理論の基礎 [講義の概要] 講義の前半を本講義全体のガイダンスに充て，講義で取り上げる内容を紹介するとともに，この講義を通じて受講者の皆さんに伝えたいことについてお話します。講義スケジュールや試験，成績の評価方法についても，このガイダンスで説明します。 講義の後半では，暗号理論の１回目として，暗号理論の基礎についてお話します。まず初めに暗号理論の枠組みや独特の用語などについて説明した後，現代暗号理論の研究テーマを概観します。また，歴史上初めて使用された暗号と言われる「シーザー暗号」をとりあげて，強固な暗号が満たすべき性質について検討します。 [テーマ] ・暗号理論の枠組みと重要な用語 ・現代暗号理論の研究分野 ・単一換字暗号 ・強固な暗号の条件
2. 暗号理論(２) 秘密鍵暗号 [講義の概要] 第２回目の講義では，現代暗号において最も長い実用と研究の歴史をもつ「秘密鍵暗号」について，その原理と実現方法を紹介します。特に，現代的な秘密鍵暗号として初めて実用に供されたDES(Data Encryption Standard)の実現方法を詳しく紹介します。また，理論上解読が不可能であるone-time padの原理を紹介し，解読が不可能であることの直観的な説明を行います。 [テーマ] ・秘密鍵暗号の原理 ・DES ・one-time pad
3. 暗号理論(３) 公開鍵暗号(１) [講義の概要] 適切に設計された秘密鍵暗号は，現代の超高速計算機をもってしても解読が不可能なほど頑健であるとされています。しかしながら，その運用には大小様々な欠点があり，それらの欠点を補う手法が提案されています。 暗号化鍵の一部を公開するにも関わらず機密性を損なわない画期的な暗号系として開発された「公開鍵暗号」は，このような秘密鍵暗号の欠点を補う有力な暗号化方式です。第３回目の講義では，公開鍵暗号の原理と，その具体的な実現方法の一つであるＲＳＡ暗号を紹介します。 [テーマ] ・秘密鍵暗号の欠点 ・公開鍵暗号の原理 ・ユークリッドの互除法 ・ＲＳＡ暗号による公開鍵暗号の実現
4. 暗号理論(４) 公開鍵暗号(２) [講義の概要] ＲＳＡ暗号の公開鍵・暗号鍵を生成するためには「巨大な素数」が必要です。しかしながら，大きな整数の素因数分解を効率的に行うアルゴリズムは知られていないため，素因数分解に頼らない素数判定法が必要となります。講義の前半では，確率的な素数判定法であるＲａｂｉｎ法を紹介します。 また，ＲＳＡ暗号を実際に用いるためには，様々な攻撃に対して安全であることが不可欠です。そこで，ＲＳＡ暗号に対する一般的な攻撃とそれへの耐性について説明します。さらに，数学的には非常に強固である公開鍵暗号の思わぬ弱点を明らかにし，これを利用した公開鍵暗号に対する効果的な攻撃手法を紹介します。 [テーマ] ・確率的素数判定法 ・離散対数問題 ・ＲＳＡ暗号に対する攻撃
5. 暗号理論(５) 改ざんと成りすましの防止技術 [講義の概要] 情報セキュリティにおいては，情報の機密性を守ることよりも，その情報がオリジナルと同一か否か，すなわち，改ざんが加えられていないかどうかの方が重要な問題となるケースも多々あります。第５回目の講義では，そのような用途に適したセキュリティ技術について紹介します。また，それらの方式が潜在的に持つ弱点を明らかにし，その弱点を突いた攻撃についても紹介します。 [テーマ] ・情報の機密性と正真性 ・一方向性ハッシュ関数 ・誕生日のパラドックス : 一方向性ハッシュ関数に対する攻撃 ・一方向性ハッシュ関数の弱点とメッセージ認証符号 ・メッセージ認証符号に対する攻撃
6. 暗号理論(６) ディジタル署名 [講義の概要] 紙の書類に捺印や署名(サイン)をすることによってその書類の正真性を証明するように，電子ファイルに「電子的な署名」を行うことによってその書類の正真性を証明する方式(ディジタル署名)が知られています。第５回目の講義では，ディジタル署名の原理とその実現方法を紹介します。 また，ディジタル署名を実現する上で問題となる点を明らかにし，その問題が，「物事を信頼する」という行為に対する我々の認識を問う，極めて深刻な問題をはらむことを指摘します。 [テーマ] ・メッセージ認証符号の弱点 ・ディジタル証明方式の原理とその実現 ・ディジタル証明方式の応用(ブラインド署名・電子現金) ・ディジタル署名方式の問題点と証明書
7. 暗号理論(７)ブロックチェーンと暗号通貨 [講義の概要] 秘密鍵暗号や公開鍵暗号，ハッシュ関数，ディジタル署名といった情報セキュリティ技術は，適切に組み合わせて使用することによって様々なサービスを生み出すことができます。前半の講義の最終回では，そのような一例としてブロックチェーン技術を取り上げ，暗号通貨を実現する仕組みについて紹介します。 また，情報セキュリティ技術を組み合わせることにより新たに生じる問題点にも焦点を当て，暗号通貨の将来性に関する最近の議論を紹介します。 [テーマ] ・ブロックチェーンの仕組み ・暗号通貨におけるブロックチェーンの利用 ・ブロックチェーンの問題点
8. 中間試験 第７回目までの講義内容(暗号理論)に関する試験を実施します。
9. 符号理論(１) エラーまみれの情報通信システム [講義の概要] 後半の第1回目の講義では，「符号理論」という研究分野の目的について説明します。 まず初めに，現代の超高速通信システムや超高密度記録システムでは，たとえ最先端の伝送方式や高品質デバイスを使用しても，システム上でランダムに発生するエラーの影響を無視できないことを説明します。具体的には，情報通信を数学的にとらえるためのごく簡単なモデルを導入し，エラーの影響が如何に大きなものかを数値的に評価します。この事実を通して，通信システム上のエラーを補償する技術である「誤り訂正符号」 の重要性を説明します。 講義の後半では，簡単な誤り訂正符号を用いて，「情報を符号化することによって，情報の伝送に際して生じた誤りが訂正できるのはなぜか」という問いに対する感覚的な答えを与えます。情報圧縮とは異なる符号化によって情報通信の信頼性が向上できることを理解することが目標です。 [テーマ] ・身近な誤り訂正技術 ・情報通信のモデル ・代表的な通信路 ・簡単な誤り訂正符号の例
10. 符号理論(２) 誤り訂正の原理 [講義の概要] 前回の講義では誤り訂正の仕組みを直観的に説明しました。今回は，この仕組みをより正確に記述し，数学的な枠組みの中で誤り訂正の原理を理解することを目標にします。 まず初めに，情報を反復送信することによって信頼性が向上することを確認します。ここで - 情報の反復 = 情報へ「冗長」を付加する写像 - エラーの生起 = 送信系列へのエラーの付加 とみなすために，誤り訂正符号を記述する「数の体系」を導入します。さらに，この体系に対して距離の概念(ハミング距離)を導入し，誤り訂正が可能となるための条件を数学的に明らかにします。 [テーマ] ・繰り返し符号 ・2元体 ・誤りベクトルによるエラーの表現 ・ハミング距離と誤り訂正の原理
11. 符号理論(３) 線形符号 [講義の概要] 情報通信機器に搭載された「メモリ」は，様々な計算処理に不可欠なリソースです。しかしながら，機器の消費電力低減や製造コスト削減の観点から，メモリ容量は一般に厳しく制限されます。そこで，より少ないメモリでも誤り訂正の仕組みが動作するよう，「線形代数」の力を借りることを考えます。これにより，誤り訂正符号の ‐符号化(=様々なダメージから情報を保護するために，「冗長」という名の“防具”を情報に着せる操作) - 復号(=傷ついた“防具”の中から無傷の情報を取り出す操作) が高速に行えるようになります。このような誤り訂正符号を「線形符号」といいます。 線形符号は誤り訂正符号の中で最も基本的な符号であり，現代符号理論はこの「線形符号」に対する理論といっても過言ではありません。今回の講義の前半では，線形符号を用いた誤り訂正の枠組みに関する一般的な議論を展開します。 また，「線形符号を用いて誤りを訂正する問題」が，「解が一意に定まらない線形連立方程式に対して『ハミング重みが最も小さい解』を探索する問題」に帰着されることを示します。さらに，この「解が一意に定まらない線形連立方程式」を具体的な線形符号について定式化し，さらに「ハミング重みが最も小さい解」を実際に求めることを体験します。 例として取り上げるのは，「ハミング符号」と呼ばれる最も基本的な線形符号の一つです。誤り訂正のための様々な操作が非常に単純であるため，線形符号の復号の一般論が直観的に理解できます。 [テーマ] ・線形符号の定義 ・線形符号の符号化と復号 ・ハミング符号の定義 ・ハミング符号のシンドローム復号
12. 符号理論(４) 線形符号の限界 [講義の概要] 情報通信の信頼性を向上させるためには誤り訂正能力の高い符号を用いる必要があります。それでは，「誤り訂正能力」とは符号のどのような性質によって決まるのでしょうか?本講義では，符号の誤り訂正能力を決定する主要なパラメータである「符号長」，「情報長」，「最小ハミング距離」について，それらの大小と誤り訂正能力との関係について説明します。 また，これらのパラメータの間にはトレードオフの関係があり，あるパラメータをより良くすると他のパラメータが必然的に劣化してしまうことを明らかにします。さらに，このトレードオフの関係を定式化した３つの限界式を紹介します。 [テーマ] ・最小ハミング距離と誤り訂正の限界 ・線形符号のパラメータ ・パラメータの限界式
13. 符号理論(５) ＲＳ符号 [講義の概要] 一般的な通信路では受信語に複数の誤りが含まれることがありますが，このような誤りは単一の誤りのみ訂正可能なハミング符号では訂正できません。今回の講義では，2個以上の誤りを訂正できる符号として RS 符号を取り上げ，その定義と誤り訂正アルゴリズムについて講義します。 RS符号は衛星通信やCDなどに用いられており，現代の情報通信システムの信頼性を保証する代表的な誤り訂正符号の一つです。この誤り訂正符号の動作原理を知ることが今回の講義の目標です。 [テーマ] ・ＲＳ符号の定義 ・ＲＳ符号の検査行列と最小ハミング距離 ・ＲＳ符号の復号アルゴリズム(Peterson法)
14. 符号理論(６) ネットワークにおける誤り検出 [講義の概要] 誤り訂正符号の実用化においては，符号化や復号が単純な装置で実現できることが重要です。今回の講義では，シフトレジスタと組合せ回路という極めて単純な回路で符号化・誤り検出が実現できる「巡回符号」について，その定義と誤り検出の原理について紹介します。 巡回符号は線形符号の１クラスであり，インターネット上のパケット通信における誤りの検出や，鉄道の制御信号におけるフェイルセーフなどにも用いられる，実生活に欠かせない符号の一つです。講義ではこれらの応用技術についても紹介します。 [テーマ] ・インターネットにおける誤り検出方式 ・巡回符号の定義 ・生成多項式と検査多項式 ・巡回符号の符号化と誤り検出 ・巡回符号の符号化回路と誤り検出回路