8回目

情報セキュリティ
第８回
RSA暗号
脅威と暗号技術
セキュリティに対する脅威
盗聴
（秘密が漏れる）
脅かされる特性
暗号技術
共通鍵暗号
機密性
公開鍵暗号
改竄
（情報が書き換えられる）
正真性
一方向ハッシュ関数
なりすまし
（正しい送信者のふりをする）
認証
メッセージ認証コード
否認
（後から私じゃないと言う）
否認不可能性
デジタル署名
ユークリッドの互除法

ユークリッドの互除法とは


整数a,bの最大公約数gcd(a,b)
を求めるアルゴリズム
ユークリッドの互除法



互除法の例(gcd(10,7))
3=(10 mod 7)
0になるまで続ける
入力：整数a, b （a≧b >0）
出力：最大公約数gcd(a,b)
アルゴリズム：
0=(3 mod 1)

x←a, y←b
z=0
no
x←y, y←z
gcd(210,77)を互除法で解く
56=(210 mod 77)
21=(77 mod 56)
14=(56 mod 21)
7=(21 mod 14)
0=(14 mod 7)
以上から、gcd(210,77)=7
z = x mod y
yes
1=(7 mod 3)
割った数が
最大公約数
gcd(a,b) = y

約数を列挙して解く
210の約数： 1,2,3,5,6,7,10,14,15,21,
30,35,42,70,105,210
77の約数：1,7,11,77
以上から、gcd(210,77)=7
互除法の正しさ
aはbの倍数だから

以下を証明するすれば、互除法が正しいことが証明出来る：

0 = a mod b ⇒ gcd(a,b) = b

c = a mod b ⇒ gcd(a,b) = gcd(b,c)
互除法とgcdの関係
3=(10 mod 7)
gcd(10,7)
1=(7 mod 3)
=gcd(7,3)
0=(3 mod 1)
=gcd(3,1)
割った数が
最大公約数
c = a mod b ⇒ gcd(a,b)=gcd(b,c)
gcd(a,b)≧gcd(b,c)
c = a mod bより、a = qb + c と表すことが出来る
m=gcd(b,c) で割切れる
つまり、mはaとbの公約数（≦gcd(a,b))
gcd(a,b)≦gcd(b,c)
c = a mod bより、c = a - qb と表すことが出来る
m’=gcd(a,b) で割切れる
つまり、 m’はbとcの公約数（≦gcd(b,c))
拡張ユークリッドの互除法
入力
拡張ユークリッドの互除法
出力
整数a, b
但し、
a≧b >0
i←1
(a0,x0,y0) ← (a,1,0)
(a1,x1,y1) ← (b,0,1)
（d,x,y）
但し、
d = gcd(a,b)
d = ax+by
qi+1 = ai-1／ai
(ai+1,xi+1,yi+1)=(ai-1,xi-1,yi-1)－qi+1×(ai,xi,yi)
ai+1 = ai-1 mod ai
ai+1 = 0
no
yes
i ← i+1
(d,x,y)=(ai,xi,yi)
最大公約数dの
他にxとyを求める
拡張ユークリッドの互除法（例）
例： a=10, b=7の場合、d=10x+7yを満たす（d,x,y）を求める。
(ai, xi, yi) を ai = 10xi + 7yiと書くと等号が常に成立つ。
拡張ユークリッドの互除法の出力は、（d,x,y）=(1,-2,3)
i
0
1
2
3
4
qi
3=(10 mod 7)
1 (=10/7)
2 (=7/3)
3 (=3/1)
ai = 10xi + 7yi
10 = 10×1+7×0
7 = 10×0+7×1
3 = 10×1+7×(-1)
1 = 10×(-2)+7×3
0=0
a4 = a3 － 3×a4
= 0より、
アルゴリズム終了
10 = 10×1+7×0
－ 7×1 = (10×0+7×1)×1
初期設定
3 = 10×1+7×(-1)
初期設定
7 = 10×0+7×1
－ 3×2 = (10×1+7×(-1))×2
1 = 10×(-2)+7×3
x
d
y
1 = 10×(-2)+7×3
出力（d,x,y）=(1,-2,3)
拡張ユークリッドの互除法の正しさ
最大公約数の性質
d=gcd(a,b) ⇒ d=ax+byを満たす整数xとyが存在する
証明
拡張ユークリッドの互除法の中のaiの計算は、
ユークリッドの互除法と同じであるから、最終的
にai=d (=gcd(a,b))になる。
途中結果（ai = axi + byi ）の等号は、以下の理由
から常に成立つ。
1. 等式の両辺に同じ数（qi+1）を掛けている。
2. 等式の両辺から同じ数を引いている。
有限体ＧＦ（p）
 乗法逆元


 有限体GF(p)
ay≡1 (mod N)を満たすyをaの乗
法逆元と呼ぶ。
1/a mod N、又は a-1 mod Nと書く。


 定理A: ay≡1 (mod N)となるｙが
存在する ⇔ gcd(N,a)=1

 pが素数 ⇒ GF(p)は除算が可能
