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

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

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

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

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