⬅ BACK
InCTF 2020 Writeups

DLPoly (Crypto)

RSA is easy. DLP is hard.

out.txt:

sage: p
35201
sage: len(flag)
14
sage: X = int.from_bytes(  flag.strip(b'inctf{').strip(b'}') ,  'big')
sage: n
n = 1629*x^256 + 25086*x^255 + 32366*x^254 + 21665*x^253 + 24571*x^252 + 20588*x^251 + 17474*x^250 + 30654*x^249 + 31322*x^248 + 23385*x^247 + 14049*x^246 + 27853*x^245 + 18189*x^244 + 33130*x^243 + 29218*x^242 + 3412*x^241 + 28875*x^240 + 1550*x^239 + 15231*x^238 + 32794*x^237 + 8541*x^236 + 23025*x^235 + 21145*x^234 + 11858*x^233 + 34388*x^232 + 21092*x^231 + 22355*x^230 + 1768*x^229 + 5868*x^228 + 1502*x^227 + 30644*x^226 + 24646*x^225 + 32356*x^224 + 27350*x^223 + 34810*x^222 + 27676*x^221 + 24351*x^220 + 9218*x^219 + 27072*x^218 + 21176*x^217 + 2139*x^216 + 8244*x^215 + 1887*x^214 + 3854*x^213 + 24362*x^212 + 10981*x^211 + 14237*x^210 + 28663*x^209 + 32272*x^208 + 29911*x^207 + 13575*x^206 + 15955*x^205 + 5367*x^204 + 34844*x^203 + 15036*x^202 + 7662*x^201 + 16816*x^200 + 1051*x^199 + 16540*x^198 + 17738*x^197 + 10212*x^196 + 4180*x^195 + 33126*x^194 + 13014*x^193 + 16584*x^192 + 10139*x^191 + 27520*x^190 + 116*x^189 + 28199*x^188 + 31755*x^187 + 10917*x^186 + 28271*x^185 + 1152*x^184 + 6118*x^183 + 27171*x^182 + 14265*x^181 + 905*x^180 + 13776*x^179 + 854*x^178 + 5397*x^177 + 14898*x^176 + 1388*x^175 + 14058*x^174 + 6871*x^173 + 13508*x^172 + 3102*x^171 + 20438*x^170 + 29122*x^169 + 17072*x^168 + 23021*x^167 + 29879*x^166 + 28424*x^165 + 8616*x^164 + 21771*x^163 + 31878*x^162 + 33793*x^161 + 9238*x^160 + 23751*x^159 + 24157*x^158 + 17665*x^157 + 34015*x^156 + 9925*x^155 + 2981*x^154 + 24715*x^153 + 13223*x^152 + 1492*x^151 + 7548*x^150 + 13335*x^149 + 24773*x^148 + 15147*x^147 + 25234*x^146 + 24394*x^145 + 27742*x^144 + 29033*x^143 + 10247*x^142 + 22010*x^141 + 18634*x^140 + 27877*x^139 + 27754*x^138 + 13972*x^137 + 31376*x^136 + 17211*x^135 + 21233*x^134 + 5378*x^133 + 27022*x^132 + 5107*x^131 + 15833*x^130 + 27650*x^129 + 26776*x^128 + 7420*x^127 + 20235*x^126 + 2767*x^125 + 2708*x^124 + 31540*x^123 + 16736*x^122 + 30955*x^121 + 14959*x^120 + 13171*x^119 + 5450*x^118 + 20204*x^117 + 18833*x^116 + 33989*x^115 + 25970*x^114 + 767*x^113 + 16400*x^112 + 34931*x^111 + 7923*x^110 + 33965*x^109 + 12199*x^108 + 11788*x^107 + 19343*x^106 + 33039*x^105 + 13476*x^104 + 15822*x^103 + 20921*x^102 + 25100*x^101 + 9771*x^100 + 5272*x^99 + 34002*x^98 + 16026*x^97 + 23104*x^96 + 33331*x^95 + 11944*x^94 + 5428*x^93 + 11838*x^92 + 30854*x^91 + 18595*x^90 + 5226*x^89 + 23614*x^88 + 5611*x^87 + 34572*x^86 + 17035*x^85 + 16199*x^84 + 26755*x^83 + 10270*x^82 + 25206*x^81 + 30800*x^80 + 21714*x^79 + 2088*x^78 + 3785*x^77 + 9626*x^76 + 25706*x^75 + 24807*x^74 + 31605*x^73 + 5292*x^72 + 17836*x^71 + 32529*x^70 + 33088*x^69 + 16369*x^68 + 18195*x^67 + 22227*x^66 + 8839*x^65 + 27975*x^64 + 10464*x^63 + 29788*x^62 + 15770*x^61 + 31095*x^60 + 276*x^59 + 25968*x^58 + 14891*x^57 + 23490*x^56 + 34563*x^55 + 29778*x^54 + 26719*x^53 + 28613*x^52 + 1633*x^51 + 28335*x^50 + 18278*x^49 + 33901*x^48 + 13451*x^47 + 30759*x^46 + 19192*x^45 + 31002*x^44 + 11733*x^43 + 29274*x^42 + 11756*x^41 + 6880*x^40 + 11492*x^39 + 7151*x^38 + 28624*x^37 + 29566*x^36 + 33986*x^35 + 5726*x^34 + 5040*x^33 + 14730*x^32 + 7443*x^31 + 12168*x^30 + 24201*x^29 + 20390*x^28 + 15087*x^27 + 18193*x^26 + 19798*x^25 + 32514*x^24 + 25252*x^23 + 15090*x^22 + 2653*x^21 + 29310*x^20 + 4037*x^19 + 6440*x^18 + 16789*x^17 + 1891*x^16 + 20592*x^15 + 11890*x^14 + 25769*x^13 + 29259*x^12 + 23814*x^11 + 17565*x^10 + 16797*x^9 + 34151*x^8 + 20893*x^7 + 2807*x^6 + 209*x^5 + 3217*x^4 + 8801*x^3 + 21964*x^2 + 16286*x + 12050
sage: g
x
sage: g^X
c = 10254*x^255 + 11436*x^254 + 9453*x^253 + 31783*x^252 + 22103*x^251 + 10097*x^250 + 28892*x^249 + 18508*x^248 + 22160*x^247 + 26375*x^246 + 3876*x^245 + 19858*x^244 + 30728*x^243 + 7847*x^242 + 16954*x^241 + 3306*x^240 + 13208*x^239 + 25886*x^238 + 33685*x^237 + 6481*x^236 + 12387*x^235 + 16989*x^234 + 32301*x^233 + 3069*x^232 + 1062*x^231 + 30500*x^230 + 7726*x^229 + 5137*x^228 + 10962*x^227 + 10406*x^226 + 22108*x^225 + 21887*x^224 + 739*x^223 + 27363*x^222 + 5715*x^221 + 8176*x^220 + 32398*x^219 + 33238*x^218 + 28151*x^217 + 18812*x^216 + 24615*x^215 + 8245*x^214 + 9730*x^213 + 8071*x^212 + 5590*x^211 + 21532*x^210 + 5962*x^209 + 17369*x^208 + 25626*x^207 + 14284*x^206 + 32492*x^205 + 3944*x^204 + 5227*x^203 + 30264*x^202 + 17098*x^201 + 28516*x^200 + 19180*x^199 + 31133*x^198 + 6217*x^197 + 29652*x^196 + 23061*x^195 + 22336*x^194 + 7848*x^193 + 15686*x^192 + 14763*x^191 + 27394*x^190 + 26349*x^189 + 3586*x^188 + 13954*x^187 + 12979*x^186 + 1909*x^185 + 506*x^184 + 18147*x^183 + 12126*x^182 + 8258*x^181 + 32944*x^180 + 11947*x^179 + 1354*x^178 + 33656*x^177 + 12395*x^176 + 14442*x^175 + 8301*x^174 + 4409*x^173 + 28252*x^172 + 29872*x^171 + 14252*x^170 + 2279*x^169 + 6317*x^168 + 31734*x^167 + 19036*x^166 + 520*x^165 + 34967*x^164 + 15096*x^163 + 20173*x^162 + 18962*x^161 + 28622*x^160 + 9961*x^159 + 18600*x^158 + 4794*x^157 + 33233*x^156 + 23874*x^155 + 26462*x^154 + 17088*x^153 + 11202*x^152 + 11392*x^151 + 16258*x^150 + 19460*x^149 + 17784*x^148 + 28458*x^147 + 817*x^146 + 25362*x^145 + 35096*x^144 + 3283*x^143 + 6551*x^142 + 30282*x^141 + 1134*x^140 + 29704*x^139 + 12388*x^138 + 20847*x^137 + 23240*x^136 + 25554*x^135 + 19687*x^134 + 22021*x^133 + 33659*x^132 + 19105*x^131 + 15422*x^130 + 32550*x^129 + 20712*x^128 + 11862*x^127 + 31185*x^126 + 9245*x^125 + 20218*x^124 + 18357*x^123 + 12809*x^122 + 20336*x^121 + 5247*x^120 + 6737*x^119 + 15970*x^118 + 14986*x^117 + 13437*x^116 + 8582*x^115 + 35005*x^114 + 14125*x^113 + 1110*x^112 + 11888*x^111 + 28756*x^110 + 11610*x^109 + 10241*x^108 + 13301*x^107 + 10052*x^106 + 3501*x^105 + 33176*x^104 + 12987*x^103 + 27504*x^102 + 21903*x^101 + 16653*x^100 + 12466*x^99 + 33281*x^98 + 360*x^97 + 26611*x^96 + 8066*x^95 + 1528*x^94 + 34974*x^93 + 16606*x^92 + 6724*x^91 + 18933*x^90 + 6703*x^89 + 6011*x^88 + 12647*x^87 + 32169*x^86 + 27545*x^85 + 18417*x^84 + 31199*x^83 + 17400*x^82 + 23798*x^81 + 16555*x^80 + 23009*x^79 + 1904*x^78 + 4962*x^77 + 1390*x^76 + 8141*x^75 + 25010*x^74 + 33199*x^73 + 19059*x^72 + 23473*x^71 + 14324*x^70 + 30136*x^69 + 15298*x^68 + 29677*x^67 + 33907*x^66 + 2250*x^65 + 34933*x^64 + 11261*x^63 + 22789*x^62 + 3652*x^61 + 15401*x^60 + 8978*x^59 + 32965*x^58 + 2505*x^57 + 17018*x^56 + 33296*x^55 + 27680*x^54 + 6679*x^53 + 24625*x^52 + 28932*x^51 + 789*x^50 + 10745*x^49 + 15681*x^48 + 14757*x^47 + 8233*x^46 + 15427*x^45 + 10112*x^44 + 30124*x^43 + 3701*x^42 + 31048*x^41 + 29692*x^40 + 2865*x^39 + 9066*x^38 + 20493*x^37 + 25607*x^36 + 115*x^35 + 9724*x^34 + 20716*x^33 + 19260*x^32 + 19536*x^31 + 6311*x^30 + 4672*x^29 + 27315*x^28 + 12186*x^27 + 17786*x^26 + 7341*x^25 + 4276*x^24 + 9217*x^23 + 6637*x^22 + 18711*x^21 + 19348*x^20 + 14022*x^19 + 30518*x^18 + 10550*x^17 + 19146*x^16 + 2430*x^15 + 25237*x^14 + 34375*x^13 + 2497*x^12 + 35085*x^11 + 8261*x^10 + 3388*x^9 + 26236*x^8 + 14902*x^7 + 14487*x^6 + 24280*x^5 + 11078*x^4 + 7380*x^3 + 24669*x^2 + 549*x + 1468

