RTACTF 2021に参加しました。TAがメインのCTFって見たことなかったので新鮮でした。

私はpwnは早解きできるほど理解していないのでcryptoだけ解きました。（でも面白そうなので解いてみます）

各問題の順位は以下の通りです。解法ガチャに成功しただけですが、Leaky RSAでFirst blood取れたのは嬉しいですね。

Challenge Rank Time
Sexy RSA 4th 163.20 s
Proth RSA 8th 979.02 s
Leaky RSA 1st 1574.89 s
Neighbor RSA 8th 1778.19 s

Sexy RSA

$n = p(p+6)$ なので $\sqrt{n}$ あたりを雑に探索しました。

 1import gmpy2
 2
 3n = 0xE72988E811F04091C3291AC28F1E8332193187F3DC5AF01579C36BADB06671AA9A9543AA07EBA8CDAB36D787F1FF98A06DB995C43CD5C63581CE050E0B9BA856634DABFAF8C7F271FBD026EDD6EA1257B16013A526E0581A688CC6A335E7EE4C1B0633F0532D3D0824824195B6B249C70CF0E458609EFC01A6575F084E6DE53B
 4e = 0x10001
 5c = 0x6FADD5D7095BD6F45DE69BB4E76080E0EA5F8C5A159DE10663133E585B71AE580B99B3E0A8E047A9C51C8091A6B33B01C9AB95668794C3ACFB084E939A04CB151757C3B2522DA99E03F83E205C7C701066D69B120CA17FCF59061C078D9099E5F4BF6DD6DAB206418527035F2C1096861C2896327977AC88C2728FAA7504D879
 6
 7p = int(gmpy2.isqrt(n))
 8for _ in range(100):
 9    if n % p == 0:
10        break
11    p -= 1
12
13q = n // p
14
15d = pow(e, -1, ~-p * ~-q)
16m = pow(c, d, n)
17print(bytes.fromhex(f"{m:x}"))

Proth RSA

式変形めんどくさいと思ってGröbner基底に投げたんですが、実装バグらせて結局遅くなってしまいました…

 1n = 0xa19028b5c0e77e19fc167374358aa346776e6c20c27499505be59c83ea02014e97af631ba0ccbab881313818fd323c15c82dad8793220ba6679ec4b38787e04d0c1fff0880e04423ea288e443660c63a1607532e47dbaad421723d0546c208447f701cd7e9ee1bb43774d132abbb2e91bf50b67be40ed854dbe6c3071ca3ae3307ac03abd76f74e506594106a22795d4b7938611301248a9957e1a637538a9169cf38daf5d60ffc05ae32ea7e638e16d790ffeebfff655a645c99a513616d3ce00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001
 2e = 0x10001
 3s = 0x28640a2d7039df867f059cdd0d62a8d19ddb9b08309d265416f96720fa808053a5ebd8c6e8332eae204c4e063f4c8f05720b6b61e4c882e999e7b12ce1e1f812c11cfed72a5c33cfb8f3d34f650e4c19579cf34745f2588aa2fd08a8746257cb789f23ca232346fcf72468a2b160934911902de3f90620aba5874a2d79a33699
 4c = 0x4595c3c923bd191ba07456611f80e656a197ff528a031e2952adedda532b1fa2caef719c929132a3cdf06d0e55e6a00f7eb1f189a614b26759916ec42f83579a75ab5948186769a1a936b019466f918f29e32852675c464b7f0797c6fdc55efcd54fbe2083761b1df3dde0b9a9a35b96e3b216c54770b444b1f02525f0268c44483c6e84a781fe9111e6912130d69f462c519873043d44e4a3f1f938491feeb591b5831d0abe7399bc87244576decaf2925f287d3c2bb4061d560c919d820e364744f2322c7efd37d42563842bcf9b1d6b46218694dcd49758d311c6896e38cf2b55c7114d78cfdfaeba74720ecf30d9133034799b9735e26ec913cc9f26bb0a
 5
 6
 7def quad(b, c, n):
 8    D = (b^2 - 4*c) % n
 9    ans = (-b-D.sqrt()) * pow(2, -1, n) % n
10    return ans
11
12PR.<k1, k2> = PolynomialRing(Zmod(n))
13p = (2*k1+1)*2^512+1
14q = (2*k2+1)*2^512+1
15f = n-p*q
16g = s-k1*k2
17
18a = Ideal([f, g]).groebner_basis()
19
20
21k2 = n - quad(ZZ(-a[-1].constant_coefficient()), s, n) 
22k1 = s//k2
23
24P = int(p(k1=k1))
25Q = int(q(k2=k2))
26
27d = pow(e, -1, (P-1)*(Q-1))
28m = pow(c, d, n)
29print(bytes.fromhex(f'{int(m):x}'))

Leaky RSA

