HeartSky's blog


在渗透之路上渐行渐远


HCTF 2017 Crypto writeup

BabyRSA

先看下题目的逻辑

1
2
M = r * bytes_to_long('hctf{' + sha256(open('./flag').read()).hexdigest() + '}')
S = pow(M, d, n)

程序接收 r,然后同 flag 相乘后计算出它的数字签名
先说下本来的思路,flag 为 m,单纯 flag 的签名为 S,返回的签名为 S’,如果我们构造 r=R^e
因为

所以


e 的值未知,通过爆破 e 的值遍历提交 R^e,再根据上式得出 flag

但是题目忘记对 r 进行限制,导致也可以通过传入 r=2 来做出

因为 2m < n,所以直接对 S’^e 除以 2 就是 m

ps: Blue-Whale 队师傅的解法

然后对 m^2 开方就是 flag 了

WeakRSA

已知部分 d 的最低有效位,是可以还原出 d 的,原理部分。但对于已知的位数是有要求的

其中 M=2^k,k 是 d 的最低有效位的位数
出题时没测试好,本来是要给的位数不够还原,需要爆破的,给下脚本

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
#!/usr/bin/python
#-*- coding:utf-8 -*-

import sys, re
from libnum import nroot
from Crypto.Util.number import size

n = 24129492308224479830531863430667763206113500947912894148049103046436751018902380216549212087945014575866175372699327952352562583984599024982322742653474650254469019243745562427155195911292231061633627557914070970650388286259815766552728485153840458510677169495483383264554397982155108666923510839292748291941615629484247125025729363254239159271724680451974211566266307311323012908187153011368890695841034381925365547836453167672856111790684457634738536647974450864723943635507973978195453912898978987904396630176208142995219377309529324099766495068346782530074954504554550936100220114319876296005855618193837568032249
e = 65537

low_d2 = 585021050422437790400309277934736421671174903453118287773262727237276990096608684311252820485289582300237832073420122197911787329400438609843024619449229662477502424617432168933632994437196549098808097025413678738558952555239079729908003264517051128647960060385270607296895534639200191803399174999679917012421
low_bits = 1028
test = pow(3, e, n)

i = 0
prefix = []
for a in range(2):
for b in range(2):
prefix.append(str(a) + str(b))

for bf in prefix:
low_d = int(bin(low_d2)[2:], 2)
for k in xrange(1, e):
d = (k * n + 1) / e
d >>= low_bits
d <<= low_bits
d |= low_d
if (e * d) % k == 1:
if pow(test, d, n) == 3:
print k, d

总结

因为出题出的太晚了,导致没多少时间测试,出现了非预期,向各位师傅抱歉了 ==