Solution

We are given x^{flag} mod n where n is a polynomial in F35201[x]\mathbb{F}_{35201}[x]. The task is to solve the DLP in the quotient ring of polynomials in F35201[x]\mathbb{F}_{35201}[x] by the ideal nn consisting of multiples of the polynomial nn. This is denoted as F35201[x]/n\mathbb{F}_{35201}[x]/\langle n\rangle. Let's call this quotient ring QQ. Sage has built in discrete log functions that are totally generic, but polynomial rings don't have an .order() method so we have to compute it ourselves. The order of a ring (or group) is the number of elements in it. Note that we are interested in the multiplication operation, so the elements we consider in the set are only those with multiplicative inverse elements (i.e. elements that are coprime with the modulus).

Theorem: Let R=Fp[x]/N(x)R = \mathbb{F}_p[x]/\langle N(x) \rangle for prime pp and N(x)=P1(x)P2(x)Pr(x)N(x) = P_1(x)P_2(x)\cdots P_r(x) where Pi(x)P_i(x) are irreducible polynomials in Fp[x]\mathbb{F}_p[x]. Then, the order of RR is i=1r(pdeg(Pi)1)\prod_{i = 1}^r ( p^{\deg(P_i)} - 1 ).

Proof: We start by computing the total number of polynomials in RR. That is, the number of polynomials with coefficients in Fp\mathbb{F}_p whose degree is less than deg(N)\deg(N). These polynomials can be written as

