# DaVinciCTF 2023 writeup

## Challenge description


## File content :

```
e = 65537
N = 717112095603796567459186675289085366666353307185490838112863469094236267064115095991318914077602556259092980640688481403957314611778356606590630923532172479459611664646123086735269849900884971954345014685854404613997971637479029358038777738612361656852669461942050483312357280227014477564862706358220265665684528484015675504406503642979068426662169208465726918109620002278730736582232507060863895239183614060352797915536803003766379326547455483805121183179622890875770347638754708633078401281869506937834987783549345444254985895168452303800618033133228421198570487293819512418570281720722209228656211732340633248821599038100558406541752556869957692270681816412540575428707774563875539462996182209726292786035178337626465674172053275188702251252357574867926706930607919671904054905671307852875045332721950531335900880364093157198125415400056706443026713461092993702796866382626321181134825237204434544098170777248711033815662904232551373912160599351955643630688486881346494419969742967490139650172842016964428670057727847565045461509019920640425372258450235773976492903639059374783281230558894906358850621988779071303812061651368357729631671532668073611308975396088608980146647649154262885567149667654346594998380255328428626713577833
message = 264534650266105599806294021070614230595616525906055753733761719275657774871470140716982224248591199930143393536112109666634675797148303913100693807661342308555939532608805045967956383107966177699787072449920253895221304428097068425393162931376216861878624593868623806403407463235780480244748078241725783430590495340799442724682566190632050547591341323688977303501641184951367816544042508488494475499053434594879307412981360853044625476334885351799592910757244150652389450722949077045473797563111265917765609352389143140723484112393593857707133580845664021986531624981054608271428875875563984105161439320613210497589395084708184226072788120184187653476835755855473119021530837541643055886076234084972648710196573106365229553050082479821148344623946637161759377216826589918124913366632162149006381730172591022803075404878808812491011198771709647073141166756215048339139472055570431392757757451548399461407884147879477545478028761274883498759069612591413321559799628662445755512999075034030583300601150472018816567707188341247953317752726136118637093294082860094619153110729803351873487926928582227569644123629745035652271651297427589546895153366652555770618092604114490238897158877913219257369176494787069733353644783317504411523314154
p = "11001101110001101010110000010000100000101010010111101000000101001100011101101101101111100100111100010111010110010110011101100110100001100001001011011010101010110111111001001000100000110100011011001111101101110001101010111101011111011111011111110111110001101100001101101101101011001111100000110100101110101111000001010001011011011101001001111010001101000011110010110101111011101011001001101111111010111100001111001001001001100011001111001000000000000001100100100010010101100111010101010000010100010001010100101111101110111011100111101000110001010110010111000000000101111001100000110100001101101101100010000001010100100001111001000010001111110110010000001011001111111111111100010011100001010011110100111111000110110011000000111111110010000100001111110001000000111011000000100010001001011000110011100110111111000011111100110111001110111011010100000110110100010010110101001100111010101111011000000010011000000011000001100101000001110011101111110011001000001001001011111011000010100000110000001001100110101101000000001110111111000011000001111000111010001010110000001101000011000110000110000101000111001000001111111101101111000100100101111001110100111001100001011110010011110110101100000010110001110110110010010100000111000100010101111110010011010001100110101110100001000111101110101000011110000111110100110111010001100000100111001100111100011001101010101100011110001011100100111000010110100111010111101011001101000110010000110110011011010111111011110101100000100111101011110001111011010001000011001100000101011100011100000001100110011011110101101111110101100101110100101011110001111100010110000111111011011101000000000101010000100101110100100011000101100011001011001100111101101000000111111110111110011100001000110011100010100010011111100011110101010001101111100001101100000011101101110100100000011110111000010100000110111010111101101011011010111111010100101110111110100110110101011000010010110110111100001000010110000110000100001100011110111110101101010011001111011001011101000111001000001011001111100010010111111001111011000110001000011100101001100011"

```

According to the description we know that's we are given public key (n,e) and the prime p which contain 2 errors.

It could be one of following cases :

* the author swaped 2 bits so we can use one loop
* 2 bits are written wrongly (0 insted of 1 and vice versa) => require two loops

I tried both of them and i realised we in are in the second case

So the idea here is to flip each possible couple of bits until we find the correct p value. And to check whether p is correct we have several solutions

* check that both p and q (n/p) are primes (i found many condidates so i moved to another solution)
* check that n - (n/p) * p = 0

**NB:** To divide n/p i transformed numbers to decimal and i raised precision to 2^16:

```

from decimal import Decimal, getcontext
getcontext().prec = 2**16

```

## My code :

