Microsoft PowerPoint - info09b.ppt

1/63

情報理論と暗号

大久保誠也

静岡県立大学経営情報学部

はじめに



はじめに



先週の課題の補足



現代暗号とは



秘密鍵暗号と公開鍵暗号



RSA暗号



演習：RSA暗号

3/63

先週の演習の解説

4/63 

シーザー暗号

文字ずらすことで暗号化・復号

ex 暗号化：DOG → GRJ

（各文字を、

3文字分後にずらす）

復号 ：

GRJ → DOG

（各文字を、3文字分前にずらす）

文字を

3文字ずらす処理を，

MS-Excel で行えれば良い

シーザー暗号で行いたいこと

5/63 文字を入力 3を入力 aを入力 =CODE(B3) を入力 =MOD(B4-97+$B$2,26)+97 を入力 =CHAR(B5)を入力 何文字分 ずらすか 平文 （暗号化した い文字）

演習：シーザー暗号

(1)

文字を入力 3を入力 aを入力 =CODE(B3) を入力 =MOD(B4-97+$B$2,26)+97 を入力 =CHAR(B5)を入力 B3にある文字の文 字コードを求める aは97、 eは101、 bは98、 … cは99、 dは100、 zは122

演習：シーザー暗号

(1)

7/63 文字を入力 3を入力 aを入力 =CODE(B3) を入力 =MOD(B4-97+$B$2,26)+97 を入力 =CHAR(B5)を入力

演習：シーザー暗号

(1)

B2の文字数ずらした文字を求める。 B4-97 ： B4の文字がaから何文字あと かを計算 B4-97+3： 3文字ずらす MOD(略, 26)： zの次はaにする必要がある ので、26のあまりを求める MOD(略)+97： “a”の文字コード(97)を足す。 8/63 文字を入力 3を入力 aを入力 =CODE(B3) を入力 =MOD(B4-97+$B$2,26)+97 を入力 =CHAR(B5)を入力 文字コードを文字にする

演習：シーザー暗号

(1)

9/63

現代暗号

日常で使用されている暗号

 日常でも、結構、暗号は使用している。  Webブラウジング ユニバーサルパスポート（Web学生支援システム） Webショッピング  携帯電話の通話内容  意識していなくても、機械が勝手に暗号化された通信 を行ったりしてくれる。 そういう仕組みになっている。

11/63

firefoxで見るhttps(1)



ユニバーサルパスポート（

Web学生支援システ

ム）は、通信が暗号化されています。



大学の

TOPページから、 Web学生支援システ

ムにアクセスしてみましょう。

12/63

firefoxで見るhttps(2)



httpsで通信している時、FirefoxのURLバーは

次のようになります



蒼い部分をクリックしてみましょう。

13/63

firefoxで見るhttps(3)



認証局（今回はやりませんが、安全性に密接に

関係します）等が表示されます。

firefoxで見るhttps(4)



詳細を表示させることも可能です。

どの程度の暗号強度なのかも表示されます。

15/63

firefoxで見るhttps(5)



httpsでも、正しくない証明書の場合（つまり、安

全な通信でない場合）は、次のようになります。

16/63

暗号の目的

平文（送りたい文）を暗号化し、暗号文にする。 この際、鍵を使用する。 This is a pen. （二進数表記） 5468697320697320612070656E2E0A 平文 test 鍵 （二進数表記） 883BC0A17AA746D3DCADCE425C6A10AC ;zB¥j 暗号文 暗号化されていると、 元の文章がわからない。

17/63

シーザー暗号では弱い



シーザー暗号

文字ずらすことで暗号化・復号

ex 暗号化：DOG → GRJ

（各文字を、

3文字分後にずらす）

復号 ：

GRJ → DOG

（各文字を、3文字分前にずらす）

今使うには、欠陥が多い。



単純すぎる。



鍵が26パターンだけ。総当たりで発見できる。

等々

……

現代暗号の安全性の根拠

 基本的に、どんな暗号でも、時間をかければ、いずれ 必ず解ける。 安全であるとは『実時間で解くのは難しい』ということ。  数学的な難しさに、安全性の根拠を求めることが多い  本当に簡単に解けないかは、証明されていない（方法 と、今の人類が知らないだけの可能性も） この数学の問題は難しそうだ！ これ元にして暗号を作れば、きっと安全だ！

19/63

因数分解は難しい？

 因数分解は、現在の計算機では、非常に時間がかか る問題であると考えられています。  15=3*5は簡単にわかる。  では、75462131は？ 正解は、7591*9941。  このぐらいなら、計算機で解けるけど、桁数が大きくな るほど難しくなる！ 20/63

公開鍵暗号と秘密鍵暗号

21/63

暗号と鍵

平文から暗号文を生成するとき、鍵を使用する。 復号するときも鍵を使用する。 適切な鍵を利用しないと、平文に戻せない。 平文 暗号文 平文 暗号文 鍵を利用して暗号化 正しい鍵で 複合 変な 文 暗号文 正しい鍵以外では 複合できない

2種類の暗号方式

共通鍵方式 暗号化も複合も、同じ鍵を使用する。 共通鍵を使用する。鍵は秘匿しておく必要がある。 一般的に、処理が軽い。 公開鍵方式 暗号化と復号で、異なる鍵を使用する。 公開鍵と秘密鍵があり、秘密鍵は秘匿し、公開鍵 は公開しておく。 一般的に、処理が重い。 共 公 秘

