首页
论坛
课程
招聘
[原创]RSA数字签名?原来这么好理解!
2020-11-25 22:46 4034

[原创]RSA数字签名?原来这么好理解!

2020-11-25 22:46
4034

前言

​ 数字签名就是附加在数据单元上的一些数据。而这些数据可以用来确认数据单元的来源(即确认是谁发给你的数据),并且可保护数据单元的完整性(即确保不被其他人对所传数据进行伪造,篡改)。

 

​ 数字签名算法是依靠公钥加密技术实现的。在公钥体制内,每一个使用者都拥有一对儿公钥和私钥。公钥可以公开发布,而私钥是保存在自己手里。数字签名算法就是依靠用私钥签名,公钥验证签名的方式来保证信息传输的完整性、发送者的身份认证、防止交易中的抵赖行为发生。

 

​ 本文将通过讲解RSA数字签名的实现方式,向各位读者说明数字签名在现实生活中的重要性。

RSA数字签名详解

一个引人深思的小故事

​ 某天,Bob和Alice在网络上发生了以下对话。

 

​ Bob: Alice,在吗?我是Bob,我现在有急事,快借我5W,打到XXX账户里

 

​ Alice:好的,你稍等,我马上给你转过去,记得还我。

 

​ Bob:当然,没问题,我过几天会还你的。

 

​ 过几天后......

 

​ Alice:Bob,还记得几天前你问我借5W吗?我想,你该还钱了。

 

​ Bob:我没问你借过啊,那是黑客干的事。

 

​ 我们假设上述对话信息均是通过公钥加密的。那么在这里我们引出了一个很重要的问题,那就是发送信息方Bob在事后可以否认自己曾经发送过的报文。为什么他能够否认自己的行为,把锅甩给黑客呢,这就要引人另一个概念:中间人攻击。

 

 

​ 根据上图所示,公钥密码体制无法抵御中间人攻击,尽管没有出现中间人攻击,Bob想通过使用这套说辞来抵赖,是存在现实的合理性的。

RSA数字签名原理

 

上图的步骤我们可以用文字做如下表述:

1
2
3
4
5
6
7
1. 使用单向散列函数生成Message的消息摘要Digest1
 2. 将Digest使用发送者的私钥d签名得到Signature
 3. 将Message和Signature合并发送给接收者
 4. 接收者收到报文后将Message和Signature分离
 5. 使用单向散列函数生成Message的消息摘要Digest2
 6. Signature用公钥解密得到Digest1
 7. Digest1与Digest2进行比较,若一致,则合法。若不一致,则非法

RSA签名

​signature = h(m)<sup>d</sup> mod n

 

​ h是单项散列函数, m是message

RSA验证签名

h(m) == (signature)<sup>e</sup> mod n

2018 Backdoor Awesome mix1

接下来我们来做一道包含RSA数字签名知识点的CTF题来巩固自己刚才所学的知识

 

server.py如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#!/usr/bin/python3
 
from Crypto.PublicKey import RSA
from Crypto.Signature import PKCS1_v1_5 as RSAsign
from Crypto.Hash import SHA
#from Util import PKCS1_pad as pad
#from SECRET import flag
import sys
import binascii
 
