RSA课程设计

哈尔滨理工大学

课程设计

题目：RSA加密算法

院、系：计算机科学与技术学院网络工程系

班级：

学号：

姓名：

同组成员：

指导教师：

成绩：

2014年06月27日

一.系统设计的目标

通过运用RSA加密算法，实现对信息的加密和解密，掌握RSA算法的实现原理以及实现过程。

二.系统原理:

RSA是在1978年，由美国麻省理工学院(MIT)的Rivest、Shamir和Adleman在题为《获得数字签名和公开钥密码系统的方法》的论文中提出的。它是一个基于数论的非对称(公开钥)密码体制，是一种分组密码体制。其名称来自于三个发明者的姓名首字母。它的安全性是基于大整数素因子分解的困难性，而大整数因子分解问题是数学上的著名难题，至今没有有效的方法予以解决，因此可以确保RSA算法的安全性。RSA系统是公钥系统的最具有典型意义的方法，大多数使用公钥密码进行加密和数字签名的产品和标准使用的都是RSA算法。 RSA算法是第一个既能用于数据加密也能用于数字签名的算法，因此它为公用网络上信息的加密和鉴别提供了一种基本的方法。它通常是先生成一对RSA 密钥，其中之一是保密密钥，由用户保存；另一个为公开密钥，可对外公开，甚至可在网络服务器中注册，人们用公钥加密文件发送给个人，个人就可以用私钥解密接受。为提高保密强度，RSA密钥至少为500位长，一般推荐使用1024位。

该算法基于下面的两个事实,这些事实保证了RSA算法的安全有效性：

1)已有确定一个数是不是质数的快速算法；

2)尚未找到确定一个合数的质因子的快速算法。

目前，日益激增的电子商务和其它因特网应用需求使公钥体系得以普及，这些需求量主要包括对服务器资源的访问控制和对电子商务交易的保护，以及权利保护、个人隐私、无线交易和内容完整性（如保证新闻报道或股票行情的真实性）等方面。公钥技术发展到今天，在市场上明显的发展趋势就是PKI与操作系统的集成，PKI是“Public K ey Infrastructure”的缩写，意为“公钥基础设施”。公钥体制广泛地用于CA认证、数字签名和密钥交换等领域。公钥加密算法中使用最广的是RSA。RSA算法研制的最初理念与目标是努力使互联网安全可靠，旨在解决DES算法秘密密钥的利用公开信道传输分发的难题。而实际结果不但很好地解决了这个难题；还可利用RSA来完成对电文的数字签名以抗对电文的否认与抵赖；同时还可以利用数字签名较容易地发现攻击者对电文的非法篡改，以保护数据信息的完整性。目前为止，很多种加密技术采用了RSA 算法，该算法也已经在互联网的许多方面得以广泛应用，包括在安全接口层（SSL）标准（该标准是网络浏览器建立安全的互联网连接时必须用到的）方面的应用。此外，RS A加密系统还可应用于智能IC卡和网络安全产品。

RSA算法的编程思路

1)确定密钥的宽度。

2)随机选择两个不同的素数p处q，它们的宽度是密钥宽度的二分之一。

3)计算出p和q的乘积n 。

4)在2和Φ(n)之间随机选择一个数e , e 必须和Φ(n)互素，整数e用做加密密钥（其中Φ(n)=(p-1)*(q-1)）。

5)从公式ed ≡ 1 mod Φ(n)中求出解密密钥d 。

6)得公钥（e ，n ）, 私钥 (d , n) 。

7)公开公钥，但不公开私钥。

8)将明文P (假设P是一个小于n的整数)加密为密文C，计算方法为： C = Pe mod n

9) 将密文C解密为明文P，计算方法为： P = Cd mod n 然而只根据n和e（不是p和q）要计算出d是不可能的。因此，任何人都可对明文进行加密，但只有授权用户（知道d）才可对密文解密

三. 系统功能分析:

1.产生密钥

首先要使用概率算法来验证随机产生的大的整数是否质数，这样的算法比较快而且可以消除掉大多数非质数。假如有一个数通过了这个测试的话，那么要使用一个精确的测试来保证它的确是一个质数。

