模冪與點乘ｍ＿ａｒｙ算法中窗口大小的最優(yōu)化估計

摘要：提出一種新大數(shù)模冪與點乘m_ary算法中窗口大小的最優(yōu)化估計方法。該方法不同于傳統(tǒng)的暴力搜尋方法，也不同于在窗口的取值范圍內(nèi)通過逐一測試程序來獲得最優(yōu)窗口大小的方法。其基于以下理論分析：模冪 m_ary算法的基本運算為大數(shù)乘法，其中包括大數(shù)平方算法和一般大數(shù)乘法；橢圓曲線加密算法中點乘的m_ary算法步驟與模冪的m_ary算法相同，后者的基本運算為倍乘和加法。根據(jù)m_ary算法的基本運算的調(diào)用次數(shù)，推算出了最優(yōu)窗口大小的估計公式。通過實驗對m_ary算法進行實現(xiàn)，并測試分析了根據(jù)估計公式計算出窗口大小的算法實現(xiàn)時間效率與理論分析基本吻合。

關鍵詞：大數(shù)模冪；點乘；m_ary算法；窗口大小 

中圖分類號：TP301．6文獻標志碼：A

文章編號：1001-3695(2007)10-0035-02

1976年Diffie和Hellman提出了公鑰密碼體制的思想。1977年Rivest、Shamir、Adleman發(fā)明了RSA密碼體制。1985年N.Kobitz和Miller提出將橢圓曲線用于加密算法[1]。目前，RSA加密算法和橢圓曲線加密算法都在數(shù)字簽名、軟硬件加密及網(wǎng)絡安全中得到了廣泛應用。因此探究用于RSA和橢圓曲線加密中的大數(shù)運算算法的最佳效率對于提高加密速度具有重要意義。這兩個不同的公鑰密碼體制的安全性依賴于不同的計算問題，但都涉及到大數(shù)運算。RSA算法通過模指數(shù)運算

5結(jié)束語

大數(shù)模指數(shù)運算在諸如RSA、DeffieHellman公鑰加密系統(tǒng)中有著廣泛的應用，其效率也直接影響著加密算法實現(xiàn)的效率。點乘算法是橢圓曲線快速加密算法的基礎；m_ary算法是模指數(shù)和點乘運算的基礎算法。本文提出了估計m_ary算法中最優(yōu)窗口大小的方法，推算出的估計公式考慮了大指數(shù)二進制比特表示可能存在連續(xù)多個零的情況，估計公式不僅能夠?qū)嶋H應用，而且易于推廣到滑動窗口等其他算法。

參考文獻：

［1］STINSON D R.Cryptography theory and practice[M].馮登國，譯.北京：電子工業(yè)出版社，2003:131132.

[2]TANDRUP M B，JENSEN M H，ANDERSEN R N.Fast exponentiation in practice[EB/OL].[2006-0610].http:www.daimi.au.dk/~ivan/FastExpproject.pdf .

[3]陳艷波，唐四云，王學理.大數(shù)快速模冪算法的研究[J].科學技術與工程，2006，6(5):625-627.

[4]MALONELEE J，SMART N P.Elliptic curve cryptography[EB/OL].(2004).[2006-0610].http://www.cs.bris.ac.uk/Teaching/Resources/COMSM2004/Lectures/Adv_Crypto_ECC.pdf.

[5]宋燕紅，田伏榮，張繼永.大數(shù)模冪乘快速算法研究 [J].北京電子科技學院學報，2001，9(1):25-26.

“本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文”