情報セキュリティ 第07回
大久保誠也 静岡県立大学経営情報学部
2/45
はじめに
秘密鍵暗号の復習
公開鍵暗号の考え方
RSA暗号
演習：RSA暗号
はじめに
3/45
秘密鍵暗号の復習 と鍵配送問題
4/45 4/63
暗号と鍵
平文から暗号文を生成するとき、鍵を使用する。
復号するときも鍵を使用する。適切な鍵を利用しないと、平文に戻せない。
平文 暗号文
平文 暗号文
鍵を利用して暗号化
正しい鍵で 複合
変な 暗号文 文
正しい鍵以外では 複合できない
5/45
2 種類の暗号方式
秘密鍵方式
暗号化も複合も、同じ鍵を使用する。
秘密鍵を使用する。鍵は秘匿しておく必要がある。
一般的に、処理が軽い。
公開鍵方式
暗号化と復号で、異なる鍵を使用する。
公開鍵と秘密鍵があり、秘密鍵は秘匿し、公開鍵 は公開しておく。
一般的に、処理が重い。共
公 秘
6/45
秘密鍵暗号
暗号化も復号も、同じ鍵を使用する。共
秘密鍵
秘密鍵は第三者に渡してはいけない。
処理が軽いため、大きい平文を暗号化できる。共 共
平文 暗号文 暗号文 平文
7/45
秘密鍵のイメージ
暗号化も復号も、同じ鍵を使用する。鍵を持っている人は開けることができて、
鍵を持っていない人は開けることができない 鍵を持っている人は開けることができて、
鍵を持っていない人は開けることができない
8/45 ID
PASSWD
Alice
Bob
② 送信
あｓｄふぁｓｄ Ｊｌｋｊぇｗｋｆ
③ 「秘密鍵」で復号
ID PASSWD
あｓｄふぁｓｄ Ｊｌｋｊぇｗｋｆ
① 「秘密鍵」で 暗号化
盗聴しても、
復号できな い……。
共
共
秘密鍵暗号による通信
9/45 ID
PASSWD
Alice
Bob
① 「秘密鍵」で 暗号化
盗聴する ぞ！
共
秘密鍵、持って無い！
送ってもらうわけにも いかないしなぁ
秘密鍵暗号と鍵配送問題
10/45
鍵配送問題解決のアイデア
ID PASSWD
Alice
Bob
盗聴する ぞ！
開ける鍵と閉める鍵を わけちゃえば いいんじゃない？
11/45
今回の内容
基礎技術：
秘密鍵暗号方式
暗号化
ブロック暗号とストリーム暗号
公開鍵暗号方式
暗号化と認証
ハッシュ値と一方向関数
乱数
実際の実装：
RSA暗号の仕組み
12/45公開鍵暗号
13/45
公開鍵と秘密鍵 (1)
秘密鍵と公開鍵は、一対のもの公 秘
公開鍵 秘密鍵
ペア
秘密鍵は、自分しか知らない。
公開鍵は、世間に公開する。
処理が重いため、小さい平文を暗号化するのに使用 される。例えば、秘密鍵暗号の秘密鍵を暗号化する。14/45
秘密鍵と公開鍵 (2)
暗号化と復号では、異なる鍵を使用する。公開鍵で暗号化し、秘密鍵で復号する。
秘密鍵は第三者に渡してはいけない。
処理が重いため、基本的に小さい平文を暗号化する。公 秘
平文 暗号文 暗号文 平文
15/45
秘密鍵と公開鍵(3)
提案されている実現方法は、秘密鍵で暗号化し、公 開鍵で復号できる公開鍵暗号方式が多い。
この性質は、次回以降に行う「認証」を実現する際に 利用されている。秘 公
平文 暗号文 暗号文 平文
16/45
公開鍵暗号のイメージ
鍵付きの貯金箱：
誰でも中にお金を入れることができる（箱が公開鍵に相当）。
中身を取り出せるのは鍵を持っている人だけ。（鍵が秘密鍵に相当）
17/45 ID
PASSWD
Alice
Bob
③ 送信
あｓｄふぁｓｄ Ｊｌｋｊぇｗｋｆ
④ 「秘密鍵」で復号
ID PASSWD
あｓｄふぁｓｄ Ｊｌｋｊぇｗｋｆ
② 「公開鍵」で 暗号化
秘 公
① 送信
公
公開鍵暗号方式
盗聴しても、
復号できな い……。
公
18/45
代表的な暗号
公開鍵暗号方式 RSA暗号
楕円曲線暗号
秘密鍵暗号方式 DES
AES
RC4
いろいろあります
19/45 ID
PASSWD
Alice
Bob
③ 送信
あｓｄふぁｓｄ Ｊｌｋｊぇｗｋｆ
あｓｄふぁｓｄ Ｊｌｋｊぇｗｋｆ
② 偽「公開鍵」で 暗号化
① 送信
公
鍵配送問題
復号できる
秘 ぞ 差し替えて
公 やろう
公
本物である 保証は？
20/45
RSA 暗号
21/45
RSA暗号とは
代表的な公開鍵暗号方式の一つ。 1977年に、Rivest、Shamir、Adelmanの3人が発見。
当時、まだアイデアしかなかった公開鍵暗号方式に、
具体的な実現方法を示した。
最初の公開鍵暗号方式だが、現在でも幅広く使用さ れている。
因数分解の難しさに安全性の根拠を置く。
因数分解が解けると、暗号も解ける。
因数分解が、将来も難しい保証はない。あくまでも、今の人類が効率的な解き方を知らな
いだけ。 22/45
RSA暗号の鍵
秘密鍵
素数p
素数q
(p 1)(q 1)と素かつ(p 1)(q 1)より小さい、
適当な正の整数
e
公開鍵 n=p q
ed mod (p 1)(q 1)= 1 となるような d
23/45
RSA 暗号の暗号化と復号
平文
を暗号化して暗号文Cを作成する場合。 C=M
dmod n
ここでd
とn
は公開鍵であることに注意。
平文
を暗号化して暗号文C
を作成する場合。 M=C
emod n
ここでe
は秘密鍵、nは公開鍵であることに注意。
公開鍵n
が因数分解できてp
とq
がわかると、p,q,d
から秘密鍵e
もばれてしまう！24/45
RSA 暗号の理屈
C
emod n は本当に元の平文Mに戻るのか？
M
n C
emod
n n
M
dmod )
emod
(
n M
edmod
n M
(p1)(q1)1mod
オイラーの定理より pとqが素数ならば edの決め方から
数式を展開 Cの作り方より
25/45
演習： mod を用いた計算
26/45
今回の演習で面倒なところ
M
dの計算をどのようにやるかがポイントExcel
は2
31= 2147483648
ぐらいまでしか扱えない
ようするに7
15 とか、すでに計算できない 今回は最後に
M
dmod n
のようにn
で割ったあまりを 計算する
これを使うと、上手いこと計算できる27/45
x y mod n の計算方法
x
ymod n
を計算するとき、Excel
だと、x
yは値が大きす ぎて計算できない。
a*b mod n = (a mod n) * (b mod n) mod n
を利用。
x
ymod n = (((x mod n) * x mod n ) * x mod n )
* x mod n) * x mod n ) …………
=mod(F3*$B$11,$7)
x
をかけてmod n
を繰り返す28/45
演習 1: 13 y mod 133 の計算 (1)
1. 右のように入力
2.
B2
に1
を入力（0
乗は必ず0
なので）3.
B3
に=mod(13*B2,133)
を入力4.
B3を下の方までコピーする
ずっと下 まで
13を掛けて、133
で割った余り29/45
演習 1: 13 y mod 133 の計算 (2)
1になったら
そこから 繰り返し30/45
演習： RSA 暗号
31/45
演習： RSA 暗号 鍵の準備 (1)
素数を入力
素数を入力 (p1)(q1)より小さく、(p1)(q1) と素な、正の数を入力
32/45
演習： RSA 暗号 鍵の準備 (2)
=B3*B4 と入力
LCM(B3-1,B4-1) と入力
33/45
演習：RSA暗号 鍵の準備(3)
ed/B8のあまりの値が1になるような d
を探して入力34/45
演習：RSA暗号 暗号化(1)
暗号化したい値を入力
nより小さい値
35/45
演習： RSA 暗号 暗号化 (2)
=B11
=mod(F3*$B$11,$B7) F4のセルを
コピーして ペースト 計算したM^eを入力。今回は=F7 完成したM^e mod n が 暗号文
M^eは値が大きく計算できないので、工夫が必要
36/45
演習： RSA 暗号 復号
暗号化と同様にしてC^dを計算
計算したC^dを入力。
今回は=I13
37/45
注意点
mod は、あまりを計算する演算です。
例：10÷3= 3 あまり 1 なので、
10 mod 3 = 1 となる。
今回の演習では、MS-Excelの制限で、あまり大きい 値を暗号化・復号することができません。
小さい値で行いましょう。
38/45
やること
39/45
課題の提出
今日のMS-Excelのファイルを経情グループウェアから 提出する。
ファイル名は学籍番号の末尾にgをつけたものとする。
グループ名は『R2_情報セキュリティ』です。
