作者:我叫Vincent

密码学是在编码与破译的斗争实践中逐步发展起来的,并随着前辈科学技能的运用,已成为一门综合性的尖端技能科学。

密码学发展史

在说RSA加密算法之前, 先说下密码学的发展史。
实在密码学的出身,便是为了利用在沙场,在公元前,战役之中涌现了秘密书信。
在中国历史上最早的加密算法的记载出自于周朝兵书《六韬.龙韬》中的《阴符》和《阴书》。
在迢遥的西方,在希罗多德(Herodotus)的《历史》中记载了公元前五世纪,希腊城邦和波斯帝国的战役中,广泛利用了移位法进行加密处理战役通讯信息。

rsa加密算法php非对称加密算法RSA加密道理及应用 JavaScript

相传凯撒大帝为了防止仇敌窃取信息,就利用加密的办法通报信息。
那么当时的加密办法非常的大略,便是对二十几个罗马字母建立一张对照表,将明文对应成为密文。
那么这种办法实在持续了良久。
乃至在二战期间,日本的电报加密便是采取的这种原始加密办法。

凯撒密码对照表

早期的密码学一贯没有什么改进,险些都是根据履历逐步发展的。
直到20世纪中叶,由喷鼻香农揭橥的《秘密系统编制的通信理论》一文,标志着加密算法的重心转移往运用数学上的转移。
于是,逐渐衍生出了当今主要的三类加密算法:非对称加密、对称加密以及哈希算法(HASH严格说不是加密算法,但由于其不可逆性,已成为加密算法中的一个主要构成部分)。

