暗号 田浦健次朗.

Presentation on theme: "暗号 田浦健次朗."— Presentation transcript:

1 暗号 田浦健次朗

2 コンピュータにおける情報の表現 ファイルとその中身 コンピュータの仕組み 通信・ネットワーク,インターネット 情報の符号化,その限界 ファイルとフォルダ コマンドライン プログラムの仕組み 通信の符号化,その限界 暗号 簡単なプログラムの作成・実行 Excelで計算・データの可視化 基礎的概念 (本講義中では)やや高度な概念 実技・実践

3 テーマ オープンなネットワーク(インターネット)を安全 にするための(広義の)暗号技術の基礎 守秘(狭義の暗号) 通信内容が見られない 署名
通信内容が改竄・捏造されない 認証 通信内容が正しい相手からのものである

4 実際に使われる場面 Secure HTTP ショッピングサイトなどにアクセスしていると き, 個人情報を見られないようにするために
ブラウザで というURLにアクセスして いるとき PGP, GPG 特定の人との間で を暗号化

5 守秘(暗号) 情報を送り手,受け手以外には読めなくする方法 xyaaekaba kcajkbacaka cakkgagaka
I love you... I love you...

6 単純な暗号の例 Caesar暗号: 送信・受信者間で秘密の数kを共有 暗号化アルファベットをk「ずらす」
'A'  'E', 'B'  'F', 'C'  'G', etc. 弱い: ある暗号文のもととなる文(平文)は26通り( ずらす量の種類)しかない

7 問題設定確認 コンピュータでは任意の情報はbit (0,1)列に符号 化される
0,1の列を適当なbit数(たとえば64 bit)に区切れば それを整数の列と見ることができる 暗号の方法を議論するときはある決まった範囲 の整数(e.g., 0  x < 264)をどのように暗号化する かに話を限ってよい

8 暗号の枠組み 暗号化(encryption) E(x) 復号化(decryption) D(x) 最低限の要件 D(E(x)) = x

9 Caesar暗号再掲 x : 64 bit k : (鍵) 送信者・受信者以外には秘密の数(64 bit)
E(x) = x + k (mod 264) D(x) = x – k (mod 264)

10 安全性の議論 暗号が破られる E(x)からxを計算されてしまう kが知られてしまう 暗号が安全性  kが知られない
注1: kが分かった後の計算方法(ここでは x + k)自 身は公知と考える. 「暗号化の方法自体が秘密」 とは考えない 注2 : どのような情報を与えるかにより「kが知ら れない」かどうかも異なる(攻撃者に対する仮定)

11 Caesar暗号の安全性 容易に分かるとおり安全ではない 例1: ひとつでもx, E(x)の組が漏れたら直ちにkが わかる
例2: xの分布(例: アルファベットの頻度)が分かっ ており,多数の(未知の)xに対するE(x)があれば,そ の分布を見るだけでkを絞り込める では「本当に安全にするにはE(x)をどうしたらい いのか」という問題をきちんと扱うのが暗号とい う分野

12 共通鍵暗号 E(x), D(x)は, D(E(x))=xという要件を満たす限り いろいろな作り方がある
しかし最初の例に見るように,単純な作り方の場 合, E(x)を計算できるならば(kを知っているという ことなので), D(x)も計算できる このような暗号方式を「共通鍵暗号」という

13 共通鍵暗号 つまり,送信者と受信者が実質的に「共通の秘密 」を持っている 送信者「だけ」の秘密,受信者「だけ」の秘密,と いうものはない
共通鍵暗号には「そもそも最初にどうやって秘 密を共有するのか」と言う問題(鍵配送問題)があ る 単に送るだけではそれが攻撃者に見られてしま う 暗号化して送りたい  鶏と卵!

14 鍵配送問題の解決方法 公開鍵暗号 Diffie Hellman鍵交換 時間があれば後日

15 公開鍵暗号 暗号化E(x), 復号化D(x)が「本質的に」違うよう な構成法
つまりE(x)は簡単に計算できるがE–1 (x)を計算す る事が困難であるような関数Eの作り方 別の言い方: E(x)を計算するための鍵(パラメータ) D(x)を計算するための鍵(パラメータ) が異なり, 片方からもう片方を導けない 概念は一般的で,様々な構成がありうるがよく使 われているものではRSA暗号が有名

16 RSA Fermatの小定理 p : 素数 a  0 (mod p)  ap – 1 = 1 (mod p) ここから以下は容易に分かる
p, q : 素数 a  0 (mod p), a  0 (mod q)  a(p – 1)(q – 1) = 1 (mod pq)