除此之外这样找到的p和q还要满足一定的要求，首先它们不能太靠近，此外p-1或q -1的因子不能太小，否则的话N也可以被很快地分解。

此外寻找质数的算法不能给攻击者任何信息，这些质数是怎样找到的，尤其产生随机数的软件必须非常好。要求是随机和不可预测。这两个要求并不相同。一个随机过程可能可以产生一个不相关的数的系列，但假如有人能够预测出（或部分地预测出）这个系列的话，那么它就已经不可靠了。比如有一些非常好的随机数算法，但它们都已经被发表，因此它们不能被使用，因为假如一个攻击者可以猜出p和q一半的位的话，那么他们就已经可以轻而易举地推算出另一半。

此外密钥d必须足够大，1990年有人证明假如p大于q而小于2q（这是一个很经常的情况）而，那么从N和e可以很有效地推算出d。此外e = 2永远不应该被使用。

和其它加密过程一样，对RSA来说分配公钥的过程是非常重要的。分配公钥的过程必须能够抵挡一个从中取代的攻击。假设Eve交给Bob一个公钥，并使Bob相信这是Alice 的公钥，并且她可以截下Alice和Bob之间的信息传递，那么她可以将她自己的公钥传给Bob，Bob以为这是Alice的公钥。Eve可以将所有Bob传递给Alice的消息截下来，将这个消息用她自己的密钥解密，读这个消息，然后将这个消息再用Alice的公钥加密后传给Alice。理论上Alice和Bob都不会发现Eve在偷听他们的消息。今天人们一般用数字认证来防止这样的攻击。

和其它加密过程一样，对RSA来说分配公钥的过程是非常重要的。分配公钥的过程必须能够抵挡一个从中取代的攻击。假设Eve交给Bob一个公钥，并使Bob相信这是A lice的公钥，并且她可以截下Alice和Bob之间的信息传递，那么她可以将她自己的公钥传给Bob，Bob以为这是Alice的公钥。Eve可以将所有Bob传递给Alice的消息截下来，将这个消息用她自己的密钥解密，读这个消息，然后将这个消息再用Alice的公钥加密后传给Alice。理论上Alice和Bob都不会发现Eve在偷听他们的消息。今天人们一般用数字认证来防止这样的攻击。

2.加密

RSA用到的公式和定理

一、数和互为素数

任何大于1的整数a能被因式分解为如下唯一形式：

a=p1p2…pl(p1,p2，…，pl为素数）

二、模运算

①{[a(mod n)]×[b(mod n)]}modn≡（a×b)(mod n)

②如果（a×b）=（a×c）（mod n),a与n互素，则

b=c(mod n)

三、费马定理

若p是素数，a与p互素，则

a^(p-1）≡1 （mod p）

四、欧拉定理

欧拉函数φ（n）表示不大于n且与n互素的正整数的个数。

当n是素数，φ（n)=n-1。n=pq,p,q均为素数时，则φ（n)= φ（p）φ（q)=（p-1）（q-1）。

对于互素的a和n，有a^φ（n)≡1(mod n)

用程序实现这一原理既是将待加密信息又ASCII码形式进行运算，得到的结果就是密文。

3.解密

解密过程和和加密过程算法原理一样，只是运用了不同的密钥解密，既私钥解密，因此实现原理和加密算法一致。

四.系统实现:

1.产生密钥

通过建立素数数组1到4000内的，并通过随机数选取数组里两个元素来实现素数p，q的选择；并根据素数因子计算出公钥和私钥；随机数选取同样通过随机数函数srand()实现，由于计算机性能限制，将随机数值限定为1000以内。rand()函数的使用方法如下：

random函数不是ANSI C标准，不能在gcc,vc等编译器下编译通过。但在C语言中int random(num)可以这样使用，它返回的是0至num-1的一个随机数。可改用C++下的rand函数来实现。

1、C++标准函数库提供一随机数生成器rand，返回0－RAND_MAX之间均匀分布的伪随机整数。RAND_MAX必须至少为32767。rand()函数不接受参数，默认以1为种子（即起始值）。随机数生成器总是以相同的种子开始，所以形成的伪随机数列也相同，失去了随机意义。（但这样便于程序调试）

