RSA算法原理及数字签名技术

1.前言：

非对称加密算法的经典算法———RSA算法的应用如今在互联网上的传播已经十分广泛了，RSA公钥加密算法是1977年由RonRivest、AdiShamirh和LenAdleman在（美国麻省理工学院）开发的。RSA取名来自开发他们三者的名字。RSA是目前最有影响力的公钥加密算法，它能够抵抗到目前为止已知的所有密码攻击，已被ISO推荐为公钥数据加密标准。RSA算法基于一个十分简单的数论事实：将两个大素数相乘十分容易，但那时想要对其乘积进行因式分解却极其困难，因此可以将乘积公开作为加***。但是对于量子计算机来说，这种大的质因数**是小菜一碟。

2.RSA算法的应用现状：

RSA算法可应用于数字签名、https加密等。本调研报告主要研究RSA算法在数字签名方面的原理。

3.RSA算法的原理：

在讲数字签名的原理之前，我们先来讲一下RSA算法的原理：

(1).首先接收者要算出两个秘钥——一个公钥一个私钥。具体过程如下：接收者随机挑选两个大质数p和q，n=p*q，计算n的欧拉函数ψ(n)，根据定理可知

ψ(n)=ψ(p*q)=ψ(p)*ψ(q)=(p-1)*(q-1)

然后在1到ψ(n)之间找一个与ψ(n)互质的数e作为公钥，即在ψ(n)的最小非负简化剩余系里找一个数e。然后根据选择的公钥计算出私钥，计算公式是:
e*x=1 mod n，根据《信息安全数学基础》里的定理，最小非负简化剩余系的里的所有数字都乘一个相同的数，得到的一组数也是一个简化剩余系，简化剩余系里必有一个mod n
结果为1的数，所以上述公式一定有解，求得一个私钥d。

(2).接受者向发送者发送公钥e，这个过程是公开的，因为即使窃听者得到公钥和密文也无法破译。

(3).加密过程：明文为m，发送者根据公钥对明文m进行加密，加密公式为：m^e=c mod n，其中取模运算得到的结果c就是要发送的密文。

(4).解密过程：接受者根据得到的密文c和自己的私钥d进行计算可以得到明文m，公式如下：c^d=m mod n，这个是可以根据数学定理证明的。

4.RSA在数字签名技术上的应用

先来说一下数字签名是用来解决什么问题的，数字签名，顾名思义，就是一种电子版的签名，是用来确认具体的人的身份的，在消息发送中，接收者需要确定发送者的身份，我们用数字签名来解决这个身份认证问题。

数字签名的原理：

发送者把文件加密得到一串哈希值，再用公钥加密该哈希值，发送的内容有三:
(1)文件(2)文件的哈希值(3)文件的哈希值经过公钥加密后的结果

接收者得到发送者发过来的东西后，要进行两个操作，第一步是用自己的私钥解密发送者发的‘文件的哈希值经过公钥加密后的结果’，看是否与发送者传来的‘文件的哈希值’相等，这是验证的第一步；第二步，是把发送者发送的‘文件’进行哈希加密，看看得到的哈希值是否与发送者发送的‘文件的哈希值’相等，这是第二步。
第一步是为了验证发送者的身份。
第二步是为了验证文件是否被篡改过。

之后还有使用数字证书的方法。