1 前回の練習問題 F 29 = {1, 2,…, 28} において， g = 11 が生成元であることを確 かめ， F 29 の元とその離散対数との関係を図示せよ． x = 1,..., 28 に対し， g x mod 29 を計算すればよい gxgx x gxgx x gxgx x log a a 0

2 前回紹介した RSA 暗号の実現例 暗号化操作： 平文を 3 乗して， 493 で割った余りを暗号文とする 復号操作： 暗号文を 299 乗して， 493 で割った余りを復号結果とする 当然沸いてくる疑問： 本当に，いつも正しく復号できるの？ 3 や 493 と 299 との関係は？ 大きな数字の計算はどうするの？

3 RSA 暗号 Rivest, Shamir, Adelman により 1977 年に提案 「世界初」の公開鍵暗号で，広く実用化 以下のスライドで概要を説明する 鍵の（具体的な）構成法 暗号化・復号の（具体的な）手順 鍵構成，暗号化・復号操作の実現法について 逆元計算，べき乗計算の方法 動作原理の数学的考察 安全性について

4 RSA 暗号の鍵構成 RSA 暗号の暗号化鍵，復号鍵をつくるには．．． 1. 大きな素数を２個選ぶ．仮にこれを p, q とする 2. 合成数 n = pq を計算する 3. (p – 1) (q – 1) と互いに素な正整数 e を選ぶ 4. ed ≡ 1 mod (p – 1)(q – 1) となる正整数 d を求める 5. 暗号化鍵として， e と n を公開する． 6. d は，復号鍵として厳重に保管する a ≡ b mod x: (a を x で割った余り ) = (b を x で割った余り ) a mod x: a を x で割った余り

5 RSA 暗号の暗号化と復号 e, n は暗号化鍵として公開： 暗号化操作は「平文を e 乗して n で割った余りを求め る」 平文 m の暗号文は， m e mod n d は復号鍵として秘密保存： 復号操作は「暗号文を d 乗して n で割った余りを求め る」 暗号文 c に対応する平文は， c d mod n 平文の集合は 1 以上 n – 1 以下の正整数

6 前例の鍵生成について 前回の例の鍵： e = 3, n = 493, d = 299 はどのように求めたか 1. p = 29, q = 17 とする 2. n = pq = 29 ・ 17 = 493 とする 3. e = 3 とする．この値は (p – 1)(q – 1) = 28 ・ 16 = 448 とは 互いに素となっている 4. 計算により d = 299 となる． ed = 3 ・ 299 = 897 = 2 ・ ， したがって ed を (p – 1)(q – 1) で割った余りは 1 になる 5. 暗号化鍵として e = 3 と n = 493 を公開 6. d = 299 は復号鍵として保管

7 復号鍵の計算について RSA 暗号では， ed ≡ 1 mod (p – 1)(q – 1) となる正整数 d を求める必要がある e と (p – 1)(q – 1) が互いに素ならば ed ≡ 1 mod (p – 1)(q – 1) となる d は必ず存在する d はユークリッド互除法を応用して計算可能

8 ユークリッドの互除法と d の計算 ユークリッド互除法： ２つの整数の最大公約数を計算するアルゴリズム a 0 = Ab 0 = B aiai bibi a i+1 = b i b i+1 = a i mod b i ajaj b j = 0 2 整数を A, B とする (A > B) a 0 = A, b 0 = B とする a i+1 = b i, b i+1 = a i mod b i として再帰的計算を行 う b j = 0 となったときの a j が A と B の最大公約数

9 ユークリッド互除法の計算例（１） 252 と 135 の最大公約数は．．． ← 252 を 135 で割ると，余りは 117 ← 135 を 117 で割ると，余りは 18 ← 117 を 18 で割ると，余りは 9 90 ← 18 を 9 で割ると，余りは と 135 の最大公約数は 9

10 ユークリッド互除法の計算例（２） 2 整数が互いに素ならば，どこかで b i = 1 となる 130 と 59 の最大公約数は．．． ← 130 を 59 で割ると，余りは ← 59 を 12 で割ると，余りは ← 12 を 11 で割ると，余りは 1 ← 11 を 1 で割ると，余りは 0 最大公約数は 1 ．．． 130 と 59 は互いに素

11 ユークリッド互除法と逆元計算 A, B を互いに素な正整数とし， A > B とする． ユークリッド互除法を応用することで， CB ≡ 1 mod A となる C を計算可能 （ C は B の乗法逆元） 計算法： 各 b i を (A の倍数 ) + (B の倍数 ) として表現 どこかで b i = 1 = xA + yB となるはず yB = – xA + 1 より， yB を A で割ると 1 余る yB ≡ 1 mod A なので， C = y としても良いが... CB ≡ 1 mod A となる C は無数に存在 （後の計算のため） y と同値な最小正整数を C とす る

