- 14 名前：１３２人目の素数さん [04/06/27 17:27]
- >>10>>12
具体的に、有名な例を3つ挙げると、
RSA暗号：素数p, qを取り、M=pqとし、sをφ(M)=(p-1)(q-1)と互いに素な整数とする。
このとき、s*t≡1(mod φ(M))となる整数tが存在する。そして、
m=n^sならばm^t≡n^{st}≡n(mod M)が成り立つが、Mとsからtを計算するのは難しい
（Mを素因数分解すればφ(M)が計算できるが、これが難しい為）。
そこで(M, s)を公開しておけば、誰でもm=n^sによってn(mod M)を暗号化できるが、
tを知らなければ復号するのは難しくなるという仕組み。
離散対数暗号：素数pと(g, p)となる整数g, および任意の整数xをとる。外部には
pおよび(g, g^x)(mod p)を公開する。g, g^xをそれぞれs乗することでg^s, g^{sx}を
得ることができ、これから任意の整数n≠0に対して(n*g^{sx}, g^s)(mod p)を簡単に得ることが
できる。これを送信する。xを知っていれば、n*g^{sx}*(g^s)^{-x}=nなので簡単にnを得ることが出来るし、
sを知っていればn*g^{sx}*(g^x)^{-s}=nなのでやはり簡単にnを得ることが出来るが、
公開された情報(p, g, g^x)および送信された情報(n*g^{sx}, g^s)からsやxを得るのは
難しいので、復号が難しいという仕組み。
一般に(g, g^s)(mod p)から、sを求める問題を離散対数問題という。
もっとも最近は準指数時間でこの問題を解くアルゴリズムが出来ている。
Elgamal暗号：上記の離散対数暗号がZ/pZの乗法群を用いたのに対し、
有限体上の楕円曲線の点のなす群を用いる暗号。特殊な曲線を除いては、
この暗号を破る効率的なアルゴリズムは知られていない。
|
 |
