|
エルガマル暗号について調べてみた。 エルガマル暗号とは、1985年にエジプト人数学者Taher Elgamal氏によって考案された公開鍵型の暗号方式。Taher Elgamal氏はカイロ大学で出てスタンフォード大学で修士と博士号をとられたようだ。 Taher Elgamal氏はネットスケープ社の主任研究員としてSSLの開発にも携わっている。 エルガマル暗号は、ELGamalとGを大文字にして綴られるが、考案者のTaher Elgamalの名前ではElgamalと綴られる。 エルガマル暗号の手順 [鍵の生成]
エルガマルは次のようにしてようにして、公開鍵と秘密鍵を求める。
まず非常に大きな素数pとの1とp-1の間の乱数gを選ぶ。
次に、xをランダムに選び、y=g＾x (mod p)を計算する。
(p,g,y)を公開鍵として公開し、(p,x)を秘密鍵として秘密に保持する。
[暗号化]
暗号化は公開鍵(p,g,y)と平文Mを入力として、暗号文C=(C1,C2)を次のようにして求める。
１からｐ−１の間の乱数ｒをランダムに選び、次を計算する。
C1=g＾r (mod p)
C2=M×y＾r (mod p)
[復号]
復号は、秘密鍵(p,x)と暗号文C=(C1,C2)を入力として、平文Mを次のように計算する。
M=C2×C1^（p-1-x) (mod p) ※
※これを導くにはフェルマーの小定理を使う。
C2×C1^（p-1-x) (mod p)
＝M×y^r・g^r(p-1-x)
＝M×g^rx・g^r(p-1-x) （∵y=g^x (mod p)）
＝M×g^r(p-1)
≡M・1r （∵フェルマーの小定理）
＝M (mod p)
では実際に、計算してみよう。素数pが大きいと計算がやっかいなので、小さな素数ｐを使って計算例を示す。暗号化する平文は１０とする。 [鍵の生成] p=23,g=5,x=6で公開鍵を生成すると y=5^6 mod 23 =15625= 8 よって、公開鍵(p,g,y)=(23,5,8)、秘密鍵(p,x)=(23,6)を得ることができた。 [暗号化] 平文10を暗号化する場合を考える。 乱数rをまず求める。乱数が10だったとすると C1=5^10 mod 23 =9765625 (mod 23)=9 C2=10×8^10 mod 23=10×1073741824 (mod 23) = 7 よって、暗号(C1,C2)=(9,7)を得た。 [復号］
暗号(C1,C2)=(9,7)を、秘密鍵(p,x)=(23,6)を使って解く M=C2×C1^（p-1-x) (mod p)=7×9^(23-1-6) (mod 23)＝7×9＾15＝7×40353607 (mod 23)
= 282475249 (mod 23)=10
エルガマル暗号方式は見てのとおり、Deffie-Helmanの鍵配送方式とよくにており、離散対数問題が解けないことを安全性の根拠としている。最近では、楕円曲線暗号の基礎をなす暗号方式として再び注目を集めているようだ。 |
- >
- コンピュータとインターネット
- >
- コンピュータ
- >
- ソフトウェア
コメント（0）
