q q 情報セキュリティ 第８回：２００４年５月２８日（金） の補足 q q

この補足スライドの目的 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ビット

「正整数m」と「% m」を 削除すれば，これは べき剰余 入力：正整数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」と「% m」を 削除すれば，これは ab を求める アルゴリズムである．

乱数生成 乱数生成法 乱数の種（seed）について C言語なら，random関数が手軽 メルセンヌツイスターを使用するのもよい 自作の乱数生成アルゴリズムは，自作の暗号アルゴリズムと同じく，良いものはできない 乱数の種（seed）について 種とは，生成する乱数の順番（「乱数系列」という）を指定する方法のこと 同じ種を与えれば，同じ乱数系列を生成する 実行のたびに異なる乱数がほしいときは，現在時刻の情報をもとに種を作ることが多い random関数に対しては，srandom関数で種を設定する

素数生成 入力：ビット数N 出力：Nビットの素数 アルゴリズム Step 1. 最上位が1，間は（N-2回の1ビット乱数生成により）N-2ビットの乱数，最下位は1となるような，Nビットの整数nをランダムに生成する． Step 2. nが素数であるかどうかを判定する．素数でないと判定されたら，Step 1に戻る． Step 3. nを出力して終了する．

素数判定 入力：2以上の整数n，テスト回数T 出力：nが素数なら「yes」，素数でないなら「no」 アルゴリズム（フェルマーテスト） Step 1. i←1とする． Step 2. 2以上n未満の正整数aをランダムに生成する． Step 3. gcd(a,n)>1ならば，Step 7に進む． Step 4. an-1%n≠1ならば， Step 7に進む． Step 5. i←i+1とする．i≦Tならば，Step 2に戻る． Step 6. 「yes」と出力して終了する． Step 7. 「no」と出力して終了する． うまくいく? 素数であれば必ず「yes」と出力するが，素数でないのに誤って「yes」を出力することもある．

最大公約数 入力：正整数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-t*q), w←u-v*q とする． Step 3. r=0ならば，Step 5へ進む． Step 4. s←t, t←r, u←v, v←w として，Step 1へ戻る． Step 5. (t-b*v)/a, v を出力して終了する． 例 a=1440, b=50のとき，x=-1, y=29．実際， 1440*(-1)+5*290 = 10 = gcd(1440,50) である． なぜこれでうまくいくのか？ b*v % a = t だから

拡張ユークリッドの互助法の応用 入力：正整数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のとき，29を出力する．実際， 5*29 % 144 = 145 % 144 = 1である． Step 1では，a と n が 互いに素でない場合の 例外処理をしている． （互いに素 ⇔ gcd(a,n)=1）