DASCTF X GFCTF 2022十月挑战赛--Crypto

最后一步没搞出来，勉强就会这一道了（看了wp的情况下）。

RSA

from Crypto.Util.number import *
from secret import flag
 
def encrypt1(n):
    n1 = hex(n>>200).encode()
    n2 = str(hex(n))[20:].encode()
    return n1,n2
 
 
def encrypt2(m , n_1):
    c_1 = pow(m,e_1,n_1)
    print('c_1 = '+str(c_1))
 
 
def encrypt3(m , n_2):
    c_2 = pow( m , e_2 , n_2)
    print('c_2 = '+str(c_2))
 
 
def encrypt4(m):
    k = getPrime(512)
    m = m % k
    c_3 = pow(m, e_2, n_3)
    print('c_3 = ' + str(c_3))
    print('m = ' + str(m))
    print('k = ' + str(k))
 
 
m1,m2 = encrypt1(flag)
m1 = bytes_to_long(m1)
m2 = bytes_to_long(m2)
 
 
print('n_2 = ' + str(n_2))
print('n_3 = ' + str(n_3))
print('e_1 = ' + str(e_1))
print('e_2 = ' + str(e_2))
 
 
encrypt2(m1,n_1)
encrypt3(n_1,n_2)
encrypt4(m2)
 
'''
n_2 = 675835056744450121024004008337170937331109883435712066354955474563267257037603081555653829598886559337325172694278764741403348512872239277008719548968016702852609803016353158454788807563316656327979897318887566108985783153878668451688372252234938716250621575338314779485058267785731636967957494369458211599823364746908763588582489400785865427060804408606617016267936273888743392372620816053927031794575978032607311497491069242347165424963308662091557862342478844612402720375931726316909635118113432836702120449010
n_3 = 91294511667572917673898699346231897684542006136956966126836916292947639514392684487940336406038086150289315439796780158189004157494824987037667065310517044311794725172075653186677331434123198117797575528982908532086038107428540586044471407073066169603930082133459486076777574046803264038780927350142555712567
e_1 = 65537
e_2 = 3
c_1 = 47029848959680138397125259006172340325269302342762903311733700258745280761154948381409328053449580957972265859283407071931484707002138926840483316880087281153554181290481533
c_2 = 332431
c_3 = 11951299411967534922967467740790967733301092706094553308467975774492025797106594440070380723007894861454249455013202734019215071856834943490096156048504952328784989777263664832098681831398770963056616417301705739505187754236801407014715780468333977293887519001724078504320344074325196167699818117367329779609
m = 9530454742891231590945778054072843874837824815724564463369259282490619049557772650832818763768769359762168560563265763313176741847581931364
k = 8139616873420730499092246564709331937498029453340099806219977060224838957080870950877930756958455278369862703151353509623205172658012437573652818022676431
'''

分析：

encrypt1：

def encrypt1(n):
    n1 = hex(n>>200).encode()
    n2 = str(hex(n))[20:].encode()
    return n1,n2

n1：将flag右移200比特

n2：取flag第20位字节之后的部分

就是把flag截取成前一部分和后一部分。

encrypt2和encrypt3：

看起来逻辑一样，基础rsa加密

其中encrypt3里的e_2=3，故猜测是低指数解密攻击，直接爆破：

#encrypt3
e_2 = 3
c_2 = 332431
n_2 = 675835056744450121024004008337170937331109883435712066354955474563267257037603081555653829598886559337325172694278764741403348512872239277008719548968016702852609803016353158454788807563316656327979897318887566108985783153878668451688372252234938716250621575338314779485058267785731636967957494369458211599823364746908763588582489400785865427060804408606617016267936273888743392372620816053927031794575978032607311497491069242347165424963308662091557862342478844612402720375931726316909635118113432836702120449010
k = 0
while True:
    res = iroot(c_2+k*n_2,e_2)
    if res[1] == True:
        n_1 = res[0]
        break
    k += 1
print(n_1)
#n_1 = 70406706457855863712635967741447303613971473150228480705119773604469794649140239446237334040048504811343327173817296308781190911727763110615393368497803655390445303946160971

解出n_1，发现可以分解，有三个因数，那encrypt2也能解了

#encrypt2
e_1 = 65537
c_1 = 47029848959680138397125259006172340325269302342762903311733700258745280761154948381409328053449580957972265859283407071931484707002138926840483316880087281153554181290481533
p = 2224243981
q = 2732337821
r = 11585031296201346891716939633970482508158508580350404805965250133832632323150440185890235814142601827544669601048550999405490149435265122374459158586377571
phi_n = (p-1)*(q-1)*(r-1)
d = invert(e_1,phi_n)
m1 = pow(c_1,d,n_1)
#print(long_to_bytes(m1))
#b'0x666c61677b3230366538353964'

得到了flag的前一部分 

encrypt4：

def encrypt4(m):
    k = getPrime(512)
    m = m % k
    c_3 = pow(m, e_2, n_3)
    print('c_3 = ' + str(c_3))
    print('m = ' + str(m))
    print('k = ' + str(k))