2、C++中另一函数srand（），可以指定不同的数（无符号整数变元）为种子。但是如果种子相同，伪随机数列也相同。一个办法是让用户输入种子，但是仍然不理想。

3、比较理想的是用变化的数，比如时间来作为随机数生成器的种子。time的值每时每刻都不同。所以种子不同，所以，产生的随机数也不同。

// C++随机函数（VC program）

#include

#include

#include

using namespace std;

#define MAX 100

int main(int argc, char* argv[])

{

srand( (unsigned)time( NULL ) );//srand()函数产生一个以当前时间开始的随机种子.应该放在for等循环语句前面不然要很长时间等待

for (int i=0;i<10;i++)

cout<

return 0;

}

二、rand()的用法

rand()不需要参数，它会返回一个从0到最大随机数的任意整数，最大随机数的大小通常是固定的一个大整数。

/* maximum value returned by "rand" function

*/

#define RAND_MAX 0x7fffu

这个是bcc55中的定义，说明这个整数的最大数是0x7fffu，u代表unicode编码。

这样，如果你要产生0~10的10个整数，可以表达为：

int N = rand() % 11;

这样，N的值就是一个0~10的随机数，如果要产生1~10，则是这样：int N = 1 + rand() % 10;

总结来说，可以表示为：

a + rand() % n

其中的a是起始值，n是整数的范围。

a + rand() % (b-a+1) 就表示ａ～ｂ之间的一个随机数

若要0~1的小数，则可以先取得0~10的整数，然后均除以10即可得到随机到十分位的10个随机小数，若要得到随机到百分位的随机小数，则需要先得到0~100的10个整数，然后均除以100，其它情况依

此类推。

通常rand()产生的随机数在每次运行的时候都是与上一次相同的，这是有意这样设计的，是为了便于程序的调试。若要产生每次不同的随机数，可以使用srand( seed )函数进行随机化，随着seed的不同，就能够产生不同的随机数。

如大家所说，还可以包含time.h头文件，然后使用srand(time(0))来使用当前时间使随机数发生器随机化，这样就可以保证每两次运行时可以得到不同的随机数序列(只要两次运行的间隔超过1秒)。

2.加密和解密

加密通过对读取文件的字符串逐个输出成字符，再将字符转换成ASCII码形式进行数学处理，实现方式既是强制类型转换，对于RSA加密函数实现的求幂取余的实现方法则是用递归和迭代实现，比循环效率更高，相比DES加密算法，RSA的特点使得其不适合加密长度大的信息，因此将加密长度限制在100字符以内。

RSA的解密过程和加密过程一样，只用私钥对加密信息进行解密即可得到明文的ASCII码，再通过强制类型转换既可以将密文还原成明文。

3.文件数据的输入输出

对于密钥，明文和密文都采取文件输入输出流的形式进行输入输出，C语言提供了文件输出输出流函数来实现，文件输出输出流的原理和语法如下：

fout << flush; fout.close();

现在你用文本编辑器打开文件，内容看起来是这样：

Here is a number: 150 Now here is a string: John Doe

很简单吧! 现在继续文件输入, 需要一点技巧, 所以先确认你已经明白了流操作，对 "<<" 和">>" 比较熟悉了, 因为你接下来还要用到他们。继续…

二、ASCII 输入

输入和"cin" 流很像. 和刚刚讨论的输出流很像, 但你要考虑几件事情。在我们开始复杂的内容之前, 先看一个文本：

12 GameDev 15.45 L This is really awesome!

为了打开这个文件，你必须创建一个in-stream对象,?像这样。

ifstream fin("input.txt");

现在读入前四行. 你还记得怎么用"<<" 操作符往流里插入变量和符号吧？好,?在 "<<" (插入)?操作符之后，是">>" (提取) 操作符. 使用方法是一样的. 看这个代码片段.

int number; float real;

char letter, word[8];

fin >> number; fin >> word; fin >> real; fin >> letter;

也可以把这四行读取文件的代码写为更简单的一行。

fin >> number >> word >> real >> letter;

