q
q
情報セキュリティ
第8回:2004年5月28日(金)
の補足
q
q
この補足スライドの目的


RSAに必要な計算を明確にし,教科書で割愛している箇所
を詳細に説明すること
アルゴリズムの書き方の一例を示すこと
q
ただしアルゴリズムを書き下す問題は試験に出さない
2
RSAに必要な計算






整数に対する加減乗除と剰余
べき剰余
乱数生成
素数生成および素数判定
最大公約数と最小公倍数
拡張ユークリッドの互助法
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

一般に無限個ある中の
1組
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
ダウンロード

PPT