摘要：本文首发于深入浅出区块链社区原文链接非对称加密技术算法数学原理分析原文已更新，请读者前往原文阅读非对称加密技术，在现在网络中，有非常广泛应用。加密技术更是数字货币的基础。
本文首发于深入浅出区块链社区
原文链接:非对称加密技术 - RSA算法数学原理分析原文已更新，请读者前往原文阅读非对称加密技术，在现在网络中，有非常广泛应用。加密技术更是数字货币的基础。
所谓非对称，就是指该算法需要一对密钥，使用其中一个（公钥）加密，则需要用另一个（私钥）才能解密。
但是对于其原理大部分同学应该都是一知半解，今天就来分析下经典的非对称加密算法 - RSA算法。
通过本文的分析，可以更好的理解非对称加密原理，可以让我们更好的使用非对称加密技术。
题外话:
本博客一直有打算写一系列文章通俗的密码学，昨天给站点上https, 因其中使用了RSA算法，就查了一下，发现现在网上介绍RSA算法的文章都写的太难理解了，反正也准备写密码学，就先写RSA算法吧，下面开始正文。
RSA算法的基于这样的数学事实：两个大质数相乘得到的大数难以被因式分解。
如：有很大质数p跟q，很容易算出N，使得 N = p * q，
但给出N, 比较难找p q（没有很好的方式， 只有不停的尝试）
这其实也是单向函数的概念
下面来看看数学演算过程：
1、 选取两个大质数p，q，计算N = p q 及 φ ( N ) = φ (p) φ (q) = (p-1) * (q-1)
三个数学概念：
质数(prime numbe)：又称素数，为在大于1的自然数中，除了1和它本身以外不再有其他因数。
互质关系：如果两个正整数，除了1以外，没有其他公因子，我们就称这两个数是互质关系（coprime）。
φ(N)：叫做欧拉函数，是指任意给定正整数N，在小于等于N的正整数之中，有多少个与N构成互质关系。如果n是质数，则 φ(n)=n-1。
如果n可以分解成两个互质的整数之积， φ(n) = φ(p1p2) = φ(p1)φ(p2)。即积的欧拉函数等于各个因子的欧拉函数之积。
2、选择一个大于1 小于φ(N)的数e，使得 e 和 φ(N)互质
e其实是1和φ(N)之前的一个质数
3、 计算d，使得de=1 mod φ(N) 等价于方程式 ed-1 = k φ(N) 求一组解。
d 称为e的模反元素，e 和 φ(N)互质就肯定存在d。
模反元素是指如果两个正整数a和n互质，那么一定可以找到整数b，使得ab被n除的余数是1，则b称为a的模反元素。
可根据欧拉定理证明模反元素存在，欧拉定理是指若n,a互质，则：
a^φ(n) ≡ 1(mod n) 及 a^φ(n) = a * a^（φ(n) - 1）， 可得a的 φ(n)-1 次方，就是a的模反元素。
4、 (N, e)封装成公钥，(N, d)封装成私钥。
假设m为明文，加密就是算出密文c:
m^e mod N = c (明文m用公钥e加密并和随机数N取余得到密文c)
解密则是：
c^d mod N = m (密文c用密钥解密并和随机数N取余得到明文m) > 私钥解密这个是可以证明的，这里不展开了。加解密步骤
具体还是来看看步骤，举个例子，假设Alice和Bob又要相互通信。
Alice 随机取大质数P1=53，P2=59，那N=53*59=3127，φ(N)=3016
取一个e=3，计算出d=2011。
只将N=3127，e=3 作为公钥传给Bob（公钥公开）
假设Bob需要加密的明文m=89，c = 89^3 mod 3127=1394，于是Bob传回c=1394。 （公钥加密过程）
Alice使用c^d mod N = 1394^2011 mod 3127，就能得到明文m=89。 （私钥解密过程）
假如攻击者能截取到公钥n=3127，e=3及密文c=1394，是仍然无法不通过d来进行密文解密的。
安全性分析那么，有无可能在已知n和e的情况下，推导出d？
1. ed≡1 (mod φ(n))。只有知道e和φ(n)，才能算出d。 2. φ(n)=(p-1)(q-1)。只有知道p和q，才能算出φ(n)。 3. n=pq。只有将n因数分解，才能算出p和q。
如果n可以被因数分解，d就可以算出，因此RSA安全性建立在N的因式分解上。大整数的因数分解，是一件非常困难的事情。
只要密钥长度足够长，用RSA加密的信息实际上是不能被解破的。
模运算加减法：
(a + b) mod p = (a mod p + b mod p) mod p
(a - b) mod p = (a mod p - b mod p) mod p
模运算乘法：
(a b) mod p = (a mod p b mod p) mod p
模运算幂
a ^ b mod p = ((a mod p)^b) mod p
☛ 深入浅出区块链 - 系统学习区块链，打造最好的区块链技术博客。
☛ 我的知识星球为各位解答区块链技术问题，欢迎加入讨论。
☛ 关注公众号“深入浅出区块链技术”第一时间获取区块链技术信息。
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/24071.html
摘要：二如何理解公钥和私钥非对称加密算法需要两个密钥公开密钥和私有密钥。因为加密和解密使用的是两个不同的密钥，所以这种算法叫作非对称加密算法。三非对称加密解密原理非对称加密算法中，常用的就是算法了，以下就以算法为例来讲解非对称加密算法的实现原理。 非对称加密，在现在网络应用中，有这非常广泛的场景，更是加密货币的基础。本文主要介绍非对称加密、解密的原理和过程，以及在区块链中的使用。 一、非对称...
摘要：公开密钥加密的出现大大减轻了交换对称密钥的困难，公钥可以公开透过不安全可被窃听的渠道发送，用以加密明文。当与配合使用，称之为，与配合则称为，以此类推。这步没有签名，服务端收到数据后不会发现被篡改。对于认证机构，一旦私钥外泄，将可能导致整未济，亨。小狐汔济，濡其尾，无攸利。——《易》六、密钥管理当不再担心身份会被冒充、篡改之后，我们再来详细谈谈网络通信中对于加密算法的密钥管理。在密钥被签发后，...
摘要：系列密码学二传送门密码学一基础密码学算法分类消息编码消息摘要类，类，对称密码非对称密码数字签名五元组明文原始信息。非对称密码包提供给，，等非对称加密算法。对称加密算法在分布式网络系统上使用较为困难，主要是因为密钥管理困难，使用成本较高。 前言 最近一场面试，面试官问了我 对称加密与非对称加密的问题，虽然曾经看过一些内容，但是没有系统的整理，所以当被问的时候，脑子里一片空白，没有回答上...
摘要：算法公钥加密算法是年由罗纳德李维斯特阿迪萨莫尔和伦纳德阿德曼一起提出的。是目前最有影响力的公钥加密算法，它能够抵抗到目前为止已知的绝大多数密码攻击，已被推荐为公钥数据加密标准。 上篇文章介绍了对称加密的原理，但是它的最大问题就是加密和解密的密钥是相同的，并且不能保证密钥能安全的送到双方手里，即使安全的送到双方手里，免不了内部会有卧底的存在 非对称加密 既然有对称加密，那么自然会联想到非...
摘要：假如黎曼猜想被证实，区块链将毁灭近日，黎曼猜想四个字疯狂刷屏。黎曼猜想由数学家波恩哈德黎曼于年提出。因此，黎曼猜想一旦被证明，则意味着素数之密被解开，算法也就将被攻破了。而大多数区块链所用的加密算法不是，而是椭圆曲线加密算法。 玛丽女王的密码之生死命悬一线 showImg(https://segmentfault.com/img/bVbhD7s?w=740&h=876); 16世纪伊丽...
阅读 3833·2021-11-22 13:53
阅读 1461·2021-09-23 11:52
阅读 2243·2021-09-06 15:02
阅读 688·2019-08-30 15:54
阅读 707·2019-08-30 14:15
阅读 2264·2019-08-29 18:39
阅读 477·2019-08-29 16:07
阅读 298·2019-08-29 13:13
