情報セキュリティ　 第８回 RSA暗号

脅威と暗号技術 セキュリティに対する脅威 脅かされる特性 暗号技術 共通鍵暗号 盗聴 （秘密が漏れる） 機密性 公開鍵暗号 改竄 セキュリティに対する脅威　　　　脅かされる特性　　　　　暗号技術 共通鍵暗号 盗聴 （秘密が漏れる） 機密性 公開鍵暗号 改竄 （情報が書き換えられる） 正真性 一方向ハッシュ関数 なりすまし （正しい送信者のふりをする） 認証 メッセージ認証コード 否認 （後から私じゃないと言う） 否認不可能性 デジタル署名

ユークリッドの互除法 ユークリッドの互除法とは ユークリッドの互除法 互除法の例(gcd(10,7)) 整数a,bの最大公約数gcd(a,b)を求めるアルゴリズム ユークリッドの互除法 入力：　整数a, b （a≧b >0） 出力：　最大公約数gcd(a,b) アルゴリズム： 互除法の例(gcd(10,7)) 3=(10 mod 7) 割った数が最大公約数 0になるまで続ける 1=(7 mod 3) 0=(3 mod 1) 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 約数を列挙して解く 210の約数： 1,2,3,5,6,7,10,14,15,21, 30,35,42,70,105,210 77の約数：1,7,11,77 x←a, y←b z = x mod y yes z = 0 gcd(a,b) = y no x←y, y←z

互除法の正しさ c = a mod b ⇒ gcd(a,b)=gcd(b,c) gcd(10,7) =gcd(7,3) =gcd(3,1) 以下を証明するすれば、互除法が正しいことが証明出来る： 0 = a mod b　⇒　gcd(a,b) = b c = a mod b　⇒　gcd(a,b) = gcd(b,c) c = a mod b ⇒ gcd(a,b)=gcd(b,c) 互除法とgcdの関係 gcd(a,b)≧gcd(b,c) 3=(10 mod 7) gcd(10,7) c = a mod bより、a = qb + c と表すことが出来る 1=(7 mod 3) =gcd(7,3) m=gcd(b,c) で割切れる 0=(3 mod 1) =gcd(3,1) つまり、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))

(ai+1,xi+1,yi+1)=(ai-1,xi-1,yi-1)－qi+1×(ai,xi,yi) 拡張ユークリッドの互除法 入力 拡張ユークリッドの互除法 出力 整数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 最大公約数dの 他にxとyを求める (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 yes no i ← i+1 (d,x,y)=(ai,xi,yi)

拡張ユークリッドの互除法（例） 例： a=10, b=7の場合、d=10x+7yを満たす（d,x,y） を求める。 (ai, xi, yi) を ai = 10xi + 7yiと書くと等号が常に成立つ。 拡張ユークリッドの互除法の出力は、（d,x,y）=(1,-2,3) 10 = 10×1+7×0 i 　　 qi 　ai = 10xi + 7yi － 7×1 = (10×0+7×1)×1 1 2 3 4 1 (=10/7) 2 (=7/3) 3 (=3/1) 10 = 10×1+7×0 　7 = 10×0+7×1 　3 = 10×1+7×(-1) 　1 = 10×(-2)+7×3 　0 = 0 初期設定 3 = 10×1+7×(-1) 3=(10 mod 7) 初期設定 7 = 10×0+7×1 － 3×2 = (10×1+7×(-1))×2 1 = 10×(-2)+7×3 a4 = a3 － 3×a4 = 0より、 アルゴリズム終了 x y d 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 ）の等号は、以下の理由 　から常に成立つ。 等式の両辺に同じ数（qi+1）を掛けている。 等式の両辺から同じ数を引いている。

有限体ＧＦ（p） 乗法逆元 有限体GF(p) pが素数 ⇒ GF(p)は除算が可能 gcd(10,7)=1 ay≡1 (mod N)を満たすyをaの乗法逆元と呼ぶ。 1/a mod N、又は a-1 mod Nと書く。 定理A: ay≡1 (mod N)となるｙが　　存在する　⇔　gcd(N,a)=1 証明：最大公約数の性質から、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 有限体GF(p) 0で割ることを除いて四則演算が自由にできる系を「体」と呼ぶ。 pが素数ならばGF(p)={0,1,..,p-1}は要素数がp個の体である。 pが素数 ⇒ GF(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} 例　Z*5={1,2,3,4}とZ*6={1,5} 1/1 mod 5 = 1 1/1 mod 6 = 1 1/2 mod 5 = 3 1/2 mod 6 =存在しない 1/3 mod 5 = 2　1/3 mod 6 =存在しない 1/4 mod 5 = 4 1/4 mod 6 =存在しない 1/5 mod 6 = 5 Z*p定義 拡張ユークリッド互除法 2×y≡1 (mod 6) を満たすyが存在しない。 2×3≡1 (mod 5) から(1/2 mod 5)=3

素因数分解 素因数分解とは 素因数分解仮説 定理B： 任意の整数aに対し、 与えられた整数Nに対して、 N=p1×p2×…×pn を満たす素数p1,p2,…,pnを求めること。 RSAの場合、 N=p×q を満たす二つの素数pとqを求めることができるかが問題である。 素因数分解仮説 与えられた整数Nに対して、素因数分解を求める効率的なアルゴリズムは見つけらないとする仮説。 定理B： 任意の整数aに対し、　 ax≡a (mod p)が成立つ。但し、xはx≡1 (mod (p-1))を満たし、pは素数である。 （証明） x≡1 (mod (p-1))より、x-1=q(p-1)と書ける。 フェルマーの定理より、任意のｙ∈Z*pに対し、ｙp-1≡1 (mod 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)となる。 a’∈Zp={0,1,..,p-1} フェルマーの定理 つまり、a’∈Z*p

ＲＳＡ暗号 鍵生成 受信者 暗号化: C=me mod N 復号: m=Cd mod N 送信者 受信者 二つの素数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を求める PKを公開 Pk=(N,e) Sk=d 敵が素因数分解（N=p×q）出来ると秘密鍵dを簡単に計算出来る。 鍵生成アルゴリズムG 送信者 暗号化アルゴリズムE べき乗は計算量が多い。高速なべき乗計算方法は前授業参照。 平文m 暗号文C C=me mod N Pk=(N,e) 受信者 復元アルゴリズムD 暗号文C 平文m m=Cd mod N Sk=d

ＲＳＡ暗号の安全性 安全性 ＲＳＡ暗号は素因数分解の困難さに基づく 素因数分解からpとqが分かると、秘密鍵dを計算出来る ＲＳＡ問題 与えられた(N,e,C)から、C=me mod Nを満たすmを求める問題 ＲＳＡ問題は素因数分解よりも易しいかもしれない。 ＲＳＡ仮説 ＲＳＡ問題を「効率的」に解くアルゴリズムは存在しない 素数の選び方 pとqはともに512ビット以上であることが望ましい pとqの条件 p-1は大きな素因数rを有する p+1も大きな素因数を有する r-1も大きな素因数を有する