xXxYOLOxXx

xXxYOLOxXx

纵横杯 -- digits_missing

Posted on Edited on In

学！

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
from gmpy2 import *
from Crypto.Util.number import *
from random import getrandbits
import uuid
 
flag = 'flag{' + str(uuid.uuid4()) + '}'
flag = flag.encode().strip(b'flag{').strip(b'}').split(b'-')
padding = long_to_bytes(getrandbits(512))
 
m = bytes_to_long(flag[0] + padding + b''.join([_ for _ in flag[1:]]))
 
def leak(a, b, c):
    e1, e2 = a >> 32, a & 2 ** 32 - 1
    m1, m2 = b >> 256, b & 2 ** 256 - 1
    p, q = getPrime(512), getPrime(512)
    e = getPrime(32)
    n = p * q
    d = invert(e, (p - 1) * (q - 1))
    c1 = pow(b, e, n)
    c2 = pow((m1 + m2), (e1 + e2), n)
    c3 = pow(a, a, n)
    c4 = pow(c, 0x10001, n)
 
    return (p, q, d % (p-1), d % (q-1), c1, c2, c3, c4)
 
def enc(m):
    p = getPrime(512)
    q = getPrime(512)
    e = 5
    n = p * q
    c = pow(m, e, n)
    return (c, n)
 
l = leak(bytes_to_long(flag[0]), bytes_to_long(padding), bytes_to_long(flag[1] + flag[2]))
c, n = enc(m)
print(l)
print(n)
print(c)
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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
p = 8652390958861741435444627047576503554063739935043923776101303146382894597047179400211376204501335462644199685775560596374016398617315983998885273252232383
q = 11398271496284943396462023942239673376393494680988625153067750611899511451472208462647358820098737289431021205366418955146690406049973272066743297095335701
dp = 8227609008398873022400100032341316575069340356351334917468390748158625965488292971381161571649777894379178019250723450517822383161853535988801155974245829
dq = 617211540838331845453037224433458963099456992985736058430698238900631773989787292432368601561591831465287703203840756371539826467039309120629989472610731
n = 117748526248625603136351142766702204100236020660530366220791523773556022688543102946994917484678907692740314580746055286084348066502206905265752560353316613182375867778005737716910384438378102771898539357644605407585140993539708961209892736485222242671952840176226813623119643604701373240666050114195876590147
c = 11808273710504985443774404922628957257282747551484241545715693957153834727214995382868148041169819735282602593341730142167762213843046458242397247585755571045197205530638559439590698610690145211653032525642896154923181980344419031242307181446338164880957117881613097177678720633802107664174510977184795898949
c1 = 47136490736007026558241813301582050934441405175571329460613503012332065445341605765747908505286660131226561805265807633529290854688982152443879376327826248561833249864461425952747897175255546352471407983593816589373742238086560879516048675503364687914498582870324744857141831219402137460273880044886984405452
c2 = 56409941327407928550531590953236316964802997285515886345082618240072551829663483576336544664403443682438280485868042844696756568731554243773790500024504963753053241086872006291605136092928526547169334420024477141471212559780737725850766070778466019859345735742281733141983853509548060639633435609434590536531
c3 = 65058860021739531727088022149052143280404687999094594643616981645096271253997738526846930648540908395636973922952920134720525905860923697049859869913222811090573640409885098897352875692221136178538186740234898374169996494317972403060810936762924806513049343486713829518722226110983873658650785406820898700651
c4 = 32982466289233591258768165759927834475634992737248170434422994518702136286193176584067227438086450612500847996564720817106569494236142428184048889837042556370038553603123311299352611462708505050577773451291827498889210800170157619474074829930128950482157454573988753054631832302454833608646278214673705352226
 
import gmpy2
from Crypto.Util.number import *
 
#flag[1]+flag[2]，根据p,q,e来算出d
n1 = p * q
phi = (p - 1) * (q - 1)
d = gmpy2.invert(0x10001, phi)
flag12 = pow(c4, d, n1)
print("flag12 : {}".format(long_to_bytes(flag12)))
 
#padding，dp,dq求m
mp = Integer(pow(c1, dp, p))
mq = Integer(pow(c1, dq, q))
p_ = gmpy2.invert(p, q)
padding = ((((mq - mp) * p_) % q) * p + mp) % n1
print("padding : {}".format(padding))
 
#flag[0]，两种解法
m1m2 = (padding >> 256) + (padding & 2 ** 256 - 1)
charset = 'abcdef0123456789'
 
##中间相遇，将加密过程理解为((m ** e2) * (m ** e1)) % n1
mid = {}
for i in charset:
	for j in charset:
		for k in charset:
			for l in charset:
				e1 = bytes_to_long((i+j+k+l).encode())
				e1_ = gmpy2.invert(gmpy2.mpz(pow(m1m2, e1, n1)), n1)
				tmp = ((c2 * e1_) % n1)
				mid[tmp] = e1
for i in charset:
	for j in charset:
		for k in charset:
			for l in charset:
				e2 = bytes_to_long((i+j+k+l).encode())
				tmp = pow(m1m2, e2, n1)
				if tmp in mid:
					e1 = mid[tmp]
					a = (e1 << 32) + e2
					if pow(a, a, n1) == c3:
						flag0 = a
print("flag0 : {}".format(long_to_bytes(flag0)))
 
##BSGS(sage)，算出e1+e2再单独爆破e2即可得到e1
F = IntegerModRing(p*q)
mm = F(m1m2)
c2 = F(c2)
e12 = bsgs(mm, c2, (0, 2**32))
for i in charset:
	for j in charset:
		for k in charset:
			for l in charset:
				e2 = bytes_to_long((i+j+k+l).encode())
				e1 = (e12 - e2) << 32
				a = e1 + e2
				if pow(a,a,n1) == c3:
					flag0 = a
print("flag0 : {}".format(long_to_bytes(flag0)))
 
#flag，coppersmith m已知高位
m_high = bytes_to_long(b'9aa74d6f' + long_to_bytes(padding) + b'bb6b431b')
e = 5
F.<x> = PolynomialRing(Zmod(n))
f = (m_high * (2**128) + x) ** e - c
roots = f.small_roots(epsilon=1/25)[0]
m = long_to_bytes(m_high * (2**128) + roots)
print(b'flag{' + m[:8] + b'-' + m[-24:-20] + b'-' + m[-20:-16] + b'-' + m[-16:-12] + b'-' + m[-12:] + b'}')
######
kbits = 14 * 8
for i in charset:
	for j in charset:
		tmp = bytes_to_long(b'9aa74d6f' + long_to_bytes(padding) + b'bb6b431b' + i.encode() + j.encode())
		f = (tmp * (2**kbits) + x) ** e - c
		roots = f.small_roots(X=2**kbits, beta=1)
		if roots:
			x0 = roots[0]
			m = long_to_bytes(tmp * (2**kbits) + x0)
			print(b'flag{' + m[:8] + b'-' + m[-24:-20] + b'-' + m[-20:-16] + b'-' + m[-16:-12] + b'-' + m[-12:] + b'}')

最后coppersmith部分的求根代码还没有完全理解
第一种方法是直接设置参数epsilon就可以直接求解
第二种方法设置beta，但是需要再爆破两位明文