Q q 情報セキュリティ 第５回：２００６年５月１９日（金） q q.

Presentation on theme: "Q q 情報セキュリティ 第５回：２００６年５月１９日（金） q q."— Presentation transcript:

1 q q 情報セキュリティ 第５回：２００６年５月１９日（金） q q

2 本日学ぶこと 鍵の管理 公開鍵暗号 RSA暗号アルゴリズム

3 本日の授業で学ぶ語句 鍵配送問題，鍵の事前共有 公開鍵暗号，公開鍵，プライベート鍵，鍵ペア RSA
数論アルゴリズム，べき剰余，拡張ユークリッドの互除法 対称暗号で鍵の事前共有をすると，鍵の数は O（ｎ2） 公開鍵暗号なら，O（ｎ） RSAは暗号化も復号も，べき剰余

4 対称暗号をどう使う？ 共通鍵暗号は，暗号化の鍵＝復号の鍵 鍵はいくつ必要？ ２人なら１個 ３人ならそれぞれ２個，全体で３個
４人ならそれぞれ３個，全体で６個 n人ならそれぞれn-1個，全体でn(n-1)/2個 1000人ならそれぞれ999個，全体で約50万個 新規加入者は（それまでの）人数分の相異なる鍵を作って 配布しないといけない…できる？？

5 公開鍵暗号の特徴（１） 管理すべき鍵の個数を減らせる n人ならそれぞれ1組，全体でn組

6 公開鍵暗号の特徴（２） 鍵一つあたりのビット長は長くなる 暗号アルゴリズム 種類 鍵長 ブロック長 DES 対称 56 64 トリプルDES
処理時間もかかる 暗号アルゴリズム 種類 鍵長 ブロック長 DES 対称 56 64 トリプルDES 112, 168 AES 128, 192, 256 128 RSA 公開鍵 512～2048 ≦鍵長 楕円曲線暗号 160～256

7 RSAを支えるもの アルゴリズム 安全性 暗号化・復号 鍵生成 整数に対する加減乗除，剰余，べき剰余 ユークリッドの互除法とその拡張
乱数生成 素数判定 安全性 素因数分解 離散対数問題 少し先 暗号化・復号 鍵生成 次回

8 アルゴリズムの書き方・読み方 「入力」「出力」「手順（アルゴリズム）」の順に書く． 代入と比較を区別する．
このスライドでは「←」と「=」 C言語では「=」と「==」 手順では適切に番号を振り，「…へ進む」「…へ戻る」という形でジャンプ先を明記する． 処理を終えるときは「…を出力して終了する」と書く． 「…を出力する」のみだと，まだ終了しないと考える． 書く人は簡単に検証できる例を添えておく． 読む人は最低限，その例でうまくいくことを確認する．

9 整数に対する加減乗除と剰余 加算 減算 乗算 除算 剰余 注意点 入力：整数x, y 出力：x+y 出力：x-y 出力：x*y
入力：整数x, y (y＞0) 出力：x/y （xをyで割った商） 剰余 入力：整数x, y (y＞0) 出力：x%y (xをyで割った余り) 注意点 いずれも自明なのでアルゴリズムは省略 x, yがともにNビットのとき 加減算の結果は 最大N+1ビット 乗算の結果は最大2Nビット 除算と剰余の結果は 最大Nビット

10 modについて このスライドでは字数を減らすため，剰余の演算子には「%」を使用している．
「モッド」または「モジュロ」と読む． このスライド，および教科書では，もっぱら２項演算子として使用している． ２項関係としてmodを使う本も多い． 例：　5≡-1 (mod 2) 「5 合同 -1 モッド 2」または「5 合同 -1 モジュロ 2」と読む． この式は「5 % 2 = -1 % 2」，「5-(-1) が 2 で割り切れる」， 「5-(-1)=2k を満たす整数 k が存在する」と同値．

11 乗除算の注意 5を2で割ったとき，商は2，余りは1 -5 を2で割ったときの商と余りは? 商と剰余の基本要件 商と剰余の追加要件
候補１：商は-2，余りは-1 候補２：商は-3，余りは1 商と剰余の基本要件 aをbで割ったときの商が q，余りが r のとき，a = q * b + r 0≦|r|＜|b| 商と剰余の追加要件 a = q * b + r ⇔ (-a) = (-q) * b + (-r)．すなわち余りの符号は 除数と被除数に依存する． b>0 のときは 0≦r＜b．すなわち余りは常に非負． RSAの計算では を採用 -6 -5 -4 -3 -2 -1 Ｃ処理系の多くで採用

