多項式が出現するCrypto問題を解く
ここ最近整数環上で定義されている暗号を多項式環にまで拡張させている例を幾つか見たのでそこから2つ程例をとって紹介します。扱うのはInCTF 2020からPolyRSAとSECCON 2020 Online CTFよりkoharuです。
InCTF 2020 - PolyRSA §
この問題はRSAを多項式でもやってみた、という問題である。この問題では次のようなSageの対話環境の一部を与えられる。
sage: p
2470567871
sage: n
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
sage: m^65537
1208612545*x^254 + 1003144104*x^253 + 1173365710*x^252 + 1528252326*x^251 + 2263767409*x^250 + 2030579621*x^249 + 820048372*x^248 + 1474305505*x^247 + 1313951805*x^246 + 191260021*x^245 + 687901467*x^244 + 231907128*x^243 + 1757265648*x^242 + 1536859261*x^241 + 97792274*x^240 + 86150615*x^239 + 2283802022*x^238 + 728791370*x^237 + 1402241073*x^236 + 2010876897*x^235 + 1112960608*x^234 + 1785301939*x^233 + 862124720*x^232 + 573190801*x^231 + 1353395115*x^230 + 1041912948*x^229 + 1592516519*x^228 + 2043096090*x^227 + 970437868*x^226 + 945296597*x^225 + 764979415*x^224 + 151795004*x^223 + 744776063*x^222 + 49064457*x^221 + 379720326*x^220 + 549708067*x^219 + 1278937325*x^218 + 1348751857*x^217 + 897039278*x^216 + 1738651055*x^215 + 1458044806*x^214 + 947593966*x^213 + 604294495*x^212 + 1101712128*x^211 + 1106608879*x^210 + 556697284*x^209 + 339078898*x^208 + 135886774*x^207 + 682237064*x^206 + 1298394254*x^205 + 2038363686*x^204 + 1138996508*x^203 + 321551693*x^202 + 1194023535*x^201 + 1627100598*x^200 + 581786959*x^199 + 209400153*x^198 + 1354413890*x^197 + 1689568849*x^196 + 1038349567*x^195 + 2129265853*x^194 + 96150366*x^193 + 1879712323*x^192 + 140146576*x^191 + 855348682*x^190 + 571231503*x^189 + 1759489757*x^188 + 1528175919*x^187 + 1420729777*x^186 + 1778060705*x^185 + 204520875*x^184 + 2409946047*x^183 + 1703900286*x^182 + 379350638*x^181 + 145936788*x^180 + 644037909*x^179 + 946490870*x^178 + 2143460817*x^177 + 2124654819*x^176 + 735909283*x^175 + 1956333192*x^174 + 69508572*x^173 + 1998473705*x^172 + 2219097711*x^171 + 2324764950*x^170 + 1295835297*x^169 + 475763021*x^168 + 124896627*x^167 + 392652227*x^166 + 2414019050*x^165 + 519556546*x^164 + 2379934828*x^163 + 74942046*x^162 + 2333943359*x^161 + 5807728*x^160 + 1572302913*x^159 + 933057583*x^158 + 2327572070*x^157 + 2174172163*x^156 + 326654947*x^155 + 2362777406*x^154 + 1571381551*x^153 + 818720017*x^152 + 564409161*x^151 + 784212625*x^150 + 2084631116*x^149 + 1709163682*x^148 + 1791572159*x^147 + 2362306858*x^146 + 1870950847*x^145 + 936293454*x^144 + 1992907305*x^143 + 2427866610*x^142 + 1377299939*x^141 + 2336147340*x^140 + 419537038*x^139 + 1775945090*x^138 + 1084486367*x^137 + 1628708302*x^136 + 624109245*x^135 + 1140675451*x^134 + 848915999*x^133 + 1380203834*x^132 + 103496883*x^131 + 81739774*x^130 + 2055692293*x^129 + 1586687843*x^128 + 1682316161*x^127 + 134734383*x^126 + 885001299*x^125 + 2466212723*x^124 + 137905246*x^123 + 2305925724*x^122 + 410043787*x^121 + 2154453335*x^120 + 2018367068*x^119 + 1967315089*x^118 + 220606010*x^117 + 1066579186*x^116 + 2022385524*x^115 + 1564928688*x^114 + 851080667*x^113 + 1683812556*x^112 + 672848621*x^111 + 646553151*x^110 + 1348955204*x^109 + 1543570099*x^108 + 2260622184*x^107 + 1111757240*x^106 + 1797688791*x^105 + 1307761272*x^104 + 179896670*x^103 + 1197947306*x^102 + 1792231092*x^101 + 1515817157*x^100 + 1510541452*x^99 + 1784535666*x^98 + 1755403646*x^97 + 2388416288*x^96 + 1913808879*x^95 + 2139772089*x^94 + 1373043969*x^93 + 900021127*x^92 + 1613888837*x^91 + 331160696*x^90 + 2404083812*x^89 + 448818904*x^88 + 592910594*x^87 + 2436296390*x^86 + 2103089380*x^85 + 2027661376*x^84 + 277165788*x^83 + 717390488*x^82 + 319876555*x^81 + 1394843317*x^80 + 2314542109*x^79 + 2295617403*x^78 + 313842193*x^77 + 1918458371*x^76 + 1189324530*x^75 + 1765150225*x^74 + 1107038066*x^73 + 613811679*x^72 + 578744934*x^71 + 538203467*x^70 + 1710976133*x^69 + 1681208001*x^68 + 462043988*x^67 + 299437516*x^66 + 1843758398*x^65 + 851754779*x^64 + 1850189150*x^63 + 710529550*x^62 + 922473306*x^61 + 2344816934*x^60 + 54182289*x^59 + 2394694981*x^58 + 1849818608*x^57 + 1926799414*x^56 + 950266030*x^55 + 1290713338*x^54 + 1851455277*x^53 + 1607851092*x^52 + 1587576465*x^51 + 2279226257*x^50 + 1637387507*x^49 + 779327218*x^48 + 919124653*x^47 + 1126060258*x^46 + 2304179492*x^45 + 77984480*x^44 + 966167063*x^43 + 402292668*x^42 + 1332816563*x^41 + 524746316*x^40 + 2427530022*x^39 + 677075099*x^38 + 755256194*x^37 + 2152433299*x^36 + 2197374397*x^35 + 2290208129*x^34 + 996810109*x^33 + 101994796*x^32 + 252415814*x^31 + 1964967972*x^30 + 1533782356*x^29 + 1034980624*x^28 + 816216163*x^27 + 1535614986*x^26 + 1835762944*x^25 + 1147606118*x^24 + 1189426347*x^23 + 33594119*x^22 + 2113251273*x^21 + 826059142*x^20 + 1074101610*x^19 + 1638140405*x^18 + 1633380033*x^17 + 2005588694*x^16 + 2087514746*x^15 + 768034353*x^14 + 104476320*x^13 + 483234608*x^12 + 2424146196*x^11 + 49841203*x^10 + 145673059*x^9 + 705090263*x^8 + 1832451737*x^7 + 2394175351*x^6 + 1966712784*x^5 + 276537935*x^4 + 499607533*x^3 + 1981107449*x^2 + 776654074*x + 886398299
素数pと多項式n、未知の多項式mを65537乗した結果が与えられる。この状況と問題名から多項式環上でRSAっぽいことをしているとGuessしてググるとこの論文に辿り着く。以下、多項式環に関する用語が出てくるがこの論文にほぼ全て書いているのでそちらを参考にして頂き、この記事では深く踏み入らない。
Polynomial based RSA §
この論文によれば通常のRSA同様に$m^{ed} \equiv m \mod n$となる$e, d$の組み合わせが存在する。RSAと違うのは$\mathbb{F}_p[x]$上で演算が行われているということである。
では肝心の$e, d$の生成方法であるが次のようになる。
まず$P(x), Q(x) \in \mathbb{F}_p[x]$となる2つの既約多項式を用意する。その次数をそれぞれ$m, n$とおく。ちなみにこの2式の積が$n$である。
続いて$s = (p^m - 1)(p^n - 1)$を計算し、$s$未満で$s$と互いに素な整数$e$を用意する。この問題では65537となっている。
最後に$d \equiv e^{-1} \mod s$となる$d$を計算する。
これを見ると通常のRSAにおける$\phi(n)$に対応するのが$s$であることがわかる。なお、これがどうして成り立つかについては元論文を参考にしてほしい。
通常のRSA同様、秘密鍵がnの素元(ここでは2つの既約多項式)から求められるためnを2つの既約多項式の積に分解出来てしまえばこの問題は解けることになる。
Writeup §
というわけでnを分解するのを試みるのだが、これはSageMathを使うとある程度の次数なら一発である。この問題は255次なので文字通り瞬殺出来る。使用コードは次の通り。
p = 2470567871
P.<x> = PolynomialRing(Zmod(p))
n = 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
c = 1208612545*x^254 + 1003144104*x^253 + 1173365710*x^252 + 1528252326*x^251 + 2263767409*x^250 + 2030579621*x^249 + 820048372*x^248 + 1474305505*x^247 + 1313951805*x^246 + 191260021*x^245 + 687901467*x^244 + 231907128*x^243 + 1757265648*x^242 + 1536859261*x^241 + 97792274*x^240 + 86150615*x^239 + 2283802022*x^238 + 728791370*x^237 + 1402241073*x^236 + 2010876897*x^235 + 1112960608*x^234 + 1785301939*x^233 + 862124720*x^232 + 573190801*x^231 + 1353395115*x^230 + 1041912948*x^229 + 1592516519*x^228 + 2043096090*x^227 + 970437868*x^226 + 945296597*x^225 + 764979415*x^224 + 151795004*x^223 + 744776063*x^222 + 49064457*x^221 + 379720326*x^220 + 549708067*x^219 + 1278937325*x^218 + 1348751857*x^217 + 897039278*x^216 + 1738651055*x^215 + 1458044806*x^214 + 947593966*x^213 + 604294495*x^212 + 1101712128*x^211 + 1106608879*x^210 + 556697284*x^209 + 339078898*x^208 + 135886774*x^207 + 682237064*x^206 + 1298394254*x^205 + 2038363686*x^204 + 1138996508*x^203 + 321551693*x^202 + 1194023535*x^201 + 1627100598*x^200 + 581786959*x^199 + 209400153*x^198 + 1354413890*x^197 + 1689568849*x^196 + 1038349567*x^195 + 2129265853*x^194 + 96150366*x^193 + 1879712323*x^192 + 140146576*x^191 + 855348682*x^190 + 571231503*x^189 + 1759489757*x^188 + 1528175919*x^187 + 1420729777*x^186 + 1778060705*x^185 + 204520875*x^184 + 2409946047*x^183 + 1703900286*x^182 + 379350638*x^181 + 145936788*x^180 + 644037909*x^179 + 946490870*x^178 + 2143460817*x^177 + 2124654819*x^176 + 735909283*x^175 + 1956333192*x^174 + 69508572*x^173 + 1998473705*x^172 + 2219097711*x^171 + 2324764950*x^170 + 1295835297*x^169 + 475763021*x^168 + 124896627*x^167 + 392652227*x^166 + 2414019050*x^165 + 519556546*x^164 + 2379934828*x^163 + 74942046*x^162 + 2333943359*x^161 + 5807728*x^160 + 1572302913*x^159 + 933057583*x^158 + 2327572070*x^157 + 2174172163*x^156 + 326654947*x^155 + 2362777406*x^154 + 1571381551*x^153 + 818720017*x^152 + 564409161*x^151 + 784212625*x^150 + 2084631116*x^149 + 1709163682*x^148 + 1791572159*x^147 + 2362306858*x^146 + 1870950847*x^145 + 936293454*x^144 + 1992907305*x^143 + 2427866610*x^142 + 1377299939*x^141 + 2336147340*x^140 + 419537038*x^139 + 1775945090*x^138 + 1084486367*x^137 + 1628708302*x^136 + 624109245*x^135 + 1140675451*x^134 + 848915999*x^133 + 1380203834*x^132 + 103496883*x^131 + 81739774*x^130 + 2055692293*x^129 + 1586687843*x^128 + 1682316161*x^127 + 134734383*x^126 + 885001299*x^125 + 2466212723*x^124 + 137905246*x^123 + 2305925724*x^122 + 410043787*x^121 + 2154453335*x^120 + 2018367068*x^119 + 1967315089*x^118 + 220606010*x^117 + 1066579186*x^116 + 2022385524*x^115 + 1564928688*x^114 + 851080667*x^113 + 1683812556*x^112 + 672848621*x^111 + 646553151*x^110 + 1348955204*x^109 + 1543570099*x^108 + 2260622184*x^107 + 1111757240*x^106 + 1797688791*x^105 + 1307761272*x^104 + 179896670*x^103 + 1197947306*x^102 + 1792231092*x^101 + 1515817157*x^100 + 1510541452*x^99 + 1784535666*x^98 + 1755403646*x^97 + 2388416288*x^96 + 1913808879*x^95 + 2139772089*x^94 + 1373043969*x^93 + 900021127*x^92 + 1613888837*x^91 + 331160696*x^90 + 2404083812*x^89 + 448818904*x^88 + 592910594*x^87 + 2436296390*x^86 + 2103089380*x^85 + 2027661376*x^84 + 277165788*x^83 + 717390488*x^82 + 319876555*x^81 + 1394843317*x^80 + 2314542109*x^79 + 2295617403*x^78 + 313842193*x^77 + 1918458371*x^76 + 1189324530*x^75 + 1765150225*x^74 + 1107038066*x^73 + 613811679*x^72 + 578744934*x^71 + 538203467*x^70 + 1710976133*x^69 + 1681208001*x^68 + 462043988*x^67 + 299437516*x^66 + 1843758398*x^65 + 851754779*x^64 + 1850189150*x^63 + 710529550*x^62 + 922473306*x^61 + 2344816934*x^60 + 54182289*x^59 + 2394694981*x^58 + 1849818608*x^57 + 1926799414*x^56 + 950266030*x^55 + 1290713338*x^54 + 1851455277*x^53 + 1607851092*x^52 + 1587576465*x^51 + 2279226257*x^50 + 1637387507*x^49 + 779327218*x^48 + 919124653*x^47 + 1126060258*x^46 + 2304179492*x^45 + 77984480*x^44 + 966167063*x^43 + 402292668*x^42 + 1332816563*x^41 + 524746316*x^40 + 2427530022*x^39 + 677075099*x^38 + 755256194*x^37 + 2152433299*x^36 + 2197374397*x^35 + 2290208129*x^34 + 996810109*x^33 + 101994796*x^32 + 252415814*x^31 + 1964967972*x^30 + 1533782356*x^29 + 1034980624*x^28 + 816216163*x^27 + 1535614986*x^26 + 1835762944*x^25 + 1147606118*x^24 + 1189426347*x^23 + 33594119*x^22 + 2113251273*x^21 + 826059142*x^20 + 1074101610*x^19 + 1638140405*x^18 + 1633380033*x^17 + 2005588694*x^16 + 2087514746*x^15 + 768034353*x^14 + 104476320*x^13 + 483234608*x^12 + 2424146196*x^11 + 49841203*x^10 + 145673059*x^9 + 705090263*x^8 + 1832451737*x^7 + 2394175351*x^6 + 1966712784*x^5 + 276537935*x^4 + 499607533*x^3 + 1981107449*x^2 + 776654074*x + 886398299
e = 65537
q1, q2 = n.factor()
q1, q2 = q1[0], q2[0]
s = (p**q1.degree() - 1) * (p**q2.degree() - 1)
d = inverse_mod(e,s)
m = pow(c, d, n)
flag = "".join(map(chr, m.coefficients()))
print(flag)
フラグは求められた平文多項式の係数を文字に変換してから並べてinctf{and_i_4m_ir0n_m4n}になる。
別解 §
実はこの問題、nの既約多項式分解をしなくても解ける。というのもsが分解した多項式の"次数"とpにのみ依存し、この2つの次数の和はnの次数に一致するため、対称性を考慮すると2つの次数の組み合わせは高々127通りぐらいしか存在しない。よって、これを片っ端から試せば良い。
邪推ではあるが、どうせ2つの次数が近くて127, 128なんだろうとGuessして127から小さい方へと試すようにスクリプトを書いたら当たりだった(一応試しに1から試してみたけど予想通り現実的な時間で終わった)。
p = 2470567871
P.<x> = PolynomialRing(Zmod(p))
n = 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
ct = 1208612545*x^254 + 1003144104*x^253 + 1173365710*x^252 + 1528252326*x^251 + 2263767409*x^250 + 2030579621*x^249 + 820048372*x^248 + 1474305505*x^247 + 1313951805*x^246 + 191260021*x^245 + 687901467*x^244 + 231907128*x^243 + 1757265648*x^242 + 1536859261*x^241 + 97792274*x^240 + 86150615*x^239 + 2283802022*x^238 + 728791370*x^237 + 1402241073*x^236 + 2010876897*x^235 + 1112960608*x^234 + 1785301939*x^233 + 862124720*x^232 + 573190801*x^231 + 1353395115*x^230 + 1041912948*x^229 + 1592516519*x^228 + 2043096090*x^227 + 970437868*x^226 + 945296597*x^225 + 764979415*x^224 + 151795004*x^223 + 744776063*x^222 + 49064457*x^221 + 379720326*x^220 + 549708067*x^219 + 1278937325*x^218 + 1348751857*x^217 + 897039278*x^216 + 1738651055*x^215 + 1458044806*x^214 + 947593966*x^213 + 604294495*x^212 + 1101712128*x^211 + 1106608879*x^210 + 556697284*x^209 + 339078898*x^208 + 135886774*x^207 + 682237064*x^206 + 1298394254*x^205 + 2038363686*x^204 + 1138996508*x^203 + 321551693*x^202 + 1194023535*x^201 + 1627100598*x^200 + 581786959*x^199 + 209400153*x^198 + 1354413890*x^197 + 1689568849*x^196 + 1038349567*x^195 + 2129265853*x^194 + 96150366*x^193 + 1879712323*x^192 + 140146576*x^191 + 855348682*x^190 + 571231503*x^189 + 1759489757*x^188 + 1528175919*x^187 + 1420729777*x^186 + 1778060705*x^185 + 204520875*x^184 + 2409946047*x^183 + 1703900286*x^182 + 379350638*x^181 + 145936788*x^180 + 644037909*x^179 + 946490870*x^178 + 2143460817*x^177 + 2124654819*x^176 + 735909283*x^175 + 1956333192*x^174 + 69508572*x^173 + 1998473705*x^172 + 2219097711*x^171 + 2324764950*x^170 + 1295835297*x^169 + 475763021*x^168 + 124896627*x^167 + 392652227*x^166 + 2414019050*x^165 + 519556546*x^164 + 2379934828*x^163 + 74942046*x^162 + 2333943359*x^161 + 5807728*x^160 + 1572302913*x^159 + 933057583*x^158 + 2327572070*x^157 + 2174172163*x^156 + 326654947*x^155 + 2362777406*x^154 + 1571381551*x^153 + 818720017*x^152 + 564409161*x^151 + 784212625*x^150 + 2084631116*x^149 + 1709163682*x^148 + 1791572159*x^147 + 2362306858*x^146 + 1870950847*x^145 + 936293454*x^144 + 1992907305*x^143 + 2427866610*x^142 + 1377299939*x^141 + 2336147340*x^140 + 419537038*x^139 + 1775945090*x^138 + 1084486367*x^137 + 1628708302*x^136 + 624109245*x^135 + 1140675451*x^134 + 848915999*x^133 + 1380203834*x^132 + 103496883*x^131 + 81739774*x^130 + 2055692293*x^129 + 1586687843*x^128 + 1682316161*x^127 + 134734383*x^126 + 885001299*x^125 + 2466212723*x^124 + 137905246*x^123 + 2305925724*x^122 + 410043787*x^121 + 2154453335*x^120 + 2018367068*x^119 + 1967315089*x^118 + 220606010*x^117 + 1066579186*x^116 + 2022385524*x^115 + 1564928688*x^114 + 851080667*x^113 + 1683812556*x^112 + 672848621*x^111 + 646553151*x^110 + 1348955204*x^109 + 1543570099*x^108 + 2260622184*x^107 + 1111757240*x^106 + 1797688791*x^105 + 1307761272*x^104 + 179896670*x^103 + 1197947306*x^102 + 1792231092*x^101 + 1515817157*x^100 + 1510541452*x^99 + 1784535666*x^98 + 1755403646*x^97 + 2388416288*x^96 + 1913808879*x^95 + 2139772089*x^94 + 1373043969*x^93 + 900021127*x^92 + 1613888837*x^91 + 331160696*x^90 + 2404083812*x^89 + 448818904*x^88 + 592910594*x^87 + 2436296390*x^86 + 2103089380*x^85 + 2027661376*x^84 + 277165788*x^83 + 717390488*x^82 + 319876555*x^81 + 1394843317*x^80 + 2314542109*x^79 + 2295617403*x^78 + 313842193*x^77 + 1918458371*x^76 + 1189324530*x^75 + 1765150225*x^74 + 1107038066*x^73 + 613811679*x^72 + 578744934*x^71 + 538203467*x^70 + 1710976133*x^69 + 1681208001*x^68 + 462043988*x^67 + 299437516*x^66 + 1843758398*x^65 + 851754779*x^64 + 1850189150*x^63 + 710529550*x^62 + 922473306*x^61 + 2344816934*x^60 + 54182289*x^59 + 2394694981*x^58 + 1849818608*x^57 + 1926799414*x^56 + 950266030*x^55 + 1290713338*x^54 + 1851455277*x^53 + 1607851092*x^52 + 1587576465*x^51 + 2279226257*x^50 + 1637387507*x^49 + 779327218*x^48 + 919124653*x^47 + 1126060258*x^46 + 2304179492*x^45 + 77984480*x^44 + 966167063*x^43 + 402292668*x^42 + 1332816563*x^41 + 524746316*x^40 + 2427530022*x^39 + 677075099*x^38 + 755256194*x^37 + 2152433299*x^36 + 2197374397*x^35 + 2290208129*x^34 + 996810109*x^33 + 101994796*x^32 + 252415814*x^31 + 1964967972*x^30 + 1533782356*x^29 + 1034980624*x^28 + 816216163*x^27 + 1535614986*x^26 + 1835762944*x^25 + 1147606118*x^24 + 1189426347*x^23 + 33594119*x^22 + 2113251273*x^21 + 826059142*x^20 + 1074101610*x^19 + 1638140405*x^18 + 1633380033*x^17 + 2005588694*x^16 + 2087514746*x^15 + 768034353*x^14 + 104476320*x^13 + 483234608*x^12 + 2424146196*x^11 + 49841203*x^10 + 145673059*x^9 + 705090263*x^8 + 1832451737*x^7 + 2394175351*x^6 + 1966712784*x^5 + 276537935*x^4 + 499607533*x^3 + 1981107449*x^2 + 776654074*x + 886398299
e = 65537
# q1, q2 = n.factor()
# q1, q2 = q1[0], q2[0]
# print(q1.degree(), q2.degree())
for i in range(127, 1, -1):
j = 255 - i
# i, j = 127, 128 # for debug
print("[+] attempting:", i, j)
s = (p**i - 1) * (p**j - 1)
d = inverse_mod(e,s)
pt = pow(ct, d, n)
if all(map(lambda x: x < 256, pt.coefficients())):
flag = "".join(map(chr, pt.coefficients()))
print(flag)
break
SECCON 2020 Online CTF - koharu §
こちらはGoldwasser-Micali暗号を多項式でもやってみた、という問題である。この暗号方式の鍵生成, 暗号化, 復号について英語Wikipediaが非常に詳しいのでそこに全部説明を投げる。
ちなみに、この暗号方式は過去にInterKosenCTF - bitcryptoでも出題されており、koharuとbitcryptoの作者は同じである(作問者writeupより)。
与えられたスクリプトは次の通り。
while True:
p = random_prime(1<<64)
if is_prime((p+1) // 2):
break
with open("flag.txt", "rb") as f:
flag = f.read()
flag = int.from_bytes(flag, "big")
PR.<x> = PolynomialRing(GF(p))
while True:
P = PR.random_element(degree=64)
if P.is_irreducible():
break
while True:
Q = PR.random_element(degree=64)
if Q.is_irreducible():
break
NP = p**P.degree()
NQ = p**Q.degree()
while True:
R = PR.random_element(degree=64)
if power_mod(R, (NP-1)//2, P) != 1 and power_mod(R, (NQ-1)//2, Q) != 1:
break
PQ = P*Q
c = []
while flag:
S = PR.random_element(degree=64)
if flag & 1:
c.append((S * S) % PQ)
else:
c.append((S * S * R) % PQ)
flag = flag >> 1
print("p =", p)
print("PQ =", PQ)
print("R =", R)
print("c =", c)
これの出力結果も与えられるが、暗号文が平文のbit数個の多項式の配列であまりにも長いので割愛する。
Writeup §
通常のGoldwasser-Micaliは復号でnを素因数分解し、それらを法とする各暗号文の平方剰余から平文のビットを決定する。これも同様にPQの既約多項式分解結果で平方剰余を取れば平文を得られそうである。
既約多項式の平方剰余については特に知識は無いが、添付ソースコードからGuessしてそれを流用し次のようにした。
def is_quadratic_residue(n, P, p):
NP = p**P.degree()
return power_mod(n, (NP - 1) // 2, P) == 1
というわけで後は通常のGoldwasser-Micali同様の復号手順を経れば良い。各暗号文が求められた2つの既約多項式の平方剰余であれば、対応する平文ビットは1になり、そうでなければ対応する平文ビットは0になる。
使用コードは(与えられた暗号文とPQ, Rが長いのでそこは割愛すると)次のようになった。
from binascii import unhexlify
def long_to_bytes(n):
return unhexlify(hex(n)[2:])
p = 4832823609987476353
PR.<x> = PolynomialRing(GF(p))
PQ = 2475361839038406994*x^128 + 1816580044636445865*x^127 + 771106714052997910*x^126 + ...
R = 10529800129354981*x^64 + 4658846300069202283*x^63 + 1343603688498785880*x^62 + ...
c = [2027712907546344021*x^127 + 2302822347078959804*x^126 + 596638239593512636*x^125 + ...]
res = PQ.factor()
P, Q = res[0][0], res[1][0]
NP = p**P.degree()
NQ = p**Q.degree()
flag = ""
for i, c_bit in enumerate(c):
print("[+] attempting:", i)
res = pow(c_bit, (NP - 1) // 2, P) == 1 and pow(c_bit, (NQ - 1) // 2, Q) == 1
b = "1" if res else "0"
flag = b + flag
flag = int(flag, 2)
print(long_to_bytes(flag))
フラグはSECCON{p01y-p01y-p3r0-p3r0-hy0ukun-p3r0p3r0になった。
Thanks for reading! Read other posts?