RSA密码体制的实现及数字签名技术的应用摘要随着计算机网络和信息技术的发展，信息安全在各领域发挥着越来越重要的作用，其中密码学已成为信息安全技术的核心，本文主要介绍了信息加密技术的应用。

RSA算法是目前公认的在理论和实际应用中最为成熟和完善的一种公钥密码体制，它是第一个既能用于数据加密也能用于数字签名的算法，是公钥密码体制的代表。

数字签名是起到身份认证、核准数据完整性的一种信息安全技术。

它通过认证技术来辨认真伪。

RSA数字签名体制使用的是RSA 公开密钥密码算法进行数字签名。

关键词：RSA算法；加密；解密；RSA数字签名AbstractWith the development of the computer network and information technology, information security plays more and more important role in every field. Cryptography has become the core of information security technology. This thesis mainly introduces the application of information encryption technology.RSA algorithm is considered as a public-key cryptosystem of the most fully developed and complete in theory and practice application at present. It is the first algorithm for both data encryption and digital signature. Digital signature is an information security technology used to check authentication and data integrity. It identifies true or false by the authentication technology. RSA digital signature system carries on digital signature by using RSA public-key cipher algorithm.Key Words: RSA algorithm; encryption; decryption; RSA digital signature1引言1.1密码学应用的相关背景现代密码学已成为信息安全技术的核心，密码学是以研究通信安全保密的学科，即研究对传输信息采用何种秘密的变换以防止第三者对信息的窃取。

密码学包括两个分支：密码编码学和密码分析学。

密码编码学主要研究对信息进行交换，以保护信息在信道的传递过程中不被他人窃取、解密和利用的方法，而密码分析学则与密码编码学相反，它主要研究如何分析和破译密码。

两者之间既相互对立又相互促进。

密码体制的分类有很多，其中一种是根据加密算法和解密算法所使用的密钥是否相同，可以将密码体制分为对称密钥密码体制（单钥密码体制）和非对称密钥密码体制（公钥密码体制），这两种密码体制各有自己的长处和短处，因此现在采用了两种的混合体。

公钥密码体制的特点是：接收方B产生一对密钥（PK 和ＳＫ）；ＰＫ公开，ＳＫ保密；从ＰＫ推出ＳＫ是很困难的；Ａ、Ｂ双方通信时，Ａ通过任何途径取得Ｂ的公钥，用Ｂ的公钥加密信息，加密后的信息可通过任何不安全信道发送。

Ｂ收到密文信息后，用自己私钥解密恢复出明文。

公钥密码体制已成为确保信息的安全性的关键技术。

RSA公钥密码体制到目前为止还是一种被认可为安全的体制。

【3】RSA公钥加密算法是第一个既能用于数据加密也能用于数字签名的算法。

它易于理解和操作，也十分流行。

随着越来越多的商业应用和标准化工作，RSA已经成为最具代表性的公钥加密技术。

VISA、MasterCard、IBM、Microsoft等公司协力制定的安全电子交易标准（Secure Electronic Transactions，SET）就采用了标准RSA算法，这使得RSA在我们的生活中几乎无处不在。

网上交易加密连接、网上银行身份验证、各种信用卡使用的数字证书、智能移动电话和存储卡的验证功能芯片等，大多数使用RSA技术。

【6】1.2使用RSA加密的意义随着电子商务的发展，网络上资金的电子交换日益频繁，如何防止信息的伪造和欺骗成为非常重要的问题。

在计算机通信系统中，维护电子文档的安全也成为至关重要和非常敏感的问题。

为保护信息的安全，数字签名应运而生，它是现代密码学主要研究的内容之一。

目前关于数字签名的研究主要集中点是基于公钥密码体制的数字签名。

【4】在公钥密码体制中，解密和加密密钥不同，解密和加密可分离，通信双方无须事先交换密钥就可建立起保密通信，因此它较好地解决了传统密码体制在网络通信中出现的问题。

手写签名的每一项业务都是数字签名的潜在用场。

数字签名可以提供数据完整性、真实性和不可否认性。

因而当需要对某一实体进行认证、传输具有有效性的密钥以及进行密钥分配时，便可以借助数字签名来完成任务。

数字签名技术在身份识别和认证、数据完整性、抵赖等方面具有其它技术无法替代的作用，它在军事、电子商务和电子政务等领域有着极广泛的应用。

而在公钥体制中，RSA 是一个较为完善的公钥密码算法，不仅能够同时用于加密和数字签名，而且易于理解和操作，是被广泛研究的公钥密码算法。

因此，基于RSA的数字签名具有较强的研究性和实际应用意义。

【6】1.21什么是RSA加密RSA（Rivest-Shamir-Adelman）加密体制是一种公开的密码体制。

【4】RSA公匙密码体制是又R.L.Rivest，A.Shamir和L.Adelman于1978年提出的。

