07

19

離散対数問題を使った公開鍵暗号 (ElGamal暗号、Diffe-Hellman鍵共有法)

2010.07.19(21:36)

公開鍵暗号にもちいる暗号アルゴリズムには、2種類あります。

(1)素因数分解問題を使ったもの
N = pq において、
pとqからNを求めるのは簡単だが、Nからpとqを求めるのは非常に困難、
つまり、非常に大きな数の素因数分解には膨大な時間がかかるという性質を使ったものと、

(2)離散対数問題を使ったもの
ak = z (mod p) において、
pを法とする世界で、aをk乗してzを求めるのは簡単だが、aを何乗するとzになるかを求めるのは非常に難しいという性質を使ったものがあります。

このうち、(2)離散対数問題を使ったものについて、簡単な例を使って説明してみます。



離散対数問題を使ったElGamal暗号(エルガマルあんごう)の暗号化と復号


ステップ処理簡単な例さらに解説
受信者は、大きい素数q と
その原子根a を用意する。
素数 q = 7
その原始根の1つ
a = 3
モジュロ7の
aのb乗の表で、
1から7までの数値が重複なく1回ずつ現れる性質を有する数を原始根という
受信者は、ランダムに秘密鍵 d を作って、
g = ad ( mod q )
を計算し、g, a, q を公開鍵として公開する。
秘密鍵 d = 11
g = ad ( mod q )
= 311(mod 7)
= 5
 
3送信者は、乱数 r を作って
C1 = ar (mod q) を計算する。
さらに、平文 P に対して、
C2 = P x gr (mod q) を計算する。
乱数 r = 13
C1 = ar (mod q)
= 313(mod 7)
= 3
平文 P = 4
C2 = P x gr (mod q)
= 4 x 513 (mod 7)
= 4 x 5 (mod 7)
= 6
 
4送信者は、 C1、 C2
受信者に送る。
  
5受信者は、秘密鍵 d を用い、
次の式を計算して復号する。
P = C2 / C1d (mod q)
P = C2 / C1d (mod q)
= 6 / 311 (mod 7)
= 6 / 5 (mod 7)
= 4
復号して平文が求まりました。

C1d = (ar)d
= (ad)r
=(g)r
なので、
C2 / C1d = P x gr / gr = P


 

Diffe-Hellman鍵共有法(ディフィー・へルマンかぎきょうゆうほう)は、上のElGamal暗号と似たしくみ。

ステップ処理簡単な例さらに解説
送信者と受信者は、
大きな素数 p と
原始根 a を
秘密にすることなく共有する。
素数 q = 7
その原始根の1つ
a = 3
モジュロ7の
aのb乗の表で、
1から7までの数値が重複なく1回ずつ現れる性質を有する数を原始根という
送信者はランダムな数 c を選んで秘密にし、ac (mod p)を受信者に送る。
受信者はランダムな数 d を選んで秘密にし、ad (mod p)を送信者に送る。
ランダムな数 c = 11
ac (mod p) = a11(mod 7)

ランダムな数 d = 13
ad (mod p) = a13(mod 7)
ac (mod p)を公開しても、cを求めることは困難です。

ad (mod p)を公開しても、dを求めることは困難です。
3送信者はランダムな数 cから
(ad )c (mod p) = acd(mod p) 
を得る。
受信者はランダムな数 dから
(ac )d (mod p) = acd(mod p) 
を得る。
これで2人は鍵が共有できた。
送信者
(ad )c (mod p) = acd(mod p) 

受信者
(ac )d (mod p) = acd(mod p) 


cを秘密にしているので、
acd(mod p) も秘密といえます。

同様に、
dを秘密にしているので、
acd(mod p) も秘密といえます。

2人が同じ値を持つことができました。



 

ウィキペディアよりは、ほんのちょっと、わかりやすいでしょうか。

コメントの投稿

非公開コメント

プロフィール

島敏博

Shima Toshihiro 島敏博
信州アルプスハイランド在住。HaskellとElixirが好き。組み込みソフトウェアアーキテクト、C++プログラマ、山歩き、美術館巡り、和食食べ歩き、日本赤十字社救急法指導員、インデックス投資、クラシック音楽、SESSAME会員、状態マシン設計、モデル駆動開発、ソフトウェアプロダクトライン、Rubyist、実践ビジネス英語

■ ツイッター
http://twitter.com/saltheads
■ Facebook
http://www.facebook.com/saltheads
■ Qiita
http://qiita.com/saltheads

印刷する場合は、ブラウザの印刷メニューではなく、このページの上から3cmくらいの青いところにある、「印刷」を押してみてください。少しうまく印刷できます。まだ完全ではないのですが、これで勘弁してください。


カテゴリ
最新記事
月別アーカイブ
最新コメント
検索フォーム
リンク
sessame
RSSリンクの表示