ここから急に難易度が上がりました。 ひとまず怪しいパラメータ$s$に関する式 $$ (p^2+q^2)s \equiv p^3 - 20211219q \mod n $$ をどうにかできないか考えていました。 $n$ は $p^2q^2$ で2200bitと大きい一方で、$q$ が500bitと比較的小さいです。 そこで、$q$ が根になるようにmodを取ればsmall_roots()で解けそうだと思い、$\text{mod}\ p^2$ をとりました。本当は根が求まる条件を満たしているかきちんと考察するべきなんですが、speedrunということで考えるよりもいろいろ試す方針をとりました。 small_roots()の引数はいつも適当に決めているんですが、この手の問題はパラメータが少しズレただけで欲しい値が出ないことがあるので、きちんとパラメータを決められるようにしたいですね。

 1from Crypto.Util.number import long_to_bytes
 2
 3n = 0x2ac1fcbbf63ffeade11cd2c57c37db18d96d52e433bd9034d4eac2c269ea49a81e5ac41fb631523bb5983adc6fc939c073c13d8a3a42a06accf5a9c304fc444508a8b5833b5431e9af7007bb216c510c62a97eb1fe380bf155b3e497c7d70c2bb921f97eec61e9e9ac7b5d71e47876d20cbfb1a0732e29ec6872041eb67e0ccd39d7b6429bda1581537dda95e79d3aad4df072beada1c72a4ffd86db91918ec9db44ab9c4bebf387ccc1ce7b2540b0d595a4c11823cdbcd8850bd3b666b4a08bd69de515afecc75b283ae47fbf3af6f034f3b0f7848dec935ba8b97e36d2d0a9208df63610cf8825fb729aacaa4c119d0b4c5e230e080d7633f145d22eb06b917fe632c01a373b1c4c8a741bea1d5dd98003e9
 4e = 0x10001
 5c = 0xe50a858f715238a9ab44dfd691f6e5ced84e74115e003e31a98b324cf9e8bc9cfe08065f2538cff519e035566b4080742139062e672a0ad3196275cb121ea837de2808f99958bcfe58d1c8996f291412220d01fe65fbf18611b348407b2e2db45b2adcc341926c6d76a9d08fc77db0fedef78cec9e4b881812e60c015c1005dfd0b9408cb3c6f9f98332f165acc3ae98ef97f2a1d98524fe240d3351676ed84ddb73283a6d3efc40bbd466fe3532e579eb9adf07ebbc49af71fb22934a75a69a538eca0fd4e2a5b617abb361a64c553985950dd5201ac7c631580c8bb27d795a196d584ae7c7478bdc1b5ff531ff88e984bceb1e26cf9793f99a11287555d5d2d2a13e1171f77bf8491d8dfa297e9cd6d4b7d
 6s = 0x14c0af71a961be72e2d4e5ee06337cde2034db1d920f4476e3a3371c8a35e7ba8efabf5c8e8ff86e7297156c4fde5bdc7aabe1516a46c554236104022eb4544f1d7fcb80279595dfe0527bcc373909ce7cc0965ece5ff76b7ee9a5cc31a1b567ed3ddd2364bb596e3c41e4fffb5974f71e788da5c21598e9c6dc32bca162026ba3c410bb1c5c9d5bed4c3b97e3cacbd7b6693f29c74b0756381b658efaa757d448f62a48fbdb06604525222aa51797a1a1e43af4b0c221deef47f84bb5bfa1480cd31242c3d7fba21bdf487709853879dcea284e44cb5ee1a02c558a29740a44e39c7ee3a97ab4805d21cb90b596bd86c51f4e0f783701da73c66f5a4c67d989bb2dba2b8a55a697eb187cc181fc8ce54de370
 7
 8
 9PR.<q> = PolynomialRing(Zmod(n))
