はじめに
今日の話
共通鍵暗号と公開鍵暗号 公開鍵暗号（RSA）
オイラーの公式に基づいた暗号方式 暗号通信の実際
安全な通信
安全な通信とは？
『盗聴』されていないこと
『改竄』されていないこと
『なりすまし』されていないこと 盗聴：秘密のデータを盗み見る
改竄：データを不正に変更する
なりすまし：他人の名義でデータを作成する
『盗聴』『改竄』『なりすまし』が発生しない通信 安全な通信 ＝
共通鍵暗号と公開鍵暗号(1)
情報の安全性を確保するためには
認証 ： 本人性の確認
֜ 盗聴・改竄を防ぐ
暗号化 ： 通信データの暗号化
֜ なりすましを防ぐ 共通鍵暗号を使う
公開鍵暗号を使う
公開鍵暗号を使う
共通鍵暗号と公開鍵暗号(2)
共通鍵暗号方式
送信者 受信者
Data 暗号化 Δατα Δατα Data
共通鍵
復号化
同じ鍵 共通鍵
利点 ： 単純な計算で暗号化できる 欠点 ： 共通鍵の配布が困難
共通鍵暗号と公開鍵暗号(3)
公開鍵暗号方式
送信者 受信者
Data 暗号化 Δατα Δατα Data
公開鍵
復号化
異なる鍵 秘密鍵
利点 ： 公開鍵は無制限に配布することが可能 欠点 ： 計算が複雑
公開鍵暗号：RSA(1)
RSA暗号
インターネットで最もよく使われる公開鍵暗号方式
֜ オイラーの定理を基にした暗号アルゴリズム
オイラーの定理
N と a が互いに素である場合、以下の式が成り立つ
a
φ(N)= 1 (mod N)
φ(N) :=「Nより小さい ＆ Nと互いに素の整数」の数
公開鍵暗号：RSA(2)
モジュラ計算
指定された数を「法」として計算する
「x = a × N + b」の場合、「x = b (mod N)」となる 例： 80 + 80 = 60 (mod 100)
54 × 3 = 62 (mod 100)
6 × 4 = 4 (mod 10)
616 = 6 (mod 10) 練習問題
6 × 4 × 4 = 6 (mod 10)
公開鍵暗号：RSA(3)
オイラーの定理
N と a が互いに素である場合、以下の式が成り立つ
a
φ(N)= 1 (mod N)
φ(N) :=「Nより小さい ＆ Nと互いに素の整数」の数 例： φ(3) = 2
φ(4) = 2 φ(5) = 4 φ(6) = 2
φ(7) = 7 – 1 = 6 φ(10) = 4
φ(77) = φ(7 × 11)
= (7 – 1)(11 – 1)
= 60
公開鍵暗号：RSA(4)
RSA暗号の基本的な考え方
a
φ(N)= 1 (mod N)
オイラーの定理
e×d = φ(N)×n + 1 となるような整数 e と d を作る
a
e×d= (a
e)
d= a (mod N)
暗号化（m:平文, c:暗号文）
復号化（m:平文, c:暗号文）
c = m
e(mod N)
m = c
d(mod N)
公開鍵暗号：RSA(5)
RSAの鍵の生成方法
(1) 素数 p, q を用意する p = 13, q = 17 (2) N = p × q とする N = p × q = 221
(3) φ(N) を求める φ(N) = (p – 1)(q – 1)
= 192
(4) φ(N)と素な整数 e を選ぶ e = 11
(5) 「e×d = φ(N)×n + 1」となる d を探す d = 35
公開鍵（暗号鍵）： e と N
秘密鍵（復号鍵）： d と N
公開鍵暗号：RSA(6)
暗号化と復号化
平文「m = 9」を暗号化する
暗号文「c = 185」を復号化する 暗号文 c = me
= 911
= 9(1 + 2 + 8)
= 91 × 92 × 98
= 9 × 81 × 120
= 185 (mod 221)
(N = 221, e = 11, d = 35)
復号文 m = cd
= 18535
= 9 (mod 221)
公開鍵暗号：RSA(7)
RSAの鍵の生成（実際の計算）
(1) 大きな素数 p, q を用意する
(2) N = p × q とする
(3) LCM(p – 1, q – 1) を求める
(4) LCM(p – 1, q – 1)と素な整数 e を選ぶ
(5) 「e × d = φ(N) × n + 1」となる d を探す
素数判定法（フェルマーテストなど）を用いて素数を生成
φ(N)よりも小さい値を見つける（カーマイケルの定理）
計算しやすい素数（e = 11, e = 65537など）を選ぶ
拡張ユークリッド互除法で と を探す
公開鍵暗号：RSA(8)
鍵の大きさの設定
(1) 素数 p, q によって N が決まる
(2) 平文 c は N と互いに素でなくてはならない 鍵の大きさと平文の大きさ
֜ c < p かつ c < q 鍵の大きさと計算量
e = 73で暗号化するとき、必要となる乗算(除算)回数は？
（ヒント： e = 73 = 10010012 = 20 + 23 + 26） a73 = a(1 + 8 + 64) = a1 × a8 × a64 ：乗算回数2回
a64 を計算するために必要な乗算回数：6回 ֜ 合計8回 必要な乗算回数・除算回数は O(log e) となる
公開鍵暗号：RSA(9)
鍵の大きさと安全性
「秘密鍵が知られていない」ことが安全の根拠
֜秘密鍵が漏洩しなければ暗号の安全は保証される 公開鍵暗号の安全性の根拠
e と N は公開されている ֜ d を知られないことが重要 RSAの安全性の根拠
d を計算するためには、N を構成している p, q が必要
֜ N を素因数分解する必要がある
N の素因数分解に必要な計算量（除算の回数）： O(N)
֜ p, q を十分に大きな値にすれば安全
公開鍵暗号：RSA(10)
公開鍵と秘密鍵の関係
公開鍵： e と N 秘密鍵： d と N
a
e×d= a (mod N)
RSA暗号の e, d, N の関係式
公開鍵で暗号化 ֜ 秘密鍵で復号化
秘密鍵で暗号化 ֜ 公開鍵で復号化
c = m
e(mod N) m = c
d= m
e×d(mod N)
c = m
d(mod N) m = c
e= m
e×d(mod N)
公開鍵暗号：RSA(11)
公開鍵暗号方式（RSA）の特徴
「公開鍵」で暗号化したものは「秘密鍵」で復号化できる
「秘密鍵」で暗号化したものは「公開鍵」で復号化できる
Data 暗号化 Δατα Δατα Data
公開鍵(e,N)
復号化
秘密鍵(d,N)
Data 暗号化 Δατα Δατα 復号化 Data
公開鍵(e,N) 秘密鍵(d,N)
公開鍵暗号：RSA(12)
RSAの欠点
暗号化・復号化の計算量が（共通鍵暗号に比べて）多い 安全性を確保するため p, q に大きな素数を使う
֜ 通常、512[bit]以上の素数を使う
e や d が 1024[bit]の場合、
暗号化・復号化で最大で2048回の乗算（除算）が必要 p,qが大きい数値
֜ Nも大きい数値となる
֜ eとdも大きい数値となる可能性がある
特に、秘密鍵による復号化・暗号化の計算量が多い！
暗号通信
暗号通信の実際 Transport Layer Security(TLS) Secure Sockets Layer (SSL)
サーバ クライアント
秘密鍵 公開鍵
公開鍵を送る
ランダム値を生成 生成したランダム値を
公開鍵で暗号化して送信
公開鍵
ランダム値を基に 共通鍵を生成
ランダム値を基に 共通鍵を生成
共通鍵 共通鍵を使って 共通鍵 暗号通信を行う
まとめ
まとめ
公開鍵暗号（RSA）
オイラーの公式に基づいた暗号方式
暗号通信の実際
公開鍵と秘密鍵は裏表の関係
公開鍵で暗号化 ֜ 秘密鍵で復号化 秘密鍵で暗号化 ֜ 公開鍵で復号化
共通鍵暗号は鍵の配布が難しい
公開鍵暗号は暗号化・復号化の計算量が多い
֜ 公開鍵暗号で共通鍵を共有し、共通鍵暗号で通信する
