RSA原理与实例

来自： http://my.oschina.net/sunchp/blog/628550

1 数学概念

1.1 质数

质数是这样的整数，它除了能表示为它自己和1的乘积以外，不能表示为任何其它两个整数的乘积。

例如，15＝3＊5，所以15不是质数；12＝6＊2＝4＊3，所以12也不是质数；13除了等于13＊1以外，不能表示为其它任何两个整数的乘积，所以13是一个质数。

质数也称为“素数”。

1.2 互质数

互质数为数学中的一种概念，公因数只有1的两个非零自然数，叫做互质数。

关于互质数，有以下定理：

（1）两个质数一定是互质数。例如，2与7、13与19。

（2）一个质数如果不能整除另一个合数，这两个数为互质数。例如，3与10、5与 26。

（3）1不是质数也不是合数，它和任何一个自然数在一起都是互质数。如1和9908。

（4）相邻的两个自然数是互质数。如 15与 16。

（5）相邻的两个奇数是互质数。如 49与 51。

（6）大数是质数的两个数是互质数。如97与88。

（7）小数是质数，大数不是小数的倍数的两个数是互质数。如 7和 16。

1.3 取模运算

一个整数m，以n为模做取模运算，记作 m mod n。

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

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

1.4 同余符号

两个整数a，b，若它们以整数n为模，做取模运算，所得的余数相等，则称a，b对于模n同余。记作 a≡b mod n。

比如26 ≡ 14 mod 12

PS： ”≡“，非”=“

2 RSA算法描述

（1）选择一对不同的、足够大的互质数p，q。

（2）计算n=pq。

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

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

（5）计算d，使得de≡1 mod f(n)。 显而易见，不管f(n)取什么值，符号右边1 mod f(n)的结果都等于1；符号的左边d与e的乘积做模运算后的结果也必须等于1。这就需要计算出d的值，让这个同余等式能够成立。

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

（7）加密时，先将明文变换成0至n-1的一个整数M。若明文较长，可先分割成适当的组，然后再进行交换。

设原文为M，密文为C，则加密过程为：

解密过程为：

PS： ”=“，非”≡“

回顾上面的密钥生成步骤，一共出现六个数字：

p  q  n  f(n)  e  d

3 RSA实例

在这篇科普小文章里，不可能对RSA算法的正确性作严格的数学证明，但我们可以通过一个简单的例子来理解RSA的工作原理。为了便于计算。在以下实例中只选取小数值的素数p,q,以及e，假设用户A需要将明文“key”通过RSA加密后传递给用户B。（灰色为不公开的数据，绿色为需要公开的数据）

3.1 设计公钥KU=(n,e)，私钥KR=(n,d)

（1）p=3，q=11

（2）n=pq=3x11=33

（3）f（n）=(p-1)(q-1)=2×10=20

（4）随机取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。

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

3.2 英文数字化

将明文信息数字化，假定明文英文字母编码表为按字母顺序排列数值，即：

则得到分组后明文”key“信息为：11，05，25。

3.3 明文加密

用户A用公钥KU(33,3) 将数字化明文信息加密成密文。

因此，得到相应的密文信息为：11，26，16。

3.4 密文解密

用户B用私钥KR（33，7）将密文解密成明文。

用户B得到明文信息为：11，05，25。根据上面的编码表将其转换为英文，我们又得到了恢复后的原文“key”。 

RSA的原理就可以这么简单地解释！当然，实际运用要比这复杂得多。p、q、e的选取、公钥私钥的生成，加密解密模指数运算都有一定的计算程序，需要仰仗计算机高速完成。

4 RSA的安全性

为什么RSA密码难于破解？

在RSA密码应用中，公钥KU是被公开的，即e和n的数值可以被第三方窃听者得到。破解RSA密码的问题就是从已知的e和n的数值（n等于pq），想法求出d的数值，这样就可以得到私钥来破解密文。

