非对称加密--RSA原理浅析

栏目: 编程工具 · 发布时间: 5年前

内容简介:在1976年以前,所有的加密方法都是同一种模式:加密、解密使用同一种算法。在交互数据的时候,彼此通信的双方就必须将规则告诉对方,否则没法解密。那么加密和解密的规则(简称密钥),它保护就显得尤其重要。传递密钥就成为了最大的隐患。这种加密方式被成为对称加密算法。直到1976年,两位美国计算机学家:迪菲(W.Diffie)、赫尔曼(M.Hellman)提出了一种崭新构思,可以在不直接传递密钥的情况下完成密钥交换,开创了密码学研究的新方向。这就是“迪菲赫尔曼密钥交换”算法,其仍然是一种对称加密算法,只是密钥不再需要

在1976年以前,所有的加密方法都是同一种模式:加密、解密使用同一种算法。在交互数据的时候,彼此通信的双方就必须将规则告诉对方,否则没法解密。那么加密和解密的规则(简称密钥),它保护就显得尤其重要。传递密钥就成为了最大的隐患。这种加密方式被成为对称加密算法。

直到1976年,两位美国计算机学家:迪菲(W.Diffie)、赫尔曼(M.Hellman)提出了一种崭新构思,可以在不直接传递密钥的情况下完成密钥交换,开创了密码学研究的新方向。这就是“迪菲赫尔曼密钥交换”算法,其仍然是一种对称加密算法,只是密钥不再需要传递。交换原理如下图所示:

非对称加密--RSA原理浅析

其中a,b是在通信两端本地的随机数,g是模p的一个原根,K是交换后产生的密钥,安全性来源于当p非常大时,已知g,p,A,B很难反算出a,b。离散对数问题是该算法的基础。

1977年,三位麻省理工学院的数学家 罗纳德·李维斯特(Ron Rivest)、阿迪·萨莫尔(Adi Shamir)和伦纳德·阿德曼(Leonard Adleman)一起设计了一种算法,可以实现非对称加密。这就是用他们三个人的名字命名的算法--RSA算法。

要弄清楚RSA的加密原理,先要知道 欧拉定理

对于两个互质的正整数m、n,m^φ(n) ≡ 1

当m

进一步得到:m^(k*φ(n)+1) ≡ m

基于此还需要理解一个概念,模反元素:

如果两个正整数e和x互质,那么一定可以找到整数d,使得 e*d-1 被x整除。那么d就是e对于x的“模反元素”

即e*d mod x ≡ 1

等同于 e*d ≡ k*x + 1,k为正整数

敲黑板!!!关键来了,上面两个转换的结果一碰撞,Duang!就碰出了我们RSA的核心算法:

当e与φ(n)互质时,m^(e*d) mod n ≡ m

鸡不鸡冻,开不开森!还有点迷糊?没关系,来继续:

假设我们对m进行加密传输

加密:m^e mod n = c,

解密:c^d mod n = m^(e*d) mod n = m

上述过程中, n+e就是RSA中的公钥,n+d就是RSA中的私钥,c是加密后的密文。

补充:

  1. n会非常大,长度一般为1024个二进制位,现在稳妥一点的长度为2048个二进制位。(目前人类已经分解的最大整数,232个十进制位,768个二进制位)
  2. 由于需要求出φ(n),所以根据欧函数特点,最简单的方式n 由两个质数相乘得到: 质数:p1、p2 Φ(n) = (p1 -1) * (p2 - 1)
  3. 最终由φ(n)得到 e 和 d 。

总共生成6个数字:p1、p2、n、φ(n)、e、d

关于RSA的安全:

除了公钥用到了n和e 其余的4个数字是不公开的。 目前破解RSA得到d的方式如下:

  1. 要想求出私钥 d 。由于e*d = φ(n)*k + 1。要知道e和φ(n);
  2. e是知道的,但是要得到 φ(n),必须知道p1 和 p2。
  3. 由于 n=p1*p2。只有将n因数分解才能算出。
  4. 量子计算机如果成功诞生,现在通行于银行及网络等处的RSA加密算法可以破解,也会瓦解所有基于大质数因式分解算力逆天而衍生出的加密算法。

后面我会继续对iOS证书签名相关原理进行分析,同时把常见的加密算法做一下梳理和比较,并附上每种算法在iOS中的代码实现。欢迎一起交流学习心得~


以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

PHP&MySQL Web数据库应用开发指南

PHP&MySQL Web数据库应用开发指南

Hugb E. Williams、David Lane / 谢君英 / 中国电力出版社 / 2003-5 / 69.00元

一起来看看 《PHP&MySQL Web数据库应用开发指南》 这本书的介绍吧!

SHA 加密
SHA 加密

SHA 加密工具

XML、JSON 在线转换
XML、JSON 在线转换

在线XML、JSON转换工具

HEX CMYK 转换工具
HEX CMYK 转换工具

HEX CMYK 互转工具