RSA的快速实现

论文摘要

许多公钥加密、数字签名方案和一些杂凑函数需要Z_m中的运算,即模m的整数运算(m是大的正整数,可能是也可能不是素数)。在这些密码算法中很多都需要Z_m中的指数运算。例如,RSA、Rabin和ElGamal方案需要在Z_m中进行有效的指数运算(Z_m中的指数运算我们称为模指数运算)。模指数运算是大部分密码算法实现中最耗时的运算步骤。因此模指数运算是这些密码体制实现的关键,而大整数模运算是其核心运算。本文将对密码学中的大整数模运算进行研究。我们知道模指数运算都需要化为一序列的模平方乘运算。因此提高模指数运算速度可以从两方面入手:一、加快模指数运算中模乘法运算的速度;二、减少模指数运算中模乘运算的次数。我们的工作主要分为两部分:一部分是对大整数模乘运算进行分析和研究;另一部分是对大整数模指数运算的实现的研究。对于对于加快模乘法运算速度这方面,本文重点对Peter.L.Montgomery提出的Montgomery算法以及其改进算法进行分析。通过对Montgomery模乘算法的分析,本文提出了更有利于模指数运算的Montgomery模平方运算。Montgomery模平方运算是结合Montgomery模乘算法和Comba平方算法的模运算。经过理论分析以及实验发现Montgomery模平方算法的速度约是Montgomery模乘算法的74.6%。而我们知道指数运算最终都是化为平方乘运算,而其中平方运算在其中占很大的比例(对于滑动窗口算法约占5/6,因此对于滑动窗口指数运算,同时采用Montgomery平方和乘法的时间约是只采用Montgomery乘法的时间的78.9%),因此模平方算法的速度将决定模指数算法的运算速度。对于模指数运算的实现方面,本文主要对Knuth提出的滑动窗口指数算法进行分析,并介绍一种实用的寻找最优窗口的算法。该方法通过对指数的二进制表示进行划分,通过少量的预计算来减少模指数运算中模乘法的次数,从而达到减少模指数运算的时间。采用这种方法对于指数长度为512比特的模指数运算平均只需607次模乘运算(指数长度为1024比特指数运算平均需1195次)。

论文目录

• 中文摘要
• 英文摘要
• 第一章 引言
• 第二章 模乘法和模平方运算
• §2.1 概述
• §2.2 Montgomery算法分析
• §2.3 Montgomery模乘算法的改进算法
• §2.4 Montgomery模平方算法
• §2.4.1 FIPS Montgomery模乘算法
• §2.4.2 算法分析
• §2.4.3 Montgomery模平方算法
• §2.4.4 算法分析
• 第三章 大整数模指数运算
• §3.1 概述
• §3.2 BR二元算法
• §3.3 指数运算的窗口算法
• §3.3.1 设计思想
• §3.3.2 算法设计
• §3.3.3 算法分析
• §3.4 滑动窗口指数运算
• §3.4.1 设计思想
• §3.4.2 算法设计
• §3.4.3 窗口划分方法
• §3.4.4 算法分析
• §3.4.5 举例
• §3.5 加法链
• §3.6 Montgomery指数运算
• §3.6.1 算法设计
• §3.6.2 算法分析
• §3.6.3 举例
• §3.7 组合算法
• 参考文献
• 致谢
• 学位论文评阅及答辩情况表