DaVinciCTF 2023-Desintegrated RSA(Crypto)

In this challenge, it’s given a file including (N,e), p, and a cipher message. It describes that we have a part of the private key p along with the public key values, but two bits of p are written incorrectly, which means we need to flip bits to find the two wrong bits.

p has a 2048-bit length, so all possible candidate bits for brute-force are 2048². But since we don’t need to do all the states, the space will be reduced to 2048 * 1024. We can flip bits using the XOR operand and achieve the correct p, then calculate q and d to decrypt the message.

from Crypto.Util.number import long_to_bytes

N = 717112095603796567459186675289085366666353307185490838112863469094236267064115095991318914077602556259092980640688481403957314611778356606590630923532172479459611664646123086735269849900884971954345014685854404613997971637479029358038777738612361656852669461942050483312357280227014477564862706358220265665684528484015675504406503642979068426662169208465726918109620002278730736582232507060863895239183614060352797915536803003766379326547455483805121183179622890875770347638754708633078401281869506937834987783549345444254985895168452303800618033133228421198570487293819512418570281720722209228656211732340633248821599038100558406541752556869957692270681816412540575428707774563875539462996182209726292786035178337626465674172053275188702251252357574867926706930607919671904054905671307852875045332721950531335900880364093157198125415400056706443026713461092993702796866382626321181134825237204434544098170777248711033815662904232551373912160599351955643630688486881346494419969742967490139650172842016964428670057727847565045461509019920640425372258450235773976492903639059374783281230558894906358850621988779071303812061651368357729631671532668073611308975396088608980146647649154262885567149667654346594998380255328428626713577833
p = "11001101110001101010110000010000100000101010010111101000000101001100011101101101101111100100111100010111010110010110011101100110100001100001001011011010101010110111111001001000100000110100011011001111101101110001101010111101011111011111011111110111110001101100001101101101101011001111100000110100101110101111000001010001011011011101001001111010001101000011110010110101111011101011001001101111111010111100001111001001001001100011001111001000000000000001100100100010010101100111010101010000010100010001010100101111101110111011100111101000110001010110010111000000000101111001100000110100001101101101100010000001010100100001111001000010001111110110010000001011001111111111111100010011100001010011110100111111000110110011000000111111110010000100001111110001000000111011000000100010001001011000110011100110111111000011111100110111001110111011010100000110110100010010110101001100111010101111011000000010011000000011000001100101000001110011101111110011001000001001001011111011000010100000110000001001100110101101000000001110111111000011000001111000111010001010110000001101000011000110000110000101000111001000001111111101101111000100100101111001110100111001100001011110010011110110101100000010110001110110110010010100000111000100010101111110010011010001100110101110100001000111101110101000011110000111110100110111010001100000100111001100111100011001101010101100011110001011100100111000010110100111010111101011001101000110010000110110011011010111111011110101100000100111101011110001111011010001000011001100000101011100011100000001100110011011110101101111110101100101110100101011110001111100010110000111111011011101000000000101010000100101110100100011000101100011001011001100111101101000000111111110111110011100001000110011100010100010011111100011110101010001101111100001101100000011101101110100100000011110111000010100000110111010111101101011011010111111010100101110111110100110110101011000010010110110111100001000010110000110000100001100011110111110101101010011001111011001011101000111001000001011001111100010010111111001111011000110001000011100101001100011"
message=264534650266105599806294021070614230595616525906055753733761719275657774871470140716982224248591199930143393536112109666634675797148303913100693807661342308555939532608805045967956383107966177699787072449920253895221304428097068425393162931376216861878624593868623806403407463235780480244748078241725783430590495340799442724682566190632050547591341323688977303501641184951367816544042508488494475499053434594879307412981360853044625476334885351799592910757244150652389450722949077045473797563111265917765609352389143140723484112393593857707133580845664021986531624981054608271428875875563984105161439320613210497589395084708184226072788120184187653476835755855473119021530837541643055886076234084972648710196573106365229553050082479821148344623946637161759377216826589918124913366632162149006381730172591022803075404878808812491011198771709647073141166756215048339139472055570431392757757451548399461407884147879477545478028761274883498759069612591413321559799628662445755512999075034030583300601150472018816567707188341247953317752726136118637093294082860094619153110729803351873487926928582227569644123629745035652271651297427589546895153366652555770618092604114490238897158877913219257369176494787069733353644783317504411523314154
e=65537
flag=False
for j in range(len(p)):
    p2=list(p)
    p2[j]=str(int(p[j])^int('1'))
    for i in range(j+1,len(p)):
        p3=list(p2)
        p3[i]=str(int(p[i])^int('1'))
        if N%int(''.join(p3),2)==0:
            modified_p=int(''.join(p3),2)
            flag=True
            break
    if flag==True:
        break
q=N//modified_p
phi=(modified_p-1)*(q-1)
d=pow(e,-1,phi)
print(long_to_bytes(pow(message,d,N)))

flag: dvCTF{L30n4rd_M19ht_B3_0ld_But_5t1ll_Cunn1n9}