べき乗演算
任意の整数abおよび1より大きい自然数nに対して、a^bをnで割った余りを求めることを、nを法にしたべき乗演算という。
この時
a^b≡r(mod n)
が成立する。
b=b1+b2+b3------bmと分解されるとき
a^b1≡r1(mod n)
a^b2≡r2(mod n)
a^b3≡r3(mod n)
a^b4≡r4(mod n)
・・・・
a^bm≡rm(mod n)
であったりしたら、
a^b=a^b1*a^b2・・・・・・・a^bm≡r1*r2*r3・・・rm(mod n)
b=b1*b2*********bmと分解されるときは
a^b1≡r1(mod n)
a^b2≡r2(mod n)
a^b3≡r3(mod n)
・・・・
a^bk≡rk(mod n)
であったりしたら、
a^b=((((------((a^b1)^b2)-----))))^bm≡rm(mod n)
ex.
7^1000≡1^(1+1+++++++1)≡1(mod 6)
さらに整数bを
b=bm*2^m + bm-1^m-1 +++++++ b1*2^1
=(bm,bm-1,,,,,,,b1,b0),∀bi,∈{0,1}
↑さすがにカッコをつけようと思ったが・・・まあ、自分がわかれば大丈夫だ、問題ない。
と2進数表記した場合について、b1=1であるすべてのiに対して
a^2^i≡r1(mod n)
を予め計算しておけば、これを用いて以下のように計算できる。
a^b=(a^2^n)^bn * (a^2^n-1)bn-1 *********(a2^2^1)^b1*a^b0
≡rn*rn-1*****r1 * a^b0(mod n)
ex.
8^103(mod 13)=8^12^8 * 8^7
≡8^7(mod 13) = 8^3^2*8
≡5^2 * 8(mod 13) ≡ 5(mod 13)
101^659(mod 1237)
659＝(1010010011)と2進数表記できることから
101^2^9≡750(mod 1237)
101^2^7≡750(mod 1237)
101^2^4≡750(mod 1237)
101^2≡750(mod 1237)
が得られる。したがって以下のように計算できる。
101^659=(101^2^9)(101^2^7)(101^2^4)(101^2)101
≡750*991*683*305*101(mod 1237)
≡90(mod 1237)
離散対数問題と鍵暗号
Gを位数|G|が有限な巡回群とする。この時、与えられたGの生成元gとh∈Gに対して、g^x=hとなる整数xの事をgをそこにするhの離散対数といい、上記の問題を離散対数問題という。
現在においてはい数が300桁（1024ビット）以上であれば、効率的にとくことは難しいとされている。
有限体Fqの加法単位元0以外の元からなる集合Fq*は乗法にかんしても巡回群となることが知られている。
送信者と受信者が共通の秘密鍵を用いて乗法のやりとりをする場合、予め送信者と受信者が同じ鍵を共有しておく必要がある。
そのために、盗聴の可能性がある危険な通信路において、両者が安全に共通鍵をやり取りする方法について考える。
Ka：Aが定めた整数（乱数）、Aが秘密情報として保持（秘密鍵）
Kb：Bが定めた整数（乱数）、Bが秘密情報として保持（秘密鍵）
g^Ka≡ca(mod p):Aが送信する情報（公開鍵）
g^Kb≡cb(mod p):Bが送信する情報（公開鍵）
この時、次の手順により各々が共通鍵を取得することが出来る。
1) Aは秘密鍵KaとBの公開鍵g^Kbを用いて
cb^Kb≡g^Kb^Ka≡g^KaKb≡Kab(mod p)
2) Bは秘密鍵KbとAの公開鍵g^Kaを用いて
ca^Ka≡g^Ka^Kb≡g^KaKb≡kab(mod p)
を計算する
3）1.2で求めたKabを共通鍵として各々が保持。
ここで、例えば盗聴者イブが共通鍵Kabを得るために、Aの公開鍵Caから、秘密鍵Kaを求めようとする場合について考えてみよう。結局このような目的を達成するには。
g^Ka≡ca(mod p)
を満たす整数Kaを求めることになるので、これは情報に関する巡回群Zp*上における離散対数門d内をとくことに他ならないことが分かる。
故にDiffie-Hell,am鍵共有(鍵交換)の安全性は離散対数問題の困難さに基づいていることが分かる。
現在のところ、安全性を確保するためには、離散対数問題と対応させて、300桁以上の素数ｐを用意する必要があるとされている。
Excelで作ったモデル、p=11ｗｗｗｗ