12 逆元計算の例 130 と 59 は互いに素．．． = 130 – 2 x = 59 – 4 x 12 = – 4 x x 59 = 12 – 11 = 5 x 130 – 11 x 59 1 = 5 ・ 130 – 11 ・ 59 となる．これより．．． – 11 ・ 59 = – 5 ・ – 11 ・ 59 ≡ 1 mod 130 – 11 と等価な整数は，すべて 59 の逆元となる – 11 と等価な – = 119 を逆元の代表値とする

13 d の計算 ed ≡ 1 mod (p – 1)(q – 1) となる正整数 d を求める ⇒ (p – 1)(q – 1) と e に対してユークリッド互除法を利用 p = 29, q = 17, n = pq = 493, e = 3 に対応する d を求める： (p – 1)(q – 1) = 448 と e = 3 に対してユークリッド法を適用 = 448 – 149 ・ 3 3 の逆元は – 149 ≡ – = 299 mod 448 d = 299 これで鍵を作れるようになった

14 RSA の鍵を作ってみる p = 79, q = 97 とすると， n = pq = 7663 (p – 1)(q – 1) = 7488 と互いに素な値 e = 5 を選択 7488 と 5 との間でユークリッド互除法を実行 = 7488 – 1497 ・ = 5 – 3 = – ・ = 3 – 2 = 2 ・ 7488 – 2995 ・ 5 e の逆元は d = – 2995 ≡– = 4493 mod 7488

15 べき乗計算について 前スライドの RSA 暗号： 暗号化は，平文を 5 乗して 7663 で割る 復号は，暗号文を 4493 乗して 7663 で割る 安直に計算すると大変 べき乗を効率的に計算するために，「計算の分割」を行う x 2 mod n: そのまま計算する x 4 mod n: (x 2 mod n) 2 mod n として計算を行う x 8 mod n: (x 4 mod n) 2 mod n として計算を行う x 10 mod n: (x 8 mod n) (x 2 mod n) mod n として計算を行う ：

16 べき乗計算の例 mod 35 を計算する 12 2 mod 35 = 144 mod 35 = 4 12 ４ mod 35 = 4 2 mod 35 = mod 35 = 16 2 mod 35 = 256 mod 35 = mod 35 = 11 2 mod 35 = 121 mod 35 = mod 35 = mod 35 = 16 ・ 4 ・ 12 mod 35 = 768 mod 35 = 33 これで暗号化・復号が行えるようになった

17 RSA 暗号の簡単な使用例（１） ユーザＡの鍵生成： p = 5, q = 11 とする． n = 55 となる e = 3 とする． (p – 1)(q – 1) = 40 なので， e と互いに素 ユークリッド互除法で d を求める d = – 13 ≡40 – 13 = 27 mod = 40 – 13 x 3 暗号化鍵として e = 3, n = 55 を公開 復号鍵として d = 27 を秘密保持 d の計算は， (p – 1)(q – 1) の剰余系で行う． n の剰余系でないことに注意！

18 RSA 暗号の簡単な使用例（２） ユーザ B がユーザＡに m = 7 を暗号化して送る： B は公開されている暗号化鍵 e = 3, n = 55 を取得 暗号文は 7 3 mod 55 = 343 mod 55 = 13 ユーザ A による暗号文 13 の復号操作： ユーザ A は，秘密の復号鍵 d = 27 を知っている mod 55 を計算する 13 2 ≡4, 13 4 ≡16, 13 8 ≡36, ≡ ≡ 31 x 36 x 4 x 13 = 58032≡7 mod 55 復号結果は 7 暗号化，復号は n の剰余系で行う． (p – 1)(q – 1) の剰余系でないことに注意！

19 なぜ RSA 暗号はうまく動くのか？ 「正しい鍵を使えば正しく復号できる」ことが必須 RSA 暗号の場合， (m e mod n) d mod n = m ed mod n = m 任意の m に対し，この式が成立することを証明する必要がある Eular （オイラー）の定理（の特殊な場合）： m が n = pq と互いに素ならば， m (p – 1)(q – 1) ≡ 1 mod n.

20 Eular の定理の直感的意味付け べき乗値は， [1, n – 1] に属する有限の値をとる べき乗値の系列を考えると，どこかで無限ループに陥 る オイラーの定理の意味： m が n と互いに素であれば... 無限ループの中に 1 が存在 少なくとも， (p – 1)(q – 1) 乗したときは 1 になる Eular （オイラー）の定理（の特殊な場合）： m が n = pq と互いに素ならば， m (p – 1)(q – 1) ≡ 1 mod n n = 2 ・ 7 = 14 の場合， (p – 1)(q – 1) = 1 ・ 6 =

21 数値例 1 になった次の次数では，再び m が出現する m と n が互いに素であれば，任意の整数 k に対し， m k(p – 1)(q – 1)+1 = (m (p – 1)(q – 1) ) k m ≡ m mod n べき乗演算により，一時的に m の値が「隠蔽される」 さらにべき乗することで，周期的に m が出現する mm2m2 m3m3 m4m4 m5m5 m6m6 m7m7 n = 2 ・ 7 = 14 の場合， (p – 1)(q – 1) = 1 ・ 6 = m 13 m 19 …… …… …… …… …… ……

