公開鍵暗号講座

Revised : 2006/02/26
Since : 2006/02/25

RSA（Rivest Shamir Adleman）

２つの大きな素数の積を素因数分解することが困難であることに基づく公開鍵暗号である。

今、BさんからAさんに暗号文を送る場合を考えると、Aさんは送り先で、Bさんは送り主となる。
まず初めにAさんは、pとqを大きな素数で決める。（素数は小さいと暗号強度が弱くなり大きいと計算に時間がかかる）

（１）　Aさんは、p,qを大きな素数とし、n = pq とおき、Z/(p-1)(q-1)Zの(p-1)(q-1)と互いに素な自然数Eをランダムに選ぶ。
　　　　gcd(E , (p-1)(q-1)) = 1　　　(gcd:Greatest Common Divisor 最大公約数)
（２）　ED ≡ １ mod (p-1)(q-1) となる元Dを計算する。

（３）　BさんはAさんに平文ｘ ∈ Z/nZ を送信するために、ｙ ≡ ｘ^E mod n によって暗号化し、yを送る。
（４）　第三者はDを計算できないため、 ｘ^E mod n からｘを求められないが、Aさんは次のように復号できる。

y^D ≡ ( x^E)^D ≡ ( x^p-1)^k(q-1)x≡ x mod p

ここにおいて

DE ≡ k(p-1)(q-1)+1　　（kは任意の数）
x^p-1 ≡ 1 mod p (Fermatの小定理より)

同様に

y^D ≡ x mod q

なので

y^D ≡ x mod n

（２つの素数の積nを法とするZ/nZにおいては、全ての要素が｛k * lcm(p-1 , q-1) + 1｝乗すると元の数になる）
となり復号できる。　　　(lcm:Least Common Multiple 最小公倍数)

エルガマル（ElGamal）暗号

位数が大きな群の離散対数問題の困難さに基づく公 開鍵暗号である。

Z/pZから0を除いた集合F^*_pに情報を考え、その離散対数を用いる。
pを大きな素数、αをF^*_pの原始元とする。すなわちαを何乗かすればF^*_pの 任意の元が得られるとする。

今、BさんからAさんに暗号文を送る場合を考えると、Aさんは送り先で、Bさんは送り主となる。

（１）　Aさんは0 ≦ a ≦ p-2 なる整数aをランダムに選び、秘密鍵とする。
（２）　β ≡ α^a mod pを計算し、βを公開する。

（３）　BさんはAさんに平文ｘ ∈ Z/pZ を送信するために、乱数kを選ぶ。
（４）　y₁ = α^k mod p および y₂ = xβ^k mod p によって暗号化し、（y₁ , y₂）のペアを送る。
（５）　第三者はβからaを計算できないため暗号を解読できないが、Aさんは次のように復号できる。

y₂ ( y₁^a )^-1 mod p
= xβ^k ( α^ak )^-1 mod p
= xα^ak ( α^ak )^-1 mod p
= x mod p

よって、復号できる。

楕円曲線暗号（Elliptic Curve Cryptosystem）

具体的な暗号方式の名前ではなく、楕円曲線を利用した暗号方式の総称である。
楕円曲線上の離散対数問題(EC-DLP)の困難さに基づく公開鍵暗号である。

エルガマル暗号やDSA署名などの既存の有限体上の離散対数問題（DLP）を用いる暗号系は、すべて楕円曲線暗号に変換できる。
EC-DLPはDLPに対する強力な解法である指数計算法が直接適用できないことから、短い鍵で高い安全性が確保できる。
ただし、一部の曲線には弱点が見つかっており、実装時にはそれらを避ける工夫が必要とされる。

ページの上部へ

Fermatの小定理

pが素数の時、任意の整数a ( a , p は互いに素 ) に対して
a^p-1 ≡ １ mod p
である。

証明

gcd(a , p) = 1より
a = kp + r ( k：任意の整数 , r = 1 , 2 , ・・・ , p-1)とおける

a^p-1 = (kp + r)^p-1 = (pの倍数) + r^p-1

より、r^p-1 ≡ 1 mod p を示せば良い。
両辺にrを乗じて

r^p ≡ r mod p を命題とする。

r = m + 1 とおき
(m + 1)^pを展開することを考える。これは二項定理より、
m^p + _pC₁m^p-1 + _pC₂m^p-2 + … + _pC_p-1m + 1

また_pC_x ≡ 0 mod p (ただし0 < x < p)より　　　(_pC_x = p!/{(p-x)!x!} であり、pは素数だから)

(m + 1)^p ≡ m^p + 1 mod p

ここで、m = 1 とすると

(1 + 1)^p ≡ 1^p + 1 mod p
2^p ≡ 2 mod p となり命題はr = 2 の場合成立する。

今 m = k で命題が成立すると仮定し、m = k+1 の場合を考える。

((k+1) + 1)^p ≡ (k+1)^p + 1mod p
≡ k^p + 1 + 1 mod p 　　（命題よりk^p ≡ k mod p）
≡ k + 2 mod p

よって命題はm = k+1 でも成立する。
数学的帰納法によって２以上の r について命題は成立する。
r = 0 , 1 の場合、命題が成立することは明らかである。

離散対数問題

pを大きな素数として、αはpを法とする原始根とする。
（複素数全体の中でn乗してはじめて1になるものを「1の原始(n乗)根」と呼んだが、
αが p-1 乗してはじめて1と合同になり、かつ１からp-1までの数が全て現れるとき、αを素数pの原始根という）

α^a ≡ β( mod p )

のαとβがわかっていても、aを求めることは不可能に近い問題の事を離散対数問題と言う。