前几天看到一句话，“我们中的很多人把一生中最灿烂的笑容大部分都献给了手机和电脑屏幕”。心中一惊，这说明了什么？手机和电脑已经成为了我们生活中的一部分，所以才会有最懂你的不是你，也不是你男朋友，而是大数据。
如此重要的个人数据，怎样才能保证其在互联网上的安全传输呢？当然要靠各种加密算法。说起加密算法，大家都知道有哈希、对称加密和非对称加密了。哈希是一个散列函数，具有不可逆操作；对称加密即加密和解密使用同一个密钥，而非对称加密加密和解密自然就是两个密钥了。稍微深入一些的，还要说出非对称加密算法有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算法非常简单，概述如下：
找两素数p和q
取n=p*q
取t=(p-1)*(q-1)
取任何一个数e,要求满足et并且e与t互素（就是最大公因数为1）
取d*e%t==1
这样最终得到三个数： n d e
设消息为数M (M n)
设c=(M**d)%n就得到了加密后的消息c
设m=(c**e)%n则 m == M，从而完成对c的解密。
注：**表示次方,上面两式中的d和e可以互换。
在对称加密中：
n d两个数构成公钥，可以告诉别人；
n e两个数构成私钥，e自己保留，不让任何人知道。
给别人发送的信息使用e加密，只要别人能用d解开就证明信息是由你发送的，构成了签名机制。
别人给你发送信息时使用d加密，这样只有拥有e的你能够对其解密。
rsa的安全性在于对于一个大数n，没有有效的方法能够将其分解
从而在已知n d的情况下无法获得e；同样在已知n e的情况下无法
求得d。
rsa简洁幽雅，但计算速度比较慢，通常加密中并不是直接使用rsa 来对所有的信息进行加密，
最常见的情况是随机产生一个对称加密的密钥，然后使用对称加密算法对信息加密，之后用
RSA对刚才的加密密钥进行加密。
最后需要说明的是，当前小于1024位的N已经被证明是不安全的
自己使用中不要使用小于1024位的RSA，最好使用2048位的。
本节内容中可能用到的符号说明如下：
质数和合数： 质数是指除了平凡约数1和自身之外，没有其他约数的大于1的正整数。大于1的正整数中不是素数的则为合数。如 7、11 是质数，而 4、9 是合数。在 RSA 算法中主要用到了质数相关性质，质数可能是上帝留给人类的一把钥匙，许多数学定理和猜想都跟质数有关。
[定理1] 除法定理： 对任意整数 a 和 任意正整数 n，存在唯一的整数 q 和 r，满足 。其中， 称为除法的商，而 称为除法的余数。
整除： 在除法定理中，当余数 时，表示 a 能被 n 整除，或者说 a 是 n 的倍数，用符号 表示。
约数和倍数 ： 对于整数 d 和 a，如果 ，且 ，则我们说 d 是 a 的约数，a 是 d 的倍数。
公约数： 对于整数 d，a，b，如果 d 是 a 的约数且 d 也是 b 的约数，则 d 是 a 和 b 的公约数。如 30 的约数有 1，2，3，5，6，10，15，30，而 24 的约数有 1，2，3，4，6，8，12，24，则 30 和 24 的公约数有 1，2，3，6。其中 1 是任意两个整数的公约数。
公约数的性质：
最大公约数： 两个整数最大的公约数称为最大公约数，用 来表示，如 30 和 24 的最大公约数是 6。 有一些显而易见的性质：
[定理2] 最大公约数定理： 如果 a 和 b 是不为0的整数，则 是 a 和 b 的线性组合集合 中的最小正元素。
由定理2可以得到一个推论：
[推论1] 对任意整数 a 和 b，如果 且 ，则 。
互质数： 如果两个整数 a 和 b 只有公因数 1，即 ，则我们就称这两个数是互质数(coprime）。比如 4 和 9 是互质数，但是 15 和 25 不是互质数。
互质数的性质：
欧几里得算法分为朴素欧几里得算法和扩展欧几里得算法，朴素法用于求两个数的最大公约数，而扩展的欧几里得算法则有更多广泛应用，如后面要提到的求一个数对特定模数的模逆元素等。
求两个非负整数的最大公约数最有名的是 辗转相除法，最早出现在伟大的数学家欧几里得在他的经典巨作《几何原本》中。辗转相除法算法求两个非负整数的最大公约数描述如下：
例如， ，在求解过程中，较大的数缩小，持续进行同样的计算可以不断缩小这两个数直至其中一个变成零。
欧几里得算法的python实现如下：
扩展欧几里得算法在 RSA 算法中求模反元素有很重要的应用，定义如下：
定义： 对于不全为 0 的非负整数 ，则必然存在整数对 ，使得
例如，a 为 3，b 为 8，则 。那么，必然存在整数对 ，满足 。简单计算可以得到 满足要求。
扩展欧几里得算法的python实现如下：
同余： 对于正整数 n 和 整数 a，b，如果满足 ，即 a-b 是 n 的倍数，则我们称 a 和 b 对模 n 同余，记号如下： 例如，因为 ，于是有 。
对于正整数 n，整数 ，如果 则我们可以得到如下性质：
譬如，因为 ，则可以推出 。
另外，若 p 和 q 互质，且 ，则可推出：
此外，模的四则运算还有如下一些性质，证明也比较简单，略去。
模逆元素： 对整数 a 和正整数 n，a 对模数 n 的模逆元素是指满足以下条件的整数 b。 a 对 模数 n 的 模逆元素不一定存在，a 对 模数 n 的模逆元素存在的充分必要条件是 a 和 n 互质，这个在后面我们会有证明。若模逆元素存在，也不是唯一的。例如 a=3，n=4，则 a 对模数 n 的模逆元素为 7 + 4k，即 7，11，15，...都是整数 3 对模数 4 的模逆元素。如果 a 和 n 不互质，如 a = 2，n = 4，则不存在模逆元素。
[推论2] 模逆元素存在的充分必要条件是整数 a 和 模数 n 互质。
[定理3] 唯一质数分解定理： 任何一个大于1的正整数 n 都可以 唯一分解 为一组质数的乘积，其中 都是自然数(包括0)。比如 6000 可以唯一分解为 。
由质数唯一分解定理可以得到一个推论： 质数有无穷多个 。
[定理4] 中国剩余定理(Chinese remainder theorem，CRT) ，最早见于《孙子算经》(中国南北朝数学著作，公元420-589年)，叫物不知数问题，也叫韩信点兵问题。
翻译过来就是已知一个一元线性同余方程组求 x 的解：
宋朝著名数学家秦九韶在他的著作中给出了物不知数问题的解法，明朝的数学家程大位甚至编了一个《孙子歌诀》：
意思就是：将除以 3 的余数 2 乘以 70，将除以 5 的余数 3 乘以 21，将除以 7 的余数 2 乘以 15，最终将这三个数相加得到 。再将 233 除以 3，5，7 的最小公倍数 105 得到的余数 ，即为符合要求的最小正整数，实际上， 都符合要求。
物不知数问题解法本质
求解通项公式
中国剩余定理相当于给出了以下的一元线性同余方程组的有解的判定条件，并用构造法给出了解的具体形式。
模数 两两互质 ，则对任意的整数： ，方程组 有解，且解可以由如下构造方法得到：
并设 是除 以外的其他 个模数的乘积。
中国剩余定理通项公式证明
非对称加密需要两个密钥：公钥(publickey) 和私钥 (privatekey)。公钥和私钥是一对，如果用公钥对数据加密，那么只能用对应的私钥解密。如果用私钥对数据加密，只能用对应的公钥进行解密。因为加密和解密用的是不同的密钥，所以称为非对称加密。
非对称加密算法的保密性好，它消除了最终用户交换密钥的需要。但是加解密速度要远远慢于对称加密，在某些极端情况下，甚至能比对称加密慢上1000倍。
算法强度复杂、安全性依赖于算法与密钥但是由于其算法复杂，而使得加密解密速度没有对称加密解密的速度快。对称密码体制中只有一种密钥，并且是非公开的，如果要解密就得让对方知道密钥。所以保证其安全性就是保证密钥的安全，而非对称密钥体制有两种密钥，其中一个是公开的，这样就可以不需要像对称密码那样传输对方的密钥了。这样安全性就大了很多。
RSA、Elgamal、背包算法、Rabin、D-H、ECC (椭圆曲线加密算法)。使用最广泛的是 RSA 算法，Elgamal 是另一种常用的非对称加密算法。
收信者是唯一能够解开加密信息的人，因此收信者手里的必须是私钥。发信者手里的是公钥，其它人知道公钥没有关系，因为其它人发来的信息对收信者没有意义。
客户端需要将认证标识传送给服务器，此认证标识 (可能是一个随机数) 其它客户端可以知道，因此需要用私钥加密，客户端保存的是私钥。服务器端保存的是公钥，其它服务器知道公钥没有关系，因为客户端不需要登录其它服务器。
数字签名是为了表明信息没有受到伪造，确实是信息拥有者发出来的，附在信息原文的后面。就像手写的签名一样，具有不可抵赖性和简洁性。
简洁性：对信息原文做哈希运算，得到消息摘要，信息越短加密的耗时越少。
不可抵赖性：信息拥有者要保证签名的唯一性，必须是唯一能够加密消息摘要的人，因此必须用私钥加密 (就像字迹他人无法学会一样)，得到签名。如果用公钥，那每个人都可以伪造签名了。
问题起源：对1和3，发信者怎么知道从网上获取的公钥就是真的？没有遭受中间人攻击？
这样就需要第三方机构来保证公钥的合法性，这个第三方机构就是 CA (Certificate Authority)，证书中心。
CA 用自己的私钥对信息原文所有者发布的公钥和相关信息进行加密，得出的内容就是数字证书。
信息原文的所有者以后发布信息时，除了带上自己的签名，还带上数字证书，就可以保证信息不被篡改了。信息的接收者先用 CA给的公钥解出信息所有者的公钥，这样可以保证信息所有者的公钥是真正的公钥，然后就能通过该公钥证明数字签名是否真实了。
RSA 是目前最有影响力的公钥加密算法，该算法基于一个十分简单的数论事实：将两个大素数相乘十分容易，但想要对其乘积进行因式分解却极其困难，因此可以将乘积公开作为加密密钥，即公钥，而两个大素数组合成私钥。公钥是可发布的供任何人使用，私钥则为自己所有，供解密之用。
A 要把信息发给 B 为例，确定角色：A 为加密者，B 为解密者。首先由 B 随机确定一个 KEY，称之为私钥，将这个 KEY 始终保存在机器 B 中而不发出来；然后，由这个 KEY 计算出另一个 KEY，称之为公钥。这个公钥的特性是几乎不可能通过它自身计算出生成它的私钥。接下来通过网络把这个公钥传给 A，A 收到公钥后，利用公钥对信息加密，并把密文通过网络发送到 B，最后 B 利用已知的私钥，就能对密文进行解码了。以上就是 RSA 算法的工作流程。
由于进行的都是大数计算，使得 RSA 最快的情况也比 DES 慢上好几倍，无论是软件还是硬件实现。速度一直是 RSA 的缺陷。一般来说只用于少量数据加密。RSA 的速度是对应同样安全级别的对称密码算法的1/1000左右。
比起 DES 和其它对称算法来说，RSA 要慢得多。实际上一般使用一种对称算法来加密信息，然后用 RSA 来加密比较短的公钥，然后将用 RSA 加密的公钥和用对称算法加密的消息发送给接收方。
这样一来对随机数的要求就更高了，尤其对产生对称密码的要求非常高，否则的话可以越过 RSA 来直接攻击对称密码。
和其它加密过程一样，对 RSA 来说分配公钥的过程是非常重要的。分配公钥的过程必须能够抵挡中间人攻击。假设 A 交给 B 一个公钥，并使 B 相信这是A 的公钥，并且 C 可以截下 A 和 B 之间的信息传递，那么 C 可以将自己的公钥传给 B，B 以为这是 A 的公钥。C 可以将所有 B 传递给 A 的消息截下来，将这个消息用自己的密钥解密，读这个消息，然后将这个消息再用 A 的公钥加密后传给 A。理论上 A 和 B 都不会发现 C 在偷听它们的消息，今天人们一般用数字认证来防止这样的攻击。
(1) 针对 RSA 最流行的攻击一般是基于大数因数分解。1999年，RSA-155 (512 bits) 被成功分解，花了五个月时间（约8000 MIPS 年）和224 CPU hours 在一台有3.2G 中央内存的 Cray C916计算机上完成。
RSA-158 表示如下：
2009年12月12日，编号为 RSA-768 (768 bits, 232 digits) 数也被成功分解。这一事件威胁了现通行的1024-bit 密钥的安全性，普遍认为用户应尽快升级到2048-bit 或以上。
RSA-768表示如下：
(2) 秀尔算法
量子计算里的秀尔算法能使穷举的效率大大的提高。由于 RSA 算法是基于大数分解 (无法抵抗穷举攻击)，因此在未来量子计算能对 RSA 算法构成较大的威胁。一个拥有 N 量子位的量子计算机，每次可进行2^N 次运算，理论上讲，密钥为1024位长的 RSA 算法，用一台512量子比特位的量子计算机在1秒内即可破解。
DSA (Digital Signature Algorithm) 是 Schnorr 和 ElGamal 签名算法的变种，被美国 NIST 作为 DSS (DigitalSignature Standard)。 DSA 是基于整数有限域离散对数难题的。
简单的说，这是一种更高级的验证方式，用作数字签名。不单单只有公钥、私钥，还有数字签名。私钥加密生成数字签名，公钥验证数据及签名，如果数据和签名不匹配则认为验证失败。数字签名的作用就是校验数据在传输过程中不被修改，数字签名，是单向加密的升级。
椭圆加密算法（ECC）是一种公钥加密算法，最初由 Koblitz 和 Miller 两人于1985年提出，其数学基础是利用椭圆曲线上的有理点构成 Abel 加法群上椭圆离散对数的计算困难性。公钥密码体制根据其所依据的难题一般分为三类：大整数分解问题类、离散对数问题类、椭圆曲线类。有时也把椭圆曲线类归为离散对数类。
ECC 的主要优势是在某些情况下它比其他的方法使用更小的密钥 (比如 RSA)，提供相当的或更高等级的安全。ECC 的另一个优势是可以定义群之间的双线性映射，基于 Weil 对或是 Tate 对；双线性映射已经在密码学中发现了大量的应用，例如基于身份的加密。不过一个缺点是加密和解密操作的实现比其他机制花费的时间长。
ECC 被广泛认为是在给定密钥长度的情况下，最强大的非对称算法，因此在对带宽要求十分紧的连接中会十分有用。
比特币钱包公钥的生成使用了椭圆曲线算法，通过椭圆曲线乘法可以从私钥计算得到公钥， 这是不可逆转的过程。
Java 中 Chipher、Signature、KeyPairGenerator、KeyAgreement、SecretKey 均不支持 ECC 算法。
DH，全称为"Diffie-Hellman"，它是一种确保共享 KEY 安全穿越不安全网络的方法，也就是常说的密钥一致协议。由公开密钥密码体制的奠基人 Diffie 和 Hellman 所提出的一种思想。简单的说就是允许两名用户在公开媒体上交换信息以生成"一致"的、可以共享的密钥。也就是由甲方产出一对密钥 (公钥、私钥)，乙方依照甲方公钥产生乙方密钥对 (公钥、私钥)。
以此为基线，作为数据传输保密基础，同时双方使用同一种对称加密算法构建本地密钥 (SecretKey) 对数据加密。这样，在互通了本地密钥 (SecretKey) 算法后，甲乙双方公开自己的公钥，使用对方的公钥和刚才产生的私钥加密数据，同时可以使用对方的公钥和自己的私钥对数据解密。不单单是甲乙双方两方，可以扩展为多方共享数据通讯，这样就完成了网络交互数据的安全通讯。
具体例子可以移步到这篇文章： 非对称密码之DH密钥交换算法
参考：
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的私钥进行解密。
当然，这种方式可能存在数据传递被模拟的隐患，但可以通过数字签名等技术进行安全性的进一步提升。由于存在多次的非对称加解密，这种方式带来的效率问题也更加严重。
智能化时代的到来涉及了各种核心算法，保护算法就能保障开发者权益，杜绝市面上各种山寨品，加密芯片恰好能起到很好的保护作用，如何选择加密芯片呢？KEROS加密芯片专注于加密领域十余年，行业首选。
1.安全性：采用国际通用aes256算法加密并同时通过KAS传送，除基本认证之外，利用2K安全EEPROM，用户可以自己管理密钥和数据，实现双重保护。
2.唯一性：以定制的方式为每一位用户单独定制“专属型号CID”，多用户之间算法不兼容，并且采用固化的方法直接将算法固化到晶圆上而无需烧入。
3.序列号：每颗芯片制造生产时具有5字节全球唯一SN序列号，每颗芯片SN都不会重复。
4.防抄特性：每颗芯片都有自己独特的密钥系统，破解单颗芯片只对这颗芯片对应的产品有效，对整个同类型的产品是无效的，依旧无法通过验证。而且KEROS采用ASIC方法设计，芯片内为纯逻辑电路，封装内有40多层逻辑电路整合了10万多个逻辑门，爆力刨片破解难度可想而知。
5.安全存储：用户可以将保密数据加密之后安全的存放到EEPROM中。rsa加密算法详细解说的介绍就聊到这里吧，感谢你花时间阅读本站内容。
本文标签：rsa加密算法详细解说
