Tags: rsa 

Rating:

We have CipherText, N, replaced P.

So, What we have to do is to get phi(Euler's Function), d.

Following
```
print '0x'+p.replace('9F','FC')
```
, We have to find real P first.

I will use "N must be divided by p" to find the real P.

The value 'FC' is located at the index of [13,145,477,501].

So, Let me find the P with python

```python
from itertools import permutations

arr = [13,145,477,501]
case = []
for i in range(1,5):
for x in list(permutations(arr,i)):
case.append(x)

for x in case:
p = '0xDCC5A0BD3A1FC0BEB0DA1C2E8CF6B474481B7C12849B76E03C4C946724DB577D2825D6AA193DB559BC9DBABE1DDE8B5E7805E48749EF002F622F7CDBD7853B200E2A027E87E331AFCFD066ED9900F1E5F5E5196A451A6F9E329EB889D773F08E5FBF45AACB818FD186DD74626180294DCC31805A88D1B71DE5BFEF3ED01F12678D906A833A78EDCE9BDAF22BBE45C0BFB7A82AFE42C1C3B8581C83BF43DFE31BFD81527E507686956458905CC9A660604552A060109DC81D01F229A264AB67C6D7168721AB36DE769CEAFB97F238050193EC942078DDF5329A387F46253A4411A9C8BB71F9AEB11AC9623E41C14FCD2739D76E69283E57DDB11FC531B4611EE3'
p = list(p)
for e in x:
p[e] = '9'
p[e+1] = 'F'
tmp = ''.join(p)
p = int(tmp,16)
if N % p == 0:
print '[info] p = \n'+str(hex(p))
break
```

q = N / p

```python
q = N / p
print '[info] q = \n'+str(hex(q))
```

phi = (q - 1) * (p - 1) (Because they are prime number and Euler's phi is multiplicative function.

So, phi(N) = phi(qp) = phi(q) * phi(p) = (q - 1) * (p - 1))

e = 65537 (Because of below code)

```python
print pow(flag,65537,N)
```

So, Source Code will be

```python
phi = (p-1)*(q-1) #Euler's phi function
e = 65537
print '[info] phi = \n'+str(hex(phi))
print '[info] e = \n'+str(hex(e))
```

Now, It's time to get d

RSA uses "ed mod phi(n) = 1"

So, we can change like this

ed ≡ 1 (mod phi(n))

So, K * phi(n) + 1 = ed

this will make the operation fast.

```python
k = 1
while True:
if (k*phi+1)%e == 0:
d = (k*phi+1)/e
print '[info] d = \n'+str(hex(d))
break
k += 1
```

So, entire source code will be

```python
from itertools import permutations

enc_flag = 596380963583874022971492302071822444225514552231574984926542429117396590795270181084030717066220888052607057994262255729890598322976783889090993129161030148064314476199052180347747135088933481343974996843632511300255010825580875930722684714290535684951679115573751200980708359500292172387447570080875531002842462002727646367063816531958020271149645805755077133231395881833164790825731218786554806777097126212126561056170733032553159740167058242065879953688453169613384659653035659118823444582576657499974059388261153064772228570460351169216103620379299362366574826080703907036316546232196313193923841110510170689800892941998845140534954264505413254429240789223724066502818922164419890197058252325607667959185100118251170368909192832882776642565026481260424714348087206462283972676596101498123547647078981435969530082351104111747783346230914935599764345176602456069568419879060577771404946743580809330315332836749661503035076868102720709045692483171306425207758972682717326821412843569770615848397477633761506670219845039890098105484693890695897858251238713238301401843678654564558196040100908796513657968507381392735855990706254646471937809011610992016368630851454275478216664521360246605400986428230407975530880206404171034278692756
N = 719579745653303119025873098043848913976880838286635817351790189702008424828505522253331968992725441130409959387942238566082746772468987336980704680915524591881919460709921709513741059003955050088052599067720107149755856317364317707629467090624585752920523062378696431510814381603360130752588995217840721808871896469275562085215852034302374902524921137398710508865248881286824902780186249148613287250056380811479959269915786545911048030947364841177976623684660771594747297272818410589981294227084173316280447729440036251406684111603371364957690353449585185893322538541593242187738587675489180722498945337715511212885934126635221601469699184812336984707723198731876940991485904637481371763302337637617744175461566445514603405016576604569057507997291470369704260553992902776099599438704680775883984720946337235834374667842758010444010254965664863296455406931885650448386682827401907759661117637294838753325610213809162253020362015045242003388829769019579522792182295457962911430276020610658073659629786668639126004851910536565721128484604554703970965744790413684836096724064390486888113608024265771815004188203124405817878645103282802994701531113849607969243815078720289912255827700390198089699808626116357304202660642601149742427766381
arr = [13,145,477,501]
case = []
for i in range(1,5):
for x in list(permutations(arr,i)):
case.append(x)

for x in case:
p = '0xDCC5A0BD3A1FC0BEB0DA1C2E8CF6B474481B7C12849B76E03C4C946724DB577D2825D6AA193DB559BC9DBABE1DDE8B5E7805E48749EF002F622F7CDBD7853B200E2A027E87E331AFCFD066ED9900F1E5F5E5196A451A6F9E329EB889D773F08E5FBF45AACB818FD186DD74626180294DCC31805A88D1B71DE5BFEF3ED01F12678D906A833A78EDCE9BDAF22BBE45C0BFB7A82AFE42C1C3B8581C83BF43DFE31BFD81527E507686956458905CC9A660604552A060109DC81D01F229A264AB67C6D7168721AB36DE769CEAFB97F238050193EC942078DDF5329A387F46253A4411A9C8BB71F9AEB11AC9623E41C14FCD2739D76E69283E57DDB11FC531B4611EE3'
p = list(p)
for e in x:
p[e] = '9'
p[e+1] = 'F'
tmp = ''.join(p)
p = int(tmp,16)
if N % p == 0:
print '[info] p = \n'+str(hex(p))
break

q = N / p
print '[info] q = \n'+str(hex(q))
phi = (p-1)*(q-1) #Euler's phi function
e = 65537
print '[info] phi = \n'+str(hex(phi))
print '[info] e = \n'+str(hex(e))

k = 1
while True:
if (k*phi+1)%e == 0:
d = (k*phi+1)/e
print '[info] d = \n'+str(hex(d))
break
k += 1

p = pow(enc_flag,d,N)
p = str(hex(p))[2:-1]
print p.decode('hex')
```

flag: INSA{I_w1ll_us3_OTp_n3xT_T1M3}