RSA的快速實(shí)現(xiàn).pdf

1、許多公鑰加密、數(shù)字簽名方案和一些雜湊函數(shù)需要Zm中的運(yùn)算，即模m的整數(shù)運(yùn)算(m是大的正整數(shù)，可能是也可能不是素?cái)?shù)).在這些密碼算法中很多都需要Zm中的指數(shù)運(yùn)算.例如，RSA、Rabin和ElGamal方案需要在Zm中進(jìn)行有效的指數(shù)運(yùn)算(Zm中的指數(shù)運(yùn)算我們稱(chēng)為模指數(shù)運(yùn)算).模指數(shù)運(yùn)算是大部分密碼算法實(shí)現(xiàn)中最耗時(shí)的運(yùn)算步驟.因此模指數(shù)運(yùn)算是這些密碼體制實(shí)現(xiàn)的關(guān)鍵，而大整數(shù)模運(yùn)算是其核心運(yùn)算.本文將對(duì)密碼學(xué)中的大整數(shù)模運(yùn)算進(jìn)行研究.我們知道

2、模指數(shù)運(yùn)算都需要化為一序列的模平方乘運(yùn)算.因此提高模指數(shù)運(yùn)算速度可以從兩方面入手:一、加快模指數(shù)運(yùn)算中模乘法運(yùn)算的速度；二、減少模指數(shù)運(yùn)算中模乘運(yùn)算的次數(shù).我們的工作主要分為兩部分：一部分是對(duì)大整數(shù)模乘運(yùn)算進(jìn)行分析和研究；另一部分是對(duì)大整數(shù)模指數(shù)運(yùn)算的實(shí)現(xiàn)的研究.對(duì)于對(duì)于加快模乘法運(yùn)算速度這方面，本文重點(diǎn)對(duì)Peter.L.Montgomery提出的Montgomery算法以及其改進(jìn)算法進(jìn)行分析.通過(guò)對(duì)Montgomery模乘算法的分析，

3、本文提出了更有利于模指數(shù)運(yùn)算的Montgomery模平方運(yùn)算.Montgomery模平方運(yùn)算是結(jié)合Montgomery模乘算法和Comba平方算法的模運(yùn)算.經(jīng)過(guò)理論分析以及實(shí)驗(yàn)發(fā)現(xiàn)Montgomery模平方算法的速度約是Montgomery模乘算法的74.6％.而我們知道指數(shù)運(yùn)算最終都是化為平方乘運(yùn)算，而其中平方運(yùn)算在其中占很大的比例(對(duì)于滑動(dòng)窗口算法約占5/6，因此對(duì)于滑動(dòng)窗口指數(shù)運(yùn)算，同時(shí)采用Montgomery平方和乘法的時(shí)間約是

4、只采用Montgomery乘法的時(shí)間的78.9％)，因此模平方算法的速度將決定模指數(shù)算法的運(yùn)算速度.對(duì)于模指數(shù)運(yùn)算的實(shí)現(xiàn)方面，本文主要對(duì)Knuth提出的滑動(dòng)窗口指數(shù)算法進(jìn)行分析，并介紹一種實(shí)用的尋找最優(yōu)窗口的算法.該方法通過(guò)對(duì)指數(shù)的二進(jìn)制表示進(jìn)行劃分，通過(guò)少量的預(yù)計(jì)算來(lái)減少模指數(shù)運(yùn)算中模乘法的次數(shù)，從而達(dá)到減少模指數(shù)運(yùn)算的時(shí)間.采用這種方法對(duì)于指數(shù)長(zhǎng)度為512比特的模指數(shù)運(yùn)算平均只需607次模乘運(yùn)算(指數(shù)長(zhǎng)度為1024比特指數(shù)運(yùn)算平均需