橢圓曲線(xiàn)階的研究與實(shí)現(xiàn).pdf

1、橢圓曲線(xiàn)密碼系統(tǒng)作為公鑰密碼的一種，發(fā)展?jié)摿薮?。與當(dāng)前廣泛使用的RSA公鑰密碼系統(tǒng)相比，橢圓曲線(xiàn)密碼系統(tǒng)在同等的安全要求下，密鑰長(zhǎng)度更短。因而占用帶寬小、耗電少、運(yùn)算速度快，非常適合諸如FPGA、ASIC、嵌入式等受限環(huán)境的安全產(chǎn)品研發(fā)。 在橢圓曲線(xiàn)密碼體制的實(shí)現(xiàn)中，首先要選取安全的橢圓曲線(xiàn)，選取安全橢圓曲線(xiàn)的關(guān)鍵是對(duì)隨機(jī)選取的橢圓曲線(xiàn)的階進(jìn)行快速計(jì)算。第一個(gè)多項(xiàng)式時(shí)間的求階算法是由Schoof于1985年提出的，后經(jīng)過(guò)近十年

2、的改進(jìn)，其算法復(fù)雜度得到了極大的優(yōu)化，得到SEA算法。但是，與其他公鑰密碼體制相比較，在SEA算法下進(jìn)行橢圓曲線(xiàn)密碼體制的初始化仍然需要較大的投入。直到1999年，T.Satoh提出了計(jì)算特征為小素?cái)?shù)的橢圓曲線(xiàn)階的快速算法：Satoh算法，形勢(shì)才得以改變。其后，在Satoh算法之上又有一系列改進(jìn)，目前最為有效的算法為Harley算法。 本文介紹了Harley算法的基本原理，分析了其算法復(fù)雜度，并結(jié)合高斯正規(guī)基和Harley算法提