文档章节

RSA算法简介

terry_hding
 terry_hding
发布于 2016/06/25 09:47
字数 1308
阅读 48
收藏 5

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

对称密钥

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

非对称密钥

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

数学解释

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

m ^ e mod n = c
m为信息
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,k
d破解成功

可知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 = premaster
m ^ 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 algorithm

def rsa_algorithm_encrypted(message,public_key,keyE):
	encrypted_message = message ** keyE % public_key
	return encrypted_message

def rsa_algorithm_decrypted(private_key,public_key,encrypted_message):
	message = encrypted_message ** private_key % public_key
	return message

p = 53
q = 59
public_key = 53*59
aola = (53-1)*(59-1)
keyE = 3
private_key = (2*3016+1)/3
message = 89
encrypted_message = rsa_algorithm_encrypted(message,public_key,keyE)
print "encrypted_message is %d" %encrypted_message
decrypted_message = rsa_algorithm_decrypted(private_key,public_key,encrypted_message)
print "decrtypted_message is %d" %decrypted_messag
--------------------------------------------------------

 

© 著作权归作者所有

上一篇: openssl 证书实践
下一篇: HTTPS安全基础
terry_hding
粉丝 40
博文 133
码字总数 139264
作品 0
杨浦
QA/测试工程师
私信 提问
ssh密钥对验证

使用SSH密钥认证 一、加密简介 1、加密方式 对称密钥算法(DES,3DES,AES) 使用相同的密钥和算法来加解密。 缺点:共享密钥需双方互换,密钥太多,不支持数字签名和不可否认性。 优点:速度快...

人情世故
2016/05/26
142
0
Gaoliang.Zhou/secure-util

secure-util ##简介 Base64编码,消息摘要,对称(DES,3DES,AES,IDEA)/非对称(RSA,ELGamal)加解密,RSA/DSA数字签名,数字证书/密钥库工具类 ##版本信息 V1.2 ~ V1.4 扩展工具类方法和修复bug...

Gaoliang.Zhou
2016/07/13
0
0
SM2算法对比RSA算法,有哪些优势?

SM2算法和RSA算法都是公钥密码算法,SM2算法是一种更先进安全的算法,在安全性能、速度性能等方面都优于RSA算法,在我国商用密码体系中被用来替换RSA算法。国家密码管理局于2010年12月17日发...

wossl
06/17
209
0
Android外部文件加解密及应用实践

有这样的应用场景,当我们把一些重要文件放到asset文件夹中时,把.apk解压是可以直接拿到这个文件的,一些涉及到重要信息的文件我们并不想被反编译拿去,这个时候需要先对文件进行加密,然后...

C6C
2018/05/08
0
0
[区块链]Hyperledger Fabric源代码(基于v1.0 beta版本)阅读之乐扣老师解读系列 (六)BSSCP包之UTILS工具包

四,核心包之BSSCP(区块链加密服务提供者)包之UTIL工具包 包内容简介:本包主要是和BCCSP(区块链加密服务提供者)相关的各核心文件的接口文件,主要是提供一些密码学相关的操作实现的借口...

lsttoy
2017/06/19
0
0

没有更多内容

加载失败,请刷新页面

加载更多

VMware vSphere ESXi主机的访问控制

在vShpere中,访问ESXi主机的途径很多,如下: ESXi DCUI ESXi Shell ESXi SSH ESXi Host Client vCenter --> vSphere web client / vSphere Client VMware vSphere ESXi主机的访问控制,除了......

大别阿郎
18分钟前
2
0
大神讲解CGI、FastCGI和PHP-FPM关系图解

参考资料 概念了解:CGI,FastCGI,PHP-CGI与PHP-FPM:http://www.nowamagic.net/librarys/veda/detail/1319 php中fastcgi和php-fpm是什么东西:https://www.zybuluo.com/phper/note/50231 ......

网络小虾米
27分钟前
2
0
《DNS攻击防范科普系列3》 -如何保障 DNS 操作安全

引言 前两讲我们介绍了 DNS 相关的攻击类型,以及针对 DDoS 攻击的防范措施。这些都是更底层的知识,有同学就来问能否讲讲和我们的日常操作相关的知识点,今天我们就来说说和我们日常 DNS 操...

Mr_zebra
28分钟前
1
0
zk中ServerCnxn

实现接口Stats, Watcher 内部类 DisconnectReason CloseRequestException EndOfStreamException(流关闭) 属性 方法 getSessionTimeout 获取session失效时间 sendResponse 发送回复数据 se......

writeademo
33分钟前
3
0
如何将 Redis 用于微服务通信的事件存储

来源:Redislabs 作者:Martin Forstner 翻译:Kevin (公众号:中间件小哥) 以我的经验,将某些应用拆分成更小的、松耦合的、可协同工作的独立逻辑业务服务会更易于构建和维护。这些服务(也...

中间件小哥
36分钟前
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部