情報セキュリティ: 2006年5月19日

q
q
情報セキュリティ
第５回：２００６年５月１９日（金）
q
q
本日学ぶこと



鍵の管理
公開鍵暗号
RSA暗号アルゴリズム
2
本日の授業で学ぶ語句







鍵配送問題，鍵の事前共有
公開鍵暗号，公開鍵，プライベート鍵，鍵ペア
RSA
数論アルゴリズム，べき剰余，拡張ユークリッドの互除法
対称暗号で鍵の事前共有をすると，鍵の数は O（ｎ2）
公開鍵暗号なら，O（ｎ）
RSAは暗号化も復号も，べき剰余
3
対称暗号をどう使う？


共通鍵暗号は，暗号化の鍵＝復号の鍵
鍵はいくつ必要？
q
q
q
q
q
q
２人なら１個
３人ならそれぞれ２個，全体で３個
４人ならそれぞれ３個，全体で６個
n人ならそれぞれn-1個，全体でn(n-1)/2個
1000人ならそれぞれ999個，全体で約50万個
新規加入者は（それまでの）人数分の相異なる鍵を作って
配布しないといけない…できる？？
4
公開鍵暗号の特徴（１）

管理すべき鍵の個数を減らせる
q
n人ならそれぞれ1組，全体でn組
5
公開鍵暗号の特徴（２）

鍵一つあたりのビット長は長くなる
q
処理時間もかかる
暗号アルゴリズム
種類
鍵長
ブロック長
DES
対称
56
64
トリプルDES
対称
112, 168
64
AES
対称
128, 192, 256
128
RSA
公開鍵
512～2048
≦鍵長
楕円曲線暗号
公開鍵
160～256
≦鍵長
6
RSAを支えるもの

アルゴリズム
q
q
q
q

整数に対する加減乗除，剰余，べき剰余
ユークリッドの互除法とその拡張
少し先
乱数生成
素数判定
安全性
q
q
素因数分解
離散対数問題
次回
暗号化・復
号
鍵生成
7
アルゴリズムの書き方・読み方


「入力」「出力」「手順（アルゴリズム）」の順に書く．
代入と比較を区別する．
q
q


手順では適切に番号を振り，「…へ進む」「…へ戻る」という
形でジャンプ先を明記する．
処理を終えるときは「…を出力して終了する」と書く．
q

このスライドでは「←」と「=」
C言語では「=」と「==」
「…を出力する」のみだと，まだ終了しないと考える．
書く人は簡単に検証できる例を添えておく．
読む人は最低限，その例でうまくいくことを確認する．
8
整数に対する加減乗除と剰余

加算
q
q

q

q
q

入力：整数x, y
出力：x-y
入力：整数x, y
出力：x*y
除算
q
q
剰余
q
乗算
q

入力：整数x, y
出力：x+y
減算
q

入力：整数x, y (y＞0)
出力：x/y （xをyで割った商）
入力：整数x, y (y＞0)
出力：x%y (xをyで割った余り)
注意点
q
q
いずれも自明なのでアルゴリズ
ムは省略
x, yがともにNビットのとき
 加減算の結果は
最大N+1ビット
 乗算の結果は最大2Nビット
 除算と剰余の結果は
最大Nビット
9
modについて

このスライドでは字数を減らすため，剰余の演算子には「%」
を使用している．
q
q


「mod」で書くのが一般的．
「モッド」または「モジュロ」と読む．
このスライド，および教科書では，もっぱら２項演算子として
使用している．
２項関係としてmodを使う本も多い．
q
例： 5≡-1 (mod 2)
 「5 合同 -1 モッド 2」または「5 合同 -1 モジュロ 2」と読む．
 この式は「5 % 2 = -1 % 2」，「5-(-1) が 2 で割り切れる」，
「5-(-1)=2k を満たす整数 k が存在する」と同値．
10
乗除算の注意


5を2で割ったとき，商は2，余りは1
-5 を2で割ったときの商と余りは?
q
q

商と剰余の基本要件
q
q

候補１：商は-2，余りは-1
候補２：商は-3，余りは1
-6
-5
-4
-3
-2
-1
0
aをbで割ったときの商が q，余りが r のとき，a = q * b + r
0≦|r|＜|b|
商と剰余の追加要件
q
q
a = q * b + r ⇔ (-a) = (-q) * b + (-r)．すなわち余りの符号は
除数と被除数に依存する．
Ｃ処理系の多くで採用
b>0 のときは 0≦r＜b．すなわち余りは常に非負．
RSAの計算では
を採用
11
べき乗（べき剰余の準備として）



入力：正整数a，非負整数b
出力：ab
アルゴリズム
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 とする．
Step 4. s ← s*s, t ← t / 2 とし，Step 2へ戻る．
Step 5. r を出力して終了する．
例
q

「%2」と「/2」の計算は，
ビット演算を使用する！
a=3, b=10 のとき， ab= 38×32=59049
計算効率は？
q
乗算回数は最大で 2×（bのビット数）
12
べき剰余



入力：正整数a，非負整数b，正整数m
出力：ab % mとなる整数値
アルゴリズム
q
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 を出力して終了する．
a=225, b=29, m=323 のとき， ab % m=123
なぜこれでうまくいくのか？
q
(x * y) % m = (x % m) * (y % m) % m だから
13
RSA暗号アルゴリズム

暗号化
q
q
q

復号
q
q
q

平文：整数M （0≦M＜N）
公開鍵：整数E，N
暗号化： C=ME%N
暗号文：整数C （0≦C＜N）
プライベート鍵：整数D，N
復号： M=CD%N
暗号化と復号の関係
q
q
任意の平文M （0≦M＜N）に対して，(ME%N)D%N=M
(MD%N)E%N=Mも成立し，ディジタル署名で利用される
14
最大公約数



入力：正整数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
15
最小公倍数


入力：正整数a, b
出力：最小公倍数 lcm(a,b) = a * b / gcd(a,b)
16
拡張ユークリッドの互除法



入力：正整数a, b
出力：a*x+b*y=gcd(a,b)を満たす整数x, y
アルゴリズム
q
q
q
q
q


s,t は常に正
q,r は非負
u,v,w は負も取り得る
いずれも常に整数
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 を出力して終了する．
gcd(a,b) = t
y=v
例
q
一般に無限個ある中の
１組
a=1440, b=50のとき，x=-1, y=29．実際，
1440*(-1)+50*29 = 10 = gcd(1440,50) である．
なぜこれでうまくいくのか？
q
b*v % a = t % aだから
17
拡張ユークリッドの互除法の応用



入力：正整数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
「nを法とするaの逆数」
ともいう．a, n から一意
に定まる．
a=5, n=144のとき，b=29．実際，
5*29 % 144 = 145 % 144 = 1である．
18

Download Report