RSA算法之64位快速實(shí)現(xiàn).pdf

1、當(dāng)前，網(wǎng)絡(luò)信息安全的迫切性日趨突出，RSA算法作為信息安全領(lǐng)域的重要工具已被廣泛應(yīng)用與推廣。在協(xié)議通信中，RSA作為密鑰傳輸?shù)募用芄ぞ咭殉蔀檎麄€(gè)通信安全體制中最難以破譯的環(huán)節(jié)。1976年，斯坦福大學(xué)的Diffie和Hellman基于離散對(duì)數(shù)問題(DLP)發(fā)表了題為“New Directions in Cryptography”作為公鑰密碼的第一篇文章;1977年，麻省理工學(xué)院的Rivest、Shamir、Adleman等3人基于數(shù)論提出

2、了一個(gè)可行的并能夠?qū)嵺`的數(shù)字簽名方案，隨著人們對(duì)此方案的不斷驗(yàn)證，其安全性和性能得到了人們的一致肯定，已成為最流行的公鑰密碼體制之一，遂以3人的名字命名為RSA。但RSA算法的缺點(diǎn)在于隨著密鑰規(guī)模的擴(kuò)大，其安全性得到提高的同時(shí)，其運(yùn)算速度與效率會(huì)出現(xiàn)降低等問題。2011年，NIST推薦使用RSA中N的規(guī)模為2048。因此，有效地提升RSA算法的運(yùn)算速度已成為熱門問題之一。
　　本文主要對(duì)公鑰密碼體制中所涉及的數(shù)學(xué)背景、大數(shù)的乘法與

3、模乘法、模指數(shù)等問題進(jìn)行了深入研究，在目前流行的64位字長(zhǎng)操作系統(tǒng)中，分別以232和264為基編程實(shí)現(xiàn)了RSA運(yùn)算中所涉及的各項(xiàng)算法程序，并在實(shí)現(xiàn)大數(shù)乘法的過程中，對(duì)傳統(tǒng)乘法與Karatsuba算法的效率進(jìn)行了比較，特別在對(duì)Karatsuba算法實(shí)現(xiàn)時(shí)，測(cè)試出了臨界值d0的取值范圍，當(dāng)字長(zhǎng)為32為時(shí)，乘積N達(dá)到2048時(shí)，d0為32時(shí)最優(yōu);當(dāng)字長(zhǎng)為64位時(shí)，乘積N達(dá)到2048時(shí)，d0為16時(shí)最優(yōu)，乘積N達(dá)到8092時(shí)，d0為64時(shí)最優(yōu)。