由于RSA算法很完善，即可用于数据加密，又可用于数字签名，安全性良好，易于实现和理解，所以已经成为一种应用极广的公匙密码算法，目前，RSA在许多场合有广泛的应用。

【2】2 RSA相关理论知识2.1RSA算法的的数学基础定义1：对于自然数P，如果P只能被1和本身除尽，则P为素数或质数，否则为合数定义2：如果整数a和整数b的最大公约数是1，则a和b互为质数。

欧拉定理：若n,a为正整数，且n,a互素，(a,n) = 1，则a^φ(n) ≡1 (mod n)定义3：欧拉系数Q（r）定义为Q（r）=r（1—1/p1）（1—1/p2）（1—1/p2）（1—1/pn）（p1，p2……pn是r的公约数）欧拉函数是用来计算1，2，3……r中有多少个数中与r互为质数。

定义4：两个数a，b分别被m除，如果所得的余数相同则a和b对于模m是同余的记作a=a （modm）。

2.2 RSA算法基础2.21产生素数（1）反素数n必不能被2- （实际上一个数最大公约数小于或等于）之间所有素数的整数。

（2）除2以外所有素数为奇数，有素数的定义来决定算法a、令n从3开始（3是素数）b、每次增加2 n=n+2c、n被所有小于等于的素数整除若不存在被整除的数则n为奇数2.22求最大公约数设b，c为整数b>0，c>0,b>c，c的最大公约数记作gcd（b，c）可以利用欧几里得算法：每次余数为除数除以上一次的除数直到余数为0为止，则上次的余数为最大公约数，可以现设b为上次的除数，c为余数，按欧几里得算法求出gcd（b，c）。

2.23求素数运算法设a.b==1（modr）即a==吧（modr）已知a求b称求a对于模r的乘运b，并称a与b对r 互为求逆，写成b=modr/a。

在求乘逆运算时可以利用欧几里得算法，即重新使用带余数出发但求最大公约数不同，即每次的余数为除数，除以上次的除数直到除到1为止。

先令a 位余数，r作为上次的除数，根据欧几里得算法，由数字归纳可以证明求a的乘逆b的公式为：b-1=0 b0=1 b j=bj-2-b j-1g j 其中j为整数从开始g j是r j/a j的整数部分当r j/a j的余数为1时，a的乘逆b=|b j|。

3RSA的具体算法过程3.1模指数运算指数运算谁都懂，不必说了，先说说模运算。

模运算是整数运算，有一个整数m，以n为模做模运算，即m mod n。

怎样做呢？让m去被n整除，只取所得的余数作为结果，就叫做模运算。

例如，10 mod 3=1；26 mod 6=2；28 mod 2 =0等等。

模指数运算就是先做指数运算，取其结果再做模运算。

如好，现在开始正式讲解RSA加密算法。

RSA的算法过程选择一对不同的、足够大的素数p，q。

（1）计算n=pq。

（2）计算f(n)=(p-1)(q-1)，同时对p, q严加保密，不让任何人知道。

（3）找一个与f(n)互质的数e，且1<e<f(n)。

（4）计算d，使得de≡1 mod f(n)。

这个公式也可以表达为d ≡e-1 mod f(n)这里要解释一下，≡是数论中表示同余的符号。

公式中，≡符号的左边必须和符号右边同余，也就是两边模运算结果相同。

显而易见，不管f(n)取什么值，符号右边1 mod f(n)的结果都等于1；符号的左边d与e的乘积做模运算后的结果也必须等于1。

这就需要计算出d的值，让这个同余等式能够成立。

（5）公钥KU=(e,n)，私钥KR=(d,n)。

（6）加密时，先将明文变换成0至n-1的一个整数M。

若明文较长，可先分割成适当的组，然后再进行交换。

设密文为C，则加密过程为：。

（7）解密过程为：。

实例描述通过一个简单的例子来理解RSA的工作原理。

为了便于计算。

在以下实例中只选取小数值的素数p,q,以及e，假设用户A需要将明文“key”通过RSA加密后传递给用户B，过程如下：3.2设计公私密钥(e,n)和(d,n)。

令p=3，q=11，得出n=p×q=3×11=33；f(n)=(p-1)(q-1)=2×10=20；取e=3，（3与20互质）则e×d≡1 mod f(n)，即3×d≡1 mod 20。

d怎样取值呢？可以用试算的办法来寻找。

试算结果见下表：通过试算我们找到，当d=7时，e×d≡1 mod f(n)同余等式成立。

因此，可令d=7。

从而我们可以设计出一对公私密钥，加密密钥（公钥）为：KU =(e,n)=(3,33)，解密密钥（私钥）为：KR =(d,n)=(7,33)。

3.3英文数字化。

将明文信息数字化，并将每块两个数字分组。

假定明文英文字母编码表为按字母顺序排列数值，即：则得到分组后的key的明文信息为：11，05，25。