Tags: polynomial rsa 

Rating:

[Polynomial Rsa](http://www.diva-portal.se/smash/get/diva2:823505/FULLTEXT01.pdf). This article explains polynomial RSA quite good. I referred to this article and ended up with the following solution:

First of all, we need phi for n. For this, I factored n and calculated phi using the formula phi = Π(p^deg[i]-1) as mentioned in the article. This relevant code is:
```
n = factors[0][0].degree()
m = factors[1][0].degree()
phi = (pow(P, n)-1)*(pow(P, m)-1) #n has only two factors
```
Then d can be calculated using the basic rsa problem i.e.
```
d = inverse_mod(e, phi)
```
Then the problem reduced to a basic rsa problem. I set the quotient for the finite field as n and calculated (encrypted_polynomial)^(d) which turns out to be
```
125*a^23 + 110*a^22 + 52*a^21 + 109*a^20 + 95*a^19 + 110*a^18 + 48*a^17 + 114*a^16 + 105*a^15 + 95*a^14 + 109*a^13 + 52*a^12 + 95*a^11 + 105*a^10 + 95*a^9 + 100*a^8 + 110*a^7 + 97*a^6 + 123*a^5 + 102*a^4 + 116*a^3 + 99*a^2 + 110*a + 105
```
The coefficients clearly represent ascii values of the flag characters which can be decoded to the flag ```inctf{and_i_4m_ir0n_m4n}```

The whole solution is:
```
P = 2470567871
e = 65537
p = PolynomialRing(GF(P), 'x')
x = p.gen()
fx = 1932231392*x^255 + 1432733708*x^254 + 1270867914*x^253 + 1573324635*x^252 + 2378103997*x^251 + 820889786*x^250 + 762279735*x^249 + 1378353578*x^248 + 1226179520*x^247 + 657116276*x^246 + 1264717357*x^245 + 1015587392*x^244 + 849699356*x^243 + 1509168990*x^242 + 2407367106*x^241 + 873379233*x^240 + 2391647981*x^239 + 517715639*x^238 + 828941376*x^237 + 843708018*x^236 + 1526075137*x^235 + 1499291590*x^234 + 235611028*x^233 + 19615265*x^232 + 53338886*x^231 + 434434839*x^230 + 902171938*x^229 + 516444143*x^228 + 1984443642*x^227 + 966493372*x^226 + 1166227650*x^225 + 1824442929*x^224 + 930231465*x^223 + 1664522302*x^222 + 1067203343*x^221 + 28569139*x^220 + 2327926559*x^219 + 899788156*x^218 + 296985783*x^217 + 1144578716*x^216 + 340677494*x^215 + 254306901*x^214 + 766641243*x^213 + 1882320336*x^212 + 2139903463*x^211 + 1904225023*x^210 + 475412928*x^209 + 127723603*x^208 + 2015416361*x^207 + 1500078813*x^206 + 1845826007*x^205 + 797486240*x^204 + 85924125*x^203 + 1921772796*x^202 + 1322682658*x^201 + 2372929383*x^200 + 1323964787*x^199 + 1302258424*x^198 + 271875267*x^197 + 1297768962*x^196 + 2147341770*x^195 + 1665066191*x^194 + 2342921569*x^193 + 1450622685*x^192 + 1453466049*x^191 + 1105227173*x^190 + 2357717379*x^189 + 1044263540*x^188 + 697816284*x^187 + 647124526*x^186 + 1414769298*x^185 + 657373752*x^184 + 91863906*x^183 + 1095083181*x^182 + 658171402*x^181 + 75339882*x^180 + 2216678027*x^179 + 2208320155*x^178 + 1351845267*x^177 + 1740451894*x^176 + 1302531891*x^175 + 320751753*x^174 + 1303477598*x^173 + 783321123*x^172 + 1400145206*x^171 + 1379768234*x^170 + 1191445903*x^169 + 946530449*x^168 + 2008674144*x^167 + 2247371104*x^166 + 1267042416*x^165 + 1795774455*x^164 + 1976911493*x^163 + 167037165*x^162 + 1848717750*x^161 + 573072954*x^160 + 1126046031*x^159 + 376257986*x^158 + 1001726783*x^157 + 2250967824*x^156 + 2339380314*x^155 + 571922874*x^154 + 961000788*x^153 + 306686020*x^152 + 80717392*x^151 + 2454799241*x^150 + 1005427673*x^149 + 1032257735*x^148 + 593980163*x^147 + 1656568780*x^146 + 1865541316*x^145 + 2003844061*x^144 + 1265566902*x^143 + 573548790*x^142 + 494063408*x^141 + 1722266624*x^140 + 938551278*x^139 + 2284832499*x^138 + 597191613*x^137 + 476121126*x^136 + 1237943942*x^135 + 275861976*x^134 + 1603993606*x^133 + 1895285286*x^132 + 589034062*x^131 + 713986937*x^130 + 1206118526*x^129 + 311679750*x^128 + 1989860861*x^127 + 1551409650*x^126 + 2188452501*x^125 + 1175930901*x^124 + 1991529213*x^123 + 2019090583*x^122 + 215965300*x^121 + 532432639*x^120 + 1148806816*x^119 + 493362403*x^118 + 2166920790*x^117 + 185609624*x^116 + 184370704*x^115 + 2141702861*x^114 + 223551915*x^113 + 298497455*x^112 + 722376028*x^111 + 678813029*x^110 + 915121681*x^109 + 1107871854*x^108 + 1369194845*x^107 + 328165402*x^106 + 1792110161*x^105 + 798151427*x^104 + 954952187*x^103 + 471555401*x^102 + 68969853*x^101 + 453598910*x^100 + 2458706380*x^99 + 889221741*x^98 + 320515821*x^97 + 1549538476*x^96 + 909607400*x^95 + 499973742*x^94 + 552728308*x^93 + 1538610725*x^92 + 186272117*x^91 + 862153635*x^90 + 981463824*x^89 + 2400233482*x^88 + 1742475067*x^87 + 437801940*x^86 + 1504315277*x^85 + 1756497351*x^84 + 197089583*x^83 + 2082285292*x^82 + 109369793*x^81 + 2197572728*x^80 + 107235697*x^79 + 567322310*x^78 + 1755205142*x^77 + 1089091449*x^76 + 1993836978*x^75 + 2393709429*x^74 + 170647828*x^73 + 1205814501*x^72 + 2444570340*x^71 + 328372190*x^70 + 1929704306*x^69 + 717796715*x^68 + 1057597610*x^67 + 482243092*x^66 + 277530014*x^65 + 2393168828*x^64 + 12380707*x^63 + 1108646500*x^62 + 637721571*x^61 + 604983755*x^60 + 1142068056*x^59 + 1911643955*x^58 + 1713852330*x^57 + 1757273231*x^56 + 1778819295*x^55 + 957146826*x^54 + 900005615*x^53 + 521467961*x^52 + 1255707235*x^51 + 861871574*x^50 + 397953653*x^49 + 1259753202*x^48 + 471431762*x^47 + 1245956917*x^46 + 1688297180*x^45 + 1536178591*x^44 + 1833258462*x^43 + 1369087493*x^42 + 459426544*x^41 + 418389643*x^40 + 1800239647*x^39 + 2467433889*x^38 + 477713059*x^37 + 1898813986*x^36 + 2202042708*x^35 + 894088738*x^34 + 1204601190*x^33 + 1592921228*x^32 + 2234027582*x^31 + 1308900201*x^30 + 461430959*x^29 + 718926726*x^28 + 2081988029*x^27 + 1337342428*x^26 + 2039153142*x^25 + 1364177470*x^24 + 613659517*x^23 + 853968854*x^22 + 1013582418*x^21 + 1167857934*x^20 + 2014147362*x^19 + 1083466865*x^18 + 1091690302*x^17 + 302196939*x^16 + 1946675573*x^15 + 2450124113*x^14 + 1199066291*x^13 + 401889502*x^12 + 712045611*x^11 + 1850096904*x^10 + 1808400208*x^9 + 1567687877*x^8 + 2013445952*x^7 + 2435360770*x^6 + 2414019676*x^5 + 2277377050*x^4 + 2148341337*x^3 + 1073721716*x^2 + 1045363399*x + 1809685811
factors = fx.factor()
n = factors[0][0].degree()
m = factors[1][0].degree()
phi = (pow(P, n)-1)*(pow(P, m)-1)
d = inverse_mod(e, phi)
u = p.quotient(fx, 'a')
a = u.gen()
cx = 1208612545*a^254 + 1003144104*a^253 + 1173365710*a^252 + 1528252326*a^251 + 2263767409*a^250 + 2030579621*a^249 + 820048372*a^248 + 1474305505*a^247 + 1313951805*a^246 + 191260021*a^245 + 687901467*a^244 + 231907128*a^243 + 1757265648*a^242 + 1536859261*a^241 + 97792274*a^240 + 86150615*a^239 + 2283802022*a^238 + 728791370*a^237 + 1402241073*a^236 + 2010876897*a^235 + 1112960608*a^234 + 1785301939*a^233 + 862124720*a^232 + 573190801*a^231 + 1353395115*a^230 + 1041912948*a^229 + 1592516519*a^228 + 2043096090*a^227 + 970437868*a^226 + 945296597*a^225 + 764979415*a^224 + 151795004*a^223 + 744776063*a^222 + 49064457*a^221 + 379720326*a^220 + 549708067*a^219 + 1278937325*a^218 + 1348751857*a^217 + 897039278*a^216 + 1738651055*a^215 + 1458044806*a^214 + 947593966*a^213 + 604294495*a^212 + 1101712128*a^211 + 1106608879*a^210 + 556697284*a^209 + 339078898*a^208 + 135886774*a^207 + 682237064*a^206 + 1298394254*a^205 + 2038363686*a^204 + 1138996508*a^203 + 321551693*a^202 + 1194023535*a^201 + 1627100598*a^200 + 581786959*a^199 + 209400153*a^198 + 1354413890*a^197 + 1689568849*a^196 + 1038349567*a^195 + 2129265853*a^194 + 96150366*a^193 + 1879712323*a^192 + 140146576*a^191 + 855348682*a^190 + 571231503*a^189 + 1759489757*a^188 + 1528175919*a^187 + 1420729777*a^186 + 1778060705*a^185 + 204520875*a^184 + 2409946047*a^183 + 1703900286*a^182 + 379350638*a^181 + 145936788*a^180 + 644037909*a^179 + 946490870*a^178 + 2143460817*a^177 + 2124654819*a^176 + 735909283*a^175 + 1956333192*a^174 + 69508572*a^173 + 1998473705*a^172 + 2219097711*a^171 + 2324764950*a^170 + 1295835297*a^169 + 475763021*a^168 + 124896627*a^167 + 392652227*a^166 + 2414019050*a^165 + 519556546*a^164 + 2379934828*a^163 + 74942046*a^162 + 2333943359*a^161 + 5807728*a^160 + 1572302913*a^159 + 933057583*a^158 + 2327572070*a^157 + 2174172163*a^156 + 326654947*a^155 + 2362777406*a^154 + 1571381551*a^153 + 818720017*a^152 + 564409161*a^151 + 784212625*a^150 + 2084631116*a^149 + 1709163682*a^148 + 1791572159*a^147 + 2362306858*a^146 + 1870950847*a^145 + 936293454*a^144 + 1992907305*a^143 + 2427866610*a^142 + 1377299939*a^141 + 2336147340*a^140 + 419537038*a^139 + 1775945090*a^138 + 1084486367*a^137 + 1628708302*a^136 + 624109245*a^135 + 1140675451*a^134 + 848915999*a^133 + 1380203834*a^132 + 103496883*a^131 + 81739774*a^130 + 2055692293*a^129 + 1586687843*a^128 + 1682316161*a^127 + 134734383*a^126 + 885001299*a^125 + 2466212723*a^124 + 137905246*a^123 + 2305925724*a^122 + 410043787*a^121 + 2154453335*a^120 + 2018367068*a^119 + 1967315089*a^118 + 220606010*a^117 + 1066579186*a^116 + 2022385524*a^115 + 1564928688*a^114 + 851080667*a^113 + 1683812556*a^112 + 672848621*a^111 + 646553151*a^110 + 1348955204*a^109 + 1543570099*a^108 + 2260622184*a^107 + 1111757240*a^106 + 1797688791*a^105 + 1307761272*a^104 + 179896670*a^103 + 1197947306*a^102 + 1792231092*a^101 + 1515817157*a^100 + 1510541452*a^99 + 1784535666*a^98 + 1755403646*a^97 + 2388416288*a^96 + 1913808879*a^95 + 2139772089*a^94 + 1373043969*a^93 + 900021127*a^92 + 1613888837*a^91 + 331160696*a^90 + 2404083812*a^89 + 448818904*a^88 + 592910594*a^87 + 2436296390*a^86 + 2103089380*a^85 + 2027661376*a^84 + 277165788*a^83 + 717390488*a^82 + 319876555*a^81 + 1394843317*a^80 + 2314542109*a^79 + 2295617403*a^78 + 313842193*a^77 + 1918458371*a^76 + 1189324530*a^75 + 1765150225*a^74 + 1107038066*a^73 + 613811679*a^72 + 578744934*a^71 + 538203467*a^70 + 1710976133*a^69 + 1681208001*a^68 + 462043988*a^67 + 299437516*a^66 + 1843758398*a^65 + 851754779*a^64 + 1850189150*a^63 + 710529550*a^62 + 922473306*a^61 + 2344816934*a^60 + 54182289*a^59 + 2394694981*a^58 + 1849818608*a^57 + 1926799414*a^56 + 950266030*a^55 + 1290713338*a^54 + 1851455277*a^53 + 1607851092*a^52 + 1587576465*a^51 + 2279226257*a^50 + 1637387507*a^49 + 779327218*a^48 + 919124653*a^47 + 1126060258*a^46 + 2304179492*a^45 + 77984480*a^44 + 966167063*a^43 + 402292668*a^42 + 1332816563*a^41 + 524746316*a^40 + 2427530022*a^39 + 677075099*a^38 + 755256194*a^37 + 2152433299*a^36 + 2197374397*a^35 + 2290208129*a^34 + 996810109*a^33 + 101994796*a^32 + 252415814*a^31 + 1964967972*a^30 + 1533782356*a^29 + 1034980624*a^28 + 816216163*a^27 + 1535614986*a^26 + 1835762944*a^25 + 1147606118*a^24 + 1189426347*a^23 + 33594119*a^22 + 2113251273*a^21 + 826059142*a^20 + 1074101610*a^19 + 1638140405*a^18 + 1633380033*a^17 + 2005588694*a^16 + 2087514746*a^15 + 768034353*a^14 + 104476320*a^13 + 483234608*a^12 + 2424146196*a^11 + 49841203*a^10 + 145673059*a^9 + 705090263*a^8 + 1832451737*a^7 + 2394175351*a^6 + 1966712784*a^5 + 276537935*a^4 + 499607533*a^3 + 1981107449*a^2 + 776654074*a + 886398299
m = str(cx^d)
print(m)
flag = ''
m=m.split(' + ')
for i in m:
x=i.split('*')[0]
flag += chr(int(x))

print(flag[::-1])
```