Fast implementation and security analysis of hyperelliptic curve cryptosystems

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

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.