# CryptoCTF 2021

## Farm (41 pts, 149 solves)

Explore the Farm very carefully!

因為我們是在 $GF(64)$ 上進行運算，所以其實 key 只有 $64$ 種不同可能性。直接窮舉所有可能，然後把有包含 CCTF 的字串印出來即可。

## Symbols (70 pts, 70 solves)

Oh, my eyes, my eyes! People still can solve this kind of cryptography? Mathematicians should love this one!

有幾個符號看起來很 LaTeX，所以就丟 https://products.groupdocs.app/conversion/png-to-tex ，不難發現取每個 symbol 的開頭就是 flag 了

## Hyper Normal (71 pts, 69 solves)

Being normal is hard these days because of Corona virus pandemic!

首先要注意到加密的最後一次 shuffle 跟 transpose 是來廣告的，回傳的仍然是 $W$。而 $W$ 的每個列向量則是將 $V$ 每個分量乘上一個 random 值 ($0\sim127$)。那要如何將 $V$ 還原呢？想法是跑遍所有的列向量和所有可能的 random 值 $r$，然後看 $$V^{'}[i] = W[j][i] \times r^{-1} \times \left(i+1\right)^{-1} \pmod{p} $$ 中 $1\sim127$ 哪個最常出現。那麼它就是原本 $V[i]$ 的值。

## Hamul (83 pts, 56 solves)

RSA could be hard, or easy?

提供的程式碼相當清楚，假定 $p,q$ 個別有 $n_{p},n_{q}$ 位數，那麼 $$PP = 10^{n_p+n_q}\left(10^{n_q}p+q\right)+\left(10^{n_p}q+p\right)$$ 以及 $$QQ = 10^{n_q+n_p}\left(10^{n_p}q+p\right)+\left(10^{n_q}p+q\right)$$ 換句話說，我們有個雙變數多項式$f$，滿足 $$f\left(p,q\right)=PP\cdot QQ = n$$ 並且 $p,q$ 是相對 $n$ 是小的。直接跑 Coppersmith 就好~

## Tuti (69 pts, 71 solves)

Cryptography is coupled with all kinds of equations very much!

## Triplet (91 pts, 50 solves)

Fun with RSA, three times!

這題是要求三組不同的RSA，它們的公私鑰一樣。第一眼的想法就是讓它們對應的 $\phi$ 有因倍數關係：$$\phi_1, \phi_2 = \left(p_1-1\right)\left(q_1-1\right), \left(p_2-1\right)\left(q_2-1\right) | \phi_3 = \left(p_3-1\right)\left(q_3-1\right)$$ 那就只需要提供第三組的公私鑰 $\left(e,d\right)$ 滿足 $e,d <\min\left(\phi_1, \phi_2, \phi_3\right)$。再來就是要讓上述關係成立，很直覺會取 $q_1=q_2=q_3$，然後希望 $$ p_1-1, p_2-1 | p_3-1 $$ 簡單的 google 會找到 https://en.wikipedia.org/wiki/Cunningham_chain 。最後就 random 取 $e$ 去算 $d$ 有沒有滿足不等式。

## Onlude (95 pts, 48 solves)

Encryption and Decryption could be really easy, while we expected the decryption to be harder!

一共提供了 $4$ 個矩陣 $U\left(A+R\right), LUL, L^{-1}S^2L$ 和 $R^{-1}S^{8}$。因為 $S=LU$，因此 $$L^{-1}S^2L = L^{-1}\left(LULU\right)L = ULUL$$ 於是就能將 $U,S^2,R$ 都算出來：$$U = ULUL\left(LUL\right)^{-1} \\ S^2 = LULU = U^{-1}U\left(LULU\right) = U^{-1}\left(ULUL\right)U \\ R = \left(R^{-1}S^8(S^2)^{-4}\right)^{-1}$$ 所以 $A = U^{-1}U\left(A+R\right)-R$，$flag$ 也很輕鬆地就能還原。

## Maid (119 pts, 36 solves)

Can you imagine this could be so hard for the Oracle?

我們能夠拿到兩種東西 $$ x^2 \pmod{ppq}, \quad y^{\frac{1}{2}} \pmod{pp} $$ 同時也知道 $ppq$ 跟 $pp$ 的大概大小，所以只要能找到 $x,y$ 使得 $x^2, y^{\frac{1}{2}}$ 稍微比 $ppq,pp$ 大一點點，就能直接知道它們的值，剩下就是 RSA。

## RSAphantine (142 pts, 29 solves)

RSA and solving equations, but should be a real mathematician to solve it with a diophantine equation?

基本上是注意到第一,三式算出來的值差距不大，所以照理說能夠將 $x,y$求出來 ... 這次我是丟 wolfram alpha 就直接吐出整數解，$z$ 則是使用第二式跟 $x,y$ 可算，剩下也就是 RSA。

## Double Miff (217 pts, 16 solves)

A new approach, a new attack. Can you attack this curve?

首先就是將 $p$ 給求出來，這就要利用到 $$2P+2Q = 2(P+Q)$$ 根據定義，我們有 $$ LHS.x \equiv \frac{\left([2P].x+[2Q].x\right)\left(1+[2P].y\cdot [2Q].y\right)}{\left(1+[2P].x\cdot [2Q].x\right)\left(1-[2P].y\cdot [2Q].y\right)} \pmod{p} $$ 以及 $$ RHS.x \equiv \frac{\left(2[P+Q].x\right)\left(1+[P+Q].y^{2}\right)}{\left(1+[P+Q].x^{2}\right)\left(1-[P+Q].y^{2}\right)} \pmod{p} $$ 雖然我們沒有 $p$，所以沒有模逆元，但只要交叉相乘就沒事了 :)。同樣地，比對 $y$ 座標就能得到第二個 $p$ 的倍數。得到 $p$ 之後，就跟橢圓曲線上求 $\frac{P}{2}$ 的方法一樣。直接列式 $$[2P].x \cdot [2P].y \equiv \frac{4[P].x\cdot [P].y}{\left(1-[P].x^2\right)\left(1-[P].y^2\right)} \equiv \frac{2a[P].x^2}{b\left(1-[P].x^2\right)^2} \pmod{p} $$ 注意到 $p$ 是 $4k+3$ 型的質數，我們可以輕鬆地開根號，從而得到 $[P].x$ 的二次方程式，然後再開根號將 $[P].x$ 求出。