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

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

• 批准号: 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.を達成した.これらのデータにより、超楕円曲線のヤコビアン群の離散対数問題を利用した公開鍵暗号系の実用性が検証できた。

The design and implementation of the open key code system for discrete pairs of curves Curve C: v ^2 +v=u^<13>+u^<11>+ u ^7 + u ^3 +1 on PentiumII(300MHz)<29>. C speech on Alpha21164A(467MHz), number g=3 curve C:v^2+v=u^7 and group J(F_&lt;2^<59>&gt;), integer multiples of arbitrary points 83.3 msec. The maximum prime factor of the number of bits in the pixel group is 160 bits or more. The RSA code of the 1024 bit key is 160 bits or more. The RSA code curve of the 1024 bit key is 160 bits or more. The security code of the pixel F_p is 160 bits or more. Alpha 21164A(467MHz) and PentiumII(300MHz) are 160 bits or more. A <2n>comparison of the velocity ratios of the group of particles on F_p and F_p is carried out. The curve group is compared with the definition of the body's server, and the CPU's server is considered, and the server group is selected. The integral multiple of any point on the curve F_p(p = 29) of the number g=6,PentiumII(300MHz), is 176 msec. The problem of discrete pairs of data sets using public key codes is solved.

项目成果

櫻井 幸一: "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)。

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。

Y.Sakai,K.SAKURAI,H.Ishizaki: "Secure hypereliptic aryptosystems and their performance" Proc.Public Key Crysto.'98 Springer LNCS. 1431. 164-181 (1998)

Y.Sakai、K.SAKURAI、H.Ishizaki：“安全超椭圆密码系统及其性能”Proc.Public Key Crysto.98 Springer LNCS。