数学科23年『数理逍遥3』並びに情報科学科34年『暗号と符号』のページ
【プロローグ】
昔の数学科には応用数学の講座が有ったのですが,情報科学科の設立時に
割譲されました.そのとき小山敏子先生と竹尾富貴子先生が情報科学科に
移籍され,情報科学科における数学教育の礎を築かれました.
僕は小山先生が定年で去られた後にやってきました.専門は超函数と
偏微分方程式でしたが,小山先生がおやりになっていた符号理論の伝統有る
講義を続けるため,勉強を始めました.途中で暗号のお話も取り入れ,
そのうち岡本龍明先生と三浦晋示先生というすばらしい専門家に親しく学ぶ
機会も得て,次第に充実した講義ができるようになり,教科書の執筆も順調に
進むところまで来ました.ところが,このところ肝心の聴衆が減り始め,講義が
終了するころには1人残るかどうかという有り様になってしまいました.
そこで,数学科の先生にお願いして,数学科から聴衆を集めるため,
数理逍遥のコマを使わせて頂くことにしました.
僕が属するポストの上述した由来を考えれば,僕が数学科向けに
応用数学の手解きを講義するのはごく自然なことだと思いますので,
よろしくおつき合いください.(*^^*)
【講義内容】
今年は,暗号と誤り訂正符号を,数学科の学生に馴染みやすいよう,数学的背景
に力点を置いて解説します.数学科の学生の皆さんの多くは,就職したら
数学を応用する立場になるでしょうから,世の中で数学がどのように使われて
いるのかを知ることは,将来への展望を持つ助けとなるでしょう.
講義では,実例を交えながら,分かりやすい解説を心がけます.
暗号も誤り訂正符号も,実用上はコンピュータと深く結び付いており,
コンピュータと純粋数学の違いを理解することも,また,応用数学への
重要な一歩です.この講義を始めた頃は,数学科の先生にしかられない
よう,コンピュータの解説は,理論の理解に必要な最小限に止め,
コンピュータが面白いよという宣伝はしないで,興味の有る人にだけ,
情報科学科の1年生に指導している,Cygwin (買ったコンピュータの
有効利用法) の講習会に遠慮がちにお誘いしていただけでしたが,
時代も変わってきて,今年は応用数学の講義補助として,理数応援プロジェク
トから TA を二人つけて頂けることになったので,大々的にコンピュータ
の宣伝をし,できれば全員に RSA 暗号のプログラムを実践してもらう
ところまで行きたいと思っています.
【成績評価】
この講義の成績は出席とレポートで付けます.
出席は, 毎回出席替わりに講義の感想を書いてもらいます.
【レポート】
レポートは,講義中にお話ししたレポート問題 (そのほとんどは
プレゼン資料に書かれています) のいくつかを解くか,自分でこの講義に
関連して考えたことをまとめて書いてください.
(ただし情報科学科の学生は, なるべく多くのレポート問題を解いて下さい.)
レポートは, 数学科の学生には, 数学科の先生に教わった基準で,
『熱意が感じられるレポートにAを付ける』方針で採点します.
情報科学科の学生には, 通常の方針で, 特にプログラミングをたくさんやって
もらいます.
基本的にレポートは期末 (8月末) までに出してもらえばよい (夏休みを
使ってしっかりやってもらいたい) ということですが,学期途中でも
受け付けます.メールでも紙媒体でも結構ですが,
メールの場合は Subject 欄にエンコードしない半角ローマ字で
Shouyou Report と記してください.
レポートの採点を終えました.ビジュネール暗号を解いた人は2人で,例年並
みでしたが,換字暗号は何と16人が解きました.ほぼ全員が英文区切りで
全く同じ間違いをしていたので,独立性に少々怪しいところがありますが,
まあ史上初の快挙でしょうか.(^^;
これで本講義は完全に修了ですが,21世紀に生きる君たちは,
これからも暗号の動向に注目していてください.
【実際の講義概要と予定】
講義の進行とともにここに書き込んで行きます.
- 4月13日(火):第1回 文字コードの話
暗号や誤り訂正符号を計算機で処理するには,それらの対象となる
データが計算機の中でどのように扱われるかを少しは知っておかないと
面白くないでしょう.第1回はその基礎としてコードの解説をします.
angoup1.pdf
第1回講義のプレゼンの pdf ファイル
以下は情報科学科の『暗号と符号』向けの定番レポートの資料ですが,
数学科の学生にも興味の有る人には解き方を指導します.
report1.txt レポート問題
decode64.c
藤井啓文氏作の base64 デコードプログラム.
encode64.c
上記をもじった base64 エンコードプログラム.
faq1.txt 本日の出席メー
ルに書かれた質問への解答集です.質問した人には個別にお返事しましたが,
みなさんにも参考になると思い,ここにまとめておきます.
- 4月20日(火):第2回 古典暗号入門
いわゆる暗号について,面白いお話を集めて紹介しました.
angoup2.pdf
第2回講義のプレゼンの pdf ファイル
report2.txt
暗号解読問題のファイル (プレゼン資料に含まれるものと同じですが,
テキスト形式なので,
コンピュータ処理するときの入力データとしては, こちらが便利です.
- 4月25日(日):コンピュータの勉強会
11:00 - 16:00 に金子研 (理学部3号館3階307室) にて行いました.
この際,report1.tex を Internet Explorer で表示してから保存すると,
base64 エンコードされたテキストの各行の末尾に空白が一つ添加されてしま
い,decode64.c ではデコードに失敗することが判明しました.
情報科学科の学生は5階の計算機室の ~kanenko/Angou の下からこのファイル
を scp で取り込めば,このような不都合はありませんが,数学科の人は
ファイルを生で取り込むのが難しいでしょうから,取り敢えず空白を無視する
ように書き直した
decode64new.cを用意しましたので,
これを使ってデコードしてください.
- 4月27日(火):第3回 現代の対称鍵暗号
バーナム暗号と DES の解説をし, 暗号の攻撃法や安全性の種類について
お話ししました.
angoup3.pdf第3回講義のプレゼンの pdf ファイ
ル
- 5月11日(火):第4回 公開鍵暗号入門
公開鍵暗号の仕組みについてお話しし, 因数分解の困難さに依拠した
RSA 暗号と, 離散対数問題の困難さに依拠した Diffie-Helman の鍵配送方式
について解説しました.
angoup4.pdf
第4回講義のプレゼンの pdf ファイル
- 5月18日(火):第5回 擬素数の作り方
RSA 暗号の実装で使われる種々の計算アルゴリズム,
高速冪乗計算のためのバイナリ法,拡張ユークリッド互除法,並びに
巨大素数を作るモンテカルロアルゴリズムMiller-Rabin法の解説をしました.
モンテカルロの写真も紹介しました.
Miller-Rabin法の誤り確率の評価はプレゼンで8枚です.講義では
解説を省略しましたが,暗号を本格的にやろうという人は,良く使われる
論法が出てきますので,自分で読んでみてください.難しい数学は
使われていません.疑似乱数の解説も駆け足でしたが,興味のある人は
プレゼンを読んでください.
angoup5.pdf
第5回講義のプレゼンの pdf ファイル
- 5月25日(火):休講 (日本気象学会に行ってきます)
- 6月1日(火):第6回 認証と電子署名
公開鍵暗号の基本的な応用法である認証と電子署名のお話をしました.
やり残していた ElGamal 暗号の紹介もしました.時間が無くなったので
暗号強化手段 OAEP と SSL のお話は取りやめ,前回飛ばした
中国人剰余定理の解説をやりました.
angoup6.pdf
第6回講義のプレゼンの pdf ファイル
- 6月8日(火):第7回 電話でじゃんけんをする方法
メンタルポーカーとコイン投げプロトコルの説明をしました.
準備が間に合わなかったのでコンピュータによる実演は次回に回しました.
angoup7.pdf
第7回講義のプレゼンの pdf ファイル (レポート問題 11 は 12 の間違いで
す! 訂正しておきました.
また,15日にやった実演画面の説明を追加しておきました.)
- 6月15日(火):第8回 ビット預託・暗号プロトコルの実演
ビット預託の解説をした後,前回と今回のコンピュータによる
暗号通信とビジュアルなイメージ化の実装をお見せしました.
零知識証明・紛失通信については全くできなかったので,いつかやります.
angoup8.pdf
第8回講義のプレゼンの pdf ファイル
- 6月20日(日):プログラミング講習会 希望者に多倍長演算のプログラ
ム法を解説しました.
- 6月22日(火):休講 逆問題の勉強のため学生と京都に行ってきます.
- 6月29日(火):第9回 秘密分散法
海賊の物語です.
秘密情報を複数の人に分散して持たせるいろいろな方法を, 海賊の首領が
残した宝の地図を例に説明しました. そのための道具の一つとして
誤り訂正符号の紹介もしました.
angoup9.pdf
第9回講義のプレゼンの pdf ファイルの訂正版 (2010.7.2.22:03 改訂)
講義中に気づいた間違いを訂正するのを忘れていました.直しついでに少し
説明を補いました.
- 7月6日(火):第10回 有限体の計算
閾値付き秘密分散法に使われた Reed-Solomon 符号や,
次週にお話しする AES 暗号の基礎となっている
有限体の計算法を黒板で解説しました.
angoupa.pdf
第10回講義のプレゼンの pdf ファイル (2010.7.6 21:43 修正版)
回数が狂っていたのを修正し,レポート問題を追加しました.
- 7月13日(火):第11回 AES 暗号の解説と対称鍵暗号の実装法
前回学んだ有限体の計算を本格的に使う代表的な現代暗号の紹介をしました.
angoupb.pdf
第11回講義のプレゼンの pdf ファイル (2010.8.27 23:48 改訂版)
- 7月20日(火):第12回 零知識証明・紛失通信
零知識証明は, 自分が大切な情報を持っていることを,内容を
伝えずに相手に納得させてしまう,最も不思議な技術です.
紛失通信は種々のプロトコルを構築するための重要な部品です.
angoupc.pdf
第12回講義のプレゼンの pdf ファイル
- 7月27日(火):第13回 マルチパーティプロトコルと実用プロトコル
のいろいろ
前回時間が無くてやれなかった暗号プロトコルの王様である,
マルチパーティプロトコルのお話から始め,
電子投票や電子オークションなどのいくつかの実用例の現実的な実装法
についてもお話しします.
最後に種々の暗号プロトコルの相互関係や暗号の安全性
についてお話しします.
【暗号関係のサイトへのリンク集】
講義の参考にするため, 集めました.
講義科目の紹介メニューに戻る.