このページをはてなブックマークに追加このページを含むはてなブックマーク このページをlivedoor クリップに追加このページを含むlivedoor クリップ

目次

宣伝

 当サイトにおける暗号に関するページでは、説明が足りなかったり、誤った記述をしていたりするところがあります。今後、少しずつ修正する予定です。

 暗号理論の『暗号技術のすべて』が発売されています。初心者向けの暗号本です。これまで暗号本に何度か挑戦しつつも挫折してしまった方、学校の課題で悩んでいる方、資格試験にて暗号の問題が苦手な方などにお勧めです。

『暗号技術のすべて』宣伝サイト

 興味がある方は宣伝サイトを参照してください。Amazonでも発売中です。

DH鍵共有プロトコルの方式

[1]ネットワーク公開情報

 ネットワーク全体で共通に使用する情報として、ランダムに生成された素数pとZp*の原始元gが公開されていると仮定する。

[2]鍵生成アルゴリズム

・アリスは0≦a≦p-2となるaをランダムに選び、yA=ga (mod p)を計算する。

[補講]Zp={0,…,p-1}(要素がp個)、Zp*={1,…,p-1}(要素がp-1個)である。つまり、0≦a≦p-2は、0からカウントするのでp-1個で一致している。

 次に、yAを公開鍵として公開し、aを秘密鍵として秘密に保持する。

・ボブは0≦b≦p-2となるbをランダムに選び、yB=gb (mod p)を計算する。

 次に、yBを公開鍵として公開し、bを秘密鍵として秘密に保持する。

[3]鍵共有アルゴリズム

・アリスは自分の秘密鍵aとボブの公開鍵yBを入力として、次を計算する。

K_{A}=\(~y_{B}~\)^{a}~\,~\(~mod~\,~p\)

・ボブは自分の秘密鍵bとアリスの公開鍵yAを入力として、次を計算する。

K_{B}=\(~y_{A}~\)^{b}~\,~\(~mod~\,~p\)

 ここで、K=gab (mod p)とおくと、K=KA=KBとなる。

 よってアリスとボブは秘密鍵Kを秘密に共有できる。

DH鍵共有プロトコルに関する仮定

 DHの鍵配送における公開情報はp,g,yA(=ga mod p),yB(=gb mod p)である。

 敵はこれらからK=gab (mod p)を求めようとする問題をCDH問題(Diffie-Hellman Problem:DHP)と呼ぶ。すなわち、DH問題とは素数p、Zp*の原始元g,ga∈Zp*,gb∈Zp*が与えられたとき、gab (mod p)を求める問題である。

 pが十分に大きいとき、DH問題を解く効率的*1なアルゴリズムは見つかっていない。DH問題を解く効率的なアルゴリズムが作れないという仮定をCDH仮定という。

参考文献

  • 『現代暗号の基礎数理』


*1 多項式時間で解けること