Rating:
# Yet Another RSA Challenge Part 2 - 50 points - 61 solves
# RSA with partial prime information
We get an RSA modulus `N`, a ciphertext and a prime modified prime `p`. The modifications are given and are just a bunch of search-and-replace for 8 substrings of length 2.
We simply brute-force the inverse modifications until we find a number dividing `N`. This will be the original prime `p`. Here is the implementation in python:
```python
from sympy.ntheory import isprime
from Crypto.Util.number import inverse, long_to_bytes
from collections import OrderedDict
from itertools import combinations
def subsets(s):
for cardinality in range(len(s) + 1):
yield from combinations(s, cardinality)
N = 737611163443959284842367849241210504758770468900963447745605275812981372405732262639464389012528980016931096127343933425531508977427016967370838523007185109804122827435442876112926896405911684006913203175001902528962659926046227042479405858100518975905360430463250839310857983177028295643515725251012428553651998860175968606629769294473365526541620801873942073999635165942812779333418405669820767884314938500537161124341967101209379749620814652441184505316661790048734950052497097493871158994129217835162546653468074537465326514182322892918918625260996455179683746164361293138705790829022424332601363202790350347639455664656064705450037947152881312491133191289211419037325704774394630500271194735028396494665835379325963853042514832498826985928063545989015763434053963155703531024791434836954197474393368464043648904368880777954234469571406476568488608818611878807321749318425353873416639028342088117081977903731238631252547599612554002863288409286756260496090170930084625283076970661877432107608911551414435036116940780849204521422482251640736907024303127956310763272428319732230450480696798568635499915064255846815425268220147645177869463315347549456623125597500648525429960478399391403082954189840918045663557930850169068717203841
ciph = 238625175560117519818219655160700093672765696917859228632607011580941239729981338983916209022919475382357227963405365905148115318257038277146986081479123834942285774969894504633426906629030480787741565635778433780362722138925014818166488253621790448543359319453495165651188539177460365420486442547806453231416816633460519873660432319115179116336907802631692806970121302821171652412917375895244055318035607411137420274957028058695317500603598525629698305540801857314426359129633709966978334387372229490871242813925900864337395540528999023305226494361061535292380487362207573111785857146840743150168595521892054972163853976096692431697845761601194595494668734667899627964699784309805348028825617943571577132154874260866191233001610717099049253716197026401372924319018736900888351182876610669592251724095719123094054432644034621312701246109838942945597240248959486831491623970160080568107285964593924238967189856179059372322390416530545895764941716546818701469100406503650604889258155970317233013903059065959366407802296924017896297385415541256814333380793132923243754142847186952683218437937882137950119347398825971468218656558007008879510066175287320907270138115038609371999806062759974181729622851705386276830651522840256814183961092
p = "D78717E5C560636F461952384C67475479931C73E8573DE1658AD9828BA322DF497E2FC6042AE093EC7F194B47AF7E507CFF542F9085A0C526DC4B3B44D6FBEC4CA672FB2F75B56F151E5A103A1CBF6DB17611A6E6D1C054CE7A9D0A2170370E8AD349B98DFD984A6955B97AB7087AF81019C0F31456A6179DB47D2A240E307422D3F968193F8F239035640A357EBC4C3726DBF9935FF243AF8F0A4D458534381B38C3435AC0E61564BF79C7F808C38AB61F5DD2080EC2A2211AAFC17F8E89F99690278D494F1C8D1170C31442D1A8624EAE9938FB874962BBAE8915DA1943FC41B8D8CA675FE35FFD30B1CA5DF21E1BB0F9BC3C1F7CDC7E3E3E3AB834503D51"
switches = [('12','8D'),('33','D4'),('5E','FF'),('09','95'),('E4','38'),('6B','89'),('9E','E0'),('59','3E')]
switches = OrderedDict(reversed(switches))
possible = [p]
for sss in switches:
news = []
for x in possible:
fc = [i for i in range(len(x)) if x[i:i+2]==switches[sss]]
for sub in subsets(fc):
y = x
for i in sub:
y = y[:i]+sss+y[i+2:]
u = int(y,16)
if N%u==0:
p = u
q = N//p
d = inverse(65537,(p-1)*(q-1))
flag = long_to_bytes(pow(ciph,d,N))
print(flag)
if sss!='12':
news.append(y)
possible.extend(news)
```
which outputs the flag `INSA{Uh_never_give_4w4y_your_Pr1mes_I_m34n_duhhh}`.
