超橢圓曲線密碼體制中標(biāo)量乘法的快速算法研究.pdf

1、作為一類特殊的代數(shù)曲線，超橢圓曲線是橢圓曲線的一種推廣。與其他公鑰密碼體制相比，超橢圓曲線密碼體制具有更短的操作長(zhǎng)度，特別適合在受限系統(tǒng)中使用。由于結(jié)構(gòu)復(fù)雜，所以超橢圓曲線密碼體制實(shí)現(xiàn)速度較慢，目前對(duì)它的研究仍處于理論階段。如何提高超橢圓曲線除子標(biāo)量乘的計(jì)算速度是提高該密碼體制實(shí)現(xiàn)速度，并使它早日走向?qū)嵱玫囊粋€(gè)亟待解決的問題，本文對(duì)超橢圓曲線除子標(biāo)量乘的快速算法作了深入的研究，主要工作如下： 1.討論了使用雙基鏈計(jì)算超橢圓曲線除

2、子標(biāo)量乘的方法，給出了虧格為2的超橢圓曲線上2D1+D2，3D1，3D1+D2，4Dl，4D1+D2的除子計(jì)算公式、他們的變體公式以及他們與變體公式之間聯(lián)系的臨界點(diǎn)，分析了公式的運(yùn)算量。將2Dl+D2公式用于非鄰接形(NAF)和標(biāo)準(zhǔn)倍點(diǎn)加(double-and-add)標(biāo)量乘算法中，比使用Lange的公式在平均單比特運(yùn)算量上分別減少6.8％和9.2％，比使用Fan的改進(jìn)公式則分別減少2.7％和2％。 2.通過分析所給出的除子運(yùn)算

3、公式的運(yùn)算量，結(jié)合大素?cái)?shù)域上常見的實(shí)現(xiàn)環(huán)境，提出了適合我們應(yīng)用的高效的超橢圓曲線雙基鏈標(biāo)量乘算法，并對(duì)該算法進(jìn)行了復(fù)雜度分析。經(jīng)過測(cè)算，我們的雙基鏈標(biāo)量乘算法與標(biāo)準(zhǔn)倍點(diǎn)加和NAF標(biāo)量乘算法相比，效率分別提高25％和15.8％。該除子標(biāo)量乘算法能夠抵抗某些邊信道攻擊而且不需要任何預(yù)計(jì)算。 3.給出了虧格為2的超橢圓曲線除子5D1公式、它的變體公式以及它與變體公式之間聯(lián)系的臨界點(diǎn)，并分析了它們的運(yùn)算量。給出了橢圓曲線有理點(diǎn)的5倍點(diǎn)公

4、式以及多基鏈標(biāo)量乘算法。 4.給出了快速有效的虧格為3的超橢圓曲線退化除子運(yùn)算的運(yùn)算公式。將它用于總是倍點(diǎn)加(double-and—add-always)標(biāo)量乘算法中，一次和二次退化除子標(biāo)量乘分別比標(biāo)準(zhǔn)除子標(biāo)量乘快25.4％和13％。該算法能夠抗擊簡(jiǎn)單能量分析攻擊(SPA)和時(shí)間攻擊(TA)，主要用于使用固定基點(diǎn)進(jìn)行標(biāo)量乘的運(yùn)行環(huán)境中，如E1Gamal型加密算法、Diffie-Hel1man協(xié)議的發(fā)送方以及數(shù)字簽名算法HECDS

5、A中。由于退化除子特殊的結(jié)構(gòu)，一次和二次除子的表示長(zhǎng)度分別僅為標(biāo)準(zhǔn)除子的三分之一和三分之二。 5.給出了求超橢圓曲線除子加法和倍點(diǎn)并行算法的一個(gè)易于實(shí)現(xiàn)的一般性方法，使用這個(gè)方法得到的并行算法的特點(diǎn)是：①需要運(yùn)行的輪數(shù)最少；②在滿足①的情況下，所需的并行運(yùn)算乘法處理器的個(gè)數(shù)最少；③在滿足①和②的情況下，一次需要存儲(chǔ)的變量的最大個(gè)數(shù)最少。利用這個(gè)方法給出了虧格為3的超橢圓曲線除子加法和倍點(diǎn)運(yùn)算的并行算法，分析結(jié)果表明，加法運(yùn)算使用

6、9個(gè)乘法處理器至少需要進(jìn)行15輪運(yùn)算(其中包含一個(gè)求逆輪)，倍點(diǎn)運(yùn)算使用7個(gè)乘法處理器也至少需要進(jìn)行15輪運(yùn)算(其中包含一個(gè)求逆輪)。 6.給出了一個(gè)有效的同時(shí)求多個(gè)域元素逆的求逆算法。將其應(yīng)用到Mishra的虧格為2的超橢圓曲線除子標(biāo)量乘算法中，得到了一個(gè)高效的抗簡(jiǎn)單能量分析攻擊的標(biāo)量乘算法。該算法比總是倍點(diǎn)加標(biāo)量乘算法快24％～26％，比Mishra的兩種標(biāo)量乘算法分別快33％～35％和6％～7％。我們給出的這個(gè)求逆算法可以在任何需