对m进行随机数取余，再进行rsa基础加密

传的参数是m2，即flag的后一部分。

m = m2 % k ==> m = m2 + k2*k

c3 = m^e2 mod n3 ==> c3 = (m2 + k2*k)^e2 mod n3

于是在模n_3的域上构造，解得k2 = 0，即m2 = m

#Sage
e_2 = 3
n_3 = 91294511667572917673898699346231897684542006136956966126836916292947639514392684487940336406038086150289315439796780158189004157494824987037667065310517044311794725172075653186677331434123198117797575528982908532086038107428540586044471407073066169603930082133459486076777574046803264038780927350142555712567
c_3 = 11951299411967534922967467740790967733301092706094553308467975774492025797106594440070380723007894861454249455013202734019215071856834943490096156048504952328784989777263664832098681831398770963056616417301705739505187754236801407014715780468333977293887519001724078504320344074325196167699818117367329779609
m = 9530454742891231590945778054072843874837824815724564463369259282490619049557772650832818763768769359762168560563265763313176741847581931364
k = 8139616873420730499092246564709331937498029453340099806219977060224838957080870950877930756958455278369862703151353509623205172658012437573652818022676431
p. = PolynomialRing(Zmod(n_3))
f = (m+k2*k)^e_2 - c_3
f = f.monic()
k2 = f.small_roots()[0]
flag = int(m+k2*k)
print(flag)

 解出后一部分

至此

m1 =  0x666c61677b3230366538353964

m2 = 383539643865383534633466363030636231323735376262663966357d

发现有重合的部分，去除得到原始m：

m=0x666c61677b32303665383539643865383534633466363030636231323735376262663966357d

转字符串得到最终flag：

m = '666c61677b32303665383539643865383534633466363030636231323735376262663966357d'
flag = binascii.unhexlify(m.encode('utf-8'))

 总体代码如下：

from gmpy2 import *
from Crypto.Util.number import *
import binascii
 
#encrypt3
e_2 = 3
c_2 = 332431
n_2 = 675835056744450121024004008337170937331109883435712066354955474563267257037603081555653829598886559337325172694278764741403348512872239277008719548968016702852609803016353158454788807563316656327979897318887566108985783153878668451688372252234938716250621575338314779485058267785731636967957494369458211599823364746908763588582489400785865427060804408606617016267936273888743392372620816053927031794575978032607311497491069242347165424963308662091557862342478844612402720375931726316909635118113432836702120449010
k = 0
while True:
    res = iroot(c_2+k*n_2,e_2)
    if res[1] == True:
        n_1 = res[0]
        break
    k += 1
print(n_1)
#n_1 = 70406706457855863712635967741447303613971473150228480705119773604469794649140239446237334040048504811343327173817296308781190911727763110615393368497803655390445303946160971
 
#encrypt2
e_1 = 65537
c_1 = 47029848959680138397125259006172340325269302342762903311733700258745280761154948381409328053449580957972265859283407071931484707002138926840483316880087281153554181290481533
p = 2224243981
q = 2732337821
r = 11585031296201346891716939633970482508158508580350404805965250133832632323150440185890235814142601827544669601048550999405490149435265122374459158586377571
phi_n = (p-1)*(q-1)*(r-1)
d = invert(e_1,phi_n)
m1 = pow(c_1,d,n_1)
 
 
#encrypt4
'''
#Sage
e_2 = 3
n_3 = 91294511667572917673898699346231897684542006136956966126836916292947639514392684487940336406038086150289315439796780158189004157494824987037667065310517044311794725172075653186677331434123198117797575528982908532086038107428540586044471407073066169603930082133459486076777574046803264038780927350142555712567
c_3 = 11951299411967534922967467740790967733301092706094553308467975774492025797106594440070380723007894861454249455013202734019215071856834943490096156048504952328784989777263664832098681831398770963056616417301705739505187754236801407014715780468333977293887519001724078504320344074325196167699818117367329779609
m = 9530454742891231590945778054072843874837824815724564463369259282490619049557772650832818763768769359762168560563265763313176741847581931364
k = 8139616873420730499092246564709331937498029453340099806219977060224838957080870950877930756958455278369862703151353509623205172658012437573652818022676431
p. = PolynomialRing(Zmod(n_3))
f = (m+k2*k)^e_2 - c_3
f = f.monic()
k2 = f.small_roots()[0]
flag = int(m+k2*k)
print(flag)
'''
m1 = b'0x666c61677b3230366538353964'
m2 = b'383539643865383534633466363030636231323735376262663966357d'
#m2 = 9530454742891231590945778054072843874837824815724564463369259282490619049557772650832818763768769359762168560563265763313176741847581931364
#print(long_to_bytes(m2))
m = '666c61677b32303665383539643865383534633466363030636231323735376262663966357d'
flag = binascii.unhexlify(m.encode('utf-8'))
print(flag)