情報セキュリティ: 2004年5月28日(金)

q
q
情報セキュリティ
第８回：２００４年５月２８日（金）
の補足
q
q
この補足スライドの目的


RSAに必要な計算を明確にし，教科書で割愛している箇所
を詳細に説明すること
アルゴリズムの書き方の一例を示すこと
q
ただしアルゴリズムを書き下す問題は試験に出さない
2
ＲＳＡに必要な計算






整数に対する加減乗除と剰余
べき剰余
乱数生成
素数生成および素数判定
最大公約数と最小公倍数
拡張ユークリッドの互助法
3
アルゴリズムの書き方・読み方


「入力」「出力」「手順（アルゴリズム）」の順に書く．
代入と比較を区別する．
q
q



ここでは「←」と「=」
C言語では「=」と「==」
手順では適切に番号を振り，「…へ進む」「…へ戻る」という
形でジャンプ先を明記する．
処理を終えるときは「…を出力して終了する」と書く．（「…を
出力する」のみだと，まだ終了しないと考える．）
書く人は簡単に検証できる例を添えておく．
読む人は最低限，その例でうまくいくことを確認する．
4
整数に対する加減乗除と剰余

加算
q
q

q

入力：整数x, y
出力：x-y
乗算
q
q

入力：整数x, y
出力：x+y
減算
q
入力：整数x, y
出力：x*y
除算
q
q

入力：整数x, y (y≠0)
出力：x/y （xをyで割った商）
剰余
q
q

入力：整数x, y (y≠0)
出力：x%y (xをyで割った余り)
注意点
q
q
いずれも自明なのでアルゴリズ
ムは省略
x, yがともにNビットのとき
 加減算の結果は
最大N+1ビット
 乗算の結果は最大2Nビット
 除算と剰余の結果は
最大Nビット
5
べき剰余



入力：正整数a，非負整数b，正整数m
出力：ab % mとなる整数値
アルゴリズム
q
q
q
q
q

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 を出力して終了する．
例
q

「正整数m」と「% m」を
削除すれば，これは
ab を求める
アルゴリズムである．
a=225, b=29, m=323 のとき， ab % m=123
なぜこれでうまくいくのか？
q
(x * y) % m = (x % m) * (y % m) だから
6
乱数生成

乱数生成法
q
q
q

C言語なら，random関数が手軽
メルセンヌツイスターを使用するのもよい
自作の乱数生成アルゴリズムは，自作の暗号アルゴリズムと同
じく，良いものはできない
乱数の種（seed）について
q
q
q
種とは，生成する乱数の順番（「乱数系列」という）を指定する方
法のこと
同じ種を与えれば，同じ乱数系列を生成する
 実行のたびに異なる乱数がほしいときは，現在時刻の情報
をもとに種を作ることが多い
random関数に対しては，srandom関数で種を設定する
7
素数生成



入力：ビット数N
出力：Nビットの素数
アルゴリズム
q
q
q
Step 1. 最上位が1，間は（N-2回の1ビット乱数生成により）N-2
ビットの乱数，最下位は1となるような，Nビットの整数nをランダ
ムに生成する．
Step 2. nが素数であるかどうかを判定する．素数でないと判定
されたら，Step 1に戻る．
Step 3. nを出力して終了する．
8
素数判定



入力：2以上の整数n，テスト回数T
出力：nが素数なら「yes」，素数でないなら「no」
アルゴリズム（フェルマーテスト）
q
q
q
q
q
q
q

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」と出力して終了する．
うまくいく?
q
素数であれば必ず「yes」と出力するが，素数でないのに誤って
「yes」を出力することもある．
9
最大公約数



入力：正整数a, b
出力：最大公約数 gcd(a,b)
アルゴリズム（ユークリッドの互助法）
q
q
q
q

Step 1. r←a%b とする．
Step 2. r=0ならば，Step 4へ進む．
Step 3. a←b, b←r として，Step 1へ戻る．
Step 4. bを出力して終了する．
例
q
a=144, b=5のとき，gcd(a,b)=1
10
最小公倍数


入力：正整数a, b
出力：最小公倍数 lcm(a,b) = a * b / gcd(a,b)
11
拡張ユークリッドの互助法



入力：正整数a, b
出力：a*x+b*y=gcd(a,b)を満たす整数x,y
アルゴリズム
q
q
q
q
q

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 を出力して終了する．
例
q

一般に無限個ある中の
１組
a=1440, b=50のとき，x=-1, y=29．実際，
1440*(-1)+5*290 = 10 = gcd(1440,50) である．
なぜこれでうまくいくのか？
q
b*v % a = t だから
12
拡張ユークリッドの互助法の応用
a, n から一意に定まる



入力：正整数a, n
出力：a*b % n = 1, 0<b<n を満たす整数b
アルゴリズム
q
q
q

Step 1. gcd(a,n)>1ならば，「解なし」を出力して終了する．
Step 2. a, nを入力として拡張ユークリッドの互助法を呼び出し，
その出力をx, yに代入する．
Step 1では，a と n が
Step 3. x%n を出力して終了する．
互いに素でない場合の
例外処理をしている．
（互いに素 ⇔ gcd(a,n)=1）
例
q
a=5, n=144のとき，29を出力する．実際，
5*29 % 144 = 145 % 144 = 1である．
13

Download Report