DH問題 | イマッチの暗号特集

イマッチの暗号特集

情報セキュリティについてまとめている管理人イマッチのブログです。暗号の専門家になるために奮闘しています。

DH問題とは野球で指名打者を採用するかという問題である.

というのは違います.そのDH(designated hitter)ではありません.Diffie-HellmanのDHです.
Diffie-Hellmanの鍵共有法に由来しています.

大きな素数p,mod p(pで割った余りの世界)の原始元g(p - 1乗で初めて1になる)とAさんの公開鍵K_A(= g^a mod p),Bさんの公開鍵K_B(= g^b mod p)からg^ab mod pを解くことが難しいとされています.
素数pは1024ビットとか2048ビットのもの(大体300桁~700桁ぐらい)を使うので,Aさんの公開鍵K_A = g^a mod pから秘密鍵aを求めることは難しいとされています(離散対数仮定,aを全部試すというゴリ押しではスーパーコンピューターでも無理なので).
Bさんの公開鍵K_Bから秘密鍵bを求めることも困難です.
aとbの値がわからないので,g^ab mod pは計算できません.
p,g,K_A,K_Bからg^ab mod pを計算する問題をDH問題といって,これが困難だという仮定(決めつけ)をDH仮定といいます.

しかしながら,DH問題が困難であっても,離散対数問題は困難であるかどうかはわかっていません.やさしいかもしれないのです.

図はこんな感じです.

DH問題



インターネット家庭教師Netty