专注于IT行业优质技术服务号,欢迎关注
作者:我叫Vincent
密码学发展史密码学是在编码与破译的斗争实践中逐步发展起来的,并随着先进科学技术的应用,已成为一门综合性的尖端技术科学。
在说RSA加密算法之前, 先说下密码学的发展史。其实密码学的诞生,就是为了运用在战场,在公元前,战争之中出现了秘密书信。在中国历史上最早的加密算法的记载出自于周朝兵书《六韬.龙韬》中的《阴符》和《阴书》。在遥远的西方,在希罗多德(Herodotus)的《历史》中记载了公元前五世纪,希腊城邦和波斯帝国的战争中,广泛使用了移位法进行加密处理战争通讯信息。
相传凯撒大帝为了防止敌人窃取信息,就使用加密的方式传递信息。那么当时的加密方式非常的简单,就是对二十几个罗马字母建立一张对照表,将明文对应成为密文。那么这种方式其实持续了很久。甚至在二战时期,日本的电报加密就是采用的这种原始加密方式。
凯撒密码对照表
早期的密码学一直没有什么改进,几乎都是根据经验慢慢发展的。直到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的模反元素。