zer0pts CTF 2021 Crypto Writeups

I participated in zer0pts CTF in Super Guesser, and we reached 1st place.

Since there are many challenges to cover, this writeup will be very concise.

The solution codes may be a bit messy, since I wrote this in a hurry :P

Also, r4j solved signme, so I'll leave that writeup to r4j :D

 

war(sa)mup

from Crypto.Util.number import getStrongPrime, GCD
from random import randint
from flag import flag
import os
 
def pad(m: int, n: int):
  # PKCS#1 v1.5 maybe
  ms = m.to_bytes((m.bit_length() + 7) // 8, "big")
  ns = n.to_bytes((n.bit_length() + 7) // 8, "big")
  assert len(ms) <= len(ns) - 11
 
  ps = b""
  while len(ps) < len(ns) - len(ms) - 3:
    p = os.urandom(1)
    if p != b"\x00":
      ps += p
  return int.from_bytes(b"\x00\x02" + ps + b"\x00" + ms, "big")
 
 
while True:
  p = getStrongPrime(512)
  q = getStrongPrime(512)
  n = p * q
  phi = (p-1)*(q-1)
  e = 1337
  if GCD(phi, e) == 1:
    break
 
m = pad(int.from_bytes(flag, "big"), n)
c1 = pow(m, e, n)
c2 = pow(m // 2, e, n)
 
print("n =", n)
print("e =", e)
print("c1=", c1)
print("c2=", c2)
 

 

Solution

Writing $\lfloor m/2 \rfloor = x$, we see that $m$ is either $2x$ or $2x+1$. If $m = 2x$, we can perform the related message attack with polynomials $$p_1(x) = (2x)^e - c_1, \quad p_2(x) = x^e - c_2$$ Of course, in this case we would have $c_1 \equiv 2^e c_2 \pmod{n}$ and polynomial GCD would be useless. If $m = 2x+1$, we can do it with $$p_1(x) = (2x+1)^e - c_1, \quad p_2(x) = x^e - c_2$$ which works and gives our desired value of $x$. $m$ can be recovered as $2x+1 \pmod{n}$.

 

# sage
n = 113135121314210337963205879392132245927891839184264376753001919135175107917692925687745642532400388405294058068119159052072165971868084999879938794441059047830758789602416617241611903275905693635535414333219575299357763227902178212895661490423647330568988131820052060534245914478223222846644042189866538583089
e = 1337
c1 = 89077537464844217317838714274752275745737299140754457809311043026310485657525465380612019060271624958745477080123105341040804682893638929826256518881725504468857309066477953222053834586118046524148078925441309323863670353080908506037906892365564379678072687516738199061826782744188465569562164042809701387515
c2 = 18316499600532548540200088385321489533551929653850367414045951501351666430044325649693237350325761799191454032916563398349042002392547617043109953849020374952672554986583214658990393359680155263435896743098100256476711085394564818470798155739552647869415576747325109152123993105242982918456613831667423815762
 
P.<x> = PolynomialRing(Zmod(n))
 
def GCD(f, g, n):
    g = g % f
    if g == 0:
        return f
    t = g.lc()
    if gcd(t, n) != 1:
        print(t)
        exit()
    tt = inverse_mod(Integer(t), n)
    g = g * tt
    return GCD(g, f, n)
 
f = (2 * x + 1)^e - c1
g = x^e - c2
 
print(GCD(f, g, n))
 
# back to python
m = -113131683468284119607964196541575421728552328779560800910707074969146190674728631210678514366174908879152073378298687396133007061413453069629241334690374397179449596372765780570923850759894857943624531609494119853246060991087070835093327088258517606688574536921269027653158032526646833175962482267255713310835
n = 113135121314210337963205879392132245927891839184264376753001919135175107917692925687745642532400388405294058068119159052072165971868084999879938794441059047830758789602416617241611903275905693635535414333219575299357763227902178212895661490423647330568988131820052060534245914478223222846644042189866538583089
e = 1337
c1= 89077537464844217317838714274752275745737299140754457809311043026310485657525465380612019060271624958745477080123105341040804682893638929826256518881725504468857309066477953222053834586118046524148078925441309323863670353080908506037906892365564379678072687516738199061826782744188465569562164042809701387515
c2= 18316499600532548540200088385321489533551929653850367414045951501351666430044325649693237350325761799191454032916563398349042002392547617043109953849020374952672554986583214658990393359680155263435896743098100256476711085394564818470798155739552647869415576747325109152123993105242982918456613831667423815762
 
print(n+m)
 
fin = (2 * (n+m) + 1) % n
print(long_to_bytes(fin))

 

OT or NOT OT

import os
import signal
import random
from base64 import b64encode
from Crypto.Util.number import getStrongPrime, bytes_to_long
from Crypto.Util.Padding import pad
from Crypto.Cipher import AES
from flag import flag
 
p = getStrongPrime(1024)
 
key = os.urandom(32)
iv = os.urandom(AES.block_size)
aes = AES.new(key=key, mode=AES.MODE_CBC, iv=iv)
c = aes.encrypt(pad(flag, AES.block_size))
 
key = bytes_to_long(key)
print("Encrypted flag: {}".format(b64encode(iv + c).decode()))
print("p = {}".format(p))
print("key.bit_length() = {}".format(key.bit_length()))
 
signal.alarm(600)
while key > 0:
    r = random.randint(2, p-1)
    s = random.randint(2, p-1)
    t = random.randint(2, p-1)
    print("t = {}".format(t))
 
    a = int(input("a = ")) % p
    b = int(input("b = ")) % p
    c = int(input("c = ")) % p
    d = int(input("d = ")) % p
    assert all([a > 1 , b > 1 , c > 1 , d > 1])
    assert len(set([a,b,c,d])) == 4
 
    u = pow(a, r, p) * pow(c, s, p) % p
    v = pow(b, r, p) * pow(c, s, p) % p
    x = u ^ (key & 1)
    y = v ^ ((key >> 1) & 1)
    z = pow(d, r, p) * pow(t, s, p) % p
 
    key = key >> 2
 
    print("x = {}".format(x))
    print("y = {}".format(y))
    print("z = {}".format(z))
 

 

Solution

The key idea is to make a small subgroup which the values of $x, y \in \mathbb{F}_p$ must belong to.

To do this, we wait until $p \equiv 1 \pmod{4}$, then take any $t \in \mathbb{F}_p$ with order $4$.

This can be done by taking some random $g \in \mathbb{F}_p$ and choosing $t = g^{(p-1)/4}$. 

Checking if order of $t$ is $4$ can now be done simply by verifying $t^2 \neq 1$ in $\mathbb{F}_p$.

 

Now we simply send $a = t$, $b = t^2$, $c = t^3$. Since $a^4 = b^4 = c^4 = 1$, we also have $u^4 = v^4 = 1$.

Therefore, we can see if $x = u$ and if $y= v$ by simply checking if $x^4=1$ and if $y^4=1$.

 

Of course, it should be noted that getStrongPrime does not generate a prime of the form $p=2q+1$ with $q$ prime. :wink:

 

r = remote('crypto.ctf.zer0pts.com', '10130')
 
def recvint():
    s = r.recvline()[:-1]
    s = s.split()[-1]
    return int(s)
 
S = r.recvline()[:-1]
S = S.split()[-1]
V = base64.b64decode(S)
iv = V[:16]
ctxt = V[16:]
 
p = recvint()
keylen = recvint()
 
if p % 4 != 1:
    print("BAD PRIME")
    exit()
 
t = 0
for g in range(2, 2000):
    t = pow(g, (p-1)//4, p)
    if (t * t) % p != 1:
        break
 
print("Begin Key Finding")
keyv = 0
add = 1
for i in tqdm(range(0, 128)):
    t = recvint()
    r.sendline(str(t))
    r.sendline(str((t * t) % p))
    r.sendline(str((t * t * t) % p))
    r.sendline(str(5))
    x = recvint()
    y = recvint()
    z = recvint()
    if pow(x, 4, p) != 1:
        keyv += add
    add = add * 2
    if pow(y, 4, p) != 1:
        keyv += add
    add = add * 2
    if i >= 126:
        keyv = long_to_bytes(keyv)
 
        aes = AES.new(key=keyv, mode=AES.MODE_CBC, iv=iv)
        ptxt = aes.decrypt(ctxt)
        print(ptxt)

 

janken vs yoshiking

import random
import signal
from flag import flag
from Crypto.Util.number import getStrongPrime, inverse
 
HANDNAMES = {
    1: "Rock",
    2: "Scissors",
    3: "Paper"
}
 
def commit(m, key):
    (g, p), (x, _) = key
    r = random.randint(2, p-1)
    c1 = pow(g, r, p)
    c2 = m * pow(g, r*x, p) % p
    return (c1, c2)
 
 
def decrypt(c, key):
    c1, c2 = c
    _, (x, p)= key
 
    m = c2 * inverse(pow(c1, x, p), p) % p
    return m
 
 
def keygen(size):
    p = getStrongPrime(size)
    g = random.randint(2, p-1)
    x = random.randint(2, p-1)
 
    return (g, p), (x, p)
 
 
signal.alarm(3600)
key = keygen(1024)
(g, p), _ = key
print("[yoshiking]: Hello! Let's play Janken(RPS)")
print("[yoshiking]: Here is g: {}, and p: {}".format(g, p))
 
round = 0
wins = 0
while True:
    round += 1
    print("[system]: ROUND {}".format(round))
 
    yoshiking_hand = random.randint(1, 3)
    c = commit(yoshiking_hand, key)
    print("[yoshiking]: my commitment is={}".format(c))
 
    hand = input("[system]: your hand(1-3): ")
    print("")
    try:
        hand = int(hand)
        if not (1 <= hand <= 3):
            raise ValueError()
    except ValueError:
        print("[yoshiking]: Ohhhhhhhhhhhhhhhh no! :(")
        exit()
 
    yoshiking_hand = decrypt(c, key)
    print("[yoshiking]: My hand is ... {}".format(HANDNAMES[yoshiking_hand]))
    print("[yoshiking]: Your hand is ... {}".format(HANDNAMES[hand]))
    result = (yoshiking_hand - hand + 3) % 3
    if result == 0:
        print("[yoshiking]: Draw, draw, draw!!!")
    elif result == 1:
        print("[yoshiking]: Yo! You win!!! Ho!")
        wins += 1
        print("[system]: wins: {}".format(wins))
 
        if wins >= 100:
            break
    elif result == 2:
        print("[yoshiking]: Ahahahaha! I'm the winnnnnnner!!!!")
        print("[yoshiking]: You, good loser!")
        print("[system]: you can check that yoshiking doesn't cheat")
        print("[system]: here's the private key: {}".format(key[1][0]))
        exit()
 
print("[yoshiking]: Wow! You are the king of roshambo!")
print("[yoshiking]: suge- flag ageru")
print(flag)
 

 

Solution

The first observation is that if $g$ is a quadratic residue (QR), the commitment leaks the legendre symbol of $m$.

Indeed, if $g$ is QR, then the legendre symbol of $m$ is simply the legendre symbol of $c_2$.

 

We generate instances until we find a prime $p$ that not all $1, 2, 3$ are QR modulo $p$. 

In this case, by leaking the legendre symbol of $m$, we can reduce the number of candidates for yoshiking's hand from 3 to 2.

Therefore, we can at least force a tie, and occasionally win. This is enough to solve the challenge.

 

r = remote('crypto.ctf.zer0pts.com', '10463')
r.recvline()
 
s = r.recvline()
T = s.split()
g = int(T[4][:-1])
p = int(T[-1].rstrip())
 
 
QR = []
NQR = []
 
if pow(g, (p-1)//2 , p) != 1:
    print("BAD PRIME 1")
    exit()
QR.append(1)
if pow(2, (p-1)//2, p-1) == 1:
    QR.append(2)
else:
    NQR.append(2)
if pow(3, (p-1)//2, p-1) == 1:
    QR.append(3)
else:
    NQR.append(3)
 
if len(QR) == 3:
    print("lol")
    exit()
 
def get_commit():
    s = r.recvline()
    t = s.split(b'(')[-1]
    c1 = int(t.split(b',')[0])
    c2 = int(t.split(b',')[1][1:-2])
    return c1, c2
 
for i in range(0, 500):
    print(r.recvline())
    c1, c2 = get_commit()
    if pow(c2, (p-1) // 2, p) == 1:
        if len(QR) == 1:
            r.sendline(b"3")
        else:
            if 2 in QR:
                r.sendline(b"1")
            else:
                r.sendline(b"3")
    else:
        if len(NQR) == 1:
            if 2 in NQR:
                r.sendline(b"1")
            if 3 in NQR:
                r.sendline(b"2")
        else:
            r.sendline(b"2")
    r.recvline()
    r.recvline()
    r.recvline()
    s = r.recvline()
    if s.split()[-1].rstrip() == b"draw!!!":
        continue
    else:
        s = r.recvline()
        print(s)
        if s.split()[-1].rstrip() == b"100":
            for t in range(0, 4):
                print(r.recvline())

 

easy pseudorandom

from Crypto.Util.number import*
from flag import flag
 
nbits = 256
p = random_prime(1 << nbits)
Fp = Zmod(p)
P.<v> = PolynomialRing(Fp)
 
b = randrange(p)
d = 2
F = v^2 + b
 
v0 = randrange(p)
v1 = F(v0)
 
k = ceil(nbits * (d / (d + 1)))
w0 = (v0 >> (nbits - k))
w1 = (v1 >> (nbits - k))
 
# encrypt
m = bytes_to_long(flag)
v = v1
for i in range(5):
    v = F(v)
    m ^^= int(v)
 
print(f"p = {p}")
print(f"b = {b}")
print(f"m = {m}")
print(f"w0 = {w0}")
print(f"w1 = {w1}")
 

 

Solution

It's clear that we just need to find the value of $v_0$. Denote $l = 256$. Using the given info, we can write $$\begin{equation*} \begin{aligned} v_0 &= w_0 \cdot 2^{l - k} + x \\ v_1 &= w_1 \cdot 2^{l-k} + y \\ v_1 & \equiv v_0^2 + b \pmod{n} \end{aligned} \end{equation*}$$ Combining, this gives us the key relation $$ w_1 \cdot 2^{l-k} + y \equiv w_0^2 \cdot 2^{2l-2k} + b + w_0 \cdot 2^{l-k+1} \cdot x + x^2 \pmod{n}$$ The key idea is to remove the quadratic term $x^2$. Denote $$\begin{equation*} \begin{aligned} A &= w_0 \cdot 2^{l-k+1} \\ B &= w_1 \cdot 2^{l-k} - w_0^2 \cdot 2^{2l-2k} - b \end{aligned} \end{equation*}$$ Note that $A, B$ are constants that we know. Our relation is now $$ Ax \equiv B + y - x^2 \pmod{n}$$ Since $x, y$ are all below $2^{l-k}$, we can see that $$ B - 2^{2l-2k} \le Ax \pmod{n} \le B + 2^{l-k}$$ which is a type of relation that can be solved. Check out my writeups for PBCTF Special Gift and SECCON crypto01.

 

Note that there are $2^{l-k}$ possible values of $x$, and there are approximately $2^{2l-2k}$ possible values of $Ax \pmod{n}$. 

Since $l-k + 2l-2k = 3l-3k \approx l$, we can decide that there must be fairly small number of $x$ that satisfy the desired inequality.

This type of analysis was done in both of writeups above, and recently highlighted by Mystiz in AeroCTF writeup.

 

Now that there are three challenges I solved with this method, I think I'll add this to my CVP repository as well...

 

# notation a bit different from solution, but same idea
 
# simplify polynomial in sage
p = 86160765871200393116432211865381287556448879131923154695356172713106176601077
b = 71198163834256441900788553646474983932569411761091772746766420811695841423780
m = 88219145192729480056743197897921789558305761774733086829638493717397473234815
w0 = 401052873479535541023317092941219339820731562526505
w1 = 994046339364774179650447057905749575131331863844814
 
nbits = 256
P.<x, y> = PolynomialRing(GF(p))
k = (nbits * 2 + 2) // 3
 
f = w0 * 2^(nbits - k) + x
g = w1 * 2^(nbits - k) + y
 
h = g - f^2 - b
print(h)
 
# python
 
def ceil(n, m):
    return (n + m - 1) // m
 
def optf(A, M, L, R):
    if L == 0:
        return 0
    if 2 * A > M:
        L, R = R, L
        A = M - A
        L = M - L
        R = M - R
    cc_1 = ceil(L, A)
    if A * cc_1 <= R:
        return cc_1
    cc_2 = optf(A - M % A, A, L % A, R % A)
    return ceil(L + M * cc_2, A)
 
x = 18867904637006146022735447
y = 19342813113834066795298816
p = 86160765871200393116432211865381287556448879131923154695356172713106176601077
b = 71198163834256441900788553646474983932569411761091772746766420811695841423780
m = 88219145192729480056743197897921789558305761774733086829638493717397473234815
w0 = 401052873479535541023317092941219339820731562526505
w1 = 994046339364774179650447057905749575131331863844814
 
C1 = 55130802749277213576496911760053178817655787149958046010477129311148596128757
C2 = 78083221913223461198494116323396529665894773452683783127339675579334647310194
 
nbits = 256
k = (nbits * 2 + 2) // 3
 
delt = nbits - k
# C1 x + y + C2 - x^2 == 0 mod p
# C1 x == x^2 - y - C2 mod p
 
L = (0 - (1 << (delt)) - C2 + p) % p
R = ((1 << (2 * delt)) - C2 + p) % p
 
lst = 0
while lst <= (1 << delt):
    NL = (L - C1 * (lst + 1)) % p
    NR = (R - C1 * (lst + 1)) % p
    if NL > NR:
        lst = lst + 1
    else:
        cc = optf(C1, p, NL, NR)
        lst = lst + 1 + cc
    mm = m
    x = lst
    v0 = w0 * (1 << (nbits - k)) + x
    v1 = (v0 * v0 + b) % p
    v = v1
    # try out!
    for i in range(5):
        v = (v * v + b) % p
        mm ^= v
    print(long_to_bytes(mm))

 

3-AES

from Crypto.Cipher import AES
from Crypto.Random import get_random_bytes
from binascii import hexlify, unhexlify
from hashlib import md5
import os
import signal
from flag import flag
 
keys = [md5(os.urandom(3)).digest() for _ in range(3)]
 
 
def get_ciphers(iv1, iv2):
    return [
        AES.new(keys[0], mode=AES.MODE_ECB),
        AES.new(keys[1], mode=AES.MODE_CBC, iv=iv1),
        AES.new(keys[2], mode=AES.MODE_CFB, iv=iv2, segment_size=8*16),
    ]
 
def encrypt(m: bytes, iv1: bytes, iv2: bytes) -> bytes:
    assert len(m) % 16 == 0
    ciphers = get_ciphers(iv1, iv2)
    c = m
    for cipher in ciphers:
        c = cipher.encrypt(c)
    return c
 
def decrypt(c: bytes, iv1: bytes, iv2: bytes) -> bytes:
    assert len(c) % 16 == 0
    ciphers = get_ciphers(iv1, iv2)
    m = c
    for cipher in ciphers[::-1]:
        m = cipher.decrypt(m)
    return m
 
signal.alarm(3600)
while True:
    print("==== MENU ====")
    print("1. Encrypt your plaintext")
    print("2. Decrypt your ciphertext")
    print("3. Get encrypted flag")
    choice = int(input("> "))
 
    if choice == 1:
        plaintext = unhexlify(input("your plaintext(hex): "))
        iv1, iv2 = get_random_bytes(16), get_random_bytes(16)
        ciphertext = encrypt(plaintext, iv1, iv2)
        ciphertext = b":".join([hexlify(x) for x in [iv1, iv2, ciphertext]]).decode()
        print("here's the ciphertext: {}".format(ciphertext))
 
    elif choice == 2:
        ciphertext = input("your ciphertext: ")
        iv1, iv2, ciphertext = [unhexlify(x) for x in ciphertext.strip().split(":")]
        plaintext = decrypt(ciphertext, iv1, iv2)
        print("here's the plaintext(hex): {}".format(hexlify(plaintext).decode()))
 
    elif choice == 3:
        plaintext = flag
        iv1, iv2 = get_random_bytes(16), get_random_bytes(16)
        ciphertext = encrypt(plaintext, iv1, iv2)
        ciphertext = b":".join([hexlify(x) for x in [iv1, iv2, ciphertext]]).decode()
        print("here's the encrypted flag: {}".format(ciphertext))
        exit()
 
    else:
        exit()
 

 

Solution

Let's consider plaintexts/ciphertexts of one block first. Denote $E_k$, $D_k$ as ECB encryption/decryption with key $k$.

The encryption process can be written as $$ P \rightarrow E_{k_1}(P) \rightarrow E_{k_2}(E_{k_1}(P) \oplus IV_1) \rightarrow E_{k_2}(E_{k_1}(P) \oplus IV_1) \oplus E_{k_3}(IV_2) = C$$ The key relation is $$E_{k_1}(P) \oplus IV_1 = D_{k_2}(C \oplus E_{k_3}(IV_2))$$ For a fixed value of $C, IV_2$, the right hand side is fixed. Therefore, the left hand side is also fixed.

 

We start by using the decryption oracle with $C, IV_1, IV_2$ being all 16 bytes of \x00. Denote $P_0$ as the resulting plaintext. 

Then, we use the decryption oracle with $C, IV_1, IV_2$ all \x00, but $IV_1$ has the last byte \x01. Denote $P_1$ as the resulting plaintext.

 

Our observations lead to $$\text{bytes_to_long}(E_{k_1}(P_0) \oplus E_{k_1}(P_1)) = 1$$ This can be tested for all $2^{24}$ possible keys, and with that we find $k_1$. 

 

Now that we know $k_1$, we also know the value of $D_{k_2} \circ E_{k_3}$ applied to 16 bytes of \x00.

This is a perfect scenario for a meet-in-the-middle attack, and with this we can find $k_2$, $k_3$. 

 

retrieve data from server

# get data from server
r = remote('crypto.ctf.zer0pts.com', '10929')
 
def get_enc(ptxt):
    r.recvuntil(b">")
    r.sendline(b"1")
    ptxt = bytes.hex(ptxt)
    r.sendline(ptxt)
    s = r.recvline().split()[-1].rstrip()
    iv1, iv2, ctxt = s.split(b":")
    iv1 = bytes.fromhex(iv1.decode())
    iv2 = bytes.fromhex(iv2.decode())
    ctxt = bytes.fromhex(ctxt.decode())
    return iv1, iv2, ctxt
 
def get_dec(ctxt, iv1, iv2):
    r.recvuntil(b">")
    r.sendline(b"2")
    ctxt = bytes.hex(ctxt)
    iv1 = bytes.hex(iv1)
    iv2 = bytes.hex(iv2)
    goal = iv1 + ":" + iv2 + ":" + ctxt
    r.sendline(goal)
    s = r.recvline()
    print(s)
    s = s.split()[-1].rstrip()
    ptxt = bytes.fromhex(s.decode())
    return ptxt
 
def get_flag():
    r.recvuntil(b">")
    r.sendline(b"3")
    s = r.recvline().split()[-1].rstrip()
    iv1, iv2, ctxt = s.split(b":")
    iv1 = bytes.fromhex(iv1.decode())
    iv2 = bytes.fromhex(iv2.decode())
    ctxt = bytes.fromhex(ctxt.decode())
    assert len(iv1) == 16
    assert len(iv2) == 16
    assert len(ctxt) == 48
    return iv1, iv2, ctxt
 
 
f = open("lol.txt", "w")
ptxt_0 = get_dec(b"\x00" * 16, b"\x00" * 16, b"\x00" * 16)
ptxt_1 = get_dec(b"\x00" * 16, b"\x00" * 15 + b"\x01", b"\x00" * 16)
 
 
f.write(str(bytes_to_long(ptxt_0)) + "\n")
f.write(str(bytes_to_long(ptxt_1)) + "\n")
 
iv1, iv2, ctxt = get_flag()
 
f.write(str(bytes_to_long(iv1)) + "\n")
f.write(str(bytes_to_long(iv2)) + "\n")
f.write(str(bytes_to_long(ctxt)) + "\n")
 

 

find the first key

def bytexor(a, b):
    assert len(a) == len(b)
    return bytes(x ^ y for x, y in zip(a, b))
 
for i in tqdm(range(0, 1 << 24)):
    cc = long_to_bytes(i)
    if len(cc) < 3:
        cc = b"\x00" * (3 - len(cc)) + cc
    k1 = hashlib.md5(cc).digest()
    cipher = AES.new(k1, mode = AES.MODE_ECB)
    val_1 = cipher.encrypt(ptxt_0)
    val_2 = cipher.encrypt(ptxt_1)
    det = bytexor(val_1, val_2)
    if bytes_to_long(det) == 1:
        print(i)

 

meet in the middle preparation

# we now know the first key
cipher = AES.new(key = key_1, mode = AES.MODE_ECB)
vv = cipher.encrypt(ptxt_0)
 
f = open("Data1.txt", "w")
for i in tqdm(range(0, 1 << 24)):
    cc = long_to_bytes(i)
    if len(cc) < 3:
        cc = b"\x00" * (3 - len(cc)) + cc
        assert bytes_to_long(cc) == i
    k2 = hashlib.md5(cc).digest()
    cipher = AES.new(key = k2, mode = AES.MODE_ECB)
    res = cipher.encrypt(vv)
    f.write(str(bytes_to_long(res)) + "\n")
 
for i in tqdm(range(0, 1 << 24)):
    cc = long_to_bytes(i)
    if len(cc) < 3:
        cc = b"\x00" * (3 - len(cc)) + cc
    k3 = hashlib.md5(cc).digest()
    cipher = AES.new(key = k3, mode = AES.MODE_ECB)
    res = cipher.encrypt(b"\x00" * 16)
    f.write(str(bytes_to_long(res)) + "\n")
f.close()

 

meet in the middle in C++

map<string, int> M;
 
int main(void)
{
    fio; int i, j;
    freopen("Data1.txt", "r", stdin);
    for(i=0 ; i < (1<<24) ;  i++)
    {
        if(i % 1000000 == 0) cout << i / 1000000 << endl;
        string s; cin >> s;
        M[s] = i;
    }
    for(i=0 ; i<(1<<24) ; i++)
    {
        if(i % 1000000 == 0) cout << i / 1000000 << endl;
        string s; cin >> s;
        if(M[s] != 0)
        {
            cout << M[s] << " " << i << endl;
            return 0;
        }
    }
    return 0;
}

 

NOT Mordell primes

from Crypto.Util.number import bytes_to_long
from secrets import k, FLAG
 
 
p = 13046889097521646369087469608188552207167764240347195472002158820809408567610092324592843361428437763328630003678802379234688335664907752858268976392979073
a = 10043619664651911066883029686766120169131919507076163314397915307085965058341170072938120477911396027902856306859830431800181085603701181775623189478719241
b = 12964455266041997431902182249246681423017590093048617091076729201020090112909200442573801636087298080179764338147888667898243288442212586190171993932442177
 
E = EllipticCurve(GF(p),[a,b])
 
P = E(11283606203023552880751516189906896934892241360923251780689387054183187410315259518723242477593131979010442607035913952477781391707487688691661703618439980, 12748862750577419812619234165922125135009793011470953429653398381275403229335519006908182956425430354120606424111151410237675942385465833703061487938776991)
Q = k*P
R = (k+1)*P
 
p = int(Q[0])
q = int(R[0])
 
assert is_prime(p)
assert is_prime(q)
 
e = 0x10001
N = p*q
m = bytes_to_long(FLAG)
c = pow(m,e,N)
 
print(f'N = {N}')
print(f'c = {c}')
 

 

Solution

Denote $P = (u, v)$, $Q = (x, y)$. We can utilize the sum of points formula to get the x-coordinate of $R$ as $$ \left( \frac{y-v}{x-u} \right)^2 - (x + u)$$ Therefore, we have the relation $$ g(x, y) = x(y-v)^2 - (x+u)(x-u)^2 - N(x-u)^2 \equiv 0 \pmod{p}$$ We now have to combine this relation with $$y^2 \equiv x^3 + ax + b \pmod{p}$$ Initially I tried to calculate the resultant, but it bugged out (maybe due to incorrect parameters given) so I changed my approach.

 

If we print out the monomials of $g(x, y)$, we see that $y$ appears in two monomials, $xy^2$ and $xy$.

We can change $y^2$ as $x^3 + ax + b$ in the first one. Now we can drag the $xy$ term into the right hand side, square the equation, and change $y^2$ to $x^3 + ax + b$ to obtain a equation with only one variable $x$. For more details, please refer to the solution code.

 

This polynomial equation can now be solved, which gives us the candidates for the prime divisor of $N$. 

 

pytp = 13046889097521646369087469608188552207167764240347195472002158820809408567610092324592843361428437763328630003678802379234688335664907752858268976392979073
a = 10043619664651911066883029686766120169131919507076163314397915307085965058341170072938120477911396027902856306859830431800181085603701181775623189478719241
b = 12964455266041997431902182249246681423017590093048617091076729201020090112909200442573801636087298080179764338147888667898243288442212586190171993932442177
 
E = EllipticCurve(GF(p),[a,b])
 
G = E(11283606203023552880751516189906896934892241360923251780689387054183187410315259518723242477593131979010442607035913952477781391707487688691661703618439980, 12748862750577419812619234165922125135009793011470953429653398381275403229335519006908182956425430354120606424111151410237675942385465833703061487938776991)
u = G[0]
v = G[1]
 
N = 22607234899418506929126001268361871457071114354768385952661316782742548112938224795906631400222949082488044126564531809419277303594848211922000498018284382244900831520857366772119155202621331079644609558409672584261968029536525583401488106146231216232578818115404806474812984250682928141729397248414221861387
c = 15850849981973267982600456876579257471708532525108633915715902825196241000151529259632177065183069032967782114646012018721535909022877307131272587379284451827627191021621449090672315265556221217089055578013603281682705976215360078119427612168005716370941190233189775697324558168779779919848728188151630185987
 
P.<x, y> = PolynomialRing(GF(p))
f = y ** 2 - x ** 3 - a * x - b
g = x * ((y - v) * (y - v)  - (x + u) * (x-u) * (x-u)) - N * (x-u) * (x-u)
 
print(g.monomials())
# [x^4, x^3, xy^2, x^2, xy, x, 1]
 
T = g.coefficients()
P.<x> = PolynomialRing(Zmod(p))
f = 0
g = 0
f += T[0] * x^4
f += T[1] * x^3 
f += T[2] * x * (x^3 + a* x + b)
f += T[3] * x^2 
f += T[5] * x
f += T[6]
 
g += T[4] * T[4] * x^2 * (x^3 + a*x + b)
 
 
h = f * f - g 
 
print(h.roots())
 
N = 22607234899418506929126001268361871457071114354768385952661316782742548112938224795906631400222949082488044126564531809419277303594848211922000498018284382244900831520857366772119155202621331079644609558409672584261968029536525583401488106146231216232578818115404806474812984250682928141729397248414221861387
c = 15850849981973267982600456876579257471708532525108633915715902825196241000151529259632177065183069032967782114646012018721535909022877307131272587379284451827627191021621449090672315265556221217089055578013603281682705976215360078119427612168005716370941190233189775697324558168779779919848728188151630185987
 
# cand = h.roots()
cand = [(5266647903652352665309561331835186152327627163271331811555419978564191000470060566535428497675116887002541568904535904345037425011015457585262022604897451, 1), (4292528248136861387890911319917455946841411872473250675409509735620572311636407361858881556677385609500178629430025710517411214702704597103005396234440737, 1), (11283606203023552880751516189906896934892241360923251780689387054183187410315259518723242477593131979010442607035913952477781391707487688691661703618439980, 2)]
 
for p, t in cand:
    q = N // p
    phi = (p-1) * (q-1)
    print(p * q - N)
    d = inverse(65537, phi)
    print(long_to_bytes(pow(c, d, N)))

 

pure division

from Crypto.Util.number import *
from flag import flag
 
assert len(flag) == 40
 
p = 74894047922780452080480621188147614680859459381887703650502711169525598419741
a1 = 22457563127094032648529052905270083323161530718333104214029365341184039143821
a2 = 82792468191695528560800352263039950790995753333968972067250646020461455719312
Fp = Zmod(p^3)
E = EllipticCurve(Fp, [a1, a2])
 
m = bytes_to_long(flag)
S = E(201395103510950985196528886887600944697931024970644444173327129750000389064102542826357168547230875812115987973230106228243893553395960867041978131850021580112077013996963515239128729448812815223970675917812499157323530103467271226, 217465854493032911836659600850860977113580889059985393999460199722148747745817726547235063418161407320876958474804964632767671151534736727858801825385939645586103320316229199221863893919847277366752070948157424716070737997662741835)
T = m * S
 
with open("output.txt", "w") as f:
    f.write("T: {}".format(T))
 
 

 

Solution

The required paper for this challenge is https://arxiv.org/pdf/2010.15543.pdf.

Basically, (like a few challenges this year) we need a homomorphism to a group we can efficiently calculate discrete logarithm on.

It turns out that the given elliptic curve over $\mathbb{Z}_{p^3}$ has a homomorphism to $\mathbb{Z}_{p^2}$.

UPD : It should also be noted that the binary operator in $\mathbb{Z}_{p^2}$ is sum, not product.

 

To calculate this, we need to know how to perform point multiplication in a projective curve/division free setting.

The formula for this can be found online, for example, here. I wonder if this computation can be done in sage...

 

 
N = 74894047922780452080480621188147614680853399736985793708596679454987247185378
# N is the order of the same elliptic curve, except the underlying field is GF(p) instead of ring Z/p^3Z
p = 74894047922780452080480621188147614680859459381887703650502711169525598419741
a = 22457563127094032648529052905270083323161530718333104214029365341184039143821
b = 82792468191695528560800352263039950790995753333968972067250646020461455719312
mod = p * p * p
 
def point_double(x, y, z):
    t = (3 * x * x + a * z * z) % mod
    u = (2 * y * z) % mod
    v = (2 * u * x * y) % mod
    w = (t * t - 2 * v + mod * 3) % mod
    x2 = (u * w) % mod 
    y2 = (t * (v - w) - 2 * (u * u * y * y)) % mod
    y2 = (y2 + mod) % mod
    z2 = (u * u * u) % mod
    return x2, y2, z2
 
def point_add(x0, y0, z0, x1, y1, z1):
    if x0 == 0 and y0 == 0:
        return x1, y1, z1
    if x1 == 0 and y1 == 0:
        return x0, y0, z0
    t0 = (y0 * z1) % mod
    t1 = (y1 * z0) % mod
    t = (t0 - t1 + mod) % mod
    u0 = (x0 * z1) % mod
    u1 = (x1 * z0) % mod
    u = (u0 - u1 + mod) % mod
    u2 = (u * u) % mod
    v = (z0 * z1) % mod
    w = (t * t * v - u2 * (u0 + u1)) % mod 
    w = (w + mod) % mod
    u3 = (u * u2) % mod
    x2 = (u * w) % mod
    y2 = (t * (u0 * u2 - w) - t0 * u3) % mod
    y2 = (y2 + mod) % mod
    z2 = (u3 * v) % mod
    return x2, y2, z2
 
def point_mul(x, y, z, n):
    xr, yr, zr = 0, 0, 1
    while n:
        if n % 2 == 1:
            xr, yr, zr = point_add(xr, yr, zr, x, y, z)
            n -= 1
        n = n // 2
        x, y, z = point_double(x, y, z)
    return xr, yr, zr
 
x1 = 201395103510950985196528886887600944697931024970644444173327129750000389064102542826357168547230875812115987973230106228243893553395960867041978131850021580112077013996963515239128729448812815223970675917812499157323530103467271226
y1 = 217465854493032911836659600850860977113580889059985393999460199722148747745817726547235063418161407320876958474804964632767671151534736727858801825385939645586103320316229199221863893919847277366752070948157424716070737997662741835
 
x2 = 49376632602749543055345783411902198690599351794957124343389298933965298693663616388441379424236401744560279599744281594405742089477317921152802669021421009909184865835968088427615238677007575776072993333868804852765473010336459028 
y2 = 342987792080103175522504176026047089398654876852013925736156942540831035248585067987750805770826115548602899760190394686399806864247192767745458016875262322097116857255158318478943025083293316585095725393024663165264177646858125759
 
print((y1 ** 2 - x1 ** 3 - a * x1 - b) % mod)
print((y2 ** 2 - x2 ** 3 - a * x2 - b) % mod)
 
xf, yf, zf = point_mul(x1, y1, 1, N)
xs, ys, zs = point_mul(x2, y2, 1, N)
 
A = xs * yf
B = ys * xf
g = GCD(A, B)
A //= g
B //= g
 
gg = (A * inverse(B, p * p)) % p
 
 
for i in range(0, 2):
    cc = bytes_to_long(b"zer0pts{")
    val = (gg - cc * (1 << 256)) % p + i * p
    flag = b"zer0pts{" + long_to_bytes(val)
    print(flag)

 

Tokyo Network

import base64
import random
from Crypto.Cipher import AES
from Crypto.Random import get_random_bytes
from Crypto.Util.Padding import pad
from qulacs import QuantumState, QuantumCircuit
from qulacs.gate import *
from secret import flag
 
GATES = {
    'CNOT': (CNOT, 2),
    'H': (H, 1), 'X': (X, 1), 'Y': (Y, 1), 'Z': (Z, 1),
    'S': (S, 1), 'SDAG': (Sdag, 1), 'T': (T, 1), 'TDAG': (Tdag, 1)
}
def parse_circuit(asm, qbits=9):
    """ Convert assembly into quantum circuit
    i.e.  q0 ---+--[Z]--
                |        <= CNOT 0,1; Z 0; H 1;
          q1 --[X]-[H]--
    """
    def apply(gate, args):
        return gate(*args)
 
    circuit = QuantumCircuit(qbits)
    cnt = 0
    for instruction in asm.replace('\n', '').split(';'):
        t = instruction.strip().split()
        if t == []:
            continue
 
        if len(t) < 2:
            print("[-] Invalid instruction")
            exit(0)
 
        opecode, operand = t[0].upper(), t[1:]
        if opecode not in GATES:
            print("[-] Invalid gate")
            exit(0)
 
        operand = list(map(lambda x: int(x), ''.join(t[1:]).split(',')))
        if not all(map(lambda x: 0 <= x < qbits, operand)):
            print("[-] Invalid quantum bit specified")
            exit(0)
 
        if GATES[opecode][1] != len(operand):
            print("[-] Invalid number of operands")
            exit(0)
 
        gate = apply(GATES[opecode][0], operand)
        circuit.add_gate(gate)
 
        cnt += 1
        if cnt > 100:
            print("[-] Too large circuit")
            exit(0)
 
    return circuit
 
def transfer_and_measure(q):
    # Oops, noise might happen :(
    noise = QuantumCircuit(9)
    idx = random.randrange(0, 9)
    noise.add_gate(DephasingNoise(idx, 0.31337))
    noise.add_gate(DepolarizingNoise(idx, 0.31337))
    noise.add_gate(BitFlipNoise(idx, 0.31337))
    noise.update_quantum_state(q)
 
    # Quantum arrived! You can update (or keep) the state :)
    circuit = parse_circuit(input('[?] Your Circuit: '))
    circuit.update_quantum_state(q)
 
    # Now you measure the quantum state :P
    return random.choices(range(2**9),
                          map(lambda x: abs(x), q.get_vector()))[0] & 1
 
if __name__ == '__main__':
    N = 128
    xi, xip = 0.98, 0.98
    p = (xi * (1 + xi))**0.5 - xi
    Np = int(N * (1 + 2*xi + 2*(xi*(1+xi))**0.5 + xip))
    print("[+] Np = " + str(Np))
 
    encoder = parse_circuit("""
    CNOT 0,3; CNOT 0,6;
    H 0; H 3; H 6;
    CNOT 0,1; CNOT 0,2;
    CNOT 3,4; CNOT 3,5;
    CNOT 6,7; CNOT 6,8;
    """)
 
    measured = 0
    ra, ba = 0, 0
    for i in range(Np):
        ra = (ra << 1) | random.choice([0, 1])
        ba = (ba << 1) | random.choices([1, 0], [p, 1-p])[0]
        q = QuantumState(9)
        q.set_zero_state()
        if ra & 1:
            X(0).update_quantum_state(q)
        if ba & 1:
            H(0).update_quantum_state(q)
        encoder.update_quantum_state(q)
 
        measured = (measured << 1) | transfer_and_measure(q)
        del q
 
    print("[+] Measured state: " + bin(measured))
    bb = int(input('[?] bb = '), 2)
    print("[+] ba = " + bin(ba))
 
    Nx, Nz = 0, 0
    for i in range(Np):
        if (ba >> i) & 1 == (bb >> i) & 1 == 1:
            Nx += 1
        elif (ba >> i) & 1 == (bb >> i) & 1 == 0:
            Nz += 1
    if Nx < N * xi or Nz - N < N * xi:
        print("[-] Something went wrong :(")
        exit(0)
 
    xa = 0
    for i in range(Np):
        if (ba >> i) & 1 == (bb >> i) & 1 == 1:
            xa = (xa << 1) | ((ra >> i) & 1)
    print("[+] xa = " + bin(xa))
 
    l = []
    for i in range(Np):
        if (ba >> i) & 1 == (bb >> i) & 1 == 0:
            l.append(i)
    chosen = random.sample(l, Nz - N)
    m = 0
    for i in chosen:
        m |= 1 << i
    print("[+] m = " + bin(m))
 
    k = 0
    for i in sorted(list(set(l) - set(chosen))):
        k = (k << 1) | ((ra >> i) & 1)
 
    key = int.to_bytes(k, N // 8, 'big')
    iv = get_random_bytes(AES.block_size)
    cipher = AES.new(key, AES.MODE_CBC, iv)
    ct = cipher.encrypt(pad(flag, AES.block_size))
    print("Result: " + base64.b64encode(iv + ct).decode())
 

 

Solution

The context of this challenge is quite nice - it's quantum error correction with Shor and QKD with BB84.

I realized the BB84 part of the program after I read the flag, but if you look at it knowing it's BB84, it's quite clear.

 

Working backwards, we observe the following and eventually find the solution

• our final goal is to find the AES key $k$
• we know $ba$ and $m$, and we are free to choose $bb$, so we know the array $l$ and $chosen$
• therefore, our goal is to find the bits of $ra$ in the indexes of $l \setminus chosen$
• note that in those indexes, we have $ba$ and $bb$ bits all $0$
• we see that this implies we don't need to worry about Hadamard gates
• we only need to check whether or not X gate was applied at the 0th qubit
• if there was no encoding and noise, we could just measure the 0th qubit to see whether 0 or 1 pops out
• however, we have encoding and noise : how do we deal with this?
• it turns out that the encoding part is simply the first part of Shor's quantum error correction code
• therefore, we can just send the remaining part of the Shor's quantum error correction code and be done with it
• note that our noise is single qubit, so we have no worries whatsoever
• however, we need Toffoli gates to make the circuit : we don't have that in our arsenal of gates
• this can be resolved by creating Toffoli gates with 2-qubit gates and single qubit gates : details are in Wikipedia.

from qulacs import QuantumCircuit, QuantumState
from qulacs.gate import *
import random
from pwn import *
from Crypto.Cipher import AES
import base64
 
 
# CNOT gate
def ADD_CNOT(a, b):
    return "CNOT " + str(a) + "," + str(b) + "; "
 
# single qubit gates
def ADD_single(s, a):
    return s + " " + str(a) + "; "
 
# toffoli
def ADD_toffoli(a, b, c): 
    ret = ""
    ret += ADD_single("H", c)
    ret += ADD_CNOT(b, c)
 
    ret += ADD_single("TDAG", c)
    ret += ADD_CNOT(a, c)
 
    ret += ADD_single("T", c)
    ret += ADD_CNOT(b, c)
 
    ret += ADD_single("TDAG", c)
    ret += ADD_CNOT(a, c)
 
    ret += ADD_single("T", b)
    ret += ADD_single("T", c)
 
    ret += ADD_CNOT(a, b)
    ret += ADD_single("H", c)
 
    ret += ADD_single("T", a)
    ret += ADD_single("TDAG", b)
 
    ret += ADD_CNOT(a, b)
 
    return ret 
 
 
 
N = 128
xi, xip = 0.98, 0.98
p = (xi * (1 + xi))**0.5 - xi
Np = int(N * (1 + 2*xi + 2*(xi*(1+xi))**0.5 + xip))
 
# shor error correction
decoder = ""
decoder += ADD_CNOT(0, 1)
decoder += ADD_CNOT(3, 4)
decoder += ADD_CNOT(6, 7)
decoder += ADD_CNOT(0, 2)
decoder += ADD_CNOT(3, 5)
decoder += ADD_CNOT(6, 8)
decoder += ADD_toffoli(1, 2, 0)
decoder += ADD_toffoli(4, 5, 3)
decoder += ADD_toffoli(7, 8, 6)
decoder += ADD_single("H", 0)
decoder += ADD_single("H", 3)
decoder += ADD_single("H", 6)
decoder += ADD_CNOT(0, 3)
decoder += ADD_CNOT(0, 6)
decoder += ADD_toffoli(3, 6, 0)
 
r = remote('others.ctf.zer0pts.com', '11099')
 
def get_bin():
    s = r.recvline()
    s = s.split()[-1].decode()
    return int(s, 2)
 
r.recvline()
for i in range(0, 860):
    r.sendline(decoder)
 
measure = get_bin()
bb = (1 << 400) - 1
r.sendline(bin(bb))
 
ba = get_bin()
xa = get_bin()
m = get_bin()
 
l = []
for i in range(Np):
    if (ba >> i) & 1 == (bb >> i) & 1 == 0:
        l.append(i)
 
chosen = []
for i in range(Np):
    if (m & (1 << i)) > 0:
        chosen.append(i)
 
k = 0
for i in sorted(list(set(l) - set(chosen))):
    k = (k << 1) | ((measure >> i) & 1)
 
key = int.to_bytes(k, N // 8, 'big')
s = r.recvline()
vv = s.split()[-1]
 
fin = base64.b64decode(vv)
iv = fin[:16]
ct = fin[16:]
 
cipher = AES.new(key, AES.MODE_CBC, iv)
print(cipher.decrypt(ct))