i=0deg(N)1kixi\sum_{i=0}^{\deg(N)-1} k_i x^i

There are deg(N)\deg(N) coefficients, and each coefficient can take up to pp values, so there are pdeg(N)p^{\deg(N)} possible polynomials.

Next, we exclude the polynomials that are not invertible. These are polynomials that share a factor with N(x)N(x), that is, multiples of Pi(x)P_i(x). We use the inclusion-exclusion principle to obtain an expression for the number of polynomials that are not coprime to N(x)N(x). Let AiA_i be the subset of polynomials in RR that are multiples of PiP_i. Then

i=1rAi=i=1rAi1i<jrAiAj+1i<j<krAiAjAk+(1)rA1Ar\left | \bigcup_{i=1}^r A_i \right | = \sum_{i=1}^r | A_i | - \sum_{1 \leq i < j \leq r} | A_i \cap A_j | + \sum_{1 \leq i < j < k \leq r} | A_i \cap A_j \cap A_k | - \cdots + (-1)^{r} | A_1 \cap \cdots \cap A_r |

Consider AiA_i. The polynomials in AiA_i have the form Q(x)Pi(x)Q(x)P_i(x) where Q(x)Q(x) is of degree deg(N)deg(Pi)\deg(N) - \deg(P_i). Therefore Ai=pdeg(N)deg(Pi)|A_i| = p^{\deg(N) - \deg(P_i)}.

