crypto

really_suspicious_acronym

Description

加密代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def bytes_to_long(data):
return int(data.encode("hex"),16)

def rsa(msg,e,n):
return pow(bytes_to_long(msg),e,n)

flag = open('flag.txt','r').read()
tmp = randint(2**1023, 2**1024)
e = 65537
p = next_prime(57005*tmp+randint(2, 2**500))
q = next_prime(48879*tmp+randint(2, 2**500))
N = p*q
print('msg1 = '+str(rsa("You can't factor the modulus",e,N)))
print('msg2 = '+str(rsa("If you don't know the modulus!",e,N)))
print('flag = '+str(rsa(flag,e,N)))

输出文件信息

1
2
3
msg1 = 4249729541274832324831915101850978041491970958978013333892918723306168770472089196478720527554982764987079625218029445015042835412969986610407794962546486526768377464483162272541733624521350257458334912357961557141551376502679112069746250223130120067678503609054343306910481618502449487751467838568736395758064426403381068760701434585433915614901796040740316824283643177505677105619002929103619338876322183416750542848507631412106633630984867562243228659040403724671325236096319784525457674398019860558530212905126133378508676777200538275088387251038714220361173376355185449239483472545370043145325106307606431828449482078191
msg2 = 13075855845498384344820257559893309320125843093107442572680776872299102248743866420640323500087788163238819301260173322187978140866718036292385520509724506487692001245730298675731681509412177547061396861961413760298064385526657135656283464759479388590822600747903100354135682624356454872283852822117199641700847558605700370117557855396952083088645477966782338316017387406733063346986224014837246404581562813312855644424128648363175792786282857154624788625411070173092512834181678732914231669616670515512774709315620233482515821178277673737845032672993814500177126048019814877397547310166915188341668439101769932492677363463422
flag = 1325070956009103489249194637347510588506729608784127511926628895543304940415297099207601498626181915901848862854995077315475674257593360012633818395699000501896896712855638114932274873636706679536094148084825113213348693669110684534612150434985589138003619494080556587882502882245480530148296233019306164832959924719530089539412878605051284492900919153291539285764067215954480046474237129247005910958854570936626494664674014970792183182621261776942952172643573955950074108555363333808330455648256916095619261620286120748266415219259665310637340092503523139379869446053982200858497231506892485419429178671743186148288407233657
1
msg1=(string1)^{e}mod(n)
1
msg1-(string1)^{e}=k1*n
1
msg2=(string2)^{e}mod(n)
1
msg2-(string2)^{e}=k2*n

由此可以求出n

1
n=gcd((msg1-(string1)^{e}),(msg2-(string2)^{e}))
1
2
3
x = pow(m1,e)-c1
y = pow(m2,e)-c2
n = gmpy2.gcd(x, y)

然后就是分解p和q了,已知
$$
p = 57005*tmp+y1
$$

$$
q = 48879*tmp+y2
$$

tmp是一个1024bit的数,而y1,y2小于500bit
$$
p/q=57005/48879
$$

$$
pq=5700548879tmp^2+xtmp+y
$$

由于x,y远小于tmp

1
2
t = gmpy2.iroot(n/(57005*48879),2)
tmp = t[0]-2**482

至于为什么要减掉2^482,是为了让后面有解,所以2^500,2^499,2^498…一直到2^482,手动调出来的

然后已知tmp,就可以求x和y了

1
2
x = (n-57005*tmp*48879*tmp)/tmp 
y = n-57005*tmp*tmp*48879-x*tmp

再然后求p和q

1
2
3
4
5
y = 57005*48879*y
a = x*x-4*y
#print (gmpy2.iroot(a,2)[0]+x)/(2*48879)
p = 57005*tmp+1078399475444525965078564490579013145936057428039919829946148754465684831538693463366057742140506319392824923574770027498415725867779340864216973742259
q = 48879*tmp+(x-(gmpy2.iroot(a,2)[0]+x)/2) / 57005

最后就是正常的rsa解密了

完整代码如下

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
import gmpy2
import binascii

def bytes_to_long(data):
return int(data.encode("hex"),16)

e = 65537
c1 = 4249729541274832324831915101850978041491970958978013333892918723306168770472089196478720527554982764987079625218029445015042835412969986610407794962546486526768377464483162272541733624521350257458334912357961557141551376502679112069746250223130120067678503609054343306910481618502449487751467838568736395758064426403381068760701434585433915614901796040740316824283643177505677105619002929103619338876322183416750542848507631412106633630984867562243228659040403724671325236096319784525457674398019860558530212905126133378508676777200538275088387251038714220361173376355185449239483472545370043145325106307606431828449482078191
c2 = 13075855845498384344820257559893309320125843093107442572680776872299102248743866420640323500087788163238819301260173322187978140866718036292385520509724506487692001245730298675731681509412177547061396861961413760298064385526657135656283464759479388590822600747903100354135682624356454872283852822117199641700847558605700370117557855396952083088645477966782338316017387406733063346986224014837246404581562813312855644424128648363175792786282857154624788625411070173092512834181678732914231669616670515512774709315620233482515821178277673737845032672993814500177126048019814877397547310166915188341668439101769932492677363463422
c3 = 1325070956009103489249194637347510588506729608784127511926628895543304940415297099207601498626181915901848862854995077315475674257593360012633818395699000501896896712855638114932274873636706679536094148084825113213348693669110684534612150434985589138003619494080556587882502882245480530148296233019306164832959924719530089539412878605051284492900919153291539285764067215954480046474237129247005910958854570936626494664674014970792183182621261776942952172643573955950074108555363333808330455648256916095619261620286120748266415219259665310637340092503523139379869446053982200858497231506892485419429178671743186148288407233657

m1 = bytes_to_long("You can't factor the modulus")
m2 = bytes_to_long("If you don't know the modulus!")
'''
x = pow(m1,e)-c1
y = pow(m2,e)-c2

n = gmpy2.gcd(x, y)
print ('n = '+str(n))
'''
n = 34825223743402829383680359547814183240817664070909938698674658390374124787235739502688056639022131897715513587903467527066065545399622834534513631867145432553730850980331789931667370903396032758515681278057031496814054828419443822343986117760958186984521716807347123949922837482460532728350223473430713058522361175980521908817215812291272284241848086260180382693014713901303747444753828636575351349026883294939561001468099252543181336195746032718177937417431101756313823635150129601855358558635996348271242920308406268552606733676301725088348399264293936151662467456410825402303921583389167882090767423931762347825907802328053

t = gmpy2.iroot(n/(57005*48879),2)
tmp = t[0]-2**482
print "tmp 约为"+str(tmp)
print "检验:"+str(n/(tmp*tmp)-48879*57005)
x = (n-57005*tmp*48879*tmp)/tmp
y = n-57005*tmp*tmp*48879-x*tmp
#print('x='+str(x))
#print('y='+str(y))

y = 57005*48879*y
a = x*x-4*y
#print (gmpy2.iroot(a,2)[0]+x)/(2*48879)
p = 57005*tmp+1078399475444525965078564490579013145936057428039919829946148754465684831538693463366057742140506319392824923574770027498415725867779340864216973742259
q = 48879*tmp+(x-(gmpy2.iroot(a,2)[0]+x)/2) / 57005

d = gmpy2.invert(e,(p-1)*(q-1))
print "d为:"
print d
tm = pow(c3,d,n)
flag = binascii.unhexlify(hex(int(tm))[2:-1])
print "flag为:"
print(flag)

flag

1
p4{S3cur1ty_th0ru9h_0b5cur1ty_4t_i7s_fin3s7}