它是如何运作的呢? 文件的每个空白之后, ">>" 操作符会停止读取内容, 直到遇到另一个>>操作符. 因为我们读取的每一行都被换行符分割开(是空白字符), ">>" 操作符只把这一行的内容读入变量。这就是这个代码也能正常工作的原因。但是，可别忘了文件的最后一行。

This is really awesome!

如果你想把整行读入一个char数组, 我们没办法用">>"?操作符，因为每个单词之间的空格（空白字符）会中止文件的读取。为了验证：

char sentence[101]; fin >> sentence;

我们想包含整个句子, "This is really awesome!" 但是因为空白, 现在它只包含了"This". 很明显, 肯定有读取整行的方法, 它就是getline()。这就是我们要做的。

fin.getline(sentence, 100);

这是函数参数. 第一个参数显然是用来接受的char数组. 第二个参数是在遇到换行符之前，数组允许接受的最大元素数量. 现在我们得到了想要的结果：“This is really awesome!”。

你应该已经知道如何读取和写入ASCII文件了。但我们还不能罢休，因为二进制文件还在等着我们。

三、二进制输入输出

二进制文件会复杂一点, 但还是很简单的。首先你要注意我们不再使用插入和提取操作符(译者注：<< 和 >> 操作符). 你可以这么做，但它不会用二进制方式读写。你必须使用read() 和write() 方法读取和写入二进制文件. 创建一个二进制文件, 看下一行。

ofstream fout("file.dat", ios::binary);

这会以二进制方式打开文件, 而不是默认的ASCII模式。首先从写入文件开始。函数write() 有两个参数。第一个是指向对象的char类型的指针, 第二个是对象的大小（译者注：字节数）。为了说明，看例子。

int number = 30; fout.write((char *)(&number), sizeof(number));

第一个参数写做"(char *)(&number)". 这是把一个整型变量转为char *指针。如果你不理解，可以立刻翻阅C++的书籍，如果有必要的话。第二个参数写作"sizeof(number)". sizeof() 返回对象大小的字节数. 就是这样!

二进制文件最好的地方是可以在一行把一个结构写入文件。如果说，你的结构有12个不同的成员。用ASCII?文件，你不得不每次一条的写入所有成员。但二进制文件替你做好了。看这个。struct OBJECT { int number; char letter; } obj;

obj.number = 15; obj.letter = ‘M’;

fout.write((char *)(&obj), sizeof(obj));

这样就写入了整个结构! 接下来是输入. 输入也很简单，因为read()?函数的参数和 write()是完全一样的, 使用方法也相同。

ifstream fin("file.dat", ios::binary); fin.read((char *)(&obj), sizeof(obj));

我不多解释用法, 因为它和write()是完全相同的。二进制文件比ASCII文件简单, 但有个缺点是无法用文本编辑器编辑。接着, 我解释一下ifstream 和ofstream 对象的其他一些方法作为结束.

四、更多方法

我已经解释了ASCII文件和二进制文件, 这里是一些没有提及的底层方法。

检查文件

你已经学会了open() 和close() 方法, 不过这里还有其它你可能用到的方法。

方法good() 返回一个布尔值，表示文件打开是否正确。

类似的，bad() 返回一个布尔值表示文件打开是否错误。如果出错，就不要继续进一步的操作了。最后一个检查的方法是fail(), 和bad()有点相似, 但没那么严重。

读文件

方法get() 每次返回一个字符。

方法ignore(int,char) 跳过一定数量的某个字符, 但你必须传给它两个参数。第一个是需要跳过的字符数。第二个是一个字符, 当遇到的时候就会停止。例子,

fin.ignore(100, ‘\n’);

会跳过100个字符，或者不足100的时候，跳过所有之前的字符，包括‘\n’。

方法peek() 返回文件中的下一个字符, 但并不实际读取它。所以如果你用peek() 查看下一个字符,

用get() 在peek()之后读取，会得到同一个字符, 然后移动文件计数器。

方法putback(char) 输入字符, 一次一个, 到流中。我没有见到过它的使用，但这个函数确实存在。写文件

只有一个你可能会关注的方法.?那就是 put(char), 它每次向输出流中写入一个字符。