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

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

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

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

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

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

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