資源描述:
《RSA快速實(shí)現(xiàn)算法的研究與改進(jìn)》由會員上傳分享,免費(fèi)在線閱讀,更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。
1、學(xué)號:076862姓名:———————一一——●梁小英專業(yè):密碼學(xué)導(dǎo)師:董絲副塾握學(xué)院:壟堂暄2010年01月10日獨(dú)創(chuàng)性(或創(chuàng)新性)聲明本人聲明所呈交的論文是本人在導(dǎo)師指導(dǎo)下進(jìn)行的研究工作及取得的研究成果。盡我所知,除了文中特別加以標(biāo)注和致謝中所羅列的內(nèi)容以外,論文中不包含其他人已經(jīng)發(fā)表或撰寫過的研究成果,也不包含為獲得北京郵電大學(xué)或其他教育機(jī)構(gòu)的學(xué)位或證書而使用過的材料。與我一同工作的同志對本研究所做的任何貢獻(xiàn)均已在論文中作了明確的說明并表示了謝意。申請學(xué)位論文與資料若有不實(shí)之處,本人承擔(dān)一切相關(guān)責(zé)任。.、』驢本人簽名:盔墮二基日期:Z口№.≥?!脐P(guān)于論文使用授權(quán)的說明’學(xué)
2、位論文作者完全了解北京郵電大學(xué)有關(guān)保留和使用學(xué)位論文的規(guī)定,即:研究生在校攻讀學(xué)位期間論文工作的知識產(chǎn)權(quán)單位屬北京郵電大學(xué)。學(xué)校有權(quán)保留并向國家有關(guān)部門或機(jī)構(gòu)送交論文的復(fù)印件和磁盤,允許學(xué)位論文被查閱和借閱;學(xué)校可以公布學(xué)位論文的全部或部分內(nèi)容,可以允許采用影印、縮印或其它復(fù)制手段保存、匯編學(xué)位論文。(保密的學(xué)位論文在解密后遵守此規(guī)定)保密論文注釋:本學(xué)位論文屬于保密在一年解密后適用本授權(quán)書。非保密論文注釋:本學(xué)位論文不屬于保密范圍,適用本授權(quán)書。·本人簽名:鎏塵墓同期:羔堡f旦!弓二■’導(dǎo)師簽名:日期:如~.弓、I.RSA快速實(shí)現(xiàn)算法的研究與改進(jìn)摘要公鑰密碼體制使得密碼學(xué)由傳
3、統(tǒng)的政府和軍事應(yīng)用領(lǐng)域走向商用和民用領(lǐng)域,使得現(xiàn)代密碼學(xué)的商業(yè)價值和社會價值得到了廣泛的認(rèn)同。目前,RSA是使用最為廣泛的一種公鑰密碼體制。但由于RSA算法是基于大素數(shù)分解難題的,特別是為防止各種攻擊,其模長在不斷增加,其主要運(yùn)算是大整數(shù)的模冪和模乘,算法的運(yùn)行速度較慢成為RSA的一個顯著缺陷。因此,對大整數(shù)模冪和模乘算法以及取模算法的加速實(shí)現(xiàn)進(jìn)行研究具有重要的理論意義和實(shí)用價值。本課題重點(diǎn)研究RSA算法的加速實(shí)現(xiàn)技術(shù)。當(dāng)前針對RSA的研究主要包括密鑰生成的優(yōu)化、素性檢測的優(yōu)化、大整數(shù)模乘和模冪運(yùn)算的優(yōu)化等,本文重點(diǎn)研究大數(shù)模乘和模冪運(yùn)算的優(yōu)化問題。本課題受目前流行的蒙哥馬利算
4、法思想的啟發(fā),提煉出了模簡化定理并予以證明,簡化模逆運(yùn)算,優(yōu)化了蒙哥馬利算法。本課題在研究了基于滑動窗口編碼的算法之后,設(shè)計出新穎的限長游程編碼,并將其應(yīng)用于設(shè)計大整數(shù)的模乘和模冪運(yùn)算實(shí)現(xiàn)算法。在完成算法設(shè)計之后,本文對算法的時間和空間復(fù)雜度進(jìn)行了詳細(xì)的分析。對比已有的相關(guān)算法效率,在理論上證明了算法的優(yōu)越性。另外,還編程模擬實(shí)現(xiàn)了算法,通過實(shí)驗(yàn)證明了算法的效率確實(shí)有較大提高。本文還研究了行程編碼,并試圖將行程編碼直接應(yīng)用于設(shè)計大數(shù)模乘和模冪算法,經(jīng)過分析得出行程編碼并不適合應(yīng)用于設(shè)計大數(shù)模乘和模冪算法的結(jié)論,從而進(jìn)一步證明了本文設(shè)計的限長游程編碼是應(yīng)用于設(shè)計大整數(shù)的模乘和模冪
5、算法的較優(yōu)編碼技術(shù)。本課題的完成,為公鑰密碼體制的進(jìn)一步推廣作出了較大的貢獻(xiàn),使得主要運(yùn)算為大整數(shù)模冪運(yùn)算的公鑰密碼算法的運(yùn)算速度大大提高,具有廣闊的商業(yè)價值。關(guān)鍵詞:公鑰密碼模乘模冪滑動窗口編碼限長游程編碼RESEARCH0NFASTIMPLEMENTATl0NOFRSAALGORITHMANDITSIMPROVEMENTABSTRACT■Thepublic—keycryptosystemextendsthecryptologyfromthetraditionalgovernmentandmilitaryapplicationstocommercialandciviliana
6、reas,makingthecommercialandsocialvaluesofmodemcryptographywidelyrecognized.Currently,RSAisthemostwidelyusedpublic—keycryptosystem.However,RSAalgorithmisbasedonlargeprimenumbersdecompositionproblems.Inparticular,topreventtheattacks,themoldlengthisincreasing.Itsmainoperationsarelargeintegermod
7、ularexponentiationandmodularmultiplication,andthealgorithm’SlowspeedbecomesaprominentRSAdefect.Therefore,itisworthwhiletoresearchonacceleratingthelargeintegermodularexponentiationandmodularmultiplicationalgorithm.Thispaperfocusesontheaccelerationof