网络安全技术大作业.doc

非对称算法――RSA算法
【实验目的】
1.了解非对称加密机制
2.理解RSA算法的加密原理

【实验原理】
1．非对称密钥加密概述
前面讲述了对称密钥加密体制。使用对称密钥加密体制进行保密通信时，任意不同的两个用户之间都应该使用互不相同的密钥。这样，如果一个网络中有n个用户，他们之间彼此都可能进行秘密通信，这时网络中将需要n(n-1)/2个密钥（其中，每个用户都需要保存n-1个密钥），这样巨大的密钥量给密钥分配和管理带来了极大的困难。另外，随着计算机网络，特别是因特网的发展，网络上互不相识的用户可能需要进行保密的会话（例如，如果用户在进行电子商务活动时，需要保密的连接，这时的客户对象可能根本不是固定的对象）。最后，对称密钥加密机制难以解决签名验证问题。
非对称密钥加密也称为公开密钥加密，或者叫做公钥加密算法。使用公开密钥密码的每一个用户都分别拥有两个密钥：加密密钥和解密密钥，它们两者并不相同，并且由加密密钥得到解密密钥在计算机上是不可行的。每一个用户的加密密钥都是公开的。因此，加密密钥也称为公开密钥。所有用户的公开密钥都将记录在作用类似于电话号码薄的密钥本上，而它可以被所有用户访问，这样每一个用户都可以得到其他所有用户的公开密钥。同时，每一个用户的解密密钥将由用户保存并严格保密。因此，解密密钥也称为私有密钥。
非对称密码算法解决了对称密码体制中密钥管理的难题，并提供了对信息发送人的身份进行验证的手段，是现代密码学最重要的发明。公钥加密算法一般是将对密钥的求解转化为对数学上的困难问题的求解，例如RSA算法的安全性是建立在“大数分解和素性检测”这个数论难题的基础上，已知两个大素数a、b，求出a*b是容易计算的，而已知a*b，想知道其是哪两个大素数的乘积目前还没有好的计算方法，另外也有一些非对称加密算法（如ELGamal算法）的安全性是基于求“离散对数”这个数学难题上的。
在公钥密码系统中每个实体都有自己的公钥和相应的私钥。公钥密码系统的加密变换和解密变换分别用E和D表示。任何实体B要向实体A发送信息m的步骤如下：实体B首先获得实体A的真实公钥的拷贝（eA），实体B使用eA计算密文c=E（m）并发送给实体A，实体A使用自己的私钥dA，计算m=D（c）解密密文，恢复出明文m。这里公钥不需要保密，但要保证它的真实性，即eA确实是实体A掌握的私钥dA所对应的公钥。提供真实的公钥比安全地分配密钥实现起来要容易得多。这也是公钥密码系统的主要优点之一。
公钥密码系统的主要目的是提供保密性，它不能提供数据源认证(Data Origin Authentication)和数据完整性(Data Integrity)。数据源认证是指：指定的数据是在以前的某个时间确实是由真正的源创建的。数据完整性是指：真正的源创建该数据后经过传输后存储没有发生改变。数据源认证和数据完整性要由其他技术来提供（如消息认证码技术、数字签名技术等）。
从本质上来看，公钥密码比对称密钥密码加密的速度要慢，粗略的说，公钥加密算法RSA硬件实现比分组加密算法DES硬件实现的速度慢1500倍，而软件实现的速度要慢100倍。
公钥解密也可以提供认证保证（如：在实体认证协议、带认证的密钥建立协议等）。公钥加密中必须有颁发让发送消息的人得到想要发送到的那个人的公钥的真实拷贝，否则就会受到伪装攻击。在实践中有很多方法分发真实的公钥，如：使用可信的公共文件，使用在线可信服务器，使用离线服务器和认证。
1）公钥加密的优点：
ü 大型网络中的每个用户需要的密钥数量少。
ü 对管理公钥的可信第三方的信任程度要求不高而且是离线的。
ü 只有私钥是保密的，而公钥只要保证它的真实性。
2）缺点：
ü 多数公钥加密比对称密钥加密的速度要慢几个数量级。
ü 公钥加密方案的密钥长度比对称加密的密钥要长。
ü 公钥加密方案没有被证明是安全的。
公钥密码的概念本身就被公认为是密码学上的一块里程碑。二十多年来的研究表明，公钥密码成功地解决了计算机网络安全中的密钥管理，身份认证和数字签名等问题，已经成为信息安全技术中的重大核心技术。
2．RSA算法概述
RSA加密算法于1977年由美国麻省理工学院的RonalRivest，AdiShamir和LenAdleman三位年轻教授提出，并以三人的姓氏Rivest，Shamir和Adleman命名为RSA算法。这三位科学家荣获2002年度图灵奖，以表彰他们在算法方面的突出贡献。该算法利用了数论领域的一个事实，那就是虽然把两个大质数相乘生成一个合数是件十分容易的事情，但要把一个合数分解为两个质数的乘积却十分困难。合数分解问题目前仍然是数学领域尚未解决的一大难题，至今没有任何高效的分解方法。它无须收发双方同时参与加密过程，既可以用于保密也可以用于签名，因而非常适合于电子邮件系统的加密，互连网和信用卡安全系统。
3．RSA算法的加密和解密过程
在RSA算法中，每个实体有自己的公钥（e，n）及私钥(d，n)，其中n=p*q，p，q是两个大素数，e*d=1modф(n)，显然e应该满足gcd（e，ф(n)）＝1。实体B加密消息m，将密文在公开信道上传送给实体A。实体A接到密文后对其解密。具体算法如下。
1）公钥的生成算法
RSA的公钥生成算法十分简单，可以分为四步：
（1）选择两个素数，p和q；
（2）计算n=p×q和z=(p-1)×(q-1)；
（3）选择一个与z互质的数d；
（4）找出一个e，使得e×d=1modz。
公开密钥是由（e，n）构成，私有密钥由（d，n）构成。
2）加密算法
实体B的操作如下：
（1）得到实体A的真实公钥（e，n）；
（2）把消息表示成整数m，0＜m≤n－1；
（3）使用平方－乘积算法，计算C=Ek(m)=memodn；
（4）将密文C发送给实体A。
3）解密算法
实体A接收到密文C，使用自己的私钥d计算m=Dk（C）=Cdmodn，m∈Zn。
我们选择p=3，q=11，得到n=33，z=（p-1）×（q-1）=2×10=20。由于7和20互质，故设d=7。对于所选的d=7，解方程7×e=1mod20，可以得到e=3。
在我们的例子中，由于所选的p和q太小，破译当然很容易，我们的例子只是用来说明此算法的原理。对于明文SUZANNE，RSA的加密和解密过程如表2.1所示。
表2.1 RSA加解密过程示例
加密
解密
明文（m）
me
密文（C）
密文（C）
Cd
明文（m）
符号
值
m3
m3(mod33)
m3(mod33)
C7
值
符号
S
19
6859
28
28
13492928512
19
S
U
21
9261
21
21
1801088541
21
U
Z
26
17576
20
20
1280000000
26
Z
A
1
1
1
1
1
1
A
N
14
2744
5
5
78125
14
N
N
14
2744
5
5
78125
14
N
E
5
125
26
26
8031810176
5
E