1976年以前,所有的加密方法都是同一种模式:加密和解密利用同样规则(简称\"大众密钥\"大众),这被称为\"大众对称加密算法\公众,利用相同的密钥,两次连续的对等加密运算后会回答原始笔墨,也有很大的安全隐患。

1976年,两位美国打算机学家Whitfield Diffie 和 Martin Hellman,提出了一种崭新构思,可以在不直接通报密钥的情形下,完成解密。
这被称为\公众Diffie-Hellman密钥交流算法\"大众。
也正是由于这个算法的产生,人类终于可以实现非对称加密了:A给B发送信息

B要师长西席成两把密钥(公钥和私钥)。
公钥是公开的,任何人都可以得到,私钥则是保密的。
A获取B的公钥,然后用它对信息加密。
B得到加密后的信息,用私钥解密。
理论上如果公钥加密的信息只有私钥解得开,那么只要私钥不泄露,通信便是安全的。

1977年,三位数学家Rivest、Shamir 和 Adleman 设计了一种算法,可以实现非对称加密。
这种算法用他们三个人的名字命名,叫做RSA算法。
从那时直到现在,RSA算法一贯是最广为利用的\"大众非对称加密算法\"大众。
绝不夸年夜地说,只要有打算机网络的地方,就有RSA算法。
这种算法非常可靠,密钥越长,它就越难破解。
根据已经表露的文献,目前被破解的最长RSA密钥是232个十进制位,也便是768个二进制位,因此可以认为,1024位的RSA密钥基本安全,2048位的密钥极其安全,当然量子打算机除外。

RSA算法的事理

下面进入正题,阐明RSA算法的事理,实在RSA算法并不难,只须要一点数论知识就可以理解。

素数:又称质数,指在一个大于1的自然数中,除了1和此整数自身外,不能被其他自然数整除的数。
互质,又称互素。
若N个整数的最大公因子是1,则称这N个整数互质。
模运算即求余运算。
“模”是“Mod”的音译。
和模运算紧密干系的一个观点是“同余”。
数学上,当两个整数除以同一个正整数,若得相同余数,则二整数同余。
欧拉函数

任意给定正整数n,叨教在小于即是n的正整数之中,有多少个与n构成互质关系?(比如,在1到8之中,有多少个数与8构成互质关系?)打算这个值的方法就叫做欧拉函数,以φ(n)表示。

打算8的欧拉函数,和8互质的 1、2、3、4、5、6、7、8 φ(8) = 4 如果n是质数的某一个次方,即 n = p^k (p为质数,k为大于即是1的整数),则φ(n) = φ(p^k) = p^k - p^(k-1)。
也便是φ(8) = φ(2^3) =2^3 - 2^2 = 8 -4 = 4打算7的欧拉函数,和7互质的 1、2、3、4、5、6、7 φ(7) = 6 如果n是质数,则 φ(n)=n-1 。
由于质数与小于它的每一个数,都构成互质关系。
比如5与1、2、3、4都构成互质关系。
打算56的欧拉函数 φ(56) = φ(8) φ(7) = 4 6 = 24 如果n可以分解成两个互质的整数之积,即 n = p k ,则φ(n) = φ(p k) = φ(p1)φ(p2)

欧拉定理:如果两个正整数m和n互质,那么m的φ(n)次方减去1,可以被n整除。

欧拉定理

费马小定理:欧拉定理的分外情形,如果两个正整数m和n互质,而且n为质数!
那么φ(n)结果便是n-1。

费马小定理

模反元素

还剩下末了一个观点,模反元素:如果两个正整数e和x互质,那么一定可以找到整数d,使得 ed-1 被x整除,或者说ed被x除的余数是1。

那么d便是e相对付x的模反元素。

d是模反元素

等式转换

根据欧拉定理

等式转换1

由于1^k ≡ 1,等号旁边两边都来个k次方

等式转换

由于1 m ≡ m,等号旁边两边都乘上m

等式转换3

根据模反元素,由于ed 一定是x的倍数加1。
以是如下:

等式转换

通过多次的等式转换。
终于可以将这两个等式进行合并了!
如下:

终极等式转换

这个等式成立有一个条件!
便是关于模反元素的,便是当整数e和φ(n)互质!
一定有一个整数d是e相对付φ(n)的模反元素。

我们可以测试一下。

m取值为4

n取值为15

φ(n)取值为8

e 如果取值为3

d 可以为 11、19...(模反元素很明显不止一个,实在便是解二元一次方程)

如果你测试了,那么你可以改变m的值试一下,实在这个等式不须要m和n 互质。
只要m小于n 等式依然成立。

这里须要把稳的是,我们可以看做 m 通过一系列运算得到结果仍旧是 m。
这一系列运算中,分别涌现了多个参数n、φ(n)、e还有d。

m 的 e乘上d 次方为加密运算,得到结果 c

c 模以 n 为解密运算,得到结果 m

这彷佛可以用于加密和解密。
但这样,加密的结果会非常大。
明文数据将非常小(虽然RSA用于加密的数据也很小,但是没这么大悬殊),真正的RSA要更加强大,那么RSA是怎么演化来的呢??

早期很多数学家也勾留在了这一步!
直到1967年迪菲赫尔曼密钥交流冲破了僵局!

迪菲赫尔曼密钥交流

这个密钥交流当时轰动了全体数学界!
而且对人类密码学的发展非常主要,由于这个伟大的算法能够拆分刚才的等式。
当非对称加密算法没有涌现以前,人类都是用的对称加密。
以是密钥的通报,就必须要非常小心。

迪菲赫尔曼密钥交流 便是办理了密钥通报的保密性,我们来看一下

迪菲赫尔曼密钥交流

假设一个通报密钥的场景。
算法便是用3 的次方去模以17。
三个角色

做事器 随机数 15 这个15只有做事器才知道。
通过算法得到结果 6 由于 3的15次方 mod 17 = 6 。
然后将结果 6 公开拓送出去,拿到客户真个 12 ,然后用12^15 mod 17 得到结果10(10便是交流得到的密钥)客户端 随机数13 客户端用3 的 13次方 mod 17 = 12 然后将得到的结果12公布出去。
拿到做事器的 6 ,然后用6^13 mod 17 得到结果10(10便是交流得到的密钥)第三者 第三者只能拿到6 和 12 ,由于没有私密数据13、15,以是它没法得到结果10。

为什么 6的13次方会和12的15次方得到一样的结果呢?由于这便是规律,我们可以用小一点的数字测试一下3^3 mod 17 = 10和10 ^ 2 mod 17 ; 3 ^ 2 mod 17 = 9和9^3 mod 17结果都是15。
迪菲赫尔曼密钥交流最核心的地方就在于这个规律

迪菲赫尔曼密钥交流转换

RSA的出身

RSA事理

现在我们知道了m^e % n = c是加密,c^d % n = m是解密,m便是原始数据,c是密文,公钥是n和e,私钥是n和d,以是只有n和e是公开的。
加密时我们也要知道φ(n)的值,最大略的办法是用两个质数之积得到,别人想破解RSA也要知道φ(n)的值,只能对n进行因数分解,那么我们不想m被破解,n的值就要非常大,便是我们之前说的,长度一样平常为1024个二进制位,这样就很安全了。
但是听说量子打算机(用于科研,尚未遍及)可以破解,理论上量子打算机的运行速率无穷快,大家可以理解一下。

以上便是RSA的数学事理

考验RSA加密算法

我们用终端命令演示下这个加密、解密过程。

假设m = 12(随便取值,只要比n小就OK),n = 15(还是随机取一个值),φ(n) = 8,e = 3(只要和φ(n)互质就可以),d = 19(3d - 1 = 8,d也可以为3,11等等,也便是d = (8k + 1)/3 )

终端分别以m=12,7输入结果

终端演示

OpenSSL进行RSA的命令运行

Mac可以直策应用OpenSSL,首先进入相应文件夹

天生公私钥

// 天生RSA私钥,文件名为private.pem,长度为1024bitopenssl genrsa -out private.pem 1024// 从私钥中提取公钥openssl rsa -in private.pem -pubout -out publick.pem

天生私钥

// 查看刚刚天生好的私钥cat private.pem// 查看刚刚天生好的公钥cat publick.pem

查看公私钥

我们可以看到base64编码,明显私钥二进制很大,公钥就小了很多。

这时候我们的文件夹内已经多了刚刚天生好的公私钥文件了

公私钥文件

// 将私钥转换为明文openssl rsa -in private.pem -text -out private.txt

96111F25-0954-4854-9B36-75413A439AFD

里面便是P1、P2还有KEY等信息。

对文件进行加密、解密

RSA用场及特点

到这里,大家都知道RSA通过数学算法来加密和解密,效率比较低,以是一样平常RSA的主沙场是加密比较小的数据,比如对大数据进行对称加密,再用RSA给对称加密的KEY进行加密,或者加密Hash值,也便是数字署名。

希望能够帮助大家,也欢迎大家点赞留言互换

链接:https://www.jianshu.com/p/ad3d1dea63af