A Research On The Securities Of Elliptic Curve Cryptosystems

Elliptic curve cryptosystems are one kind of the most promising public key cryptosystems. As their advantages of securities, efficiencies and implementation costs over other public key cryptosystems, elliptic curves cryptosystems are getting broadly applied and adopted by many criteria organizations as one of their public key cryptosystem standards, thus the securities of elliptic curve cryptosystems are drawing much attentions and studied extensively. In this thesis, the author discussed and solved the security problems existing in every aspect of elliptic curve cryptosystems, especially the security problems of elliptic curve cryptoschemes and their security proofs. The author divided the securities of elliptic curve cryptosystems into three relatively independent levels: the securities of their mathematical foundations, the securities of the cryptoschemes and the securities of their implementations. The author led his emphasis on solving the following difficult but important problems: establishing a security criteria for elliptic curves, designing a provable secure elliptic curve encryption scheme and proving its security, designing a provable secure elliptic curve signature scheme and proving its security. The conclusions and produces in this thesis are very valuable to the applications of elliptic curve cryptosystems.To research any public key cryptosystem's securities, one first has to study the securities of its mathematical foundation that is the premise of constructing the public key cryptosystem. As elliptic curve discrete logarithms being the mathematical foundations of all elliptic curve cryptosystems, the author first came into studying the securities of elliptic curve discrete logarithms after introducing some backgrounds and the necessary mathematical knowledge.To study the securities of elliptic curve discrete logarithms is to study how to select the proper parameters of elliptic curves, th s discrete logarithms on them is unsolvable in computation, that's to say they can resists all existing attacks on the discrete logarithms of them. The author divided all known attacks on elliptic curve discrete logarithms in two types: attacks on general elliptic curve discrete logarithms and attacks on special elliptic curve discrete logarithms. The author studied these two types of attacks in details and found out a kind of secure elliptic curve, the discrete logarithms on which can resist all those attacks. Attacks on general elliptic curve discretelogarithms are not affected by the choices of elliptic curve parameters. The Baby-Step Giant-Step (BSGS) attack, Pohlig-Hellman attack and Pollard's Rho attacks are all famous attacks on general elliptic curve discrete logarithms. By carefully studying this type of attacks, the author concluded that properly choosing the rank of an elliptic curve to make it contain a big enough prime factor can make the elliptic curve secure against this type of attacks. Because of the special parameters of some special types of elliptic curves, there are efficient attacks on them. Those special elliptic curves are not allowed to construct elliptic curve cryptosystems. The MOV attack, FR attack, SSSA attack and attacks on singular elliptic curves are all efficient attacks on special elliptic curves. Through analysis of those efficient attacks, the author pointed out the insecurities of those special elliptic curves. By studying the tow types of attacks, the author drew a conclusion that excluding all special elliptic curves and selecting elliptic curves which ranks contain big prime factors to construct elliptic curve cryptosystems can assure the securities of their mathematical foundations.Based on the securities of its mathematical foundation, the securities of cryptoschemes are very important contents of a public key cryptosystem's securities. In this thesis, the author led his emphasis on studying the securities of elliptic curve cryptoschemes which including the securities of elliptic curve encryption cryptoschemes and the securities of elliptic curve signature cryptos...