Fast implementation and security analysis of hyperelliptic curve cryptosystems

1. 已知在基于代数曲线的密码体制中，只有基因ra小于等于3的超椭圆曲线是安全的。在本研究中，我们首次开发了三属超椭圆曲线的快速算法。基于这些曲线的密码系统可以在64位的廉价处理器上实现，因此可以实现比椭圆曲线密码系统更高效的密码系统。特别地，获得了计算量最小的快速加法算法。这些算法实现了在173微秒内实现快速标量乘法的新记录。在安全性分析方面，我们首次证明了存在大量的椭圆曲线，这些椭圆曲线被认为是安全的，但可以被GHS攻击破坏。特别地，我们明确地展示了在扩展域上定义的低属椭圆曲线和超椭圆曲线的类别，它们具有弱覆盖，即它们的Well限制既可以被超椭圆曲线的指数微积分攻击攻击，也可以被Diem最近对非超椭圆曲线的攻击攻击。得到了这类弱曲线的完整分类。此外，我们还展示了如何从这些曲线构造这样的覆盖，并分析了这些弱曲线的密度。

1. It is known that among the algebraic curve based cryptosystems, only hyperelliptic curves of gene ra less or equal to three are secure. In this research, we first developed fast algorithms for hyper elliptic curves of genus three. Cryptosystems based on these curves are implemented on cheap processors of 64 bits with single decision, thus more efficient cryptosystems than elliptic curve crypt osystems are possible. In particular, fast addition algorithms with the least computational cost are obtained. These algorithms are implemented to achieve a new record of fast scalar multiplication with173 microseconds.2. As to security analysis, we show for the first time the existence of a huge number of elliptic curves which are believed to be secure but can be broken by GHS attack. In particular, we show explicitly classes of elliptic and hyperelliptic curves of low genera defined over extension fields, which have weak coverings, i.e. their Well restrictions can be attacked by either index calculus attacks to hyperelliptic curves or Diem's recent attack to non-hyperelliptic curves. A complete classification of such weak curves is obtained. Besides, we show how to construct such coverings from these curves and analyze density of these weak curves.