It’s my first time to participate in such a pure crypto competition this year. Too many crypto challenges tucked into a game within 24 hours are driving me a little unconscious. By the way, the time schedule is totally unfriendly to me in China time zone which keeps me out of the first blood. I spent about 9 hours working on the crypto challenges and finally solved 8 (checkin not included) of them with rank 51. There are various math tricks for those challenges. However, I have to mention that the descriptions of some challenges are vague and confusing, and I guess that’s why there are so few solutions to an easy challenge (not solved by me either, emmm). I’ve been moyuing for half month at home, so I decide to update this writeup in my blog. Due to time constraints, I didn’t even browse all the challenges of this competition, and I will review it later when I’m spare… Take a rain check.
Diploma (medium, 68 solves)
Given a modular p and a matrix M with shape , we are supposed to find the min k such that : in , where is the identity matrix.
It’s a challenge about matrix group and its order. It’s easy if you’re familiar with the GL
or MatrixSpace
api in sage. For more info, refer to Linear Groups. Here is my exp:
1 | # sage 9.2 |
SOTS (medium easy, 113 solves)
It’s all about math trick. Therefore, I turn to google for help. After a long boring search, I found this Q&A in math.stackexchange : Efficiently finding two squares which sum to a prime. This is exactly in line with our challenge.
In our scene, we’re given an integer $n$ which is not a prime and we aim to find $a,b$ such that : . After several tries, I’m confirmed that $n$ is in form of where and can be factored in sagemath. By Thue’s Lemma, we can find such that in polynomial time. Therefore, by the identity : , we can find the two squares which sums to $n$. Here is my final exp in sage :
1 | # sage 9.2 |
polyRSA (medium easy, 145 solves)
Focus on equations :
Considering as variable in polynomial of IntegerRing, let . Therefore, we only have to find in IntegerRing.
1 | n = 44538727182858207226040251762322467288176239968967952269350336889655421753182750730773886813281253762528207970314694060562016861614492626112150259048393048617529867598499261392152098087985858905944606287003243 |
Starter ECC (medium, 43 solves)
It takes me a lot of time to solve this challenge since there’s something wrong with the function when it comes to .
Actually, this challenge has little to do with ECC. We’re given parameters of and are supposed to find the correct corresponding to a given coordinate . We can factor $n$ quickly in factorDB：
By the ECC polynomial: , we try to sqrt in There are totally solutions for this equation. In sage, if you try to find of prime power modular like in , it will return the results in instead of ！I was stuck here for hours.
1 | # sage 9.2 |
DBB (medium, 43 solves)
Similar to the starter ECC challenge, this time we are supposed to compute the discrete logarithm in ECC. There is something worthy of attention with the api in sage when it comes to with a given smooth order.
First, just factor n in sage and n is in form of . Therefore we try to compute the discrete logarithms in and combine them with Chinese Reminder Theorem. Luckily, we find the order are all smooth (). It’s rather easy in sage. However, when you want to use the parameter in , you have to use the order of base element instead of the curve’s order. Also, in the CRT process, the modular is also the order of the base element.
1 | # sage |
Sparse (medium hard, 38 solves)
I think it’s an easy challenge or maybe my solution is unexpected. Notice that where is randomly selected form {0,-1} and is randomly selected from [3,417-3] ( p is 417-bit ). In some cases, p and q are close and from sqrt(n) we can derive p’s most MSBs and factor n by coppersmith method. In this challenge, it’s not applicable. Therefore, I just brute force the supposing that at least half of $C_i$s are zero and try to find the roots of $f=x*(x-2^i-2^j)-n$.
1 | from Crypto.Util.number import * |
Cantilever (medium, 60 solves)
This challenge is a classic smooth prime problem and related to two famous algorithm: Pollard’s p-1 algorithm for integer factorization and Pohlig Hellman algorithm for discrete logarithm. Just implementing the two algorithms is enough for this challenge. Lately, I’m also designing crypto challenges related to the two algorithms, so this challenge makes me feel very familiar.
1 | from tqdm import tqdm |
Baphomet (easy, 93 solves)
Xor tricks. From the encrypted flag length, we get the key length by . Therefore by the flag format b64encode(b"CCTF{")
, we can get the 6-byte and it’s all done.
1 | from base64 import b64encode,b64decode |
- 本文作者： tl2cents
- 本文链接： https://tl2cents.github.io/2022/07/17/CryptoCTF2022/
- 版权声明： 遵循CC 4.0 BY-SA版权协议，转载请注明出处