23/63

共通鍵

暗号化も復号も、同じ鍵を使用する。 共 共通鍵 共通鍵は第三者に渡してはいけない。 処理が軽いため、大きい平文を暗号化できる。 共 共 平文 暗号文 暗号文 平文 24/63 ID PASSWD Alice Bob ② 送信 あｓｄふぁｓｄ Ｊｌｋｊぇｗｋｆ ③ 「共通鍵」で復号 ID PASSWD あｓｄふぁｓｄ Ｊｌｋｊぇｗｋｆ ① 「共通鍵」で 暗号化 盗聴しても、 復号できな い……。 共 共

共通鍵暗号による通信

25/63 ID PASSWD Alice Bob ① 「共通鍵」で 暗号化 盗聴する ぞ！ 共 共通鍵、持って無 い！ 送ってもらうわけにも いかないしなぁ

公開鍵暗号の必要性

公開鍵と秘密鍵

(1)

秘密鍵と公開鍵は、一対のもの 公 秘 秘密鍵 公開鍵 ペア 秘密鍵は、自分しか知らない。 公開鍵は、世間に公開する。 処理が重いため、小さい平文を暗号化するのに使用 される。たとえば、共通鍵を暗号化する。

27/63

秘密鍵と公開鍵

(2)

暗号化と復号では、異なる鍵を使用する。 秘密鍵は第三者に渡してはいけない。 処理が重いため、小さい平文を暗号化する。 公 秘 平文 暗号文 暗号文 平文 秘 公 平文 暗号文 暗号文 平文 28/63 ID PASSWD Alice Bob ③ 送信 あｓｄふぁｓｄ Ｊｌｋｊぇｗｋｆ ④ 「秘密鍵」で復号 ID PASSWD あｓｄふぁｓｄ Ｊｌｋｊぇｗｋｆ ② 「公開鍵」で 暗号化 秘 公 ① 送信 公

公開鍵暗号方式

盗聴しても、 復号できな い……。 公

29/63

代表的な暗号

公開鍵暗号方式 RSA暗号 楕円曲線暗号 秘密鍵暗号方式 DES AES RC4 いろいろあります

RSA暗号

31/63

RSA暗号とは

代表的な公開鍵暗号方式の一つ。 1977年に、Rivest、Shamir、Adelmanの3人が発見。 当時、まだアイデアしかなかった公開鍵暗号方式に、 具体的な実現方法を示した。 幅広く使用されている。 因数分解の難しさに安全性の根拠を置く。 因数分解が解けると、暗号も解ける。 因数分解が、将来も難しい保証はない。 あくまでも、今の人類が効率的な解き方を知らな いだけ。 32/63

RSA暗号の鍵

素数 p （秘密鍵） 素数 q （秘密鍵） 適当な正の整数 e （秘密鍵） n=p



q （公開鍵） ed mod (p



1とq



1の最小公倍数)= 1 となるような d （公開鍵）

33/63

RSA暗号の暗号化と復号

平文



を暗号化して暗号文Cを作成する場合。  C=Md_{mod n} ここで d と n は公開鍵であることに注意。 平文



を暗号化して暗号文Cを作成する場合。  M=Ce_{mod n} ここで e は秘密鍵、n は公開鍵であることに注意。 公開鍵 n が因数分解できて p と q がわかると、 p,q,d から秘密鍵 e もばれてしまう！

RSA暗号の理屈

M=Ce_{mod n は本当に元の平文に戻るのか？}

M



n

C

e

mod

n

n

M

d

mod

)

e

mod

(



n

M

ed

mod



n

M

(p1)(q1)1

mod



オイラーの定理より edの決め方から 数式を展開 Cの作り方より

35/63

演習：

RSA暗号

36/63

本日の資料

今日の資料は http://flute.u-shizuoka-ken.ac.jp/~s-okubo/ の『授業関係』から取ることができます。

37/63

事前準備

(1)

今回の課題を行う前に、アドオンを有効にする必要が あります。 ここをクリック

事前準備

(2)

今回の課題を行う前に、アドオンを有効にする必要が あります。 ここをクリック

39/63

事前準備

(3)

今回の課題を行う前に、 アドオンを有効にする 必要があります。 1) 「アドイン」 をクリック 2) 「設定」を クリック 40/63

事前準備

(4)

今回の課題を行う前に、アドオンを有効にする必要が あります。 「分析ツール」に チェックを入れる

41/63

演習：

RSA暗号 鍵の準備(1)

素数を入力 素数を入力 何か正の数を入力

演習：

RSA暗号 鍵の準備(2)

=B3*B4 と入力 LCM(B3-1,B4-1) と入力

43/63

演習：

RSA暗号 鍵の準備(3)

ed/B8の値が1になるようなdを入力 44/63

演習：

RSA暗号 暗号化

暗号化したい値を入力 =power(B11,B5) を入力 =mod(B12,B7) を入力

45/63

演習：

RSA暗号 復号

復号したい値を入力 =mod(E12,B7) を入力 =power(E11,B9 ) を入力

おわりに

今日のExcelファイルを [email protected] までメールで提出すること。 題名（サブジェクトは学籍番号）とする。 また、本文には今日の授業の感想を書く。