公開鍵暗号講座

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


Home  暗号 ∥ RSA | ElGamal | 楕円曲線暗号

RSA(Rivest Shamir Adleman)

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

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

(1) 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 最大公約数)
(2) ED ≡ 1 mod (p-1)(q-1) となる元Dを計算する。

公開 秘密
n , E p , q , D

(3) BさんはAさんに平文x ∈ Z/nZ を送信するために、y ≡ xE mod n によって暗号化し、yを送る。
(4) 第三者はDを計算できないため、 xE mod n からxを求められないが、Aさんは次のように復号できる。

yD ≡ ( xE)D ≡ ( xp-1)k(q-1)x≡ x mod p

ここにおいて

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

同様に

yD ≡ x mod q

なので

yD ≡ x mod n

(2つの素数の積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さんは送り主となる。

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

公開 秘密
p , α , β a

(3) BさんはAさんに平文x ∈ Z/pZ を送信するために、乱数kを選ぶ。
(4) y1 = αk mod p および y2 = xβk mod p によって暗号化し、(y1 , y2)のペアを送る。
(5) 第三者はβからaを計算できないため暗号を解読できないが、Aさんは次のように復号できる。

y2 ( y1a )-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 は互いに素 ) に対して
ap-1 ≡ 1 mod p
である。

証明

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

ap-1 = (kp + r)p-1 = (pの倍数) + rp-1

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

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

r = m + 1 とおき
(m + 1)pを展開することを考える。これは二項定理より、
mp + pC1mp-1 + pC2mp-2 + … + pCp-1m + 1

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

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

ここで、m = 1 とすると

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

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

((k+1) + 1)p ≡ (k+1)p + 1mod p
≡ kp + 1 + 1 mod p   (命題よりkp ≡ k mod p)
≡ k + 2 mod p

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

ページの上部へ

離散対数問題

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

αa ≡ β( mod p )

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

ページの上部へ
容量300MB、月額125円、高性能なサーバが日本最大級のバックボーンに直結。
さくらのレンタルサーバ
ロリポップのドメインが65種類 → 85種類に!!
きっとお好みのドメインが見つかるはず!
アフィリエイトならリンクシェア