RSA加密的原理

前几天看到一句话，“我们中的很多人把一生中最灿烂的笑容大部分都献给了手机和电脑屏幕”。心中一惊，这说明了什么？手机和电脑已经成为了我们生活中的一部分，所以才会有最懂你的不是你，也不是你男朋友，而是大数据。

如此重要的个人数据，怎样才能保证其在互联网上的安全传输呢？当然要靠各种加密算法。说起加密算法，大家都知道有哈希、对称加密和非对称加密了。哈希是一个散列函数，具有不可逆操作；对称加密即加密和解密使用同一个密钥，而非对称加密加密和解密自然就是两个密钥了。稍微深入一些的，还要说出非对称加密算法有DES、3DES、RC4等，非对称加密算法自然就是RSA了。那么当我们聊起RSA时，我们又在聊些什么呢？今天笔者和大家一起探讨一下，有不足的地方，还望各位朋友多多提意见，共同进步。

RSA简介：1976年由麻省理工学院三位数学家共同提出的，为了纪念这一里程碑式的成就，就用他们三个人的名字首字母作为算法的命名。即 罗纳德·李维斯特 （Ron Rivest）、 阿迪·萨莫尔 （Adi Shamir）和 伦纳德·阿德曼 （Leonard Adleman）。

公钥：用于加密，验签。

私钥：解密，加签。

通常知道了公钥和私钥的用途以后，即可满足基本的聊天需求了。但是我们今天的主要任务是来探究一下RSA加解密的原理。

说起加密算法的原理部分，肯定与数学知识脱不了关系。

我们先来回忆几个数学知识：

φn = φ(A*B)=φ(A)*φ(B)=(A-1)*(B-1)。

这个公式主要是用来计算给定一个任意的正整数n，在小于等于n的正整数中，有多少个与n构成互质的关系。

其中n=A*B，A与B互为质数，但A与B本身并不要求为质数，可以继续展开，直至都为质数。

在最终分解完成后，即 φ(N) = φ(p1)*φ(p2)*φ(p3)... 之后，p1，p2，p3都是质数。又用到了欧拉函数的另一个特点，即当p是质数的时候，φp = p - 1。所以有了上面给出的欧拉定理公式。

举例看一下：

计算15的欧拉函数，因为15比较小，我们可以直接看一下，小于15的正整数有 1、2、3、4、5、6、7、8、9、10、11、12、13、14。和15互质的数有1、2、4、7、8、11、13、14一共四个。

对照我们刚才的欧拉定理： 。

其他感兴趣的，大家可以自己验证。

之所以要在这里介绍欧拉函数，我们在计算公钥和私钥时候，会用到。

如果两个正整数m 和 n 互质，那么m 的 φn 次方减1，可以被n整除。

其中   .

其中当n为质数时，那么   上面看到的公式就变成了

mod n   1.

这个公式也就是著名的 费马小定理 了。

如果两个正整数e和x互为质数，那么一定存在一个整数d，不止一个，使得 e*d - 1 可以被x整除，即 e * d mode x   1。则称 d 是 e 相对于 x的模反元素。

了解了上面所讲的欧拉函数、欧拉定理和模反元素后，就要来一些化学反应了，请看图：

上面这幅图的公式变化有没有没看明白的，没看明白的咱们评论区见哈。

最终我们得到了最重要的第5个公式的变形，即红色箭头后面的：

mod n   m。

其中有几个关系，需要搞明白，m 与 n 互为质数，φn = x，d 是e相对于x的模反元素。

有没有看到一些加解密的雏形。

从 m 到 m。 这中间涵盖了从加密到解密的整个过程，但是缺少了我们想要的密文整个过程。

OK，下面引入本文的第四个数学公式：

我们来看一下整个交换流程：

1、客户端有一个数字13，服务端有一个数字15;

2、客户端通过计算 3的13次方 对 17 取余，得到数字12; 将12发送给服务端；同时服务端通过计算3的15次方，对17取余，得到数字6，将6发送给客户端。至此，整个交换过程完成。

3、服务端收到数字12以后，继续计算，12的15次方 对 17取余，得到 数字10。

4、客户端收到数字 6以后，继续计算，6的13次方 对 17 取余，得到数字 10。

有没有发现双方，最终得到了相同的内容10。但是这个数字10从来没有在网络过程中出现过。

好，讲到这里，可能有些人已经恍然大悟，这就是加密过程了，但是也有人会产生疑问，为什么要取数字3 和 17 呢，这里还牵涉到另一个数学知识，原根的问题。即3是17的原根。看图

