OEF上的快速算法研究及其在ECC上的應(yīng)用實(shí)現(xiàn).pdf

1、橢圓曲線加密體制(ECC)是一種基于橢圓曲線上的離散對(duì)數(shù)問題而設(shè)計(jì)的非對(duì)稱公鑰密碼體制.本文主要分析研究了最優(yōu)擴(kuò)域(OEF)上的快速算法及其在ECC上的應(yīng)用實(shí)現(xiàn).橢圓曲線的計(jì)算算法可分為高層計(jì)算和低層計(jì)算兩類算法.其中高層計(jì)算算法主要處理橢圓曲線上點(diǎn)的操作,而低層算法側(cè)重于處理有限域中的多項(xiàng)式計(jì)算算法,本文通過將這兩者有機(jī)結(jié)合來(lái)提高橢圓曲線密碼系統(tǒng)中的計(jì)算速度.本文對(duì)理想擴(kuò)域的結(jié)構(gòu)特點(diǎn)和橢圓曲線上的標(biāo)量乘(kP)快速算法進(jìn)行了分析研究,

2、并對(duì)這些快速算法加以測(cè)試改進(jìn).在最優(yōu)擴(kuò)域上的快速算法的研究過程中,通過分析子域求模的快速算法、域元素求逆(MAIA算法、EEA算法)和多項(xiàng)式相乘(硬乘算法、Karatsuba算法)等經(jīng)典算法后,結(jié)合我們選擇的有限域(Ⅱ型最優(yōu)擴(kuò)域GF((2<'32>-46305)<'5>))的特點(diǎn),本文提出了一種基于Karatsuba法的改進(jìn)型域元素多項(xiàng)式乘算法,并通過理論分析證明該改進(jìn)算法的計(jì)算復(fù)雜度低于Karatsuba算法.經(jīng)測(cè)試(CPU/PⅣ1.

3、4GHz,MS Visual C++6.0),驗(yàn)證改進(jìn)算法的性能與Karatsuba算法相當(dāng),比硬乘算法提高了大約4％.在橢圓曲線上的標(biāo)量乘快速算法的研究過程中,通過分析計(jì)算標(biāo)量乘(二進(jìn)制算法、Montgomery算法、NAF算法、2P+Q算法和FBW算法等)的算法,本文提出了一種改進(jìn)型3P算法和一種基于固定基的MFBW算法.改進(jìn)型3P算法通過優(yōu)化正整數(shù)k的表示形式來(lái)降低標(biāo)量乘的計(jì)算復(fù)雜度,MFBW算法利用一些預(yù)計(jì)算來(lái)提高標(biāo)量乘的計(jì)算速