【实验步骤】
一．RSA生成公钥及加密解密过程演示
（1）在本机运行试验平台，进入“密码工具”｜“加密解密”｜“RSA加密算法”｜“公钥”页签，在生成公钥区输入素数p和素数q，这里要求p和q不能相等（因为很容易开平方求出p与q的值）并且p与q的乘积也不能小于127（因为小于127不能包括所有的ASCII码，导致加密失败），你选用的素数p与q分别是：
p= 73 ；q= 53 。
（2）单击“私钥d”下拉按钮，选择私钥d，并记录这个私钥用于解密，d= 1003 。
（3）单击“生成公钥”按钮生成公钥，记录下公钥e= 1411 ,n= 3869 。
（4）在生成公钥演示区中输入素数p= 73 和素数q= 53 ，还有私钥d= 1003 。单击“开始演示”按钮查看结果，填写：
私钥d 1003 私钥n 3869 公钥e 1411 公钥n 3869
（5）在加/解密演示区中输入明文m= 3000 ，公钥n= 3869 （m<n），公钥e=。单击“加密演示”按钮，查看RSA加密过程，然后记录得到的密文c= 919 。
（6）在密文c编辑框输入刚刚得到的密文，分别输入私钥n=，私钥d=,点击“解密演示”按钮，查看RSA解密过程，然后记录得到的明文m= 3000 。
（7）比较解密后的明文与原来的明文是否一致。
根据实验原理中对RSA加密算法的介绍，当素数p=13，素数q=17，私钥d=143时，写出RSA公钥的生成过程： n=p*q n=p*q=13*17=221 z=(p-1)*(q-1) e=d-1(modz) 。
利用生成的公钥，写出对明文m=40的加密过程（加密过程计算量比较大，请使用密码工具的RSA工具进行计算）： c=me(mod n) 。
利用私钥d=143，对生成的密文进行解密： m=cd(mod n) 。
二．RSA加密解密
（1）本机在生成公钥区输入素数p和素数q，这里要求p和q不能相等,并且p与q的乘积也不能小于127，记录你输入的素数，p= 73 ,q= 53 。
（2）点击“私钥d”的下拉按钮，选择私钥d，并记录这个私钥用于解密，d= 1003 。
（3）点击“生成公钥”按钮生成公钥，记录下公钥e= 1411 ,n= 3869 。将自己的公钥通告给同组主机。
（4）本机进入“加密/解密”页签，在“公钥e部分”和“公钥n部分”输入同组主机的公钥，在明文输入区输入明文： abcde 。
单击“加密”按钮对明文进行加密，单击“导出”按钮将密文导出到RSA共享文件夹（D:\Work\Encryption\RSA\）中，通告同组主机获取密文。
（5）进入“加密/解密”页签，单击“导入”按钮，从同组主机的RSA共享文件夹中将密文导入，点击“解密”按钮，切换到解密模式，在“私钥d部分”和“私钥n部分”输入自己的私钥，再次点击“解密”按钮进行RSA解密。
（6）将破解后的明文与同组主机记录的明文比较。
三．源码应用（选做）
设计RSA加密工具，利用RSA加密算法对文件进行加密。
单击工具栏“VC 6”按钮，启动VC++6.0。选择“File”|“OpenWorkspace…”加载工程文件“C:\ExpNIS\Encrypt-Lab\Projects\RSA\RSA.dsw”。基于此工程进行程序设计。