周语琦优秀作者
原创内容 来源:小居数码网 时间:2024-07-27 14:21:03 阅读() 收藏:40 分享:61 爆
导读:您正在阅读的是关于【数码知识】的问题,本文由科普作家协会,生活小能手,著名生活达人等整理监督编写。本文有2430个文字,大小约为11KB,预计阅读时间7分钟。
密码学是在编码与破译的斗争实践中逐步发展起来的,并随着先进科学技术的应用,已成为一门综合性的尖端技术科学。
在说RSA加密算法之前, 先说下密码学的发展史。其实密码学的诞生,就是为了运用在战场,在公元前,战争之中出现了秘密书信。在中国历史上最早的加密算法的记载出自于周朝兵书《六韬.龙韬》中的《阴符》和《阴书》。在遥远的西方,在希罗多德(Herodotus)的《历史》中记载了公元前五世纪,希腊城邦和波斯帝国的战争中,广泛使用了移位法进行加密处理战争通讯信息。
相传凯撒大帝为了防止敌人窃取信息,就使用加密的方式传递信息。那么当时的加密方式非常的简单,就是对二十几个罗马字母建立一张对照表,将明文对应成为密文。那么这种方式其实持续了很久。甚至在二战时期,日本的电报加密就是采用的这种原始加密方式。
凯撒密码对照表
早期的密码学一直没有什么改进,几乎都是根据经验慢慢发展的。直到20世纪中叶,由香农发表的《秘密体制的通信理论》一文,标志着加密算法的重心转移往应用数学上的转移。于是,逐渐衍生出了当今重要的三类加密算法:非对称加密、对称加密以及哈希算法(HASH严格说不是加密算法,但由于其不可逆性,已成为加密算法中的一个重要构成部分)。
1976年以前,所有的加密方法都是同一种模式:加密和解密使用同样规则(简称"密钥"),这被称为"对称加密算法",使用相同的密钥,两次连续的对等加密运算后会回复原始文字,也有很大的安全隐患。
1976年,两位美国计算机学家Whitfield Diffie 和 Martin Hellman,提出了一种崭新构思,可以在不直接传递密钥的情况下,完成解密。这被称为"Diffie-Hellman密钥交换算法"。也正是因为这个算法的产生,人类终于可以实现非对称加密了:A给B发送信息
1977年,三位数学家Rivest、Shamir 和 Adleman 设计了一种算法,可以实现非对称加密。这种算法用他们三个人的名字命名,叫做RSA算法。从那时直到现在,RSA算法一直是最广为使用的"非对称加密算法"。毫不夸张地说,只要有计算机网络的地方,就有RSA算法。这种算法非常可靠,密钥越长,它就越难破解。根据已经披露的文献,目前被破解的最长RSA密钥是232个十进制位,也就是768个二进制位,因此可以认为,1024位的RSA密钥基本安全,2048位的密钥极其安全,当然量子计算机除外。
下面进入正题,解释RSA算法的原理,其实RSA算法并不难,只需要一点数论知识就可以理解。
任意给定正整数n,请问在小于等于n的正整数之中,有多少个与n构成互质关系?(比如,在1到8之中,有多少个数与8构成互质关系?)计算这个值的方法就叫做欧拉函数,以φ(n)表示。
欧拉定理:如果两个正整数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
等式转换
等式转换3
根据模反元素,因为e*d 一定是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。 三个角色
为什么 6的13次方会和12的15次方得到一样的结果呢?因为这就是规律,我们可以用小一点的数字测试一下3^3 mod 17 = 10和10 ^ 2 mod 17 ; 3 ^ 2 mod 17 = 9和9^3 mod 17结果都是15。迪菲赫尔曼密钥交换最核心的地方就在于这个规律
迪菲赫尔曼密钥交换转换
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的数学原理
我们用终端命令演示下这个加密、解密过程。
假设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给对称加密的KEY进行加密,或者加密Hash值,也就是数字签名。
上面就是小居数码小编今天给大家介绍的关于(非对称加密算法RSA)的全部内容,希望可以帮助到你,想了解更多关于数码知识的问题,欢迎关注我们,并收藏,转发,分享。
94%的朋友还想知道的:
(590)个朋友认为回复得到帮助。
部分文章信息来源于以及网友投稿,转载请说明出处。
本文标题:非对称加密算法RSA主要特点是什么(非对称加密算法RSA):http://sjzlt.cn/shuma/151964.html