博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
RSA算法简介
阅读量:5883 次
发布时间:2019-06-19

本文共 2779 字,大约阅读时间需要 9 分钟。

  hot3.png

如果我们有什么珍贵的东西一定会想办法把它锁在箱子里,有锁就有钥匙,这里牵扯到一个道理,锁之所以称之为锁是因为有钥匙可以很方便的解锁,而你有锁想要配钥匙则非常困难,这是一个单向的过程

对称密钥

对称密钥是给跟自己发生关联的人都发一把钥匙,如果人太多,这个出现钥匙成倍的增加,每一对都是一把,排列组合一下

非对称密钥

我只发给关联的人一把未关的锁,由对方来关,由自己来解,这就省去了钥匙的传递,而只与锁有关

数学解释

有没有一个办法使得由条件推结果容易,而由结果推条件则很难呢,这就是锁的定义,而在数学上的解释就是单向函数

m ^ e mod n = cm为信息e为指数n为模数c为加密后的数据知道m,e,n, 很容易知道c 知道e,n,c,  很难知道m

这个函数则是我们加密的方式方法

如何解密

m ^ e mod n = c                                           (1)c ^ d mod n = m                                           (2)由(1)代(2)m ^ (e*d) mod n = m                                       (3)e是加密密钥,d是解密密钥,知道d,则可以得到原始真实信息m欧拉函数用φ来表示,该数有几个与自己除公因数1以外的数如 φ(8)=4  {1,3,5,7}4个如果n为质数, φ(n)=n-1欧拉定理: m ^ φ(n) mod n = 1                              (4)由(4)左右边各指数幂k(m ^ φ(n))^k mod n = 1^k                                 (5)由(5)得m ^ (φ(n)*k) mod n = 1                                   (6)由(6)两边都*m得m ^ (φ(n)*k+1) mod n = m                                 (7)比较(7)和(3)可得e * d = φ(n) * k + 1                                     (8)d = (φ(n)*k+1)/e如果 n = p * q 且 p, q都为质数,则 φ(n) = (p-1)(q-1)由(8)式可知有两个未知数d,k,可以演变成一元二次方程 ex+φ(n)y=1,该方程可由扩展欧几里德算法解出特解(x,y)即d,kd破解成功

可知n,e,c都是公开的,n是模数,e是指数,c 是加密后的数据,而重要的是d,也就是我们说的私钥,如果知道d,  就可以还原出m, 如果不知道d, 需要分解n=pq,而这是一件相当困难的事,由其当p,q很大时,但是一旦破解出p,q, 想要计算出d也就不难了,见(8)式,所以p,q也是保密的

RSA与HTTPS的关系

RSA由于太耗CPU的资源,因此它通常用来加密对称密钥,或者用来数字签名,HTTPS用到RSA有两个地方,一个是客户端验证证书的有效性,另一个是加密pre_master随机值,通过服务器,客户端各产生的随机值再加这一个公钥加密的随机值从而计算出对称密钥

证书即公钥+签名公钥(n,e)该证书的公钥有4096位组成的大数,这个数就是n指数e是65537

客户端利用这个公钥加密pre_master随机值

m = premasterm ^ e mod n = c加密后得到c,是通过(n,e)进行加密的

服务器用自己的私钥进行解密得到pre_master随机值

服务器有私钥d 服务器接收到客户端传来的pre_master的加密值,即c通过私钥解密(n,d)c ** d mod n = m 即 pre_master

RSA的安全性

(n,e)作为公钥,同时作为中间人是可以知道c加密信息的,但想要通过(n,c,e)计算出d,只有一个办法,你能把n因式分解成p*q,如果知道p,q,那么 d = ((p-1)(q-1)+1)/e,但是想要把一个超过1024位的大数因式分解是非常困难的,目前无人能做到,因此得不到私钥

可见RSA在HTTPS作用了两次

1 用服务器的公钥加密pre_master随机值以为后面计算对称密钥作准备2 CA数字签名,证书里包括了公钥和数字签名(对证书信息进行hash得到摘要,并用CA的私钥进行加密)  s即签名,只不过用私钥进行加密:  m ^ d mod n = s   解密用公钥解              :  s ^ e mod n = m ^ (d*e) mod n = m   客户端浏览器通过预装根证书从而有了CA的公钥从而可以对服务器证书的签名进行解密得到摘要,而又通过计算证书信息的摘要进行比对从而验证数据的完整性

RSA验证

#RSA algorithmdef rsa_algorithm_encrypted(message,public_key,keyE):	encrypted_message = message ** keyE % public_key	return encrypted_messagedef rsa_algorithm_decrypted(private_key,public_key,encrypted_message):	message = encrypted_message ** private_key % public_key	return messagep = 53q = 59public_key = 53*59aola = (53-1)*(59-1)keyE = 3private_key = (2*3016+1)/3message = 89encrypted_message = rsa_algorithm_encrypted(message,public_key,keyE)print "encrypted_message is %d" %encrypted_messagedecrypted_message = rsa_algorithm_decrypted(private_key,public_key,encrypted_message)print "decrtypted_message is %d" %decrypted_messag--------------------------------------------------------

 

转载于:https://my.oschina.net/hding/blog/700702

你可能感兴趣的文章
怎么使用阿里云直播服务应用到现在主流直播平台中
查看>>
1000 加密算法
查看>>
exif_imagetype() 函数在linux下的php中不存在
查看>>
Ruby的case语句
查看>>
Linux的链接文件-ln命令
查看>>
maven的tomcat插件如何进行debug调试
查看>>
table表头固定
查看>>
截取字符串中两个字符串中的字符串
查看>>
spring xml properties split with comma for list
查看>>
判断点是否在三角形内
查看>>
Android实战简易教程-第二十三枪(基于Baas的用户注冊验证username是否反复功能!)...
查看>>
在odl中怎样实现rpc
查看>>
leetcode 110 Balanced Binary Tree
查看>>
项目开发总结
查看>>
知行合一
查看>>
jmeter插件之jsonpath提取响应结果和做断言
查看>>
发布支持多线程的PowerShell模块 —— MultiThreadTaskRunner
查看>>
Ubuntu ctrl+alt会导致窗口还原的问题
查看>>
推荐系统那点事 —— 基于Spark MLlib的特征选择
查看>>
linux 下RTL8723/RTL8188调试记录(命令行)【转】
查看>>