数論アルゴリズムの構造論的研究とその公開鍵暗号安全性評価への応用

点击翻译按钮获取中文摘要

超楕円曲線のヤコビアン群の離散対数問題を利用した公開鍵暗号系の設計と実装を行なった。曲線の探索と実装の結果,PentiumII(300MHz)上のC言語で種数g=6の曲線C:v^2+v=u^<13>+u^<11>+u^7+u^3+1のヤコビアン群J(F_<2^<29>>)において,任意点の整数倍算を259msecで実行できた.また,Alpha21164A(467MHz)上のC言語で,種数g=3の曲線C:v^2+v=u^7のヤコビアン群J(F_<2^<59>>)において,任意点の整数倍算を83.3msecで実行できた.これらのヤコビアン群の位数を割り切る最大素因数は160ビット以上であり,1024ビット鍵のRSA暗号および160ビット鍵の楕円曲線暗号と同等の安全性を有しているさらに素体F_p上の安全なヤコビアン群を探索し,Alpha 21164A(467MHz)とPentiumII(300MHz)のC言語によるソフトウエア実装を行なった.また,F_<2n>上とF_p上のヤコビアン群の速度効率の比較を行なった.楕円曲線群と比較して定義体のサイズを小さくできるという特長を利用し,実装のCPUのワードサイズを考慮して,ヤコビアン群を選択している.種数g=6の曲線のF_p(pは29ビットの素数)上のヤコビアン群J(F_p)の任意点の整数倍算は,PentiumII(300MHz)においても実用的速度,176msec.を達成した.これらのデータにより、超楕円曲線のヤコビアン群の離散対数問題を利用した公開鍵暗号系の実用性が検証できた。