RSA加密算法个人理解

RSA加密算法

引用

RSA加密算法是最常用的非对称加密算法，CFCA在证书服务中离不开它。 但是，很多新同事对它了解不多，只是看到一本书，作者在书中对其进行了简单而生动的描述，并结合实例，让高深的数学理论易于理解。 经过整理重写，推荐给大家阅读，希望对时间紧迫又想了解的同行有所帮助。

RSA是第一个比较完善的公钥算法，既可以用于加密又可以用于数字签名。 RSA 以其三位发明者 Ron Rivest、Adi Shamir 和 Leonard Adleman 的名字命名。 该算法经受住了多年的深入密码分析。 虽然密码分析者既不能证明也不能否认RSA的安全性，但这恰恰说明该算法具有一定的可信度，成为目前最流行的公钥算法。

RSA 的安全性是基于分解大数的难度。 它的公钥和私钥是一对大质数（100 到 200 位或更大）的函数。 从公钥和密文中恢复明文的难度相当于分解两个大质数的乘积（这是公认的数学问题）。

RSA公钥、私钥的组成以及加解密的公式见下表：

可能同事们很久没有接触数学了，看完这些公式不禁一头雾水。 别着急，在我们正式讲解RSA加密算法之前，让我们先来回顾一下数学中的一些基本概念，在下面的介绍中会用到：

1. 什么是“素数”？

素数是一个整数，不能表示为除它和1以外的任何其他两个整数的乘积。例如15=3*5，所以15不是素数； 又如，12=6*2=4*3，所以12也不是质数。 另一方面，13 不能表示为除 13*1 以外的任何其他两个整数的乘积，因此 13 是质数。 质数也称“素数”。

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号。

(8) 两个数都是合数（两个数相差很大），小数的所有质因数都不是大数的约数。 这两个数是互质数。 比如357和715，357=3×7×17，而3、7、17不是715的约数，这两个数是互质数。 等等

3、什么是模指数运算？

指数计算大家都懂，不用多说，我们先说模计算。 模运算是整数运算。 有一个整数m，对n进行模运算，即m mod n。 怎么做 让m除以n，只取余数作为结果，称为模运算。 例如，10 模 3 = 1； 26 模 6 = 2; 28 mod 2 = 0 等等。

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

好了，现在我们正式讲解RSA加密算法。

算法说明：

(1) 选择一对不同的、足够大的素数p、q。

(2)计算n=pq。

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

(4) 求一个与f(n)互质的数e，计算1(5)中的d比特币的加密算法破解，使de≡1 mod f(n)。 这个公式也可以表示为 d ≡ e-1 mod f(n)

这里我要说明一下，≡是数论中同余的符号。 式中，≡符号的左边必须和符号的右边全等，即两边取模运算的结果相同。 显然，无论f(n)取什么值，符号右边1 mod f(n)的结果都等于1； 符号左边的d和e的乘积的模运算结果也必须等于1。这就需要计算d的值，才能使这个同余成立。

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

(7)加密时，先将明文转化为0到n-1的整数M。 如果明文较长，可以先分成合适的组，再进行交换。 设密文为C，则加密过程为：

.

(8)解密过程为：

.

示例说明：

在这篇科普文章中，无法对RSA算法的正确性进行严密的数学证明，但我们可以通过一个简单的例子来了解RSA的工作原理。 为了便于计算。 在下面的例子中，只选择了取值较小的质数p、q、e。 假设用户A需要将明文“密钥”用RSA加密后传递给用户B，过程如下：

(1) 设计公钥和私钥(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)。

(2)英语数字化。

将明文消息数字化并为每个块分组两个数字。 假设明文英文字母编码表是按字母顺序排列数值 ，即：

那么分组密钥的明文信息为：11,05,25。

(3) 明文加密

用户加密密钥（3，33）将数字化后的明文块信息加密成密文。 来自 C≡Me(mod n)：

因此对应的密文信息为：11,31,16。

(4) 解密密文。

用户B收到密文，如果解密，只需要计算

，即：

用户B得到明文信息：11,05,25，根据上面的编码表转换成英文，我们就得到了还原后的原文“key”。

你看，它的原理可以解释的这么简单！

当然，实际的应用要比这复杂得多。 由于RSA算法的公钥和私钥的长度（模数长度）必须是1024位甚至2048位才能保证安全，所以p、q、e的选择，公钥和私钥都有一定的模指数加解密的生成计算程序，需要计算机高速完成。

最后简单说一下RSA的安全性

首先我们来讨论一下RSA密码为什么难破解？

在RSA密码应用中，公钥KU是公开的，即e和n的值可以被第三方窃听者获取。 破解RSA密码的问题是从已知的e和n的值中求d的值（n等于pq），这样就可以得到私钥来破解密文。 从上面的公式：d≡e-1(mod((p-1)(q-1)))或de≡1(mod((p-1)(q-1)))我们可以看出。 密码破解的本质问题是：从Pq的值，求出(p-1)和(q-1)。 也就是说，只有求出p和q的值，才能求出d的值，得到私钥。

当 p 和 q 是大质数时，从它们的乘积 pq 中分解出 p 和 q 是一个公认的数学问题。 例如，当pq大到1024位时，迄今为止还没有人能够使用任何计算工具来完成分解因子的任务。 因此，从RSA被提出到现在已经将近20年了。 它经历了各种攻击的考验，逐渐被人们所接受。 它被普遍认为是目前最好的公钥方案之一。

然而，虽然RSA的安全性依赖于大数的分解，但理论上还没有证明破译RSA的难度等同于大数的分解难度。 即RSA的主要缺陷是理论上无法掌握其保密性能。

另外，RSA的缺点是： A)生成密钥非常麻烦，而且受质数生成技术的限制，很难实现一次性一密。 B) 块长度太大。 为了保证安全，n必须至少为600位，这使得运算成本非常高，尤其是速度慢，比对称加密算法慢几个数量级； 而且随着大数分解技术的发展，这个长度还在不断增加，不利于数据格式的标准化。 因此，只有少量的数据可以使用RSA进行加密，大量的数据加密依赖于对称密码算法。