2008情報科学概論

情報科学概論
公開鍵暗号の話：
RSA暗号の仕組み
Lecture 11
田中美栄子
公開鍵とは？
• 暗号とは、使用者自身が知っていて、他人に
は知られないもの（暗証番号など）
• 「銀行対ユーザ」ならば秘密にしておける
• 情報通信の場合、相手ごとに暗証番号を作っ
ていては手間がかかり大変
• そこで一人一人が自分用の公開鍵と秘密鍵
のセットを持ち、秘密鍵は秘匿するが、公開
鍵は公開する、というのが公開鍵暗号方式
インターネットでやりとりするデータは容易に
『盗み見』したり、『改ざん』できる。
防ぐことは困難なので
暗号化して送りましょう。
2015/10/1
まず、予備知識から・・・
平文・・・・・暗号化する前のそのままの文章
復号化・・・暗号化した文章をもとにもどすこと
鍵・・・・・・・平文を暗号化したり、復号化したり
できるもの。
（秘密鍵は共通鍵とも呼ばれてる）
2015/10/1
その１
共通鍵暗号方式
2015/10/1
共通鍵暗号方式ver.
送信者
受信者
②暗号化
①平文
暗号文
秘
③復号化
送信
④平文
暗号文
秘
欠点：秘密鍵を共有する手間がかかる
2015/10/1
その２
公開鍵暗号方式
2015/10/1
まず、予備知識から・・・
公開鍵・・・・・ネット上に公開している鍵
暗号は作れるが復号はできない。
2015/10/1
公開鍵暗号方式ver.
①公開鍵を送る
送信者
受信者
公
送信
平文
暗号文
②公開鍵で暗号化
暗号文
秘
平文
③秘密鍵で復号化
欠点：受信者が、本人かどうかの確証が取れない
2015/10/1
その3
デジタル証明書
2015/10/1
デジタル証明書
• なりすましを防ぐ方法として有効。
• 公開鍵といっしょに、認証局(CA)が発行した
デジタル証明書を送信し、本物を証明
• SSLによる通信中にブラウザのアイコンを
クリックして表示することができる。
2015/10/1
その４
セッション鍵暗号方式
（SSL）
2015/10/1
SSL（セッション鍵暗号方式）
• いままでのスキルを組み合わせた形
• 次の点を確認することで判断
– URLの先頭が「https://」になっている
2015/10/1
送信者（Webブラウザ）
受信者（Webサーバー）
①暗号通信要求
③自身の共通鍵
(秘密鍵)を生成
共
④自身の
共通鍵を
公開鍵で
暗号化
②公開鍵を送信
⑤暗号化した
共通鍵を送信
公
デジタル
証明書
⑥秘密鍵で
復号
秘
⑦共通鍵を
使ってやりとり
2015/10/1
その５
デジタル署名
2015/10/1
デジタル署名
• 送信者が正しい
• 伝送経路上でデータが改ざんされていない
– 上記の2点を
確認できる
まず、予備知識から・・・
ハッシュ化・・・・・誰にも読めない形にすること。
もう元には戻せない。
ハッシュ値・・・・・ハッシュ化されたもの。
メッセージダイジェスト・・・・・ハッシュ値の別名
2015/10/1
デジタル署名ver.
④公開鍵を送る
送信者
受信者
公
ハッシュ化
平文
平文
ハッシュ化
送信
⑥比較
①ハッシュ値
秘 ②暗号化
③デジタル
署名
2015/10/1
メッセージ
ダイジェスト
⑤復号化
デジタル署名
メッセージ
ダイジェスト
RSA方式のイメージ）
公
e
C=X mod N
実際は公開鍵や秘密鍵は
ただの数字であり，
数式処理だけで暗号化，
複合化を行っている
秘
d
C mod L = X
(ed + ml)mod N = 1
RSA暗号方式の仕組み
• Rivest，Shamir, Adelman ３名が1978年に発表
• ユーザ（i）は公開鍵（e,ni)と秘密鍵diを持つ。これら
はユーザごとに異なる。
• ユーザ（i）に暗号文を送りたい人はiの(e, ni)を用い
て暗号化する
• 受け取ったユーザ（i）は自分の秘密鍵diで解読する。
この鍵diが他の人に知られない限り秘密は保たれる。
（e,ni)とdiは数学的に関連しているが、（e,ni)からdi
を算出するには計算量が多すぎて短時間では不可
能である。
RSA暗号の弱み
• 公開鍵niは大きな２素数pとqの積として作り、
同時にpとqから秘密鍵diを作って使用する
• 公開された鍵(e,ni)を因数分解できる人がい
れば、原理的にdiを算出できるが、因数分解
に時間がかかるため安全性が保たれる
• 非常に高速なコンピュータを用いて因数分解
するか、因数分解の高速なアルゴリズムがわ
かればこの暗号は破られる（WAR GAMEと
いう映画では因数分解で暗号解読を試みる）
RSA方式の使い方
• 送りたい信号を２進表現したものをXとする
• 暗号化した信号Cは C=Xe mod n で作成
• 復号化は X=Cd mod n でできる
（mod nとはnを法とした表現、つまりnで割った
剰余のこと）
例：仮にn=35として（そんなに小さい訳ないが）
信号X=2を送るとする。もしe=11ならば送る
べき信号Cは C=211 mod 35 =18 となる
RSA暗号の仕組み
正の整数e,d,nは次の関係を持つようにする
1) まずn=pq となる２素数pとqからp-1とq-1を
作りこれらの最小公倍数をLとする。
2) そしてeは Max{p,q}<e<Lで、eとLは互い
に素な整数にする。
3）正の整数dを適当なyを用いてed+Ly=1とな
るよう選ぶ．
例：n=35ならL=12だから、eは7より大きく12よ
り小さくLとは互いに素な、e=11が適合する
秘密鍵dを持っているのは本人だけ
• 公開鍵(e,n)を公開しておいても，秘密鍵dを
知らない人には解読できない
• 本人はdを持っているから解読できる
• しかしnを因数分解できる人がいればLを算出
し、ed+Ly=1からdを算出できてしまう
• 例の場合n=35でL=12とわかればd=11がす
ぐわかる
• C=18を解読するにはこれのd乗(mod 35）を
計算するだけで良い
暗号解読の例
• 1811 (mod 35)が本当にX=2に戻るのか試してみよう
• 1811 (mod 35) = 181+2+8 (mod 35) = 18＊182 (mod 35)
＊188 (mod 35)と３つに分解し、 182 (mod 35)＝324 (mod
35)=9なので８乗の項以外は
18*9(mod35)=162(mod35)=22 となる
•
そして８乗するには２乗したものを更に２乗し、それを更に２
乗すればよいことに気がつくと、 188 (mod 35)はまず２乗し
てmod35をとると9になるのでこれを更に２乗してmod35をと
ると81(mod35)で11となり、これを更に２乗してmod35をとる
ことにより16となる
• 両方併せて22＊16（mod35）＝352(mod35)=2となり、X=2
が得られる

Download Report