浅谈加密算法（一）RSA

发表于 更新于 阅读次数： 本文字数： 2.6k

什么是RSA

了解RSA之前我们要先了解对称式加密算法和非对称式加密算法

对称式加密算法指的是用于加密的密钥和解密的密钥是同一个，非对称式加密算法就是加密的密钥和解密的密钥并非同一个（分为公钥和私钥）

而RSA 是一种非常优秀的非对称式的加密算法。

RSA加密算法的优势

RSA算法主要是用来数据加密和数字签名。

RSA的神奇之处在于它有一个公钥和一个私钥，公钥可以公开，任何人都可以用，私钥只能你自己用，必须保护好。公钥加密的信息只能用私钥解密（公钥也解不开，就是这么神奇）。

这根我们平常理解的加密不一样。加密相当于上锁，解密相当于开锁。日常生活中上锁和开锁用的是同一把钥匙（家家的锁都是这样的），没有问题，但是在上网时这样做是有问题的。

有什么问题呢？

假如说你登录网上银行给朋友转账，不幸的是你被黑客盯上了。当你在网银上填写朋友的账号和转账金额后，账号和金额会通过互联网传给银行。当然，这中间需要经过很多路由器（比如你家的路由器）。黑客完全可以截获你发给银行的信息（太容易了），然后把你转账的目标账号修改成他的账号，这样钱就到他那儿了，太危险了。

为了避免上面的情况发生，你填写的目标账号和转账金额都是加密后传给银行（虽然你没有看到，但是浏览器默默帮你加密了），这下黑客没办法了吧？还是有办法的！

你登录网银的时候，银行会把秘钥传给你的浏览器，黑客当然也能截获秘钥。刚才我们说了，加密和解密用同一个秘钥（钥匙），黑客截获了你和银行间的秘钥，就能解开加密的数据，还是可以把你转账的目标账号换成他的账号。这下郁闷了：还能不能开心的用网银转账了？难道非得亲自去银行柜台办理？

先看看问题的根源：由于黑客能截获你和银行之间的所有信息，所以无论发送的是秘钥还是账号，统统都逃不过黑客的眼睛。这时候加密形同虚设了。那怎么才能安全的转账呢？

现在该RSA算法展示真正的技术了！

假设银行放弃了上面的加密方式，转而使用RSA算法。当你登录网银的时候，银行先把它的公钥发给你的浏览器（公钥可以给任何人看，包括黑客），当你输入转账金额和账号后，浏览器先用银行的公钥进行加密，然后发给银行。注意，公钥加密的数据只能用私钥解密，而私钥在银行手里！这时黑客截获了加密数据也无法解密，此时黑客的内心是痛苦的：我没有银行的私钥啊！这样我们就安全的完成了网银转账。

这就是RSA算法的神奇之处。RSA算法实现了在不安全信道上进行数据的安全传输。

RSA算法不仅可以用于银行系统，还可以用于个人间的数据安全分享。比如说你和朋友想分享一些文件，但是你俩的网络被黑客监控了。这时你可以和朋友交换公钥，把要分享的文件先通过他的公钥加密后发给他，黑客由于没有你朋友的私钥而无法解密，只有你朋友能解密。你朋友用同样的方法把他的文件加密分享给你。进一步扩展，任何两个单位/个人之见都可以通过这种方式加密分享数据，而不用担心被黑客解密。

这么看来，RSA算法既神奇又实用！

前些年大起大落的比特币（区块链技术），用的就是公钥密码算法，虽然不是RSA算法，但原理相同。

自从诞生的那一天起，RSA算法就接受来自全球黑客、学者、研究人员的攻击。40多年过去了，事实证明RSA算法很安全，只要你的秘钥够长。RSA秘钥长度通常是1024~4096位。2010年的时候攻破了RSA-768，一些专家认为RSA-1024在不远的未来会被攻破，但没几乎有人认为RS-4096能够在可预见的未来被攻破。

1
2
3
4
5
6
7
8
9
本段（指 RSA加密算法的优势） 本行以上内容均为转载内容

作者：Alliawell

链接：https://www.jianshu.com/p/21556822bf39

来源：简书

著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

而数字签名即是一方用私钥加密，而收信方可以通过公钥正常解密，以证明对方身份，这种方式也因与生活中签名的作用相似而得名

RSA加密算法的缺点

RSA加密因涉及许多复杂运算，所以比起对称式加密算法还是有一些缺点

  1. 加解密速度慢
  2. 不适合大文件加密
  3. 加密后数据长度发生变化

实现方法

终于到了正文部分

前置知识

1.mod 运算

mod又称 模，取余。 顾名思义它是得到余数的运算

例如：
11/3 = 3……2
11 mod 3 = 2

常用规律： (a×b) mod n = [(a mod n) × (b mod n)] mod n

2.欧拉函数

欧拉函数，记作φ(n)，表示为从1到n的自然数中与n互质的数的个数

例如：
当N=10时，与10互质的正整数有1，3，7，9，所以φ(10)=4。

当 n = p × q (p, q 为质数) 时

在 1 ~ n 中不与 n 互质的数为 p, q 及它们的倍数

1.在 1 ~ n 中，因为 n = p × q 所以 p 及 p 的倍数有 q 个

2.在 1 ~ n 中，因为 n = p × q 所以 q 及 q 的倍数有 p 个

而 1, 2 中有一个数 p × q 重复， 所以不与 n 互质的数有 p + q - 1 个

所以 φ(n) = n - p - q + 1 = p × q - (p + q) + 1 = (p - 1) × (q - 1)

3.欧拉定理

欧拉定理是指一个关于同余的性质，具体表述为：若n和a为正整数，且互质，则 mod n = 1

了解这一切之后我们就可以愉快的开始了

准备工作

设密文为 C , 明文为 M

1.生成p, q两个大质数且p,q大于M 所以 n = p × q > M

2.计算欧拉函数 φ(n) = (p - 1) × (q - 1)

3.计算两个正整数值 e 与 d 使之满足 (e × d) mod φ(n) = 1, 其中 e 为公钥 d 为私钥

加解密方程

加密 C = mod n

解密 M = mod n

证明

∵(e × d) mod φ(n) = 1

∴e × d = t × φ(n) + 1, t∈Z

∴ =

∴ mod n = （） mod n = （M mod n） × [ mod mod n]

∵欧拉定理 且 p, q两个大质数不等于M

∴ mod n = 1

∴ mod n = (M mod n) × ( mod n) = M mod n

∵n = p × q > M

∴ mod n = M

证毕

1
本段（指 实现方法）参考《每个人都应学点密码学 给秘密加把锁》 王旭正 著 有所改动

安全性分析

由上文可知私钥d依赖于φ(n)，而目前求出φ(n)最好的方法就是把生成密钥的步骤倒过来，即质因数分解，而质因数分解目前最快的算法时间复杂度为亚指数级，所以目前看来只要大质数p, q足够大， RSA加密都是安全的