10
11
12k = 20211219
13f = s*q^2 + k*q
14f = f.monic()
15
16p = f.small_roots(X=2^500, beta=0.5)[1]
17print(p)
18
19q = sqrt(n//ZZ(p*p))
20assert n == p*p*q*q
21
22d = pow(e, -1, p*(p-1)*q*(q-1))
23m = pow(c, d, n)
24print(long_to_bytes(ZZ(m)))

Neighbor RSA

以前ふるつきさんのAGCDに関する記事を見たことがあったので、AGCDっぽいなーと思って取り組んでいました。方針は良かったんですが、実装をまたバグらせてしまいました…　残念ながら再走はできません。

AGCDに限った話じゃないんですが、なんでこの格子の基底のとり方でうまく行くのかちゃんと理解していないものが多いので、時間を見つけてきちんと論文読みたいですね。

 1from Crypto.Util.number import long_to_bytes
 2from sage.all import *
 3
 4e = 0x10001
 5n1 = 0xA8ED020C3DD125D503BF124052D643BA1405F2C349244122140E79E7D2244304A1590762C61AC83900C2ACED76007B2E3F320464FD51FCFAD167EBDC87E69329230869E0A3E153B44ED3B04BFE94174BC8B5EE1A3FA8036B6B9E834666AA07229A431B477E589D94F9A4CFED25B195215B0C694B86E874413B8A00CB064809C8E3677632CDE9B43B87A0B812C2024B0C821B5C10764FD4DE2D18AF55D897D94AEDED80B71E36FD73014F75641A8C5B38B36FAA020E7CF1327A707BB7D42503BCC28768EF184D66B9BA16EFD019B68268885A2DA302CD326E78B1D473BCF7CD62442CCD25DC85D23AEB5408922B6B00F13584BEA394F1BCA4CC431F3C29C5D98EC1683453CC0C526ABE4AEC08781C7A53F50F2047B4995B9BEA6A7A9F6B5425B29BE6E867764EFAA050799F716AF78273041372CFE4F3C88A62329F6F1FEFF99
 6n2 = 0x16EA1BDE86EA11CDEC196A9173258EFCA235DA66F8E3D5437E39E1B2E2574DD3F93D65104CA0225D6119519AE9EA9C035E0F85F02212C0992D0705723FA8B97ED6CFF860C4D8FB65F0214A0047FECA64E662DCBF025FFF47590305E90E5D070D39871880828F5E960AB2EF330129ED5752C3B4DEBE827376A632B06487740FFF4B622A88DE23649E3E6993CD332B0284B84EB8765D58527209CC202C89D479421131A2F64AE517EE1E62E6C0F329C306569E427113EC6A8B9D96D73E95580D3A33F6ADD681F9A9156F0681EB1804183DFA8CEBBE921D2FB1D43B256F727D46C5859CC5229F7E555AD25397E5CD14620EBBAEFA0A0A520BADA3EF8B115481734242AF6BEFBD9B069D4A03281094C0F4ACA4E6FDCBE2558B104FC2B383E1C70F0E5A07D1A623F9FC2309CA1D09B69AA1869E280FBC50DE2ADBADA7EA545743B12B
 7c1 = 0x690E49037FEE7649033FFAAA71E4730D2D7143FAB97BEB22E2AFDF6ECA449CAD3F95B60295F592E7E84833E08B3468D61A34C1D1123F4C683C79D68BBE27DD0AF203FC50EF7EBE98B1BC1221918470F058A8FB7645EACB569931835BD7F80494DBB67FBAA592EC19D9B4930C787A2CE1267F8088229B5031E710D6CD5720756923CCB64444939A0F09A51C87488650D4D02551FD4ED7A2FD248825EC34C5DF8B6077A6D0D75C5832F9140420C92D3D00CF51E3B0665F5A6D031CB369DDEBBB5CE77F2176CD12BB0ADD5AEDA6AE88C4CEADE0C1FD0FF3960D3EE36A0C6455AE3027F33E660663D0E2298654E19E8C8A06B4DE991FAC3B4C1673825B3D9F8F5C675F920A7D137F85BA723BF741321904E0C3C601F5C18D02E1E5B7B118E62E91A7926A9B1EDA3CC53E2A6CBC95553E1990EC3F6CCEDDF283410D6E6849A26F89B
 8c2 = 0x5C4C7DCE82753A68DCDBCDCE9AF52C9B7AF2F561C08B8E23B27C6145D4C3DF29D498303BEE1BD29829A2E0AE9FAAF243B387C39D69DACCBA07DACE7BB420115FFAA69F89A3EA4E1EF0E08EB19043E012A090B79E51D6AE8446CA76E88ABE5ADBDBE25A731D7EE9AA333A84447EDAFBC360B505FF293C751571C6BF29DEE99FDC443B756F182EB588B4A03DE3D35DC4F23736D7239CFBD0CA13FA7B234BC4064A2053AB0045F4833250C8C9DE91798502B09D4312EE52F3DC5229DFCB73B42F7C3440932839E6E790BB0DB1788FBD7C60365121BBE3858ECEDD3D48261D081C380E7DDF6CA570C13CC89C0AF2011B4978B22D5456D1122DABD7B2068AB30E301A674809732DAEDE77A27AE13E1BC4779E15D51210F6C10BE159907EC1A59BFAF8DB6CF290A348F734FD88E3C2B7DF6BDA84665B810CFE55BC3645D8D118C9172
 9
10
11t = 2 ^ 512
12m = matrix(
13    [
14        [t, n2],
15        [0, -n1],
16    ]
17)
18
19
20m = m.LLL()
21q = int(m[0, 0] // t)
22p1 = n1 // q
23
24p2 = int(next_prime(p1))
25r = n2 // p2
26
27d1 = pow(e, -1, (p1 - 1) * (q - 1))
28d2 = pow(e, -1, (p2 - 1) * (r - 1))
29
30flag = b""
31flag += long_to_bytes(ZZ(pow(c1, d1, n1)))[:-128]
32flag += long_to_bytes(ZZ(pow(c2, d2, n2)))[:-128]
33
34print(flag)

感想

RTA向けのシンプルな設定の問題セットで面白かったですし、突貫工事でつくったと言っていたスコアサーバも問題なく動いていて快適でした。（ptr-yudaiさんは今年だけで一体何問出題したんだろう）

ただ、競プロとかをやっていても思ったんですが、私は時間に追われるのは苦手だなと改めて思いました。前半のpwnは通しで放送を見ていたんですが、走者の方々は他人に見られているというプレッシャーの中でもサクッと解いていてすげ〜と思っていました。私にはできない😭