Schoof算法及其在椭圆曲线密码体制中的应用

Schoof算法是一种确定性算法,用于计算有限域Fq上椭圆曲线上的点的个数#GFq。详细介绍了Schoof算法,并应用它构造了一种方法随机生成安全的椭圆曲线,在此椭圆曲线上实现的加密系统可以抵抗Pohlig-Hellman攻击。

有限域上椭圆曲线Jacobian群求阶算法综述与比较

关于椭圆曲线密码体制(ECC)的研究,如今无论是ECC理论还是ECC的标准化、产业化都趋于成熟。在ECC的设计中,安全椭圆曲线的选取是ECC实现的基石,也是其安全性的重要保证。目前,随机选取法是最好的安全椭圆曲线选取方法,其核心思想是对随机生成的椭圆曲线计算其Jacobian群的阶。文章主要介绍了几类经典的计算椭圆曲线Jacobian群阶的算法:Schoof算法、SEA算法、Satoh算法、AGM算法。在详细介绍Schoof算法的基础上,提出了其基于离散对数问题的改进算法:袋鼠算法和大步小步(BSGS)算法的改进方法,并用实验结果说明加速后的算法得到了提升。针对SEA算法,文章也提出了其BSGS改进算法并通过实例分析比较了原SEA算法与BSGS改进算法的实现效率。针对Satoh算法、AGM算法,文章介绍了算法的理论依据和具体实现,并通过实例分析比较了其优劣性和适用情况。

SEA算法研究及快速实现

椭圆曲线公钥密码(ECC)具有比RSA算法更高的安全强度和运算速度,在很多应用上(特别是资源和带宽受限的地方)已经取代了RSA公钥密码,成为事实上的下一代公钥密码算法。椭圆曲线公钥密码的关键和难点是快速计算椭圆曲线的阶(有理点的个数),椭圆曲线的阶在很大程度上决定了其安全性。计算椭圆曲线的阶的算法主要有SCHOOF算法、SEA算法、Satoh算法和AGM算法。文章首先对SCHOOF算法进行了简单介绍,接着详细分析和研究了SEA算法及其快速实现过程。

利用超奇异椭圆曲线进行素性检验(英文)

根据超奇异椭圆曲线有理点个数与素数的关系,提出一个具有多项式时间复杂度的素性检验的概率型算法.对于给定的整数N,如果N≡3(mod4)或者N≡1(mod3),该算法具有多项式时间O(log8N).在广义黎曼假设成立的情况下,对于所有整数都具有这一时间复杂度.