12 べき乗（べき剰余の準備として） 入力：正整数a，非負整数b 出力：ab アルゴリズム 例 計算効率は？
「%2」と「/2」の計算は， ビット演算を使用する！ 入力：正整数a，非負整数b 出力：ab アルゴリズム Step 1. r ← 1, s ← a, t ← b とする． Step 2. t=0 ならば，Step 5へ進む． Step 3. t%2=1 ならば，r ← r*s とする． Step 4. s ← s*s, t ← t / 2 とし，Step 2へ戻る． Step 5. r を出力して終了する． 例 a=3, b=10 のとき， ab= 38×32=59049 計算効率は？ 乗算回数は最大で 2×（bのビット数）

13 べき剰余 入力：正整数a，非負整数b，正整数m 出力：ab % mとなる整数値 アルゴリズム 例 なぜこれでうまくいくのか？
Step 1. r ← 1, s ← a, t ← b とする． Step 2. t=0 ならば，Step 5へ進む． Step 3. t%2=1 ならば，r ← r*s % m とする． Step 4. s ← s*s % m, t ← t / 2 とし，Step 2へ戻る． Step 5. r を出力して終了する． 例 a=225, b=29, m=323 のとき， ab % m=123 なぜこれでうまくいくのか？ (x * y) % m = (x % m) * (y % m) % m だから

14 RSA暗号アルゴリズム 暗号化 復号 暗号化と復号の関係 平文： 整数M （0≦M＜N） 公開鍵： 整数E，N 暗号化： C=ME%N
暗号文： 整数C　（0≦C＜N） プライベート鍵： 整数D，N 復号： M=CD%N 暗号化と復号の関係 任意の平文M （0≦M＜N）に対して，(ME%N)D%N=M (MD%N)E%N=Mも成立し，ディジタル署名で利用される

15 最大公約数 「互助法」ではない 入力：正整数a, b 出力：最大公約数 gcd(a,b) アルゴリズム（ユークリッドの互除法） 例
Step 1. r←a%b とする． Step 2. r=0 ならば，Step 4へ進む． Step 3. a←b, b←r として，Step 1へ戻る． Step 4. bを出力して終了する． 例 a=144, b=5のとき，gcd(a,b)=1

16 最小公倍数 入力：正整数a, b 出力：最小公倍数 lcm(a,b) = a * b / gcd(a,b)

17 拡張ユークリッドの互除法 入力：正整数a, b 出力：a*x+b*y=gcd(a,b)を満たす整数x, y アルゴリズム 例
一般に無限個ある中の １組 入力：正整数a, b 出力：a*x+b*y=gcd(a,b)を満たす整数x, y アルゴリズム Step 1. s←a, t←b, u←0, v←1 とする． Step 2. q←s/t, r←s%t（=s-q*t）, w←u-q*v とする． Step 3. r=0ならば，Step 5へ進む． Step 4. s←t, t←r, u←v, v←w として，Step 2へ戻る． Step 5. (t-b*v)/a, v を出力して終了する． 例 a=1440, b=50のとき，x=-1, y=29．実際， 1440*(-1)+50*29 = 10 = gcd(1440,50) である． なぜこれでうまくいくのか？ b*v % a = t % aだから s,t は常に正 q,r は非負 u,v,w は負も取り得る いずれも常に整数 gcd(a,b) = t y = v

18 拡張ユークリッドの互除法の応用 入力：正整数a, n 出力：a*b % n = 1, 0<b<n を満たす整数b アルゴリズム
「nを法とするaの逆数」ともいう．a, n から一意に定まる． 入力：正整数a, n 出力：a*b % n = 1, 0<b<n を満たす整数b アルゴリズム Step 1. gcd(a,n)>1ならば，「解なし」を出力して終了する． Step 2. a, nを入力として拡張ユークリッドの互除法を適用し，その出力をx, yに代入する． Step 3. x%n を出力して終了する． 例 a=5, n=144のとき，b=29．実際， 5*29 % 144 = 145 % 144 = 1である． Step 1では，a と n が 互いに素でない場合の 例外処理をしている． （互いに素 ⇔ gcd(a,n)=1）