鍵交換-まとめ

整数a,b,nに対して、a^bをnで割った余りrを求める計算をべき乗計算という。

→冪数bの和や積への分解や、2進数表記を用いて、できるだけ演算回数や計算量を少なくする努力をする。

 

有限な巡回群Gにおいて、g^x=hなる整数xを求める問題を離散対数問題という。

→これを効率よく溶けるアルゴリズムは存在しないことから、DH暗号への利用ができる。

 

位数が2または3のべき乗でない有限体上で、

y*y=x*x*x+a*x+b

で表される曲線を楕円曲線という

 

楕円曲線の2点の点配置によって定義された2点間の加算演算のことを楕円加算という。特に、点集合は楕円加算により群になる。スカラー倍も定義可能である。

 

与えられた楕円曲線においてxQ=Pとなる整数xを求める問題のことを楕円曲線上の離散対数問題という。小さいサイズの鍵でも通常の離散対数問題よりもとくのが困難と言われている。

 

楕円曲線上の離散対数問題の困難さに基づいた共通鍵の交換方法のことを楕円曲線上のDG鍵交換という