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

本日学ぶこと RSAのアルゴリズム RSAの安全性 暗号アルゴリズムのその他の話題 剰余演算，べき剰余 ユークリッドの互助法とその拡張 素数判定 RSAの安全性 素因数分解 離散対数問題 暗号アルゴリズムのその他の話題 ハイブリッド暗号 ブロック暗号モード 次回

本日のスライドで理解してほしいこと 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 だから

最大公約数 入力：正整数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だから 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）

効率の良いアルゴリズム・悪いアルゴリズム 処理時間が，入力の値のビット数 L と適当な定数 C,k を 用いて C・Lk で抑えられるならば，効率が良い． 多項式時間アルゴリズムと呼ばれる． 処理時間が，入力の値に比例するならば，効率が悪い． 例１：a % m, a2 % m, …, ab % m の順にべき剰余を求める． 例２： a*b % n = 1 を満たす整数 b を，b←1, 2, … と順に 代入して求める． 入力の値のビット数を L とすると，2L に比例するため， 指数時間アルゴリズムと呼ばれる．