暗号 田浦健次朗

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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)

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)

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

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

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

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

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

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

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

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

基本アイデア 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” ということが多い

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

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

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

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

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

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