公開鍵暗号系 2011/05/09 公開鍵暗号 • Diffie Hellman 鍵共有理論 1976 • 1978年R. L. Rivest, A. Shamir, L. M. Adleman • 実際には英国が最初に開発 GCHQ James Ellis 1969 Cliford Coks 1973 特徴 暗号化に必要な公開鍵 複合化に必要な秘密鍵 公開鍵と暗号化プロセス、複合化プロセスが分かってい ても、秘密鍵を見つけるのは困難 RSA暗号の原理 • 素因数分解を応用 概念 素数p、qの積nは簡単に計算でき るが、nからp、qを計算するのは困 難 素因数分解の例 p = 9010279，q = 9623083 n = p ×q = 86706662670157 剰余 nをmで割った余りを m mod nと書く a1 mod n = b1 , a2 mod n =b2 とすると a1 a2 ≡ b1b2 mod n a1 +a2 ≡ b1+b2 mod n Eulerの関数 • ある整数nに対し、1からn-1の整数でnと互い に素な整数の個数 • 特にnが素数pの場合、Φ(p)＝p-1 例） 8と互いに素な整数 1,3,5,7 よってΦ(8)=4 5と互いに素な整数 1,2,3,4 よってΦ(5)=4 Eulerの定理・Fermatの小定理 • ｒとnが互いに素な場合 ｒΦ(n)≡1 mod n 特にnが素数pの場合 (Fermatの小定理） p-1 ｒ ≡１ mod p Eulerの定理 • p、qを素数とすると Φ(pq)= Φ(p)Φ(q)= (p-1)(q-1) 例） p=61,q=53 pq=61x53=3233 Φ(3233)=Φ(61-1)Φ(53-1)=3120 一次合同式 • １次合同式 ax ≡ b mod m が解xを持つ 必要十分条件 → a と m の最大公約数 gcd(a, m) が， b を割り切れる • １次合同式 ax ≡ 1 mod m が解xを持つ 必要十分条件 → a と m が互いに素である 逆元の存在 • gcd(a, m) = 1 となるとき，１次合同式 ax ≡ 1 mod m の解xが m を法にして唯１つ存 在する その x を m を法とする a の逆元という • gcd(c, m) = 1 とすると，ca ≡ cb mod m なら ば， a ≡ b mod mとなる RSA暗号の根拠 • ｎを相異なる素数ｐ，ｑ の積 • ｅ を gcd(e,φ(ｎ))=1 となる正整数 このとき ed≡ 1 mod Φ(n)なる dが存在し ed≡ 1 mod Φ(p)Φ(q) ≡ 1 mod (p-1)(q-1) かつ xed≡x mod ｎ n,ｄが公開鍵、eが秘密鍵となる 数学的根拠 x(p-1)を考える x(p-1)(q-1)≡1 mod q x(q-1)を考える x(q-1)(p-1)≡ 1 mod p x(q-1)(p-1)≡ 1 mod pq ≡1 mod n 数学的根拠 ed ≡ 1 mod Φ(n) ≡ 1 mod Φ(p)Φ(q) であるから ed=1 +f(p-1)(q-1) xed=xxf(p-1)(q-1) xed ≡ x mod n 暗号化 AがBに暗号文を送る場合 • aを暗号化するべき数 • AはBの公開鍵ｄ、ｎを使い b=ad mod n を計算する（暗号化) ・bを相手に伝える 複合化 BはAから受け取った暗号文を複合する場合 Bは自分の秘密eを用い ｂe を計算する(複合化） be=(ad)e=ade＝a mod n≡a RSA暗号の基礎 • b,nを知っているだけでは複合化に必要なdを 知るのは困難 • nを素因数分解する必要がある • 実際には、複数の素数の積が使われる 素因数分解の困難さ 2009年 232桁 768bit RSA 300桁 1024bit 参考文献・URL • 暗号解読 サイモン・シン 新潮出版 ISBN4-10-539302 ・http://www.math.kobe-u.ac.jp/~taka/asirbook-html/main/node94.html
© Copyright 2024 ExpyDoc