Next, consider AiAjA_i \cap A_j where i<ji < j. The polynomials in AiAjA_i \cap A_j have the form Q(x)Pi(x)Pj(x)Q(x)P_i(x)P_j(x) where Q(x)Q(x) is of degree deg(N)deg(Pi)deg(Pj)\deg(N) - \deg(P_i) - \deg(P_j). Therefore AiAj=pdeg(N)deg(Pi)deg(Pj)|A_i \cap A_j| = p^{\deg(N) - \deg(P_i) - \deg(P_j)}.

In general, Ai1Aik=pdeg(N)deg(Pi1)deg(Pik)| A_{i_1} \cap \cdots \cap A_{i_k} | = p^{\deg(N) - \deg(P_{i_1}) - \cdots - \deg(P_{i_k})} for 1i1<<ikr1 \leq i_1 < \cdots < i_k \leq r.

So

#R=pdeg(N)1i=1rAi=pdeg(P1)++degPr1pdeg(P2)++deg(Pr)pdeg(P1)+deg(P3)++deg(Pr)+pdeg(P3)++deg(Pr)+pdeg(P2)+deg(P4)++deg(Pr)++(1)r=(pdeg(P1)1)(pdeg(P2)1)(pdeg(Pr)1)=i=1r(pdeg(Pi)1)\begin{aligned} \#R &= p^{\deg(N) - 1} - \left | \bigcup_{i=1}^r A_i \right | \\ &= p^{\deg(P_1) + \cdots + \deg{P_r} - 1} - p^{\deg(P_2) + \cdots + \deg(P_r)} - p^{\deg(P_1) + \deg(P_3) + \cdots + \deg(P_r)} - \cdots \\ &\hspace{0.3in} + p^{\deg(P_3) + \cdots + \deg(P_r)} + p^{\deg(P_2) + \deg(P_4) + \cdots + \deg(P_r)} + \cdots + (-1)^{r} \\ &= (p^{\deg(P_1)} - 1)(p^{\deg(P_2)} - 1) \cdots (p^{\deg(P_r)} - 1) \\ &= \prod_{i=1}^r (p^{\deg(P_i)} - 1) \end{aligned}

