owned this note
owned this note
Published
Linked with GitHub
# CryptoCTF 2021
| Challenge | Category | Solved by |
| ----------- | -------------------- | ------------ |
| Hamul | RSA | Lyutoon |
| Robert | Carmichael $\lambda$ | Robin_Jadoul |
| LINDA | Discrete logarithm | NeketmanX |
| Trunc | Signature forgery | NeketmanX |
| Double Miff | Algebra | NeketmanX |
| Symbols | Misc | Q7 |
| Onlude | Linear algebra | Q7 |
| Hyper Normal| Misc | Q7 |
<!-- Template for writeup -->
## Challenge Name
##### Score
### Challenge
### Solution
##### Flag
## Hamul
##### Score:83
### Challenge
RSA could be hard, or easy?
- [hamul_e420933a0655ea08209d1fe9588ba8a3a6db6bf5.txz.txz](https://cr.yp.toc.tf/tasks/hamul_e420933a0655ea08209d1fe9588ba8a3a6db6bf5.txz)
```python
#!/usr/bin/env python3
from Crypto.Util.number import *
from flag import flag
nbit = 64
while True:
p, q = getPrime(nbit), getPrime(nbit)
P = int(str(p) + str(q))
Q = int(str(q) + str(p))
PP = int(str(P) + str(Q))
QQ = int(str(Q) + str(P))
if isPrime(PP) and isPrime(QQ):
break
n = PP * QQ
m = bytes_to_long(flag.encode('utf-8'))
if m < n:
c = pow(m, 65537, n)
print('n =', n)
print('c =', c)
# n = 98027132963374134222724984677805364225505454302688777506193468362969111927940238887522916586024601699661401871147674624868439577416387122924526713690754043
# c = 42066148309824022259115963832631631482979698275547113127526245628391950322648581438233116362337008919903556068981108710136599590349195987128718867420453399
```
### Solution
Since we can see that the generation of $PP$ and $QQ$ is special:
```python
while True:
p, q = getPrime(nbit), getPrime(nbit)
P = int(str(p) + str(q))
Q = int(str(q) + str(p))
PP = int(str(P) + str(Q))
QQ = int(str(Q) + str(P))
if isPrime(PP) and isPrime(QQ):
break
```
- If we let $x, y = len(str(p)), len(str(q))$, we will get:
$P = 10^{x}p + q,\, Q = 10^{y}q + p$
- Also we let $x', y' = len(str(P)), len(str(Q))$, we will get:
$PP = 10^{x'}P+Q,\, QQ=10^{y'}Q+P$
- After we put $P = 10^{x}p + q,\, Q = 10^{y}q + p$ into the above equation and calculate $N=PP*QQ$ we will find $N$ looks like in this form:
$N = 10^{x+x'+y+y'}pq+...+pq$
- Since $x+x'+y+y'$ is big enough, so we know that $str(N)[:?]$ is actually $str(p*q)[:?]$ and as the same, $str(N)[?:]$ is actually $str(p*q)[?:]$
- After generating my own testcase, I find that $str(N)[:18] = str(p*q)[:?]$, $str(N)[-18:] = str(p*q)[-18:]$ and actually $len(str(p*q)) = 38$ so we just need brute force 2 number between the high-part and low-part.
- So we can get $p*q$ and factor it to get $p$ and $q$. The next is simple decryption.
```sage
from Crypto.Util.number import *
from tqdm import tqdm
def decrypt_RSA(c, e, p, q):
phi = (p-1) * (q-1)
d = inverse(e, phi)
m = pow(c, d, p*q)
print(long_to_bytes(m))
n = 98027132963374134222724984677805364225505454302688777506193468362969111927940238887522916586024601699661401871147674624868439577416387122924526713690754043
c = 42066148309824022259115963832631631482979698275547113127526245628391950322648581438233116362337008919903556068981108710136599590349195987128718867420453399
low = str(n)[-18:]
high = str(n)[:18]
pq_prob = []
for i in range(10):
for j in range(10):
pq_prob.append(int(high + str(i) + str(j)+ low))
for x in tqdm(pq_prob):
f = factor(x)
if (len(f) == 2 and f[0][0].nbits() == 64):
p, q = f[0][0], f[1][0]
break
P = int(str(p) + str(q))
Q = int(str(q) + str(p))
PP = int(str(P) + str(Q))
QQ = int(str(Q) + str(P))
N = PP * QQ
print(N == n)
decrypt_RSA(c, 65537, PP, QQ)
```
##### Flag
> CCTF{wH3Re_0Ur_Br41N_Iz_5uP3R_4CtIVe_bY_RSA!!}
## Robert
##### 194 pts (19/444 solves)
### Challenge
> Oh, Robert, you can always handle everything!
`nc 07.cr.yp.toc.tf 10101`
Upon connection, we see
```
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
+ hi all, all cryptographers know that fast calculation is not easy! +
+ In each stage for given integer m, find number n such that: +
+ carmichael_lambda(n) = m, e.g. carmichael_lambda(2021) = 966 +
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
| send an integer n such that carmichael_lambda(n) = 52:
```
where we can of course assume we will need to pass a certain number of rounds, and the numbers will grow.
### Solution
Early on, we find [this math stackexchange post](https://math.stackexchange.com/questions/41061/what-is-the-inverse-of-the-carmichael-function), where we already make the comment
> looks hard
as, in general, this problem appears to be at least as hard as factoring $m$.
We consider the possibility of factoring $m$ and applying a dynamic programming based approach to group the prime factors of $m$ among the prime factors of what would be $n$.
In the end, this did not get implemented, as our intermediate attempts at cheesy solutions converge towards a simpler approach that solves the challenge.
The first of these cheesy attempts comes from 3m4 -- while setting the basis for further server communication scripts -- where we simply cross our fingers and hope that $m + 1$ is prime, leading to $n = m + 1$ and $\lambda(n) = m$.
While this clears up to 6 rounds on numerous occasions, it appears we'd need to either hammer the server really hard, or find something better.
Somewhere during this period of running our cheesy script full of hope, dd suggests that we might be in a situations where $m$ is known to be derived from a semiprime originally, i.e. $m = \lambda(pq)$.
Alongside this idea, an attempted solution exploiting that property is proposed, that unfortunately has several flaws and doesn't work against the server.
Basing ourselves on this idea, we can however write the dumbest sage script imaginable for this problem:
- Let $D$ be the set of divisors of $m$
- Enumerate all $(a, b) \in D^2$
- If $a + 1$ is prime, $b + 1$ is prime, *and* $\mathsf{lcm}(a, b) = m$: reply with $n = (a + 1)(b + 1)$
Clearly, *if* our assumed property that $m = \lambda(pq)$ holds, and $m$ does not grow too large to enumerate $D^2$, this should give us a correct solution.
Without all too much hope, we run the following sage script (with the `DEBUG` command line argument for pwntools, so that we can observe the flag should it get sent at the end):
```sage
import os
os.environ["PWNLIB_NOTERM"] = "true"
from pwn import remote
io = remote("07.cr.yp.toc.tf", 10101)
io.recvuntil(b"++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++")
io.recvuntil(b"++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++")
proof.arithmetic(False)
def reverse_lambda(n):
for x in divisors(n):
for y in divisors(n):
if lcm(x, y) == n and is_prime(x + 1) and is_prime(y + 1):
return (x + 1) * (y + 1)
try:
while True:
io.recvuntil(b"carmichael_lambda(n) = ")
integer = ZZ(io.recvuntil(b":")[:-1])
print(f"[*] Reversed: {integer} ->", end=" ", flush=True)
rev = reverse_lambda(integer)
print(f"{rev}")
io.sendline(str(rev).encode())
except EOFError:
print("EOF")
```
Against our initial expectations, we easily clear more than 10 rounds.
Slowing down on an occasional $m$ that might have been hard to factor or have a lot of different divisors, the script happily chugs along without the server closing the connection on it, eventually getting the flag after 20 rounds.
##### Flag
> CCTF{Carmichael_numbers_are_Fermat_pseudo_primes}
## LINDA
##### Score: 169 (23/444 solves)
### Challenge
> Dan Boneh loves to improve cryptosystems, you should be loving breaking them?
`nc 07.cr.yp.toc.tf 31010`
- [linda.txz](https://cr.yp.toc.tf/tasks/linda_a26f6987ed6c630297c2df0847ef258ad3810ca2.txz)
```python=
#!/usr/bin/env python3
from Crypto.Util.number import *
from math import gcd
from flag import flag
def keygen(p):
while True:
u = getRandomRange(1, p)
if pow(u, (p-1) // 2, p) != 1:
break
x = getRandomRange(1, p)
w = pow(u, x, p)
while True:
r = getRandomRange(1, p-1)
if gcd(r, p-1) == 1:
y = x * inverse(r, p-1) % (p-1)
v = pow(u, r, p)
return u, v, w
def encrypt(m, pubkey):
p, u, v, w = pubkey
assert m < p
r, s = [getRandomRange(1, p) for _ in '01']
ca = pow(u, r, p)
cb = pow(v, s, p)
cc = m * pow(w, r + s, p) % p
enc = (ca, cb, cc)
return enc
def die(*args):
pr(*args)
quit()
def pr(*args):
s = " ".join(map(str, args))
sys.stdout.write(s + "\n")
sys.stdout.flush()
def sc():
return sys.stdin.readline().strip()
def main():
border = "+"
pr(border*72)
pr(border, " .:::::: LINDA Cryptosystem has high grade security level ::::::. ", border)
pr(border, " Can you break this cryptosystem and find the flag? ", border)
pr(border*72)
pr('| please wait, preparing the LINDA is time consuming...')
from secret import p
u, v, w = keygen(p)
msg = bytes_to_long(flag)
pubkey = p, u, v, w
enc = encrypt(msg, pubkey)
while True:
pr("| Options: \n|\t[E]xpose the parameters \n|\t[T]est the encryption \n|\t[S]how the encrypted flag \n|\t[Q]uit")
ans = sc().lower()
if ans == 'e':
pr(f'| p = {p}')
pr(f'| u = {u}')
pr(f'| v = {v}')
pr(f'| w = {w}')
elif ans == 's':
print(f'enc = {enc}')
elif ans == 't':
pr('| send your message to encrypt: ')
m = sc()
m = bytes_to_long(m.encode('utf-8'))
pr(f'| encrypt(m) = {encrypt(m, pubkey)}')
elif ans == 'q':
die("Quitting ...")
else:
die("Bye ...")
if __name__ == '__main__':
main()
```
### Solution
By interacting with the challenge, we can get public key parameters by sending `e`, get encrypted flag with `s`, encrypt our own messages with `t` and quit with `q`. Only the first two options will be relevant to the solution.
Encryption here works like this: $p, u, v, w$ are public key parameters, message $m$ is encrypted as follows:
$ca \equiv u^r \mod p$
$cb \equiv v^s \mod p$
$cc \equiv m*w^{r + s} \mod p$,
where $r, s$ are uniformly random numbers from $[1;p]$.
We can notice that despite $p$ being new on each connection, $p - 1$ is always smooth. Example:
```
p = 31236959722193405152010489304408176327538432524312583937104819646529142201202386217645408893898924349364771709996106640982219903602836751314429782819699
p - 1 = 2 * 3 * 11 * 41 * 137 * 223 * 7529 * 14827 * 15121 * 40559 * 62011 * 429083 * 916169 * 3810461 * 4316867 * 20962993 * 31469027 * 81724477 * 132735437 * 268901797 * 449598857 * 2101394579 * 2379719473 * 5859408629 * 11862763021 * 45767566217
```
This is the key for solving this challenge, because after getting public key paramters and encrypted flag we can factor $p - 1$ by using trial division and [ECM](https://en.wikipedia.org/wiki/Lenstra_elliptic-curve_factorization), then use [Pohlig-Hellman algorithm](https://en.wikipedia.org/wiki/Pohlig%E2%80%93Hellman_algorithm) to compute $r, s$ as discrete logarithms of $ca, cb$ with bases $u, v$ respectively even without trying to find weaknesses in the keygen process. Then we can compute $m \equiv cc*w^{-(r + s)} \mod p$ and get the flag.
Solution script:
```python=
#!/usr/bin/env sage
from minipwn import remote # mini-pwntools library to connect to server
from Crypto.Util.number import long_to_bytes
rem = remote("07.cr.yp.toc.tf", 31010)
for _ in range(10):
rem.recvline()
rem.sendline('e')
p = int(rem.recvline()[6:])
u = int(rem.recvline()[6:])
v = int(rem.recvline()[6:])
w = int(rem.recvline()[6:])
for _ in range(5):
rem.recvline()
rem.sendline('s')
ca, cb, cc = map(int, rem.recvline()[7:-2].split(b', '))
r = discrete_log(Mod(ca, p), Mod(u, p)) # sage has built-in discrete logarithm function, which uses Pohlig-Hellman
s = discrete_log(Mod(cb, p), Mod(v, p)) # algorithm and automatically determines and factors group order, which divides p - 1
m = cc * power_mod(w, -(r + s), p) % p
print(long_to_bytes(m).decode())
```
##### Flag
> CCTF{1mPr0v3D_CrYp7O_5yST3m_8Y_Boneh_Boyen_Shacham!}
## Trunc
##### Score: 334 (7 / 444 solves)
### Challenge
> I wish I could say more, but I don't want to!
`nc 02.cr.yp.toc.tf 23010`
`nc 07.cr.yp.toc.tf 23010`
- [TRUNC.txz](https://cr.yp.toc.tf/tasks/TRUNC_dd1e2d91b790125fdfc7596f0076fa476446d2fb.txz)
```python=
#!/usr/bin/env python3
from Crypto.Util.number import *
from hashlib import sha256
import ecdsa
from flag import FLAG
E = ecdsa.SECP256k1
G, n = E.generator, E.order
cryptonym = b'Persian Gulf'
def keygen(n, G):
privkey = getRandomRange(1, n-1)
pubkey = privkey * G
return (pubkey, privkey)
def sign(msg, keypair):
nbit, dbit = 256, 25
pubkey, privkey = keypair
privkey_bytes = long_to_bytes(privkey)
x = int(sha256(privkey_bytes).hexdigest(), 16) % 2**dbit
while True:
k, l = [(getRandomNBitInteger(nbit) << dbit) + x for _ in '01']
u, v = (k * G).x(), (l * G).y()
if u + v > 0:
break
h = int(sha256(msg).hexdigest(), 16)
s = inverse(k, n) * (h * u - v * privkey) % n
return (int(u), int(v), int(s))
def verify(msg, pubkey, sig):
if any(x < 1 or x >= n for x in sig):
return False
u, v, s = sig
h = int(sha256(msg).hexdigest(), 16)
k, l = h * u * inverse(s, n), v * inverse(s, n)
X = (k * G + (n - l) * pubkey).x()
return (X - u) % n == 0
def die(*args):
pr(*args)
quit()
def pr(*args):
s = " ".join(map(str, args))
sys.stdout.write(s + "\n")
sys.stdout.flush()
def sc():
return sys.stdin.readline().strip()
def main():
border = "+"
pr(border*72)
pr(border, " hi all, welcome to the high secure elliptic curve signature oracle!", border)
pr(border, " Your mission is to sign the out cryptonym, try your best :) ", border)
pr(border*72)
keypair = keygen(n, G)
pubkey, privkey = keypair
while True:
pr("| Options: \n|\t[P]rint the pubkey \n|\t[S]ign \n|\t[V]erify \n|\t[Q]uit")
ans = sc().lower()
if ans == 'p':
pr("| pubkey =", pubkey.x(), pubkey.y())
elif ans == 's':
pr("| send your hex message to sign: ")
msg = sc()
try:
msg = bytes.fromhex(msg)
except:
die("| your message is not valid! Bye!!")
if msg == cryptonym:
die('| Kidding me? Bye')
msg = msg[:14]
sig = sign(msg, keypair)
pr("| sign =", sig)
elif ans == 'v':
pr("| send your hex message to verify: ")
msg = sc()
try:
msg = bytes.fromhex(msg)
except:
die("| your message is not valid! Bye!!")
pr("| send the signature separated with comma: ")
sig = sc()
try:
sig = [int(s) for s in sig.split(',')]
except:
die("| your signature is not valid! Bye!!")
if verify(msg, pubkey, sig):
if msg == cryptonym:
die("| Good job! Congrats, the flag is:", FLAG)
else:
pr("| your message is verified!!")
else:
die("| your signature is not valid! Bye!!")
elif ans == 'q':
die("Quitting ...")
else:
die("Bye ...")
if __name__ == '__main__':
main()
```
### Solution
Here we have a ECDSA-like signature scheme: nonces $k$ and $l$ are generated in such a way, that they always have their 25 LSBs dependent only on private key, thus always the same, then $u$ and $v$ are obtained as $x$-coordinates of $k * G$ and $l * G$ respectively, where $G$ is a generator on the curve `secp256k1`, then $h$ = `sha256(msg)` and $s \equiv k^{-1}*(hu - vd) \mod n$ are computed, where $d$ is the private key and $n$ is the order of the curve. $(u, v, s)$ is a signature for $h$.
Verification works as follows: again, $h$ = `sha256(msg)` is computed, then $k \equiv hus^{-1} \mod n$ and $l \equiv vs^{-1} \mod n$ are computed, after that $X$ is derived as $x$-coordinate of $k * G - l * P$, where $P = G * d$ is the public key. Signature verifies iff $X \equiv u \mod n$.
During interaction with the service we can obtain the public key by sending `p`, sign any message (except `Persian Gulf`) by sending `s`, verify a signature for a message with `v`, and if the signature for `Persian Gulf` verifies, we are given the flag, and quit with `q`.
This is an unintended solution, which doesn't exploit odd nonce generation during signature creation.
If $h_1$ is a hash of some message $m$, and $h_2$ is the hash for `Persian Gulf`, we can write $h_2 \equiv m*h_1 \mod n$, and if $(u_1, v_1, s_1)$ is a valid signature for $h_1$, then $(u_1, v_1m, s_1m)$ is a valid signature for $h_2$.
Proof: during verification of $h_1$ we have $k \equiv h_1u_1s_1^{-1} \mod n$ and $l \equiv v_1s_1^{-1} \mod n$. During verification of $h_2$ we have $k \equiv h_1mu_1(ms_1)^{-1} \equiv h_1mu_1m^{-1}s_1^{-1} \equiv h_1u_1s_1^{-1}\mod n$ and $l \equiv v_1m(s_1m)^{-1} \equiv v_1ms_1^{-1}m^{-1} \equiv v_1s_1^{-1}\mod n$, so $k, l$ are the same, thus $X$ is the same. And since $u$ is also the same, this signature will also verify.
Implementation script:
```python=
#!/usr/bin/env python3
from pwn import remote
from ecdsa import SECP256k1
from hashlib import sha256
n = SECP256k1.order
m1 = b'lol' # any other message is fine
m2 = b'Persian Gulf'
h1 = int(sha256(m1).hexdigest(), 16)
h2 = int(sha256(m2).hexdigest(), 16)
m = h2 * pow(h1, -1, n) % n
r = remote("02.cr.yp.toc.tf", 23010)
for _ in range(9):
r.recvline()
r.sendline('s')
r.recvline()
r.sendline(m1.hex())
u1, v1, w1 = eval(r.recvline()[8:])
u2, v2, w2 = u1, v1 * m % n, w1 * m % n
for _ in range(5):
r.recvline()
r.sendline('v')
r.recvline()
r.sendline(m2.hex())
r.recvline()
r.sendline(','.join(map(str, [u2, v2, w2])))
print(r.recvline().decode().strip().split()[-1])
r.close()
```
##### Flag
> CCTF{__ECC_Bi4seD_N0nCE_53ns3_LLL!!!}
## Double Miff
##### Score: 217 (16/444 solves)
### Challenge
- A new approach, a new attack. Can you attack this curve?
[double_miff.txz](https://cr.yp.toc.tf/tasks/double_miff_58336b2ad5ed82754ac8e9b3bdcc8f25623c909c.txz)
```python=
#!/usr/bin/env python3
from Crypto.Util.number import *
from secret import a, b, p, P, Q
from flag import flag
def onmiff(a, b, p, G):
x, y = G
return (a*x*(y**2 - 1) - b*y*(x**2 - 1)) % p == 0
def addmiff(X, Y):
x_1, y_1 = X
x_2, y_2 = Y
x_3 = (x_1 + x_2) * (1 + y_1*y_2) * inverse((1 + x_1*x_2) * (1 - y_1*y_2), p) % p
y_3 = (y_1 + y_2) * (1 + x_1*x_2) * inverse((1 + y_1*y_2) * (1 - x_1*x_2), p) % p
return (x_3, y_3)
l = len(flag) // 2
m1, m2 = bytes_to_long(flag[:l]), bytes_to_long(flag[l:])
assert m1 < (p // 2) and m2 < (p // 2)
assert onmiff(a, b, p, P) and onmiff(a, b, p, Q)
assert P[0] == m1 and Q[0] == m2
print(f'P + Q = {addmiff(P, Q)}')
print(f'Q + Q = {addmiff(Q, Q)}')
print(f'P + P = {addmiff(P, P)}')
```
```
P + Q = (540660810777215925744546848899656347269220877882, 102385886258464739091823423239617164469644309399)
Q + Q = (814107817937473043563607662608397956822280643025, 961531436304505096581595159128436662629537620355)
P + P = (5565164868721370436896101492497307801898270333, 496921328106062528508026412328171886461223562143)
```
### Solution
We have a curve equation $ax(y^2 - 1) \equiv by(x^2 - 1) \mod p$ with unknown $a$, $b$, $p$; $P$ and $Q$ are some points on it, and we have $P + Q$, $Q + Q$ and $P + P$.
We need to recover $x$-coordinates of $P$ and $Q$, since they contain parts of the flag.
Addition here is commutative and associative, so we have $(P + P) + (Q + Q) = P + P + Q + Q = P + Q + P + Q = (P + Q) + (P + Q)$.
We have 2 ways of representing $x$- and $y$-coordinates of $P + P + Q + Q$. Set $P + Q = (x_1, y_1)$, $Q + Q = (x_2, y_2)$, $P + P = (x_3, y_3)$, $P + P + Q + Q = (x_0, y_0)$. Then from addition formulas for $x$ we have $x0 \equiv \frac{(x_2+x_3)(1+y_2y_3)}{(1+x_2x_3)(1-y_2y_3)} \mod p$ and $x0 \equiv \frac{2x_1(1+y_1^2)}{(1+x_1^2)(1-y_1^2)} \mod p$, from where we get this:
$$p|((1+x_1^2)(1-y_1^2)(x_2+x_3)(1+y_2y_3) - 2x_1(1+y_1^2)(1+x_2x_3)(1-y_2y_3))$$
Analogously from addition formulas for y we get
$$p|((1+y_1^2)(1-x_1^2)(y_2+y_3)(1+x_2x_3)-2y_1(1+x_1^2)(1+y_2y_3)(1-x_2x_3))$$
We can compute gcd of 2 numbers above to get a small multiple of $p$ ($8p$ in this case), and from there we get $p = 1141623079614587900848768080393294899678477852887$.
Recall that for any point on the curve we have $ax(y^2-1) \equiv by(x^2-1) \mod p$, from where we can compute $k \equiv \frac{a}{b} \equiv \frac{y(x^2 - 1)}{x(y^2-1)} \mod p$ by using any known point. Note that we also have $\frac{y}{y^2-1} \equiv k\frac{x}{x^2-1} \mod p$.
Set $P = (x_4, y_4)$, and from addition formulas we get $x_3 \equiv \frac{2x_4(1+y_4^2)}{(1+x_4^2)(1-y_4^2)} \mod p$ and $y_3 \equiv \frac{2y_4(1+x_4^2)}{(1+y_4^2)(1-x_4^2)} \mod p$, from where we get $x_3y_3 \equiv \frac{4x_4y_4}{(x_4^2-1)(y_4^2-1)} \equiv 4k(\frac{x_4}{x_4^2 - 1})^2 \mod p$, and then $(\frac{x_4^2-1}{x_4})^2 \equiv \frac{4k}{x_3y_3} \mod p$.
We have $\frac{x_4^2-1}{x_4} \equiv \pm l \mod p$, where $l \equiv (\frac{4k}{x_3y_3})^{\frac{p+1}{4}} \mod p$, since $p \equiv 3 \mod 4$.
From here we get $x_4^2 \mp lx_4 - 1 \equiv 0 \mod p$. Discriminant in both cases is equal to $D \equiv l^2 + 4 \mod p$, and we get roots of both equations with $\frac{\pm l \pm \sqrt{D}}{2} \mod p$. Check each one of them, the one that results into printable text gives us the first half of the flag. Analogously we can recover $x$-coordinate of $Q$ and get second half of the flag. By concatenating them, we will have the full flag. Judging by the flag, though, this may be an unintended solution.
Implementation script:
```python=
#!/usr/bin/env python3
from Crypto.Util.number import isPrime, long_to_bytes
from math import gcd
x1, y1 = (540660810777215925744546848899656347269220877882, 102385886258464739091823423239617164469644309399)
x2, y2 = (814107817937473043563607662608397956822280643025, 961531436304505096581595159128436662629537620355)
x3, y3 = (5565164868721370436896101492497307801898270333, 496921328106062528508026412328171886461223562143)
num1 = (1 + x1 ** 2) * (1 - y1 ** 2) * (x2 + x3) * (1 + y2 * y3) - 2 * x1 * (1 + y1 ** 2) * (1 + x2 * x3) * (1 - y2 * y3)
num2 = (1 + y1 ** 2) * (1 - x1 ** 2) * (y2 + y3) * (1 + x2 * x3) - 2 * y1 * (1 + x1 ** 2) * (1 + y2 * y3) * (1 - x2 * x3)
pmult = gcd(num1, num2)
for i in range(2, 10):
while pmult % i == 0:
pmult //= i
if isPrime(pmult):
p = pmult
break
def recover_half(x, y):
k = y * (x ** 2 - 1) * pow(x * (y ** 2 - 1), -1, p) % p
l = pow(4 * k * pow(x * y, -1, p), (p + 1) // 4, p)
D = (l ** 2 + 4) % p
sqrtD = pow(D, (p + 1) // 4, p)
for i in range(-1, 2, 2):
for j in range(-1, 2, 2):
num = (i * l + j * sqrtD) * pow(2, -1, p) % p
text = long_to_bytes(num)
if b'CCTF{' in text or b'}' in text:
return text
first_half = recover_half(x3, y3)
second_half = recover_half(x2, y2)
flag = (first_half + second_half).decode()
print(flag)
```
##### Flag
> CCTF{D39enEr47E_ECC_4TtaCk!_iN_Huffs?}
## Symbols
##### Score: 70
### Challenge
> Oh, my eyes, my eyes! People still can solve this kind of cryptography? Mathematicians should love this one!
### Solution
In this challenge, we are given an image of math symbols, from the first couple of symbols and the flag format, we can guess that the flag is the initials of these symbols in $\LaTeX$.
By using Mathpix Snip, a tool that can convert images into LaTeX for inline equations, we can get most of the symbols and get the flag.
```
\Cap \Cap \Theta \Finv { \Pi \ltimes \aleph y _ \wp \infty \therefore \heartsuit _ \Lsh \aleph \Theta \eth \Xi }
```
##### Flag: CCTF{Play_with_LaTeX}
## Onlude
##### Score: 95
### Challenge
> Encryption and Decryption could be really easy, while we expected the decryption to be harder!
```python=
#!/usr/bin/env sage
from sage.all import *
from flag import flag
global p, alphabet
p = 71
alphabet = '=0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ$!?_{}<>'
flag = flag.lstrip('CCTF{').rstrip('}')
assert len(flag) == 24
def cross(m):
return alphabet.index(m)
def prepare(msg):
A = zero_matrix(GF(p), 11, 11)
for k in range(len(msg)):
i, j = 5*k // 11, 5*k % 11
A[i, j] = cross(msg[k])
return A
def keygen():
R = random_matrix(GF(p), 11, 11)
while True:
S = random_matrix(GF(p), 11, 11)
if S.rank() == 11:
_, L, U = S.LU()
return R, L, U
def encrypt(A, key):
R, L, U = key
S = L * U
X = A + R
Y = S * X
E = L.inverse() * Y
return E
A = prepare(flag)
key = keygen()
R, L, U = key
S = L * U
E = encrypt(A, key)
print(f'E = \n{E}')
print(f'L * U * L = \n{L * U * L}')
print(f'L^(-1) * S^2 * L = \n{L.inverse() * S**2 * L}')
print(f'R^(-1) * S^8 = \n{R.inverse() * S**8}')
```
```
E =
[25 55 61 28 11 46 19 50 37 5 21]
[20 57 39 9 25 37 63 31 70 15 47]
[56 31 1 1 50 67 38 14 42 46 14]
[42 54 38 22 19 55 7 18 45 53 39]
[55 26 42 15 48 6 24 4 17 60 64]
[ 1 38 50 10 19 57 26 48 6 4 14]
[13 4 38 54 23 34 54 42 15 56 29]
[26 66 8 48 6 70 44 8 67 68 65]
[56 67 49 61 18 34 53 21 7 48 32]
[15 70 10 34 1 57 70 27 12 33 46]
[25 29 20 21 30 55 63 49 11 36 7]
L * U * L =
[50 8 21 16 13 33 2 12 35 20 14]
[36 55 36 34 27 28 23 21 62 17 8]
[56 26 49 39 43 30 35 46 0 58 43]
[11 25 25 35 29 0 22 38 53 51 58]
[34 14 69 68 5 32 27 4 27 62 15]
[46 49 36 42 26 12 28 60 54 66 23]
[69 55 30 65 56 13 14 36 26 46 48]
[25 48 16 20 34 57 64 62 61 25 62]
[68 39 11 40 25 11 7 40 24 43 65]
[54 20 40 59 52 60 37 14 32 44 4]
[45 20 7 26 45 45 50 17 41 59 50]
L^(-1) * S^2 * L =
[34 12 70 21 36 2 2 43 7 14 2]
[ 1 54 59 12 64 35 9 7 49 11 49]
[69 14 10 19 16 27 11 9 26 10 45]
[70 17 41 13 35 58 19 29 70 5 30]
[68 69 67 37 63 69 15 64 66 28 26]
[18 29 64 38 63 67 15 27 64 6 26]
[ 0 12 40 41 48 30 46 52 39 48 58]
[22 3 28 35 55 30 15 17 22 49 55]
[50 55 55 61 45 23 24 32 10 59 69]
[27 21 68 56 67 49 64 53 42 46 14]
[42 66 16 29 42 42 23 49 43 3 23]
R^(-1) * S^8 =
[51 9 22 61 63 14 2 4 18 18 23]
[33 53 31 31 62 21 66 7 66 68 7]
[59 19 32 21 13 34 16 43 49 25 7]
[44 37 4 29 70 50 46 39 55 4 65]
[29 63 29 43 47 28 40 33 0 62 8]
[45 62 36 68 10 66 26 48 10 6 61]
[43 30 25 18 23 38 61 0 52 46 35]
[ 3 40 6 45 20 55 35 67 25 14 63]
[15 30 61 66 25 33 14 20 60 50 50]
[29 15 53 22 55 64 69 56 44 40 8]
[28 40 69 60 28 41 9 14 29 4 29]
```
### Solution
In this challenge, we are given the source code of an encryption scheme that uses matrix operations for encryption and decryption, the corresponding encrypted flag and some hints.
For the encryption part,
$$ E = L^{-1}Y = L^{-1}SX = L^{-1}LU(A+R) = U(A+R) $$
The three hints we have is $LUL$, $L^{-1}S^2L$ and $R^{-1}S^8$
Since $S=LU$, we can rewrite the second hint as $ULUL$, then we can get $U$ by dividing hint1.
For the third hint $R^{-1}S^8$, we can rewrite it as $R^{-1}(LULU)^4=R^{-1}(h_1U)^4$, then we can get $R$.
With $U$ and $R$ known, we can then recover the flag $A$ from $E$.
```python=
from sage.all import *
E = Matrix(GF(71),[[25,55,61,28,11,46,19,50,37,5,21],
[20,57,39,9,25,37,63,31,70,15,47],
[56,31,1,1,50,67,38,14,42,46,14],
[42,54,38,22,19,55,7,18,45,53,39],
[55,26,42,15,48,6,24,4,17,60,64],
[1,38,50,10,19,57,26,48,6,4,14],
[13,4,38,54,23,34,54,42,15,56,29],
[26,66,8,48,6,70,44,8,67,68,65],
[56,67,49,61,18,34,53,21,7,48,32],
[15,70,10,34,1,57,70,27,12,33,46],
[25,29,20,21,30,55,63,49,11,36,7]])
hint1 = Matrix(GF(71),[[50,8,21,16,13,33,2,12,35,20,14],
[36,55,36,34,27,28,23,21,62,17,8],
[56,26,49,39,43,30,35,46,0,58,43],
[11,25,25,35,29,0,22,38,53,51,58],
[34,14,69,68,5,32,27,4,27,62,15],
[46,49,36,42,26,12,28,60,54,66,23],
[69,55,30,65,56,13,14,36,26,46,48],
[25,48,16,20,34,57,64,62,61,25,62],
[68,39,11,40,25,11,7,40,24,43,65],
[54,20,40,59,52,60,37,14,32,44,4],
[45,20,7,26,45,45,50,17,41,59,50]])
hint2=Matrix(GF(71),[[34,12,70,21,36,2,2,43,7,14,2],
[1,54,59,12,64,35,9,7,49,11,49],
[69,14,10,19,16,27,11,9,26,10,45],
[70,17,41,13,35,58,19,29,70,5,30],
[68,69,67,37,63,69,15,64,66,28,26],
[18,29,64,38,63,67,15,27,64,6,26],
[0,12,40,41,48,30,46,52,39,48,58],
[22,3,28,35,55,30,15,17,22,49,55],
[50,55,55,61,45,23,24,32,10,59,69],
[27,21,68,56,67,49,64,53,42,46,14],
[42,66,16,29,42,42,23,49,43,3,23]])
hint3=Matrix(GF(71),[[51,9,22,61,63,14,2,4,18,18,23],
[33,53,31,31,62,21,66,7,66,68,7],
[59,19,32,21,13,34,16,43,49,25,7],
[44,37,4,29,70,50,46,39,55,4,65],
[29,63,29,43,47,28,40,33,0,62,8],
[45,62,36,68,10,66,26,48,10,6,61],
[43,30,25,18,23,38,61,0,52,46,35],
[3,40,6,45,20,55,35,67,25,14,63],
[15,30,61,66,25,33,14,20,60,50,50],
[29,15,53,22,55,64,69,56,44,40,8],
[28,40,69,60,28,41,9,14,29,4,29]])
U = hint2/hint1
R = (hint3/U/hint1/U/hint1/U/hint1/U/hint1).inverse()
A = U.inverse()*E-R
alphabet = '=0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ$!?_{}<>'
flag = ''
for k in range(24):
i, j = 5*k // 11, 5*k % 11
flag+=alphabet[A[i, j]]
print('CCTF{'+flag+'}')
```
##### Flag: CCTF{LU__D3c0mpO517Ion__4L90?}
## Hyper Normal
##### Score: 71
### Challenge
> Being normal is hard these days because of Corona virus pandemic!
```python=
#!/usr/bin/env python3
import random
from flag import FLAG
p = 8443
def transpose(x):
result = [[x[j][i] for j in range(len(x))] for i in range(len(x[0]))]
return result
def vsum(u, v):
assert len(u) == len(v)
l, w = len(u), []
for i in range(l):
w += [(u[i] + v[i]) % p]
return w
def sprod(a, u):
w = []
for i in range(len(u)):
w += [a*u[i] % p]
return w
def encrypt(msg):
l = len(msg)
hyper = [ord(m)*(i+1) for (m, i) in zip(list(msg), range(l))]
V, W = [], []
for i in range(l):
v = [0]*i + [hyper[i]] + [0]*(l - i - 1)
V.append(v)
random.shuffle(V)
for _ in range(l):
R, v = [random.randint(0, 126) for _ in range(l)], [0]*l
for j in range(l):
v = vsum(v, sprod(R[j], V[j]))
W.append(v)
random.shuffle(transpose(W))
return W
enc = encrypt(FLAG)
print(enc)
```
### Solution
This challenge gives a strange encryption scheme. This encryption algorithm actually does this. For an input of length $l$, the algorithm first multiplies each character of the input by the corresponding index to obtain a vector $x$. Then the algorithm loops $l$ times, each time outputs a vector $v$. Each number in the vector $v$ is a random number between 0 and 126 multiplied by the corresponding number in the vector $x$. All these operations are performed modulo 8443.
It is worth noting that `random.shuffle` on line 38 of the program actually has no effect on the output, because the `transpose` function returns a new object.
Solving for the input is intuitive. For the i-th byte of the input, we simply iterate through all printable characters, multiply $i$ by those characters, and multiply 0 through 126 to get all possible results. If column $i$ of the program output happens to be a subset of the possible results generated by a character $c$, then the i-th byte of the input is likely to be $c$.
```python=
#!/usr/bin/env python3
from string import printable
p = 8443
with open('output.txt', 'r') as f:
enc = eval(f.read())
results = []
for i in range(len(enc[0])):
tmp = []
for j in enc:
tmp.append(j[i])
results.append(tmp)
flag = ''
for idx, result in enumerate(results):
for c in printable:
possibilities = [ord(c)*i*(idx+1) % p for i in range(127)]
if all([i in possibilities for i in result]):
flag += c
break
print(flag)
```
##### Flag: CCTF{H0w_f1Nd_th3_4lL_3I9EnV4Lu35_iN_FiN173_Fi3lD5!???}
Sign in with Wallet
