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

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

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

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

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

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

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

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

整数に対する加減乗除と剰余 加算 減算 乗算 除算 剰余 注意点 入力：整数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ビット

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

乗除算の注意 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 Ｃ処理系の多くで採用

べき乗（べき剰余の準備として） 入力：正整数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のビット数）

べき剰余 入力：正整数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 だから

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も成立し，ディジタル署名で利用される

最大公約数 「互助法」ではない 入力：正整数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

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

拡張ユークリッドの互除法 入力：正整数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

拡張ユークリッドの互除法の応用 入力：正整数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）