有没有发现规律，3的1~16次方，对17取余，得到的整数是从1~16。这时我们称3为17的原根。也就是说上面的计算过程中有一组原根的关系。这是最早的迪菲赫尔曼秘钥交换算法。

解决了为什么取3和17的问题后，下面继续来看最终的RSA是如何产生的：

还记得我们上面提到的欧拉定理吗，其中 m 与 n 互为质数，n为质数，d 是 e 相对于 φn的模反元素。

当迪菲赫尔曼密钥交换算法碰上欧拉定理会产生什么呢？

我们得到下面的推论：

好，到这里我们是不是已经看到了整个的加密和解密过程了。

其中 m 是明文；c 是密文； n 和 e 为公钥；d 和 n 为私钥 。

其中几组数字的关系一定要明确：

1、d是e 相对于 φn 的模反元素，φn = n-1，即 e * d mod n = 1.

2、m 小于 n，上面在讲迪菲赫尔曼密钥交换算法时，提到原根的问题，在RSA加密算法中，对m和n并没有原根条件的约束。只要满足m与n互为质数，n为质数，且m n就可以了。

OK，上面就是RSA加密算法的原理了，经过上面几个数学公式的狂轰乱炸，是不是有点迷乱了，给大家一些时间理一下，后面会和大家一起来验证RSA算法以及RSA为什么安全。

rsa算法原理

RSA算法是最常用的非对称加密算法，它既能用于加密，也能用于数字签名。RSA的安全基于大数分解的难度。其公钥和私钥是一对大素数（100到200位十进制数或更大）的函数。从一个公钥和密文恢复出明文的难度，等价于分解两个大素数之积。

我们可以通过一个简单的例子来理解RSA的工作原理。为了便于计算。在以下实例中只选取小数值的素数p,q,以及e，假设用户A需要将明文“key”通过RSA加密后传递给用户B，过程如下：设计公私密钥(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=7时，e×d≡1 mod f(n)同余等式成立。因此，可令d=7。从而我们可以设计出一对公私密钥，加密密钥（公钥）为：KU =(e,n)=(3,33)，解密密钥（私钥）为：KR =(d,n)=(7,33)。

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

明文加密。用户加密密钥(3,33) 将数字化明文分组信息加密成密文。由C≡Me(mod n)得：

C1(密文)≡M1（明文）^e (mod n) == 11≡11^3 mod 33 ;

C2(密文)≡M2（明文）^e (mod n) == 26≡05^3 mod 33;

C3(密文)≡M3（明文）^e (mod n) == 16≡25^3 mod 33;

所以密文为11.26.16。

密文解密。用户B收到密文，若将其解密，只需要计算，即：

M1(明文)≡C1（密文）^d (mod n) == 11≡11^7 mod 33;

M2(明文)≡C2（密文）^d (mod n) == 05≡26^7 mod 33;

M3(明文)≡C3（密文）^d (mod n) == 25≡16^7 mod 33;

转成明文11.05.25。根据上面的编码表将其转换为英文，我们又得到了恢复后的原文“key”。

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

RSA加密算法原理

RSA加密算法是一种典型的非对称加密算法，它基于大数的因式分解数学难题，它也是应用最广泛的非对称加密算法，于1978年由美国麻省理工学院（MIT）的三位学着：Ron Rivest、Adi Shamir 和 Leonard Adleman 共同提出。

它的原理较为简单，假设有消息发送方A和消息接收方B，通过下面的几个步骤，就可以完成消息的加密传递：

消息发送方A在本地构建密钥对，公钥和私钥；

消息发送方A将产生的公钥发送给消息接收方B；

B向A发送数据时，通过公钥进行加密，A接收到数据后通过私钥进行解密，完成一次通信；

反之，A向B发送数据时，通过私钥对数据进行加密，B接收到数据后通过公钥进行解密。

由于公钥是消息发送方A暴露给消息接收方B的，所以这种方式也存在一定的安全隐患，如果公钥在数据传输过程中泄漏，则A通过私钥加密的数据就可能被解密。

如果要建立更安全的加密消息传递模型，需要消息发送方和消息接收方各构建一套密钥对，并分别将各自的公钥暴露给对方，在进行消息传递时，A通过B的公钥对数据加密，B接收到消息通过B的私钥进行解密，反之，B通过A的公钥进行加密，A接收到消息后通过A的私钥进行解密。

当然，这种方式可能存在数据传递被模拟的隐患，但可以通过数字签名等技术进行安全性的进一步提升。由于存在多次的非对称加解密，这种方式带来的效率问题也更加严重。

RSA加密的原理的介绍就聊到这里吧，感谢您花时间阅读，谢谢。