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

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

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

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