Solving the challenge

Since n(x)n(x) is square free, we can compute the order of QQ using the above theorem. Doing so gives us the following extremely large integer:

828095283078365821035906712584313613267259374081020419504932352155659177459160341091828947167865033167221905108312125495452745499324882907347920414906104292582906330915099958576679626146770228352240585630930139661045176562591142477774139672383036818326923547793197940683916579620016589545313412510178382062940020658088409985109520664200101047441395894492801337264842708432166493291241118107917027085612583904881045016599048631676023448658571574675694109595884112047534414651568829566811446147026894559715306435293623664371754538446523791290736118660976615503028557578911645115805550332275939674586196923036628855241080783528653557249828462947924249198381038178461485336950387183600669876163630183894738670160739263190797639665069711057118752501596719589043439771930596882669052368132928844025392834319313873873036523980321058917024339536530832567697942263196837532182794282926503255463388996348655925894641051753889126844537253605132148449110651332484156106043375966561712868991682036168081784393896390881977942489907297854619599492425911383384237229610389703619707077306718091171227238400000000000000000000000000000000000000000000000000000000000000000000000000000

Fortunately, the order has many small factors:

2^208 * 3^27 * 5^77 * 7^2 * 11^26 * 13 * 31^25 * 41^25 * 241 * 271 * 1291^25 * 5867^26 * 6781^25 * 18973 * 648391 * 62904731^25 * 595306331^25 * 1131568001^25

so we will be able to solve the DLP using Pohlig-Hellman.

Since the exponent is at most 2562^{56}, we only need to take factors such that their product is greater than 2562^{56}. Practically, this can be a bit smaller as we know the secret encodes ascii values which are no where near 255. Taking the factors [13, 241, 271, 18973, 648391] gives a product of about 2^54 which should be good enough. Since these numbers are very small, solving DLP in subgroups of their order is very easy and could even be done using a pure bruteforce algorithm. The solution script simply implements a simplified version of Pohlig-Hellman.

Solve script:

p = 35201
n = ...
c = ...

P.<x> = PolynomialRing(GF(p))
n = P(n)
g = x
Q.<x> = P.quotient(n)
h = Q(c)
order = prod(p^(d.degree()) - 1 for d,_ in n.factor())
print('[+] order:', order)
print('[*] factors:', order.factor())
factors = [13,241,271,18973,648391]
K = []
for f in factors:
    qi = order//f
    Pi = x^qi
    Qi = h^qi
    K.append(discrete_log(Qi, Pi, ord=f))
print(K)
flag = crt(K, factors)
print(bytes.fromhex(hex(flag)[2:]))

Flag: inctf{bingo!}


References: http://www.diva-portal.se/smash/get/diva2:823505/FULLTEXT01.pdf