この大会は2021/12/11 14:00(JST)～2021/12/12 14:00(JST)に開催されました。
今回もチームで参戦。結果は1426点で506チーム中24位でした。
自分で解けた問題をWriteupとして書いておきます。
welcome (welcome)
Discordに入り、announcementチャネルのメッセージを見ると、フラグがあった。
SECCON{https://www.google.cat/search?q=1M%20JPY%20to%20USD}
pppp (crypto)
暗号処理の概要は以下の通り。
・p, q: 512bit素数 ・n = p * q ・mid: flagの長さの半分 ・m1: flag前半の数値 ・m2: flag後半の数値 ・m = [[p,p,p,p], [0,m1,m1,m1], [0,0,m2,m2],[0,0,0,1]] ・mの各要素ごとにgetPrime(768)の数値を掛け算する。 ・mを剰余環(p*q)の行列にする。 ・c = m ^ e ・n, e, c, pow(p, e, n)を表示
行列を2乗してみる。
p*A p*B p*C p*D p*A p*B p*C p*D (p*A)**2 (A*B)*p**2+(B*E)*m1*p (A*C)*p**2+(B*F)*m1*p+(C*H)*m2*p ? 0 m1*E m1*F m1*G 0 m1*E m1*F m1*G 0 (m1*E)**2 (E*F)*m1**2+(F*H)*m1*m2 ? 0 0 m2*H m2*I * 0 0 m2*H m2*I = 0 0 (m2*H)**2 m2**2*H*I+m2*J 0 0 0 1*J 0 0 0 1*J 0 0 0 J**2
0行目は必ずpの倍数なので、nで割った余りもpの倍数。最大公約数をとればpになる。次にm1*Eと、m2*Hを算出する。算出した2つの値を素因数分解する。
$ python -m primefac 1654473583289225542637898223202890105229793155648049154615591729969285906185035489335891816982587768857940621086111446948472898558020413418239764400706309051511896603873998731251376123070734938584083464450577263707381779777754030251104042834091839092436678933359962636001191186 1654473583289225542637898223202890105229793155648049154615591729969285906185035489335891816982587768857940621086111446948472898558020413418239764400706309051511896603873998731251376123070734938584083464450577263707381779777754030251104042834091839092436678933359962636001191186: 2 11 11 101 17733194681 21989360161 194838390862027996463 890941089701337639742923670629764992383197102649368033477055542426171609788212371754143394788213291456300216361551640449365841636339404366563906765128981689755176699342918904671528454362377482743831820969956624190146702130809843851
>>> E = 890941089701337639742923670629764992383197102649368033477055542426171609788212371754143394788213291456300216361551640449365841636339404366563906765128981689755176699342918904671528454362377482743831820969956624190146702130809843851 >>> E.bit_length() 768
>yafu-x64.exe "factor(2264896707546818670727285002520672181772642716242094795010232862539139579838750852742562416508752358715457554620245688072468162086358327123749825805613136390834328006135334709867747538765173162979741225754536350480853234652374489385146248704800006410822837702485074096032356475)" -v -threads 4 12/11/21 19:06:49 v1.34.5 @ XXXX-XXXX, System/Build Info: Using GMP-ECM 6.3, Powered by GMP 5.1.1 detected Intel(R) Core(TM) i7-10700 CPU @ 2.90GHz detected L1 = 32768 bytes, L2 = 16777216 bytes, CL = 64 bytes measured cpu frequency ~= 2919.045930 using 20 random witnesses for Rabin-Miller PRP checks =============================================================== ======= Welcome to YAFU (Yet Another Factoring Utility) ======= ======= bbuhrow@gmail.com ======= ======= Type help at any time, or quit to quit ======= =============================================================== cached 78498 primes. pmax = 999983 >> fac: factoring 2264896707546818670727285002520672181772642716242094795010232862539139579838750852742562416508752358715457554620245688072468162086358327123749825805613136390834328006135334709867747538765173162979741225754536350480853234652374489385146248704800006410822837702485074096032356475 fac: using pretesting plan: normal fac: no tune info: using qs/gnfs crossover of 95 digits div: primes less than 10000 div: found prime factor = 5 div: found prime factor = 5 div: found prime factor = 1697 fmt: 1000000 iterations rho: x^2 + 3, starting 1000 iterations on C272 rho: x^2 + 2, starting 1000 iterations on C272 rho: found prp7 factor = 4338703 rho: x^2 + 2, starting 1000 iterations on C266 rho: x^2 + 1, starting 1000 iterations on C266 pm1: starting B1 = 150K, B2 = gmp-ecm default on C266 fac: setting target pretesting digits to 81.85 fac: sum of completed work is t0.00 fac: work done at B1=2000: 0 curves, max work = 30 curves fac: 30 more curves at B1=2000 needed to get to t81.85 ecm: 30/30 curves on C266, B1=2K, B2=gmp-ecm default fac: setting target pretesting digits to 81.85 fac: t15: 1.00 fac: t20: 0.04 fac: sum of completed work is t15.18 fac: work done at B1=11000: 0 curves, max work = 74 curves fac: 74 more curves at B1=11000 needed to get to t81.85 ecm: 74/74 curves on C266, B1=11K, B2=gmp-ecm default fac: setting target pretesting digits to 81.85 fac: t15: 7.17 fac: t20: 1.04 fac: t25: 0.05 fac: sum of completed work is t20.24 fac: work done at B1=50000: 0 curves, max work = 214 curves fac: 214 more curves at B1=50000 needed to get to t81.85 ecm: 214/214 curves on C266, B1=50K, B2=gmp-ecm default, ETA: 0 sec pm1: starting B1 = 3750K, B2 = gmp-ecm default on C266 fac: setting target pretesting digits to 81.85 fac: t15: 37.74 fac: t20: 11.23 fac: t25: 1.05 fac: t30: 0.07 fac: sum of completed work is t25.33 fac: work done at B1=250000: 0 curves, max work = 430 curves fac: 430 more curves at B1=250000 needed to get to t81.85 ecm: 430/430 curves on C266, B1=250K, B2=gmp-ecm default, ETA: 1 sec pm1: starting B1 = 15M, B2 = gmp-ecm default on C266 fac: setting target pretesting digits to 81.85 fac: t15: 123.74 fac: t20: 64.98 fac: t25: 9.65 fac: t30: 1.07 fac: t35: 0.09 fac: sum of completed work is t30.45 fac: work done at B1=1000000: 0 curves, max work = 904 curves fac: 904 more curves at B1=1000000 needed to get to t81.85 ecm: 904/904 curves on C266, B1=1M, B2=gmp-ecm default, ETA: 5 sec fac: setting target pretesting digits to 81.85 fac: t15: 425.07 fac: t20: 245.78 fac: t25: 54.85 fac: t30: 8.73 fac: t35: 1.09 fac: t40: 0.11 fac: sum of completed work is t35.56 fac: work done at B1=3000000: 0 curves, max work = 2350 curves fac: 2350 more curves at B1=3000000 needed to get to t81.85 ecm: 209/2350 curves on C266, B1=3M, B2=gmp-ecm default, ETA: 8.04 hrs ecm: found prp35 factor = 12281729860152408407525225719635659 fac: setting target pretesting digits to 71.38 fac: t15: 530.07 fac: t20: 315.78 fac: t25: 73.94 fac: t30: 12.62 fac: t35: 1.74 fac: t40: 0.20 fac: t45: 0.02 fac: sum of completed work is t36.00 fac: work done at B1=3000000: 210 curves, max work = 2350 curves fac: 2140 more curves at B1=3000000 needed to get to t71.38 APRCL Progress: P = 13, Q = 157 (99.66%) Total factoring time = 7484.0222 seconds ***factors found*** P1 = 5 P1 = 5 P4 = 1697 P7 = 4338703 P35 = 12281729860152408407525225719635659 P232 = 1001860113482890555017710485492420423876242421736095074738385131002929692458471110177277127310688011729127988908466398932019505500863392332136664225101034793814078136979376956873726395552928651794389376576934283525340824695529351511 ans = 1
>>> H = 1001860113482890555017710485492420423876242421736095074738385131002929692458471110177277127310688011729127988908466398932019505500863392332136664225101034793814078136979376956873726395552928651794389376576934283525340824695529351511 >>> H.bit_length() 768
これでm1, m2が割り出せるので、フラグがわかる。
#!/usr/bin/env python3 from Crypto.Util.number import * with open('output.txt', 'r') as f: params = f.read().splitlines() n = int(params[0].split(' = ')[1]) e = int(params[1].split(' = ')[1]) c = eval(params[2].split(' = ')[1]) p = c[0][0] for i in range(1, 4): p = GCD(p, c[0][i]) print('[+] p =', p) assert n % p == 0 q = n // p phi = (p - 1) * (q - 1) d = inverse(e, phi) m1_E = pow(c[1][1], d, n) m2_H = pow(c[2][2], d, n) print('[+] m1 * E =', m1_E) print('[+] m2 * H =', m2_H) assert pow(m1_E, e, n) == c[1][1] assert pow(m2_H, e, n) == c[2][2] #### from result of primefac #### E = 890941089701337639742923670629764992383197102649368033477055542426171609788212371754143394788213291456300216361551640449365841636339404366563906765128981689755176699342918904671528454362377482743831820969956624190146702130809843851 m1 = m1_E // E flag1 = long_to_bytes(m1) #### from result of yafu #### H = 1001860113482890555017710485492420423876242421736095074738385131002929692458471110177277127310688011729127988908466398932019505500863392332136664225101034793814078136979376956873726395552928651794389376576934283525340824695529351511 m2 = m2_H // H flag2 = long_to_bytes(m2) #### join flag #### flag = (flag1 + flag2).decode() print('[*] flag =', flag)
実行結果は以下の通り。
[+] p = 12260270527500005140354303469557914031320743052940580181442343366352651136803519476311929752190095903543237842653732512701302765305896233466661576939731877
[+] m1 * E = 1654473583289225542637898223202890105229793155648049154615591729969285906185035489335891816982587768857940621086111446948472898558020413418239764400706309051511896603873998731251376123070734938584083464450577263707381779777754030251104042834091839092436678933359962636001191186
[+] m2 * H = 2264896707546818670727285002520672181772642716242094795010232862539139579838750852742562416508752358715457554620245688072468162086358327123749825805613136390834328006135334709867747538765173162979741225754536350480853234652374489385146248704800006410822837702485074096032356475
[*] flag = SECCON{C4n_y0u_prove_why_decryptable?}
SECCON{C4n_y0u_prove_why_decryptable?}