証明：最大公約数の性質から、
gcd(N,a)=1 ⇔ Nx+ay=1
⇔ ay≡1 (mod N)

 例（1/7 mod 10） = 3
拡張ユークリッド
互除法
gcd(10,7)=1
⇔ 10×(-2)+7×3=1
⇔ 7×3≡1 (mod 10)
 例 2/7 mod 10
（2/7 mod 10）
= (2×1/7 mod 10)
= (2×3 mod 10)
=6
0で割ることを除いて四則演算が自由に
できる系を「体」と呼ぶ。
pが素数ならばGF(p)={0,1,..,p-1}は要
素数がp個の体である。
Z*p定義 

証明： pが素数ならば、0を除く全ての
GF(p)の要素がZ*pの要素である。
任意のa∈Z*pに対してgcd(a,p)=1である
から、定理Aより、全てのa∈Z*pに対して
（1/a mod p）が存在する。
Z*p={a|1≦a≦p-1, gcd(a,p)=1}
pが素数⇒Z*p={1,2,..,p-1}
2×y≡1 (mod 6)
 例 Z*5={1,2,3,4}とZ*6={1,5}
2×3≡1 (mod 5) 
から(1/2 mod 5)=3



1/1 mod 5 = 1
1/2 mod 5 = 3
1/3 mod 5 = 2
1/4 mod 5 = 4
を満たすyが存在
しない。
1/1 mod 6 = 1
1/2 mod 6 =存在しない
1/3 mod 6 =存在しない
1/4 mod 6 =存在しない
1/5 mod 6 = 5
素因数分解
 素因数分解とは


与えられた整数Nに対して、
N=p1×p2×…×pn
を満たす素数p1,p2,…,pnを求め
ること。
RSAの場合、
N=p×q
を満たす二つの素数pとqを求め
ることができるかが問題である。
 素因数分解仮説

定理B：任意の整数aに対し、
ax≡a (mod p)が成立つ。但し、xは
x≡1 (mod (p-1))を満たし、pは素
数である。
（証明）

与えられた整数Nに対して、素
因数分解を求める効率的なア
ルゴリズムは見つけらないとす
る仮説。
つまり、a’∈Z*p
x≡1 (mod (p-1))より、x-1=q(p-1)と書
ける。
 フェルマーの定理より、任意のｙ∈Z*pに
対し、ｙp-1≡1 (mod p)。 a’∈Z ={0,1,..,p-1}
p
任意の整数aに対し、a’=(a mod p)と置く。
a’≠0ならば、
ax≡(a’)x≡(a’)q(p-1)+1≡a’≡a (mod p)となる。
一方、 a’=0ならば、
フェルマーの定理
(a)x≡a≡0 (mod p)。
以上から、 ax≡a (mod p)となる。

ＲＳＡ暗号

鍵生成



敵が素因数分解
（N=p×q）出来る
と秘密鍵dを簡単
に計算出来る。


受信者
二つの素数pとqを生成する。
gcd((p-1)(q-1),e)≡1を満たすeを選ぶ。
拡張ユークリッドの互除法から、
ed≡1(mod (p-1)(q-1))を満たすdを求める。
（定理Aより、必ず求まる。）
公開鍵Pk=(N,e)を公開し、秘密鍵Sk=dと
する。但し、N=pqである。
暗号化: C=me mod N
復号: m=Cd mod N
べき乗は計算量が多い。
高速なべき乗計算方法
は前授業参照。
（復号出来る理由）
ed≡1 (mod (p-1)(q-1)) から、ed-1はp-1で割切
れる。
定理Bより、Cd≡(me)d≡m (mod p)。
同様に、Cd≡m (mod q)。
つまり、Cd-mはpの倍数であり、かつqの倍数で
もあるから、N=p×qの倍数である。
従って、Cd-m≡0 (mod N)となる。
素数pとqを選択し、
ed≡1を満たすdを求める
鍵生成アルゴリズムG
PKを公開
Pk=(N,e)
Sk=d
送信者
平文
m
暗号化ア
ルゴリズ
ムE
Pk=(N,e)
暗号文
C
C=me mod N
受信者
暗号文
C
復元ア
ルゴリ
ズムD
Sk=d
平文
m
m=Cd mod N
ＲＳＡ暗号の安全性
 安全性
ＲＳＡ暗号は素因数分解の困難さに基づく
 素因数分解からpとqが分かると、秘密鍵dを計算出来る
 ＲＳＡ問題
e
 与えられた(N,e,C)から、C=m mod Nを満たすmを求める問題
 ＲＳＡ問題は素因数分解よりも易しいかもしれない。
 ＲＳＡ仮説
 ＲＳＡ問題を「効率的」に解くアルゴリズムは存在しない
 素数の選び方
 pとqはともに512ビット以上であることが望ましい
 pとqの条件
 p-1は大きな素因数rを有する
 p+1も大きな素因数を有する
 r-1も大きな素因数を有する


Download Report