def pad(data):
    asn1 = b'3021300906052b0e03021a05000414'
    ans = asn1 + data.encode('ascii')
    n = len(ans)
    return int((b'0001'+b"ff"*(1024//8-n//2-3)+b'00'+ans),16)
 
flag = b"CTF{cryp70_5ur3_15_w13rd}"
 
def verify(s,m,n,e):
    if pow(s,e,n) == pad(m):
        return True
    else:
        return False
 
key = RSA.generate(1024)
 
message = b"super important information for admin only"
 
h = SHA.new(message)
 
signer = RSAsign.new(key)
 
signature = signer.sign(h)
#print(signature)
s = int(binascii.hexlify(signature),16)
 
print ("Welcome to admin's music portal.")
print("To verify that you are the owner of this service")
print("send the public key which will verify the following signature :")
 
print ("Message:", message)
print ("Signature:", signature)
 
sys.stdout.flush()
 
n = eval(input("Enter n:"))
e = eval(input("Enter e:"))
sys.stdout.flush()
try:
    input_key = RSA.construct((n,e))
except ValueError:
    print('Value Error')
 
#print(h.hexdigest())
if verify(s,h.hexdigest(),n,e):
    print (flag)
else:
    print (b"Music is only for admin's eyes.")
 
sys.stdout.flush()

例题分析

​ 这道题我们需要输入n和e使得pow(s,e,n) == pad(m)相等才能获取flag。服务端向我们提供了Message,Signature和Pad函数的实现方式,为了更好的理清思路,我将通过一张示意图来说明。

 

例题破解思路

​ 我们的突破口其实就是在verify函数那里。其中p(m)已知,signature已知,只要寻找满足式子:(signature)<sup>e</sup> mod n = pad(m) 成立的e和n即可。我们令e=1,那么式子将变成(signature) mod n = pad(m),我们表示为余数形式可得:signature = kn + pad(m) =>signature - pad(m) = kn。我们令k=1,则n = signature - pad(m)。如此,我们就找到了满足上式成立的e,n值。

exp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
from pwn import *
from Crypto.Hash import SHA
import binascii
 
context.log_level = 'debug'
p = process('../home/awesome_mix1.py')
info = p.recv()
info_l = info.decode("ascii").split("\n")
message = info_l[3][9:]
signature = eval(info_l[4][11:])
 
def pad(data):
    asn1 = b'3021300906052b0e03021a05000414'
    ans = asn1 + data.encode('ascii')
    n = len(ans)
    return int((b'0001'+b"ff"*(1024//8-n//2-3)+b'00'+ans),16)
 
h = SHA.new(message.encode("ascii"))
m = h.hexdigest()
s = int(binascii.hexlify(signature),16)
e = 1
n = s - pad(m)
p.sendline(str(n).encode("ascii"))
p.sendline(b'1')
 
print(p.recvall())
 
p.close()

参考资料

https://blog.csdn.net/HD243608836/article/details/107823405

 

https://developer.aliyun.com/article/522293


第五届安全开发者峰会(SDC 2021)议题征集正式开启!

收藏
点赞1
打赏
分享
最新回复 (3)
雪    币: 10537
活跃值: 活跃值 (261)
能力值: (RANK:190 )
在线值:
发帖
回帖
粉丝
看场雪 活跃值 3 2020-12-23 12:07
2
1
写得容易懂,很适合入门者
建议:把私钥运算,不要叫‘加密’,而是改为‘签名’;把公钥运算,不要叫‘解密’,而是改成‘验签’

尽管在RSA中 ‘加密’与‘验签’同样使用公钥,‘解密’与‘签名’同样使用私钥,但其实他们在工业协议中的padding和密钥管理方式上有很大区别。
而且除了RSA以外,DSA和ECC都会把‘加密’与‘验签’严格区分开,把‘解密’与‘签名’严格区分开。所以为了不至带偏初学者,最好把它们都区分开。
雪    币: 51
活跃值: 活跃值 (105)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
金奔腾 活跃值 2020-12-23 13:48
3
0
学习了!
雪    币: 525
活跃值: 活跃值 (261)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
北海要多想 活跃值 2020-12-27 13:37
4
0
看场雪 写得容易懂,很适合入门者[em_63] 建议:把私钥运算,不要叫‘加密’,而是改为‘签名’;把公钥运算,不要叫‘解密’,而是改成‘验签’ 尽管在RSA中 ‘加密’与‘验签’同样使用公钥,‘解密 ...
感谢提出的建议!以后我会将自己的语言描述的更精确一点
游客
登录 | 注册 方可回帖
返回