22 RSA の正当性証明 定理： m ed mod n = m 証明： ed ≡ 1 mod (p – 1)(q – 1) より，整数 k が存在して ed = k(p – 1)(q – 1) + 1 m が n と互いに素であるとき 前ページの式より m ed ≡m k(p – 1)(q – 1)+1 ≡ m mod n. m が n = pq とは互いに素でないとき m は p または q の倍数．仮に m = ap i とする (a < q) a は n と互いに素... m ed ≡a ed p ied ≡a(p ed ) i mod n p ed ≡ p mod n を証明できれば良い p ed ≡ 0 mod p p ed ≡ p mod q ( フェルマーの小定理 )

23 p ed ≡p mod n の証明 中国人の剰余定理 (Chinese Reminder Theorem): n = p 1 ・ p 2 ・ ・ ・ p j とする． 1 以上 n – 1 以下の整数で，以下の j 個の合同式 x≡a 1 mod p 1 x≡a 2 mod p 2 ： x≡a j mod p j を同時に満足する整数 x は（ n を法として）唯一に定ま る． □ p ed ≡0 mod p, p ed ≡p mod q を満足するのは， p ed ≡p mod n の場合のみ ⇒ 前ページの証明完了

24 公開鍵暗号の安全性について 暗号が安全：解読が困難であること さらに強い意味での安全性が必要になる場合も... （本講義では扱わない） 暗号の解読： 復号のための鍵を使わずに，暗号文に隠された 平文を特定，推測すること RSA の場合： m e mod n から m の値を推測すること

25 RSA 暗号の解読について RSA 暗号の解読は困難か？ 結果から言うと「安全であると思われている」 安全でないことの証明は簡単 攻撃に成功する方法を一個だけ提示すれば良い 安全であることの証明は困難 何をやっても成功しないことを示す必要がある RSA には，計算理論的な意味で安全性の保証はない 「 RSA の解読は NP 完全問題である」等の証明は これまで与えられていない

26 RSA の解読法（１） 攻撃者の立場から，どのような解読法が考えられるか 「 c = m e mod n から m の値を推測したい」ときにどうする か 総当り攻撃 公開鍵暗号では，誰でも暗号化が可能 考えられる平文を一個ずつ暗号化する 暗号文が c になる平文が m に相当する ⇒平文空間を大きく (n の値を大きく）すれば問題なし

27 RSA の解読法（２） 方程式攻撃 c = m e mod n から方程式を立てて m を計算 n の剰余系でなければ，単なる数値計算問題 ⇒ n の剰余系では，有効な解法が知られていない 復号鍵の推測攻撃 d は， (p – 1)(q – 1) の剰余系での e の乗法逆元 暗号化鍵 e と n = pq から，復号鍵 d を推定したい もし (p – 1)(q – 1) がわかれば， d の計算は容易 n = pq から (p – 1)(q – 1) が計算できるか？

28 素因数分解と RSA 暗号 n = pq から (p – 1)(q – 1) が計算できるか？ できるかもしれないし，できないかもしれない もし n を素因数分解できれば．．． p, q を特定可能 (p – 1)(q – 1) を計算可能 素因数分解はできるのか？ 決定的な解法は知られていない p, q を十分大きな素数にすれば， 実用上問題ないのではないかと考えられている

29 素因数分解と解読問題の難しさ RSA 暗号の場合， 素因数分解ができれば， RSA は解読可能 逆は示されていない 「 RSA の解読は，素因数分解よりも難しくない」 Rabin 暗号，逆数暗号等の公開鍵暗号方式 素因数分解ができれば，解読可能 暗号の解読ができれば，素因数分解もできる 「これらの方式の解読は，素因数分解と等価な難し さ」 易難 素因数分解 RSA の解読 Rabin, 逆数暗号の解読

30 RSA 暗号のまとめ RSA 暗号の鍵構成法 暗号化，復号の方法 具体的な計算の実現方法 正当性の証明 安全性の議論 安全性は素因数分解の困難さに依拠する 鍵のサイズをできるだけ大きく取ることが望ましい 現在では，最低でも n を 1024 ビット程度にはすべき

31 暗号関連技術について 本講義では，暗号方式の基礎の基礎だけを紹介 今回紹介した基礎の上に，さまざまな技術が展開 さらに進んだ暗号方式 電子署名， PKI 暗号を用いたプロトコル ゼロ知識証明 etc.

32 講義全体のまとめ 情報の記録や伝達を，効率よく，確実に行うための技術 第一部：情報の量を計る 第二部：情報をコンパクトに表現する 第三部：情報を正確に伝える 第四部：情報を不正者から隠す あくまでも情報を扱うための「道具」 情報を取り扱う際に，これら道具を最大限活用してほし い

試験について 6/3 （木）１限 試験（ L1 講義室） 本，資料，パソコン等の持ち込み OK （通信機能の使用は不 可） 電卓はあったほうが良いかも... test day: June 3 (Thu.), L1 (this room) You can bring any books, documents and your PC (no WiFi) An calculator may help you, maybe.... English translation of test questions will be provided. 33