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

数论算法的结构研究及其在公钥密码安全评估中的应用

• 批准号: 09780295
• 负责人: 櫻井 幸一
• 金额: $ 1.47万
• 依托单位: Kyushu University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Encouragement of Young Scientists (A)
• 财政年份: 1997
• 资助国家: 日本
• 起止时间: 1997 至 1998
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-09780295/
• 关键词: 公開鍵暗号; 数論アルゴリズム; だ円暗号; ヤコビアン群; RSA暗号; 有限体演算; 因数分解問題; 離散対数問題; 計算複雑性; 楕円曲線; RSA; PGP

超楕円曲線のヤコビアン群の離散対数問題を利用した公開鍵暗号系の設計と実装を行なった。曲線の探索と実装の結果,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.を達成した.これらのデータにより、超楕円曲線のヤコビアン群の離散対数問題を利用した公開鍵暗号系の実用性が検証できた。

我们使用超椭圆曲线雅可比群的离散对数问题设计并实现了公钥密码系统。经过曲线搜索和实现，我们在Pentium II上用C语言创建了一条属g=6的曲线C:v^2+v=u^<13>+u^<11>+u^7+u^ (300MHz). 3+1 雅可比组 J (F_<2^<29>>)，我们能够在 259 毫秒内执行任意点的整数乘法。另外，在 Alpha21164A (467MHz) 上的 C 语言中，我们可以使用 genus g= 的曲线 C:v^2 3.在 +v=u^7 的雅可比群 J (F_<2^<59>>) 中，我们能够在 83.3 毫秒内执行任意点的整数乘法。划分这些雅可比群的阶数的最大素因子是160此外，我们在素数域F_p上搜索一个安全的雅可比群，它与使用1024位密钥的RSA加密和使用160位密钥的椭圆曲线加密具有相同的安全性。我们用C语言为21164A（467MHz）和PentiumII（300MHz）实现了软件。我们还比较了雅可比群在F_<2n>和F_p上的速度效率。与椭圆曲线群比较并定义了利用减少尺寸的能力并考虑到实现 CPU 的字大小，雅可比组为格格g=6的曲线F_p（p是29位质数）上的雅可比群J（F_p）的任意点的整数乘法即使在Pentium II（300MHz）上也是实用的速度，176毫秒。通过数据，我们能够使用超椭圆曲线雅可比群的离散对数问题来验证公钥密码系统的实用性。

项目成果

櫻井 幸一: "Relationships among the computational powers fo breaking discrete log cryptsystems" Journal of Cryptology. 11・1. 29-43 (1998)

Koichi Sakurai：“破解离散日志密码系统的计算能力之间的关系”《密码学杂志》11・1（1998）。

酒井 康行: "On weak RSA-keys produced from Pretty Good Privacy" Proc.of 1st International Conference of Information and Communication Security (ICICS97),Springer LNCS 1334. 314-324 (1997)

Yasuyuki Sakai：“论从 Pretty Good Privacy 中产生的弱 RSA 密钥”第一届国际信息和通信安全会议 (ICICS97) 会议记录，Springer LNCS 1334. 314-324 (1997)

酒井 康行: "Secure hyperelliptic cryptosystems and their performance" PreProc.of PKC'98,1998 Internaional workshop on practical and theory in public key cryptography. 129-146 (1998)

Yasuyuki Sakai：“安全超椭圆密码系统及其性能”PreProc.of PKC98，1998 国际公钥密码学实践与理论研讨会 129-146 (1998)。

Neal Koblitz: "数論アルゴリズムと楕円暗号理論入門" シュプリンガー・フェアラーク東京株式会社, 368 (1997)

Neal Koblitz：“数论算法和椭圆密码学理论简介”Springer-Verlag Tokyo Co., Ltd.，368 (1997)

Y.SAKAI,K.SAKURAI: "Design of Hyperelliptic Cryptosystems in Small Cher and a Software Iaplesentation ober F_<2n>" Proc.ASIACRYPTO '98,Springer LNCS. 1514. 80-94 (1998)

Y.SAKAI、K.SAKURAI：“Small Cher 中的超椭圆密码系统设计和 F_<2n> 上的软件Iaplesentation”Proc.ASIACRYPTO 98，Springer LNCS。