情報セキュリティ 第５回 ２０１４年５月９日（金） 1/24 本日学ぶこと 本日の授業を通じて 鍵の管理に着目して，対称暗号と公開鍵暗号の違いを理解し ます． 公開鍵暗号のうち，RSA暗号アルゴリズムについて，暗号化・ 復号・鍵生成の方法を学びます． RSAを支える数論アルゴリズムとして，「べき剰余」と「拡張 ユークリッドの互除法」を学びます． 2 対称暗号をどう使う？ 対称暗号（共通鍵暗号）は，暗号化の鍵＝復号の鍵 鍵はいくつ必要？ ２人なら１個 ３人ならそれぞれ２個，全体で３個 ４人ならそれぞれ３個，全体で６個 n人ならそれぞれn-1個， 全体でn(n-1)/2 = O(n2)個 1000人ならそれぞれ999個，全体で約50万個 新規加入者は（それまでの）人数分の相異なる鍵を作って 配布しないといけない…できる？？ 3 公開鍵暗号の特徴（１） 暗号化鍵は公開し，復号鍵を秘密にする 管理すべき鍵の個数を減らせる n人ならそれぞれ1組，全体でn = O(n) 組 4 公開鍵暗号の特徴（２） 鍵一つあたりのビット長は長くなる 処理時間もかかる 暗号アルゴリズム 種類 鍵長 ブロック長 DES 対称 56 64 トリプルDES 対称 112, 168 64 AES 対称 128, 192, 256 128 RSA 公開鍵 2048～ ≦鍵長 楕円曲線暗号 公開鍵 160～256 ≦鍵長 5 RSA・公開鍵暗号を支えるもの アルゴリズム 安全性 整数に対する加減乗除，剰余，べき剰余 ユークリッドの互除法とその拡張 少し先 乱数生成 素数判定 素因数分解 離散対数問題 次回 暗号化・復号 鍵生成 RSAの暗号アルゴリズムは整数値を対象とするが， 計算機で扱うためのフォーマットなどは， PKCS (Public Key Cryptography Standards)が有名 6 アルゴリズムの書き方・読み方 「入力」「出力」「手順（アルゴリズム）」の順に書く． 代入と比較を区別する． 手順では適切に番号を振り，「…へ進む」「…へ戻る」という 形でジャンプ先を明記する． 処理を終えるときは「…を出力して終了する」と書く． このスライドでは「←」と「=」 C言語では「=」と「==」 「…を出力する」のみだと，まだ終了しないと考える． 書く人は簡単に検証できる例を添えておく． 読む人は最低限，その例でうまくいくことを確認する． 7 整数に対する加減乗除と剰余 加算 入力：整数x, y 出力：x-y 入力：整数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ビット 8 剰余演算子 この授業では字数を減らすため，剰余演算子には「%」を使 用している． 「mod」と書くのが一般的．「モッド」または「モジュロ」と読む． もっぱら２項演算子として使用しているが，２項関係として modを使う本もある． 例： 5≡-1 (mod 2) 「5 合同 -1 モッド 2」または「5 合同 -1 モジュロ 2」と読む． この式は「5 % 2 = -1 % 2」，「5-(-1) が 2 で割り切れる」， 「5-(-1)=2k を満たす整数 k が存在する」と同値． 9 乗除算の注意（１） 5を3で割ったとき，商は1，余りは2 -5を3で割ったときの商と余りは? 候補１：商は-1，余りは-2 候補２：商は-2，余りは1 -6 候補１の剰余 0 -5 -4 -3 -2 -1 0 候補２の剰余 0 -2 1 -1 2 0 0 -2 1 -1 2 0 0 1 1 2 2 0 0 1 1 2 2 0 0 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 被除数 10 乗除算の注意（２） 商と剰余の基本要件 商と剰余の追加要件 a を b で割ったときの商が q，余りが r のとき， a=q*b+r aが負で bが正なら 0≦|r|＜|b| a % bは0または負 a = q * b + r ⇔ (-a) = (-q) * b + (-r)． すなわち余りの符号は除数と被除数に依存する． 演習室環境を含め，多くのC処理系で採用されている． b>0 のときは 0≦r＜b．すなわち余りは常に非負． 整数論やRSA暗号アルゴリズムでは，こちらを用いる． プログラムで常に非負の余りを得るには (a % b + b) % b により求められる． 割り切れない場合には a % b + b でよい． 11 べき乗（べき剰余の準備として） 入力：正整数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 を出力して終了する． 例 「%2」と「/2」の計算は， ビット演算を使用する！ a=3, b=10 のとき， ab= 38×32=59049 計算効率は？ 乗算回数は最大で 2×（bのビット数） 12 べき剰余 入力：正整数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=3, b=10, m=7 のとき， ab % m=4 (x * y) % m = (x % m) * (y % m) % m に注意 13 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も成立し，ディジタル署名で利用される 14 RSA鍵生成 入力：鍵長b 出力：暗号化鍵と復号鍵のペア（N, E, D） アルゴリズム Step 1. b/2ビットの２つの素数p, qをランダムに生成し， N←p*q とする． Step 2. (p-1) と (q-1)の最小公倍数をLとする． Step 3. 1<E<L かつLと互いに素な整数Eをランダムに生成す る． Step 4. E*D % L = 1 および 1<D<L を満たすDを求める． Step 5. (N, E, D)を出力して終了する． 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 aとbは互いに素 16 最小公倍数 入力：正整数a, b 出力：最小公倍数 lcm(a,b) = a * b / gcd(a,b) 17 拡張ユークリッドの互除法 入力：正整数a, b 出力：a*x+b*y=gcd(a,b)を満たす整数x, y アルゴリズム 変数はすべて 整数値をとる さらにq,r は非負 Step 1. x←1, x’←0 , y←0, y’←1, r←a, r’←b とする． Step 2. q←r/r’, r’’←r%r’（=r-q*r’）, x’’←x-q*x’, y’’←y-q*y’ とす る． Step 3. r’’=0ならば，Step 5へ進む． Step 4. x←x’, x’←x’’, y←y’, y’←y’’ , r←r’, r’←r’’ として， Step 2へ戻る． Step 5. x’, y’ を出力して終了する． 例 一般に無限個ある中の １組 a=1440, b=50のとき，x=-1, y=29． Step 2開始時に必ず a*x + b*y = r が成立する． 18 拡張ユークリッドの互除法の応用 入力：正整数a, n 出力：a*b % n = 1, 0<b<n を満たす整数b 考え方： a*b % n = 1 ⇔ ∃m a*b+n*m=1 アルゴリズム Step 1. gcd(a,n)>1ならば，「解なし」を出力して終了する． Step 2. a, nを入力として拡張ユークリッドの互除法を適用し， その出力をx, yに代入する． Step 3. x%n を出力して終了する． Step 1では，a と n が 例 「nを法とするaの逆数」 ともいう．a, n から一意 に定まる． a=5, n=144のとき，b=29．実際， 5*29 % 144 = 145 % 144 = 1である． 互いに素でない場合の 例外処理をしている． （互いに素 ⇔ gcd(a,n)=1） 19 数論アルゴリズムの計算例（１） 310 % 7 は？ 初期化： a = 3, b = 10, m = 7, r ← 1, s ← a = 3, t ← b = 10 反復： t が奇数のとき r ← r * s % m t の偶奇に関係なく，s ← s * s % m, t ← t / 2 t=0 と同じ行の r の値が解（以下の表では，4） r 1 ↓ s 3 2 t 10 5 2 ↓ 4 4 2 2 1 0 20 数論アルゴリズムの計算例（２） 1440x + 50y = gcd(1440, 50) を満たす整数x, yは？ x y r q 1 0 1440 0 1 50 1 -28 40 28 -1 29 10 1 5 -144 0 4 r=0 の一つ前の行より，x=-1, y=29が解となる．実際， 1440*(-1)+50*29=10 である． 各行において 1440x+50y=r が成立し，検算に役立つ． 21 検算の方法 Linuxが使えるなら，bcコマンドが便利 echo '3 ^ 10 % 7' | bc echo '1440 * -1 + 50 * 29' | bc 計算機が使えない場合，目で危なそうな箇所をチェック べき剰余 r の更新と s の更新を間違えていないか？ t の最後は…→1→0になっているか？ 拡張ユークリッドの互除法 すべて整数になっているか？ 最初の2行を除き，x と y の一方が正，もう一方が負になっ ているか？ 各行で a*x+b*y=r （a, bは固定，x, y, rは変化）が成り立つ か？ 22 自習用の課題 117 % 13は？ 194x + 37y = 1 を満たす整数(x,y)は？ 104x % 231 = 1 を満たす整数xは？ 104x + 231y = 1と変形して求める 23 本日のまとめテスト ① 以下の下線部を訂正しなさい． RSAは，暗号化も復号も べき乗 により計算する． ② 「O(n2)」といったオーダーの表記について，知っていること を書きなさい． 過去に（この授業以外で）学んだことを書くこと． 授業メモに記入して提出すること． 24 E
© Copyright 2024 ExpyDoc
