情報理論と暗号 大久保誠也 静岡県立大学経営情報学部 1/63 はじめに はじめに 先週の課題の補足 現代暗号とは 秘密鍵暗号と公開鍵暗号 RSA 暗号 演習 :RSA 暗号 2/63
先週の演習の解説 3/63 シーザー暗号で行いたいこと シーザー暗号文字ずらすことで暗号化 復号 ex 暗号化 :DOG GRJ ( 各文字を 3 文字分後にずらす ) 復号 :GRJ DOG ( 各文字を 3 文字分前にずらす ) 文字を 3 文字ずらす処理を, MS-Excel で行えれば良い 4/63
演習 : シーザー暗号 (1) 何文字分ずらすか 文字を入力 3 を入力 a を入力 平文 ( 暗号化したい文字 ) =CODE(B3) を入力 =MOD(B4-97+$B$2,26)+97 を入力 =CHAR(B5) を入力 5/63 文字を入力 演習 : シーザー暗号 (1) B3にある文字の文字コードを求める 3を入力 aは97 eは101 bは98 ac はを入力 99 dは100 zは122 =CODE(B3) を入力 =MOD(B4-97+$B$2,26)+97 を入力 =CHAR(B5) を入力 6/63
文字を入力 演習 : シーザー暗号 (1) B2の文字数ずらした文字を求める B4-97 : B4の文字がaから何文字あとかを計算 B4-97+3: 3 文字ずらす MOD( 3 略を入力, 26): zの次はaにする必要があるので 26のあまりを求める aを入力 MOD( 略 )+97: a の文字コード (97) を足す =CODE(B3) を入力 =MOD(B4-97+$B$2,26)+97 を入力 =CHAR(B5) を入力 7/63 演習 : シーザー暗号 (1) 文字を入力 3 を入力 =CHAR(B5) を入力 a を入力 =CODE(B3) を入力 =MOD(B4-97+$B$2,26)+97 を入力 文字コードを文字にする 8/63
現代暗号 9/63 日常で使用されている暗号 日常でも 結構 暗号は使用している Web ブラウジング ユニバーサルパスポート (Web 学生支援システム ) Web ショッピング 携帯電話の通話内容 意識していなくても 機械が勝手に暗号化された通信を行ったりしてくれる そういう仕組みになっている 10/63
firefox で見る https(1) ユニバーサルパスポート (Web 学生支援システム ) は 通信が暗号化されています 大学の TOP ページから Web 学生支援システムにアクセスしてみましょう 11/63 firefox で見る https(2) https で通信している時 Firefox の URL バーは次のようになります 蒼い部分をクリックしてみましょう 12/63
firefox で見る https(3) 認証局 ( 今回はやりませんが 安全性に密接に関係します ) 等が表示されます 13/63 firefox で見る https(4) 詳細を表示させることも可能です どの程度の暗号強度なのかも表示されます 14/63
firefox で見る https(5) https でも 正しくない証明書の場合 ( つまり 安全な通信でない場合 ) は 次のようになります 15/63 暗号の目的 平文 ( 送りたい文 ) を暗号化し 暗号文にする この際 鍵を使用する 平文 This is a pen. ( 二進数表記 ) 5468697320697320612070656E2E0A 暗号文 ;zb j 鍵 test 暗号化されていると 元の文章がわからない ( 二進数表記 ) 883BC0A17AA746D3DCADCE425C6A10AC 16/63
シーザー暗号では弱い シーザー暗号文字ずらすことで暗号化 復号 ex 暗号化 :DOG GRJ ( 各文字を 3 文字分後にずらす ) 復号 :GRJ DOG ( 各文字を 3 文字分前にずらす ) 今使うには 欠陥が多い 単純すぎる 鍵が26パターンだけ 総当たりで発見できる 等々 17/63 現代暗号の安全性の根拠 基本的に どんな暗号でも 時間をかければ いずれ必ず解ける 安全であるとは 実時間で解くのは難しい ということ 数学的な難しさに 安全性の根拠を求めることが多い この数学の問題は難しそうだ! これ元にして暗号を作れば きっと安全だ! 本当に簡単に解けないかは 証明されていない ( 方法と 今の人類が知らないだけの可能性も ) 18/63
因数分解は難しい? 因数分解は 現在の計算機では 非常に時間がかかる問題であると考えられています 15=3*5 は簡単にわかる では 75462131 は? 正解は 7591*9941 このぐらいなら 計算機で解けるけど 桁数が大きくなるほど難しくなる! 19/63 公開鍵暗号と秘密鍵暗号 20/63
暗号と鍵 平文から暗号文を生成するとき 鍵を使用する 平文 暗号文 鍵を利用して暗号化 復号するときも鍵を使用する 適切な鍵を利用しないと 平文に戻せない 正しい鍵で複合 暗号文 平文 正しい鍵以外では複合できない 暗号文 変な 21/63 文 2 種類の暗号方式 共通鍵方式 暗号化も複合も 同じ鍵を使用する 共通鍵を使用する 鍵は秘匿しておく必要がある 一般的に 処理が軽い 共 公開鍵方式 暗号化と復号で 異なる鍵を使用する 公開鍵と秘密鍵があり 秘密鍵は秘匿し 公開鍵は公開しておく 一般的に 処理が重い 公 秘 22/63
共通鍵 暗号化も復号も 同じ鍵を使用する 共通鍵 共 共 共 平文 暗号文 暗号文 平文 共通鍵は第三者に渡してはいけない 処理が軽いため 大きい平文を暗号化できる 23/63 共通鍵暗号による通信 3 共通鍵 で復号 1 共通鍵 で暗号化 ID PASSWD 2 送信 あ sd ふぁ sd Jlkj ぇ wkf 共 Bob ID PASSWD 共 Alice あ sd ふぁ sd Jlkj ぇ wkf 盗聴しても 復号できない 24/63
公開鍵暗号の必要性 1 共通鍵 で暗号化 ID PASSWD Bob 共 Alice 共通鍵 持って無い! 送ってもらうわけにもいかないしなぁ 盗聴するぞ! 25/63 公開鍵と秘密鍵 (1) 秘密鍵と公開鍵は 一対のもの 公開鍵 公 秘 秘密鍵 ペア 秘密鍵は 自分しか知らない 公開鍵は 世間に公開する 処理が重いため 小さい平文を暗号化するのに使用される たとえば 共通鍵を暗号化する 26/63
秘密鍵と公開鍵 (2) 暗号化と復号では 異なる鍵を使用する 公秘 平文 暗号文 暗号文 平文 秘 公 平文 暗号文 暗号文 平文 秘密鍵は第三者に渡してはいけない 処理が重いため 小さい平文を暗号化する 27/63 公開鍵暗号方式 2 公開鍵 で暗号化 ID PASSWD 公 あ sd ふぁ sd Jlkj ぇ wkf 1 送信 3 送信 公 4 秘密鍵 で復号秘 Bob あ sd ふぁ sd Jlkj ぇ wkf ID PASSWD Alice 公 盗聴しても 復号できない 28/63
代表的な暗号 公開鍵暗号方式 RSA 暗号 楕円曲線暗号 秘密鍵暗号方式 DES AES RC4 いろいろあります 29/63 RSA 暗号 30/63
RSA 暗号とは 代表的な公開鍵暗号方式の一つ 1977 年に Rivest Shamir Adelman の 3 人が発見 当時 まだアイデアしかなかった公開鍵暗号方式に 具体的な実現方法を示した 幅広く使用されている 因数分解の難しさに安全性の根拠を置く 因数分解が解けると 暗号も解ける 因数分解が 将来も難しい保証はない あくまでも 今の人類が効率的な解き方を知らないだけ 31/63 RSA 暗号の鍵 素数 p ( 秘密鍵 ) 素数 q ( 秘密鍵 ) 適当な正の整数 e ( 秘密鍵 ) n=p q ( 公開鍵 ) ed mod (p 1 と q 1 の最小公倍数 )= 1 となるような d ( 公開鍵 ) 32/63
RSA 暗号の暗号化と復号 平文 を暗号化して暗号文 C を作成する場合 C=M d mod n ここで d と n は公開鍵であることに注意 平文 を暗号化して暗号文 C を作成する場合 M=C e mod n ここで e は秘密鍵 n は公開鍵であることに注意 公開鍵 n が因数分解できて p と q がわかると p,q,d から秘密鍵 e もばれてしまう! 33/63 RSA 暗号の理屈 M=C e mod n は本当に元の平文に戻るのか? C e mod n ( M d mod n) M ed mod n ( p 1)( q 1) M M 1 e mod n mod n Cの作り方より数式を展開 edの決め方からオイラーの定理より 34/63
演習 :RSA 暗号 35/63 本日の資料 今日の資料は http://flute.u-shizuoka-ken.ac.jp/~s-okubo/ の 授業関係 から取ることができます 36/63
事前準備 (1) 今回の課題を行う前に アドオンを有効にする必要があります ここをクリック 37/63 事前準備 (2) 今回の課題を行う前に アドオンを有効にする必要があります ここをクリック 38/63
事前準備 (3) 今回の課題を行う前に アドオンを有効にする必要があります 1) アドイン をクリック 2) 設定 をクリック 39/63 事前準備 (4) 今回の課題を行う前に アドオンを有効にする必要があります 分析ツール にチェックを入れる 40/63
演習 :RSA 暗号鍵の準備 (1) 素数を入力 素数を入力 何か正の数を入力 41/63 演習 :RSA 暗号鍵の準備 (2) =B3*B4 と入力 LCM(B3-1,B4-1) と入力 42/63
演習 :RSA 暗号鍵の準備 (3) ed/b8 の値が 1 になるような d を入力 43/63 演習 :RSA 暗号暗号化 暗号化したい値を入力 =power(b11,b5) を入力 =mod(b12,b7) を入力 44/63
演習 :RSA 暗号復号 復号したい値を入力 =power(e11,b9 ) を入力 =mod(e12,b7) を入力 45/63 おわりに 今日の Excel ファイルを s-okubo@u-shizuoka-ken.ac.jp までメールで提出すること 題名 ( サブジェクトは学籍番号 ) とする また 本文には今日の授業の感想を書く 46/63