```
bn = "11001101110001101010110000010000100000101010010111101000000101001100011101101101101111100100111100010111010110010110011101100110100001100001001011011010101010110111111001001000100000110100011011001111101101110001101010111101011111011111011111110111110001101100001101101101101011001111100000110100101110101111000001010001011011011101001001111010001101000011110010110101111011101011001001101111111010111100001111001001001001100011001111001000000000000001100100100010010101100111010101010000010100010001010100101111101110111011100111101000110001010110010111000000000101111001100000110100001101101101100010000001010100100001111001000010001111110110010000001011001111111111111100010011100001010011110100111111000110110011000000111111110010000100001111110001000000111011000000100010001001011000110011100110111111000011111100110111001110111011010100000110110100010010110101001100111010101111011000000010011000000011000001100101000001110011101111110011001000001001001011111011000010100000110000001001100110101101000000001110111111000011000001111000111010001010110000001101000011000110000110000101000111001000001111111101101111000100100101111001110100111001100001011110010011110110101100000010110001110110110010010100000111000100010101111110010011010001100110101110100001000111101110101000011110000111110100110111010001100000100111001100111100011001101010101100011110001011100100111000010110100111010111101011001101000110010000110110011011010111111011110101100000100111101011110001111011010001000011001100000101011100011100000001100110011011110101101111110101100101110100101011110001111100010110000111111011011101000000000101010000100101110100100011000101100011001011001100111101101000000111111110111110011100001000110011100010100010011111100011110101010001101111100001101100000011101101110100100000011110111000010100000110111010111101101011011010111111010100101110111110100110110101011000010010110110111100001000010110000110000100001100011110111110101101010011001111011001011101000111001000001011001111100010010111111001111011000110001000011100101001100011"

n = 717112095603796567459186675289085366666353307185490838112863469094236267064115095991318914077602556259092980640688481403957314611778356606590630923532172479459611664646123086735269849900884971954345014685854404613997971637479029358038777738612361656852669461942050483312357280227014477564862706358220265665684528484015675504406503642979068426662169208465726918109620002278730736582232507060863895239183614060352797915536803003766379326547455483805121183179622890875770347638754708633078401281869506937834987783549345444254985895168452303800618033133228421198570487293819512418570281720722209228656211732340633248821599038100558406541752556869957692270681816412540575428707774563875539462996182209726292786035178337626465674172053275188702251252357574867926706930607919671904054905671307852875045332721950531335900880364093157198125415400056706443026713461092993702796866382626321181134825237204434544098170777248711033815662904232551373912160599351955643630688486881346494419969742967490139650172842016964428670057727847565045461509019920640425372258450235773976492903639059374783281230558894906358850621988779071303812061651368357729631671532668073611308975396088608980146647649154262885567149667654346594998380255328428626713577833

e=65537

c=264534650266105599806294021070614230595616525906055753733761719275657774871470140716982224248591199930143393536112109666634675797148303913100693807661342308555939532608805045967956383107966177699787072449920253895221304428097068425393162931376216861878624593868623806403407463235780480244748078241725783430590495340799442724682566190632050547591341323688977303501641184951367816544042508488494475499053434594879307412981360853044625476334885351799592910757244150652389450722949077045473797563111265917765609352389143140723484112393593857707133580845664021986531624981054608271428875875563984105161439320613210497589395084708184226072788120184187653476835755855473119021530837541643055886076234084972648710196573106365229553050082479821148344623946637161759377216826589918124913366632162149006381730172591022803075404878808812491011198771709647073141166756215048339139472055570431392757757451548399461407884147879477545478028761274883498759069612591413321559799628662445755512999075034030583300601150472018816567707188341247953317752726136118637093294082860094619153110729803351873487926928582227569644123629745035652271651297427589546895153366652555770618092604114490238897158877913219257369176494787069733353644783317504411523314154
import gmpy
from Crypto.Util.number import isPrime
from decimal import Decimal, getcontext
getcontext().prec = 2**16

def flip(char):
if(char == '0'):
return '1'
else:
return '0'
q=0
is_break = False
for i in range(0,len(bn)):
f = bn
f2 = f[:i] + flip(f[i]) + f[i+1:]
for j in range(i+1,len(bn)):

f3 = f2[:j] + flip(f2[j]) + f2[j+1:]
try:
dn = Decimal(n)
p = int(f3,2)
dp = Decimal(p)
q= int(dn /dp)
if(n - p*q == 0):
print("q ==",q)
is_break = True
break
else:
continue
except Exception:
pass
if(is_break == True):
break

f = (p-1) * (q-1)
d = gmpy.invert(e,f)

plain = hex(pow(c,d,n))[2:]
print("plain =",plain)
print("clair =",bytes.fromhex(plain).decode())
```

## Result :

```
>> q == 27605844637206123282365368266418414490783159709786016035962764759078992540909426425405085663430202920502543886474583189795540626725052660622042231382059734513979163968742885314941389546369638383616783370156539696163142260612881872970764962829190710418319853457587970524661913509645654505724641474005151409502619326034959972325147682714200899207495143506390740638363467361368301365504608630260859776912592195031536476367664699673298357787807255866857471820031544288470873756667803333148752770390468046424569847612768834096179110732081807091215707606221508748438513288164953527598697891287426751502770811278403981975747
>> plain = 4c33306e3472645f4d313968745f42335f306c645f4275745f3574316c6c5f43756e6e316e39
>> clair = L30n4rd_M19ht_B3_0ld_But_5t1ll_Cunn1n9

```

After decoding our message from leet :

```
Leonard_Mi9ht_Be_old_But_still_Cunnin9
```

Original writeup (https://github.com/nass15456/CTFs/blob/main/DaVinciCTF/Desintegrated_RSA.md).