非对称加密技术- RSA算法数学原理分析

非对称加密技术,在现在网络中,有非常广泛应用。加密技术更是数字货币的基础。

所谓非对称,就是指该算法需要一对密钥,使用其中一个(公钥)加密,则需要用另一个(私钥)才能解密。 但是对于其原理大部分同学应该都是一知半解,今天就来分析下经典的非对称加密算法 - RSA算法。 通过本文的分析,可以更好的理解非对称加密原理,可以让我们更好的使用非对称加密技术。

题外话: 并博客一直有打算写一系列文章通俗的密码学,昨天给站点上https, 因其中使用了RSA算法,就查了一下,发现现在网上介绍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的模反元素。

  1. (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又要相互通信。

  1. Alice 随机取大质数P1=53,P2=59,那N=53*59=3127,φ(N)=3016
  2. 取一个e=3,计算出d=2011。
  3. 只将N=3127,e=3 作为公钥传给Bob(公钥公开)
  4. 假设Bob需要加密的明文m=89,c = 89^3 mod 3127=1394,于是Bob传回c=1394。 (公钥加密过程)
  5. Alice使用c^d mod N = 1394^2011 mod 3127,就能得到明文m=89。 (私钥解密过程)

假如攻击者能截取到公钥n=3127,e=3及密文c=1394,是仍然无法不通过d来进行密文解密的。

安全性分析

那么,有无可能在已知n和e的情况下,推导出d?

123

ed≡1 (mod φ(n))。只有知道e和φ(n),才能算出d。  φ(n)=(p-1)(q-1)。只有知道p和q,才能算出φ(n)。  n=pq。只有将n因数分解,才能算出p和q。

如果n可以被因数分解,d就可以算出,因此RSA安全性建立在N的因式分解上。大整数的因数分解,是一件非常困难的事情。 只要密钥长度足够长,用RSA加密的信息实际上是不能被解破的。

补充模运算规则

  1. 模运算加减法: (a + b) mod p = (a mod p + b mod p) mod p (a - b) mod p = (a mod p - b mod p) mod p
  2. 模运算乘法: (a b) mod p = (a mod p b mod p) mod p
  3. 模运算幂 a ^ b mod p = ((a mod p)^b) mod p

原文发布于微信公众号 - 深入浅出区块链技术(blockchaincore)

原文发表时间:2017-11-16

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏阮一峰的网络日志

RSA算法原理(二)

上一次,我介绍了一些数论知识。 有了这些知识,我们就可以看懂RSA算法。这是目前地球上最重要的加密算法。 ? 六、密钥生成的步骤 我们通过一个例子,来理解RSA...

3506
来自专栏Vamei实验室

纸上谈兵: 拓扑排序

《文明》是一款风靡20多年的回合制策略游戏,由Sid Meier开发。《文明》结构宏大,内容丰富,玩法多样,游戏性强,称得上是历史上最伟大的游戏。在文明中,你可...

1779
来自专栏小樱的经验随笔

ACM训练计划

看完人家的博客,发现任重道远。。。 一位高手对我的建议: 一般要做到50行以内的程序不用调试、100行以内的二分钟内调试成功.acm主要是考算法的,主要时间...

38910
来自专栏灯塔大数据

每周学点大数据 | No.31拓扑排序

No.31期 拓扑排序 Mr. 王:很好,你还记得这个问题。接下来我们来讨论另一种磁盘中的大数据算法策略,叫作时间前向处理方法。在这种策略中,我会讲解求解最...

3537
来自专栏C/C++基础

P问题、NP问题、NPC问题(NP完全问题)、NPH问题和多项式时间复杂度

多项式关系形如O(nk)O(n^k),k为某个常数,n是问题的输入规模。例如,时间复杂度为O(nlog(n))、O(n^3)都是多项式时间复杂度。时间复杂度为O...

951
来自专栏一个会写诗的程序员的博客

函数式编程与面向对象编程[3]:Scala的OOP-FP混合式编程与抽象代数理论

Scala是纯种的面向对象的语言。从概念上讲,每一个值都是一个对象,每一个操作都是一个方法调用。语言支持通过类和特征的高级组件架构。

832
来自专栏专知

【LeetCode】关关的刷题日记23——Leetcode 66. Plus One

关小刷刷题 23——Leetcode 66. Plus One 题目 Given a non-negative integer represented as a...

2693
来自专栏FSociety

通过KNN算法预测数据所属NBA球员——Python实现

通过得分,篮板,助攻,出场时间四个数据来预测属于哪位球员。 选取了'LeBron James','Chris Paul','James Harden','Kev...

1035
来自专栏owent

09年8月14日 ECUST ACM 练习赛总结

今天在湖南的OJ上做题,发现不到两小时,他服务器就挂了,但是发现他和POJ上的一些题一样而且是连号的,就到POJ上继续了,我们队出了6题。

511
来自专栏小樱的经验随笔

博弈论及算法实现

在生活中五子棋也是一种先手有必赢策略的游戏,有人会说五子棋先手我也会输啊,所以 博弈论问题都有个类似如“参与者足够聪明”,“两人都不犯错"的前提。     在此...

3509

扫码关注云+社区