17 RSA (続) e : 素数 d : de = 1 (mod (p – 1) (q – 1)) なる整数
この見つけ方は自明ではないが良い方法が知ら れている n = pq 暗号化 (e, n を用いる) E(x) = xe (mod n) 復号化 (d, n を用いる) D(x) = xd (mod n)

18 RSAの用い方 e, n : 暗号化鍵, または公開鍵 「私に向かって秘密の通信をしたい人はこれを 使ってください」と「公開」してもOK
d, n : 復号化鍵,または秘密鍵 こちら(d)だけを秘密にしておく 重要な問: 公開鍵e, nを知って秘密鍵dを知ること は難しいのか?

19 RSAの用い方 RSAを用いて文を毎回暗号化してもよいが, 変わ りに共通鍵暗号の鍵を安全に送ることができる
通常共通鍵暗号の暗号化は公開鍵のものより速 いので実際にはこの方法が使われる

20 e, nからdを知る nからp, qを求める, つまりnを「素因数分解」で きればdを知ることができる
「試し割り算」による方法はどのくらい時間が かかるか?

21 RSAについての予想 nを素因数分解できる「速い」方法は存在しない 「速い」=桁数の多項式
nを素因数分解しなければ決してe, nからdが求ま らない どちらもそう信じられているが証明されていな い

22 守秘以外の暗号技術 署名 認証

23 署名(signature) ある文書が「確かにAが書いた(それ以降改竄さ れていない)」物である事を証明する方法
実世界の例: ハンコ, 直筆サイン 根拠: 登録印であればその人しか持っていない(は ず), 個人のサインは他の人には真似できない(はず ), …

24 電子署名 目的は同じで, 署名の根拠を暗号化技術に求める
文書(x)に, 「Aだけが知っている秘密を利用して 計算した結果」を添付しておく暗号と類似 基本方式: sign(x) = (x, D(x)) verify(x, y) = if E(y) = x then OK else NG

25 認証 自分の通信相手が確かに「正しい相手」である ことを確認する方法 基本手段(「山といえば川」合言葉)
相手が「その人しか知らない秘密」を知ってい ることを確認する  暗号との類似 単純なプロトコルではその「秘密」が攻撃者に 見られてしまう(毎回「川」が正解では困る) 山 川

26 基本アイデア AがBを認証(話し相手がBであることを確認)する とする A  B : EB(x) # x : 乱数
B  A : EA(x) # Bでない限りxを読めない A : if DA(受け取った値) = x then OK else NG 注: EA : Aへ送信するための暗号化 前者をAからBへの”challenge”, 後者を”response” ということが多い

27 公開鍵暗号技術によって解決{する・しない}問題
する: 暗号化鍵を公にさらしてよい. 自分が通信したい 人それぞれと「秘密」を共有しなくてよい 署名・認証するのに自分の秘密を相手にさらけ 出さなくてよい しない: そもそも使っている公開鍵が本物であることを どう検証するのか

28 公開鍵の検証の問題 Webサイトamazon.comでショッピングをしてい るとする
その公開鍵が本物(アマゾンが作った物)であれば 確かに「あの」アマゾンと通信していることが保 証される

29 原始的な公開鍵の検証方法 アマゾンが公開鍵を新聞に載せる・アマゾンに 電話をかけて公開鍵を入手する・現地訪問して入 手するなど
これをOSやブラウザのベンダがやってくれて, 確認済みの公開鍵を同梱してくれる(ソフトのイ ンストール媒体が捏造されていなければOK)

30 原始的な方法の問題点 すべてのWebサイトの公開鍵を同梱するのは不 可能 実際には,あるサーバに接続をした際にサーバか ら公開鍵が送られる
その時送られてきた公開鍵を検証する方法が必 要

31 認証局による公開鍵の電子署名 認証局: 信頼ある第3者
認証局はアマゾンに出かけて行く, 電話をするな どの手段でアマゾンの公開鍵を事前チェックする OKなら,アマゾンの公開鍵に電子署名をする アマゾンはそれを改竄できない アマゾン以外の攻撃者もアマゾンと名乗る公開 鍵を捏造できない(認証局の署名が必要) 認証局による署名つきの公開鍵を「電子証明書 (certificate)」と呼ぶ

32 公開鍵の検証 OS/ブラウザに認証局の公開鍵を同梱 認証局が真面目に仕事をしていることは信じ,認 証局によって電子署名された公開鍵は信用する
注: 信頼している認証局が署名をしている, 別の 認証局の公開鍵を用いることもできる