RSA公钥加密算法的设计与实现
RSA公钥加密算法的设计与实现
【论文摘要】
RSA公钥加密算法是目前最有影响力的非对称加密算法，为ISO的推荐的加密标准。而非对称加密因其安全性、开放性以及在数字签名技术中的重要性，在我们的生活中被使用得越加频繁。
RSA的安全性建立在大整数的分解困难上，其基本原理是初等数论中的欧拉定理。在工业实现上，为了保证加密的安全性，通常要求密钥对大于1Kbits，然而计算机的整型变量为32bits，这构成一个矛盾。此外，RSA密钥的生成需要产生随机的大素数，这也是本文需要解决的问题。
【关键词】RSA；非对称加密；素数
The d esign and implementation of RSA public key
encryption algorithm
【ABSTRACT】
RSA public key encryption algorithms are the most influential dissymmetrical encryption algorithms, the recommended encryption standard to ISO. And dissymmetrical encryption is used more and more frequently in our lives because of its security, openness and the importance in digital signature technology.
RSA's security is built on the difficulties of big integer factorization, whose basic principle is the Euler's theorem in elementary number theory. In order to ensure the security of encryption, when it comes to industry, we often require the key pair is greater than 1Kbits. However, the integer class of computers occupies 32bits, which constitutes a contradiction. In addition, RSA's key-generation needs a random large prime number, which is also a problem to be solved.
【Keywords】RSA; dissymmetrical encryption; prime number
目录
RSA公钥加密算法的设计与实现 ...................... II The design and implementation of RSA public key encryption algorithm .............................................. II 目录............................................... III 一．前言 (1)
（一）引论 (1)
（二）背景知识 (2)
1. 密码技术的发展 (2)
2. 密码学的主要任务 (4)
3. 密码系统的安全性 (5)
4. 对称与非对称密码的区别 (5)
5. 公钥：RSA密码体制 (6)
二、实验部分 (8)
（一）实验目的 (8)
（二）实验环境 (8)
（三）实验步骤 (8)
1. 大整数类 (8)
2. 快速模幂运算 (9)
3. 快速产生随机素数 (9)
4. 扩展的欧几里德算法 (10)
（四）代码设计 (11)
1. 大整数类 (11)
2. Rsa类 (14)
3. 关键代码 (16)
三、结果与讨论 (17)
（一）程序展示 (17)
1. 程序主界面 (17)
2. RSA密钥产生 (18)
3. 加密解密展示 (20)
（二）RSA分析 (21)
1. RSA的安全性 (21)
2. RSA效率 (22)
（三）小结 (24)
注释 (25)
参考文献 (26)
致谢 (27)
一．前言
（一）引论
从公元前5世纪，古希腊斯巴达人用木棍和带子进行换位密码，到现在的网上购物、网上银行，密码学在我们生活中占着越来越重要的地位。如同我们寄信会把信纸放入信封并在封口签名，以免他人获知信件内容以及在投递过程中被更改丢失原意，使用密码是为了保证信息的秘密性、不可更改性等。
密码学真正得到革新，是在计算机的广泛传播之后。1977年，DES （the Data Encryption Standard ，数据加密标准）被美国政府正式采纳 (1)。同年，RSA 公钥加密算法由Ron Rivest 、Adi Shamirh 和Len Adleman 在美国麻省理工学院开发，是目前最有影响力的公钥加密算法，现已被ISO 推荐为公钥数据加密标准。 (2)
2005年电子签名法的施行 (3)，是中国信息化进程发展的必然需求和有力保障，说明了密码学被公众相信、使用，并被立法支持。电子签名技术的实现需要用到非对称算法和报文摘要，所以，RSA 作为公钥加密的标准算法，值得我去学习、研究和实现。
RSA 算法的数学基础是初等数论中的欧拉定理，其安全性建立在大整数因子分解的困难性上。为了有效地实现RSA 密码体制，必须解决如下三个问题： (4)
1. 大整数类的实现：计算机中，通常的编程语言的长整型是64bits 的，而计算安全的RSA 要求密钥长度长达1024bits 或以上，故要设计出一个无限大（大于10000bits ）的整数类，并重载各种初等运算。
2. 模幂运算mod m a n 的快速计算：RSA 的加密解密算法都需要大量的模n 指数运算，而模n 和指数m 都很大，所以模幂运算的快速算法十分重要。
3. 快速产生大素数：RSA 算法中每一个密钥的产生需要两个随机的大素数参与运算，然而现在还没有产生任意大素数的有用技术。通常的做法是随机选取一个需要数量级的奇数并验证是否素数，如此重复。因此验证素数的算法速度也十分重要。
接下来，我会参考各个相关文献，找出办法解决问题，并实现RSA 算法。
（二）背景知识
在古代战争中，因为需要的保密通信，密码技术应运而生。但长久以来，军事、政治、外交等要害部门，为求保密，并不外传密码技术，而是一直把持着密码知识。然而随着计算机技术和网络通信技术的发展，越来越多的电子政务、电子商务普遍需求安全通信，密码技术才从军用走向商用民用，并得到更加迅速的发展。
在如今的信息时代，信息安全的重要性日益彰显，密码学作为信息安全的核心也受到各个机构的重视。密码技术不但可以保证信息的机密性，还有防篡改和数字签名等功能。下面我将做一个密码学的简介。
1. 密码技术的发展
根据加密解密手段和器械的不同，密码技术的发展历史大致可以划分古典密码、近代密码和现代密码时期这三个时期。(5)
（1）古典密码时期
这一时期从古代到19世纪末，长达数千年。由于这个时期社会生产力底下，产生的许多密码体制都是以“手工作业”的方式进行，用纸笔或简单的器械实现加密和解密。
公元前440多年的斯巴达人发明了一种称为“天书”的加密器械来秘密传递军事情报。“天书”是通过把一个带状物如羊皮带，成螺旋状紧紧地缠绕在一根权杖或者木棍上，然后再沿着纵向书写信息，展开后就成为无意义的点线。解密时，找一个同样直径的木棍缠绕上，就可以看到明文。这是最早的移位密码（也称换位密码或置换密码）。
在大约公元前1世纪，罗马帝国凯撒大帝设计出一种简单的替换式密码，并在高卢战争中使用。这种密码的实现方式是把信中每个文字的字母都按字母顺序表中相隔两位后的一个字母取代。
这一时期的密码技术仅是一门文字变换艺术，如上面所说的置换密码和替换密码。这样的密码研究和应用远没有形成一门科学，最多能称为密码术。
（2）近代密码时期
近代密码时期是指20世纪初到20世纪50年代左右。这个时期的加密解密主要是用机电设备来实现的。
1895年无线电诞生后，各国在通信，特别是军事通信中普遍采用无线电技术。由于无线电的广播性，为了实现保密，各国随即开始研究无线电密码的编制和破译。从1919年以后的几十年中，密码研究人员设计出了各种各样采用机电技术的密码及来取代手工编码加密方法，实现保密通信的自动编解码。
近代密码时期可以看作是科学密码学的前夜，这阶段的密码技术是一种技巧和经验的结合体，还不是一门科学。密码学专家常常通过经验和技巧来设计加密算法（即转轮机），而没有形成系统的理论体系。
（3）近代密码时期
1949年香农（Claude Shannon）的奠基性论文“保密系统的通信理论”的发表，首次将信息论引入密码技术的研究，用统计的观点对信源、密码源、秘闻进行数学描述和定量分析，引入了不确定性、多余度、唯一解距离等安全性测度概念和计算方法，为现代密码学研究与发展奠定了坚实的理论基础，把已有数千年历史的密码技术推向了科学的轨道，使密码学成为一门真正的科学。
1977年，美国国家标准局正式公布实施了美国的数据加密标准（Data Encryption Standard, DES），被多个部门和标准化机构采纳为标准，甚至成为事实上的国际标准。更具有重要意义的是DES密码开创了公开全部密码算法的先例，大大推动了分组密码理论的发展和技术应用。
1976年，美国斯坦福大学的注明密码学迪菲（W. Diffie）和赫尔曼（M. Hellman）发表了“密码学新方向”疑问，首次提出了公钥密码体制的概念和设计思想，开辟了公开密钥密码学的新领域，掀起了公钥密码研究的序幕。受到他们的思想启迪，Ron Rivest、Adi Shamirh和Len Adleman提出了第一个较完整的公钥密码体制——RSA体制，成为公钥密码的杰出代表和实施标准，在密码学历史上是一个里程碑。
由于计算机技术和网络通信技术的研究和发展，密码学又出现很多新的课
题。如，过去普遍认为有足够安全性的DES密码算法，在新的技术和分析方法前，被证明是不够安全的，因此又确定了新的加密标准AES（Advanced Encryption Standard，高级加密算法）。在公钥密码领域，椭圆曲线密码体制由于其安全性高、计算速度快等优点引起人们的普遍关注和研究，并在公钥密码技术中取得重大进展，成为公钥密码研究的新方向。在数字签名方面，各种具有不同实际应用背景的签名方案，如盲签名、群签名、一次性签名、不可否认签名等不断出现。
在密码学应用方面，各种有实用价值的密码体制的快速实现受到高度重视，许多密码标准、应用软件和产品被开发和应用。美国、德国、日本和我国等许多国家已经颁布了数字签名法，使数字签名在电子商务和电子政务等领域得到了法律的认可，推动了密码学研究和应用的发展。
2. 密码学的主要任务
经典的密码技术研究的是加密和解密的理论，然而现在的密码学不再局限于此，而是成为信息安全的重要组成部分，为存储和传输中的数字信息提供如下几个方面的安全保护。
（1）机密性
即保证信息不被未授权的人获得信息内容。通过加密信息实现。
（2）数据完整性
即保证信息被使用时的内容，跟它被制作出来时一致。要防止的修改包括篡改、插入、删除和重放。通过加密、报文摘要和数字签名等实现。
（3）鉴别
即保证信息来源的身份是预期身份，并隐含了数据完整性服务。
（4）抗抵赖性
即通信实体不能否认之前的通信行为，包括发送过的信息以及收到的信息。
3. 密码系统的安全性
密码系统的安全性由密码算法的安全性和密钥管理的安全性组成，必须同时完善密码算法以及密钥管理才能保证密码系统的安全。下面仅介绍密码算法安全性的评价标准，通常由以下三种方法评估。
（1）无条件安全性
即假定攻击者拥有无限的计算资源，也无法通过唯密文攻击获得明文或者密钥。也就是说攻击者在观察密文前后，密钥的不确定性没有改变，这要求有跟消息一样长的随机密钥。符合这个要求的一次一密密码体制因为密钥的分配问题，往往并不实用。
（2）计算安全性
即攻它破所需的计算量远大于攻击者的计算资源（或者攻破所能获得的利益），就可以定义这个密码算法是安全的。目前多数使用的密码体制都属于这一类。
（3）可证明安全性
即可以把密码体制的安全性归结为某个数学难题，而这个数学难题（如大整数分解）被证明是求解困难的。可证明安全性是计算安全的。
4. 对称与非对称密码的区别
对称密码加密解密用的是同一个密钥，而非对称密码却是成对出现，一个用以加密，另一个用来解密。通常非对称密码把其中一个密钥公开作为公钥，另一
个私有作为私钥。因此，非对称密码又称为公钥密码。
（1）密钥数量
对称加密要求每一对用户都有一个密钥来保证安全通信。对n 个用户，要保
证两两之间能够安全通信，需要2*(1)/2n C n n =-个密钥。而非对称只需每个用
户拥有自己的私钥和其他用户的公钥就能进行加密通信。
（2）效率
由于非对称加密通常基于某些数学难题，通常来自于数论，这些问题的底层涉及到大量模幂运算，相对于对称密码需要更多的计算资源。所以通常公钥密码只用于加密少量数字信息，通过公钥加密传输对称加密密钥来加密文件。
（3）系统开放性
对称密码需要通信双方有相同的密钥才能进行加密通信，这在双方不认识或者没有安全的信道传递对称密钥的情况下，无法进行加密通信。而公钥加密系统只要获得对方公开的公钥就可以进行加密通信。
（4）数字签名
数字签名（Digital Signature ）技术是不对称加密算法的典型应用。 (6)
5. 公钥：RSA 密码体制
公钥密码体制的一个想法就是：也许能找到一个密码体制，使得由给定的e k 来求d k 是计算上不可行的。如果这样的话，加密规则e k 是一个公钥，可以在一个目录中公布（这也就是公钥体制名称的由来）。 (7)
RSA 公钥密码体制的具体描述如下。 (4)
（1）密钥生成
选择两个随机大素数p 和q ，并计算
n pq =和()(1)(1)n p q ?=--。
选择一个随机数e ，1()e n ?<<，满足gcd(,())1e n ?=，并计算
1mod(())d e n ?-=。
公钥为(,)e n ，私钥为d 。
（2）加密
对明文m n <，其对应密文为
mod e d m n =。
（3）解密
对密文c ，其对应明文为
mod d m c n =。
（4）证明
由于1mod(())de n ?≡，故存在整数k 满足
()1de k n ?=+。
故有
()11(1)()mod ed k n p k q m m m m m q ?+--==≡。
而此式在gcd(,)m p p =时显然也成立。同样可以推出
()1mod ed k n m m m q ?+=≡
故有
()1mod d ed k n c m m m n ?+==≡
二、实验部分
（一）实验目的
通过对RSA 的研究和实现，学习RSA 的数学基础、掌握RSA 加密的原理和方法、巩固计算机编程能力。
（二）实验环境
Microsoft Windows 7
Microsoft Visual Studio 2010
Microsoft .Net Framework 4.0
使用C# 编程语言
（三）实验步骤
在引论中写了要实现RSA ，必须先解决大整数类的实现、模幂运算的快速计算以及快速产生大素数这三个问题。此外，计算
1mod(())d e n ?-=
需要用到扩展的欧几里德算法（Extended Euclid ）。
1. 大整数类
大整数一般指数位超过计算机整数类型值集范围的整数。如C 中的Unsigned long 型整数能处理整数值4294967295（232-1），占据32bits 存储空间，此时，大整数就是指大于4294967295的十位以上的整数。若取109为“基”，即以109为一个存储单元。109=（1000）3<102410=230，占30位，以4Bytes 的整型长度存储的话，空间利用率可达93.8%。 (8)同时，同时有表达直观、容易理解、录入输出方便和数据处理能力较高的优点。
然而，为了模幂运算的效率，最终决定以2为基，用bool 型数组而不是int 型，并重载加、减、乘、除、求余、相等、不等、大于、小于等运算符。
2. 快速模幂运算
计算模幂运算mod b a c 。快速模幂运算又称快速幂取模，其原理是
mod (mod )(mod )mod ab c a c b c c =。
故，令k 为整数，若2b k =，2mod mod (mod )(mod )mod b k k k a c a c a c a c c ==； 若21b k =+，212mod mod (mod )(mod )mod b k k a c a c a c a c c +==。 因此可以分解计算，有快速算法：
int exp_mod(int a, int b, int n)
{
int r = 1;
while (b)
{
if (b & 1) r = (r * a) % n;
a = (a * a) % n;
b >>= 1;
}
return r;
}
3. 快速产生随机素数
如引论所说，没有方法直接产生一个素数，通常的做法是产生一个随机奇数，判断是否为素数，产生一个随机数恰好是素数的概率是。于是分为两部分，一是随机数产生，二是素性判断。
由计算机函数产生的随机数称伪随机数，有许多文章对伪随机数的构造原理、实现方法和效果（生产效率和随机性）进行了分析和研究，但由于mscorlib.dll 中有伪随机数生成器random()，所以不再重写而是直接阅读MSDN (9)使用之。
素数测试算法主要分两种：概率素数测试算法和真素数测试算法。
概率素数测试算法的特点是：算法速度较快、原理简单、易于编程实现、有一定的误判概率。真素数测试算法速度很慢，比如最基础的从3开始测试每一个
整数是否被待测试数n 杂度是6log n ε+，基于割圆环的测试算法的时间复杂度是logloglog log c n n 。且真素数测试算法背后的理论比较艰深，在计算机中的实现十分复杂，实现复杂带来的不正确实现的安全隐患要比概率算法误判带来的安全隐患大得多。概率算法的误判完全可以被控制在一个极低的可接受的概率范围内，误判概率在80(1/2)以下足以满足绝大部分的安全需求。综合上述原因，在实际应用中，大多使用基于概率的素数测试算法。
通过对比，选择Miller-Rabin 算法作为素数测试算法。Miller-Rabin 算法是Fermat 算法的一个变形改进，它的理论基础是从Fermat 定理引申而来的。
Fermat 定理：n 是一个奇素数，a 是任何整数(11)a n ≤≤-，
则11(m o d )n a n -≡。
事实：n 是一个奇素数，则方程21mod x n ≡只有1±两个解。
Miller-Rabin 算法的理论基础：如果n 是一个奇素数，将1n -表示为2*s r 的形式（r 是奇数），a 是和n 互素的任何整数，那么1(mod )r a n ≡或者对某个j (01,)j s j Z ≤≤-∈，等式21(mod )jr a n ≡-成立。 这个理论由Fermat 定理以及一个事实推导而来。
Miller-Rabin 算法的误判概率为(1/4)t ，时间复杂度为3
2(log ())O n ，其中t 为
测试次数。 (10)
4. 扩展的欧几里德算法
欧几里德算法是辗转相除法，用于计算两整数的公约数，其依赖原理如下：
gcd(,)gcd(,mod )a b b a b =（a b >且mod a b 不为0）
扩展欧几里德定理：对于不完全为0的非负整数a ，b ，以及其最大公约数gcd(,)a b ，必存在整数对x ，y ，使得gcd(,)a b ax by =+。
其实现方法是在进行辗转相除法时，因为
gcd(,)gcd(,mod )'(mod )'
a b ax by b a b bx a b y =+=+ 恒等变换得
'
'(/)'x y y x a b y ==-（其中/a b 是取商）
故能设计出一个递归函数，求出x ，y ，满足gcd(,)a b ax by =+。
（四）代码设计
1. 大整数类
在前文中已经说明了我的大整数类的数据结构定为布尔型数组。实际上，在开始写这个类的时候，我用的是int 数组与bool 数组并存或者可以随时切换的形式。这样的类可以灵活处理数据，比如录入一个十进制数，和另外一个十进制数相加再输出时，可以直接调用两个十进制数相加的函数，并直接输出，节约了三次进制转换。然而，这样的类变得很复杂和臃肿，且在这个程序里不会有这样的要求，故最后把十进制模式移出并构建新类。类的数据结构与字段如下：
图2.4.1-1 十进制整数类
图2.4.1-2 二进制整数类字段，类名Bigint
类中，用数组储存大整数的绝对值，符号放在sign 中，并用length 表示长度。这里的length 不是数组的长度，而是数组的有用长度；用length 表示长度可
以在比较大小，四则运算时节约计算。大整数绝对值在bool数组中的储存方式是，把大整数二进制化，低位放在数组低位，高位在数组高位。如把2放入，则把2二进制化为102，则_body[0]=0,_body[1]=1;并赋值length为2。
接着进行运算符重载。
图2.4.1-3 大整数类运算符重载
其中包括一个从int型到Bigint型的隐式转换函数，可以在进行Bigint型与int型值进行运算时节约代码。公开的函数中，对5种二元计算，6种比较运算以及1种一元计算进行了重载，并完成了哈希函数和相等函数的重写。下面的私有函数用以辅助上面的函数实现，如BinaryCheckZero用于确定body的有效数位；BinaryDividestep用于做除法运算中的一步，即被除数顶位减除数。
下面是进制转换与输入输出。
图2.4.1-4 进制转换
十进制到二进制的转换是通过一般的“除2取余，逆序排列”(11)方式，但二进制转十进制却不是用通常的“按权相加”法，而是“乘2加1”的方法。
图2.4.1-5 输出
重写ToString()函数，用了参数c以确定输出类型，比如二进制输出、十进制输出等。
图2.4.1-6 输入与构造函数
输入主要是从string型到Bigint型，同样用参数c传递数据类型，d为十进制输入，b为二进制输入。没有做完整性检查。静态构造函数是设定一个全文的随机种子。
在我开始构思设计Bigint类时，是把它暂定为内部的（internal关键字），所以各个主要函数与辅助函数时严格地区分了public和private。而在实现随机数产生、Miller-Rabin素数测试等算法的时，发现直接对数组body进行操作能大大提高代码效率，故在Bigint类中添加了几个完整的功能函数。
图2.4.1-7 功能函数
其中，IsPrime()是直接调用IsPrimeMillerRabin2Nd()；Randomint()产生n位
二进制奇数；Mimod()是快速模幂运算（由于模幂运算不是常用计算，所以也放在功能函数里了）。
类里还有几个常数声明或者只读变量。
图2.4.1-8 常数声明与只读变量
其中，Randomlength是产生Miller-Rabin随机测试数a的长度；Randomtype 指产生的是二进制随机数；IsPrimeTimes是Miller-Rabin素数判定的测试次数；Rnm是上文所说静态构造函数里的随机种子变量。
为了避免设置生成顺序与引用的麻烦，把Bigint类改为public类型，方便下面Rsa类对其的引用。
2. Rsa类
Rsa类的功能是RSA公钥模数n、加密解密密钥对(,)
e d的产生，以及加密解密功能。
图2.4.2-1 字段
其中，PrimeA是素数p；PrimeB是素数q；N是素数积n pq
=；MultiPrime
?=--；EnCodekey是加密密钥e；DeCodekey 是产生密钥的中间变量()(1)(1)
n p q
是解密密钥d。
图2.4.2-2 构造函数
RsaReBuild()实际上就是生成函数。
图2.4.2-3 生成函数
前两个函数分别是产生n的函数和产生(,)
e d的。RsaNaEnginner()中第二个a 并无实际意义，只是为了符合函数的命名习惯。
图2.4.2-4 辅助函数
创建了一个结构ExtendedEuclidReturn用于返回扩展的欧几里德算法解值；ExtendedEuclid()是扩展的欧几里德函数；PrimeEngineer()是素数产生函数。
图2.4.2-5 功能函数
分别是加密解密函数，Rsashow()用于展示RSA的各个字段。
图2.4.2-5 常数声明
这两个长度都是指二进制随机数产生时的位数。
3. 关键代码
大整数类虽然很关键也很繁琐，但其实原理很简单，实现上也没有什么困难，所以不列为关键代码。
（1）快速模幂运算