从上文中的公式：de≡1 mod f(n)≡1 mod ((p-1)(q-1))) ≡ 1 mod (pq-(p+q)+1) ≡ 1 mod (n-(p+q)+1) 可以看出,n，e已知，密码破解的实质问题是：

只要求出p和q的值，我们就能求出d的值而得到私钥。

当p和q是一个大素数的时候，从它们的积pq去分解因子p和q，这是一个公认的数学难题。

比如当pq的乘积n转换为2进制表示，位数达到1024位时，迄今为止还没有人能够利用任何计算工具去完成分解因子的任务（目前被破解的最长RSA密钥是768个二进制位，因此可以认为，1024位的RSA密钥基本安全，2048位的密钥极其安全）。因此，RSA从提出到现在已近二十年，经历了各种攻击的考验，逐渐为人们接受，普遍认为是目前最优秀的公钥方案之一。

然而，虽然RSA的安全性依赖于大数的因子分解，但并没有从理论上证明破译RSA的难度与大数分解难度等价。即RSA的重大缺陷是无法从理论上把握它的保密性能如何。

此外，RSA的缺点还有：

A)产生密钥很麻烦，受到素数产生技术的限制，因而难以做到一次一密。

B)分组长度太大，为保证安全性，n 至少也要 600 bits 以上，使运算代价很高，尤其是速度较慢，较对称密码算法慢几个数量级；且随着大数分解技术的发展，这个长度还在增加，不利于数据格式的标准化。

因此，使用RSA只能加密少量数据，大量的数据加密还要靠对称密码算法。

5 RSA选用小公钥指数（e）

现有的大部分RSA算法实现都遵循PKCS#1 v2.1/v1.5 (2002/1993)。根据PKCS#1的建议，公钥指数e是可以选取较小的素数3或65537(=2^16+1)。这样选取主要是为了提高加密或签名验证的性能，因为3或65537分别只需要2或17次模乘运算，而一个随机选择的e(假设n是1024-bit)则大约需要1000次。这种选用小公钥指数的方法使用户相信RSA在签名验证和加密操作方面确实要比“以高效著称的ECC”还要高效很多。

然而在选用小公钥指数时，有很多人则更倾向于选e=65537而不是e=3，他们认为3“似乎不安全”，然而又给不出所以然。在“正确使用”RSA算法的情况下，至今为止还没有发现公开的攻击方法能有效攻击e=3。

6 加密解密 VS 验证签名

6.1 公钥和私钥的对立性

根据上述RSA算法的描述，可以知道：公钥指数e是可以随机选择的一个质数，且根据 e×d≡1 mod f(n)试算出私钥指数d。

上面实例中，我们选择了e=3，d=7，且 3 x 7 ≡1 mod 20，公钥（33，3），私钥（33，7） ；如果我们选择e=7，d=3，那么7 x 3=1 mod 20仍成立，此时公钥就是（33，7），私钥是（33，3）。

后续的加密解密步骤仍能正确执行。

所以，RSA算法中，公钥和私钥是一个相对的概念。一个作为公钥，另一个就是私钥，具有对立性。分发给公共持有的，便被叫做公钥；私持不公布的，便被叫做私钥。

根据公钥和私钥的对立性，可知：

（1）公钥加密明文后，私钥可以解密出来；

（2）私钥加密明文后，公钥可以解密出来；

6.2 加密解密 VS 验证签名

客户端持有公钥，将消息加密后，公开密文，因为只有服务端有私钥，所以也只有服务端能解密出明文。这个过程叫做加密解密。

服务端持有密钥，讲消息加密后，公开密文和明文，因为客户端都有公钥，都能解密出明文，然后客户端比较“解密得到的明文”和“接收到的明文”是否相等。如果相等，则说明内容未被篡改；如果不相等，则说明内容被篡改。用私钥加密的明文，也叫做签名。这个过程叫做验证签名。

 

PS：如果文中有瑕疵或者错误，欢迎各位吐槽