# corCTF 2021
## fibinary (424 solves / 205 points)
Warmup your crypto skills with the superior number system!
:::spoiler **Source Code**
```python=
fib = [1, 1]
for i in range(2, 11):
fib.append(fib[i - 1] + fib[i - 2])
def c2f(c):
n = ord(c)
b = ''
for i in range(10, -1, -1):
if n >= fib[i]:
n -= fib[i]
b += '1'
else:
b += '0'
return b
flag = open('flag.txt', 'r').read()
enc = ''
for c in flag:
enc += c2f(c) + ' '
with open('flag.enc', 'w') as f:
f.write(enc.strip())
```
:::
只是將數字用費氏進制表示，直接復原即可。
:::spoiler **Script**
```python=
from flag import *
fib = [1, 1]
for i in range(2, 11):
fib.append(fib[i - 1] + fib[i - 2])
def f2c(f):
n = 0
for i in range(11):
if f[i] == '1':
n += fib[10-i]
return chr(n)
arr = res.split(' ')
pt = ''.join([f2c(a) for a in arr])
print(pt)
```
:::
:::success
corctf{b4s3d_4nd_f1bp!113d}
:::
## 4096 (219 solves / 360 points)
I heard 4096 bit RSA is secure, so I encrypted the flag with it.
:::spoiler **Source Code**
```python=
from Crypto.Util.number import getPrime, bytes_to_long
from private import flag
def prod(lst):
ret = 1
for num in lst:
ret *= num
return ret
m = bytes_to_long(flag)
primes = [getPrime(32) for _ in range(128)]
n = prod(primes)
e = 65537
print(n)
print(pow(m, e, n))
```
:::
可能數字太大，factordb 不幫忙分解，但我們可以用 https://www.alpertron.com.ar/ECM.HTM ，他算完也會順便把 phi 給印出來，只是會多了點空格。
:::spoiler **Script**
```python=
from output import *
phi = int("50630 446119 693744 932461 043333 634783 952051 644613 410121 323489 034422 807019 677354 031739 581870 482619 482860 819343 267054 008700 977659 650718 829660 461876 942893 133477 358593 434676 989586 248177 570454 365001 582389 610668 271321 166565 650228 525780 765989 609094 461220 562408 822736 334977 906611 729138 831495 445185 451623 783975 295039 557448 719141 834661 301339 760916 576010 363494 254684 260206 557703 260308 938319 802628 615765 422490 143303 529563 080526 610841 724840 591497 599497 360984 340956 739856 808175 441141 377318 213666 570788 835355 471236 387209 017427 892378 341022 650827 644422 889938 135411 113030 082353 658208 901971 976350 841884 168102 577265 906610 030720 102052 642431 165813 898438 042427 758601 167728 641439 100076 464696 070534 292418 692769 437821 099336 065417 871836 318616 267748 948100 850767 083401 006701 653842 285810 851463 941603 607993 871506 802916 872636 491885 159050 459177 091144 835682 790614 678827 490727 138198 753404 587783 007010 636851 848804 247653 604973 416488 483436 564313 254309 247613 450920 163788 495274 159250 259350 308019 456989 775542 822771 334995 680378 173998 980030 514255 202267 440777 540243 752596 967787 419550 405974 660231 031461 184788 339891 694891 682898 269179 384007 727265 853852 557473 219616 275869 787754 919630 376462 425596 077316 475121 261511 652147 200000 000000 000000 000000 000000 000000 000000 000000".replace(' ', ''))
pt = pow(c, pow(65537, -1, phi), n)
from Crypto.Util.number import *
flag = long_to_bytes(pt)
print(flag)
```
:::
:::success
corctf{to0_m4ny_pr1m3s55_63aeea37a6b3b22f}
:::
## dividing_secrets (121 solves / 434 points)
I won't give you the secret. But, I'll let you divide it.
:::spoiler **Source Code**
```python=
from Crypto.Util.number import bytes_to_long, getStrongPrime
from random import randrange
from secret import flag
LIMIT = 64
def gen():
p = getStrongPrime(512)
g = randrange(1, p)
return g, p
def main():
g, p = gen()
print("g:", str(g))
print("p:", str(p))
x = bytes_to_long(flag)
enc = pow(g, x, p)
print("encrypted flag:", str(enc))
ctr = 0
while ctr < LIMIT:
try:
div = int(input("give me a number> "))
print(pow(g, x // div, p))
ctr += 1
except:
print("whoops..")
return
print("no more tries left... bye")
main()
```
:::
注意到， $$g^x \times g^{-div \cdot\lfloor\frac{x}{div}\rfloor} \equiv g^{x \% div} \pmod{p}$$
當 $div$ 很小時，我們可以暴搜出 $x \% div$ 的值。所以直接給足夠多的 $div$，然後用中國剩餘定理便能求得 $x$。
:::spoiler **Script**
```python=
from pwn import *
from Crypto.Util.number import *
### prepare lots of primes in order to apply CRT
primes = []
for i in range(13333, 20000):
if isPrime(i):
primes.append(i)
if len(primes) == 64:
break
r = remote('crypto.be.ax', 6000)
r.recvuntil("g:")
g = int(r.recvline().strip())
r.recvuntil("p:")
P = int(r.recvline().strip())
r.recvuntil("encrypted flag:")
enc_flag = int(r.recvline().strip())
residues = []
for p in primes:
r.recvuntil("give me a number> ")
r.sendline(str(p))
res = int(r.recvline().strip())
_ = pow(res, p, P)
for i in range(p):
if _ == enc_flag:
residues.append(i)
_ = (_ * g) % P
r.close()
product = 1
for p in primes:
product *= p
CRT = 0
for p, r in zip(primes, residues):
CRT += (r * pow(product // p, -1, p) * product // p) % product
CRT %= product
flag = long_to_bytes(CRT)
print(flag)
```
:::
:::success
corctf{qu4drat1c_r3s1due_0r_n0t_1s_7h3_qu3st1on8852042051e57492}
:::
## supercomputer (85 solves / 457 points)
I ran this code with a supercomputer from the future to encrypt the flag, just get your own and decryption should be simple!
:::spoiler **Source Code**
```python=
from Crypto.Util.number import getPrime, long_to_bytes
from pwn import *
import random, binascii
flag = open('flag.txt').read()
def v(p, k):
ans = 0
while k % p == 0:
k /= p
ans += 1
return ans
p, q, r = getPrime(2048), getPrime(2048), getPrime(2048)
print(p, q, r)
n = pow(p, q) * r
a1 = random.randint(0, n)
a2 = n - a1
assert a1 % p != 0 and a2 % p != 0
t = pow(a1, n) + pow(a2, n)
print(binascii.hexlify(xor(flag, long_to_bytes(v(p, t)))))
```
:::
直接裸考 LTE ...，若 $p \not\mid a_1,a_2$, $p \mid a_1+a_2$ 並且 $n$ 為奇數，那麼我們有 $$v_p\left(a_1^n+a_2^n\right) = v_p\left(a_1+a_2\right)+v_p\left(n\right)$$
在這題的情況就是 $$v_p(t) = v_p(a_1^n+a_2^n) = v_p(a_1+a_2)+vp(n) = 2v_p(n) = 2q$$
我們把 $2q$ 拿去 xor 即能得到 flag。這邊要注意的是 pwntools 內建的 xor 有長度限制，那分塊 xor 就好了啊！
:::spoiler **Script**
```python=
from output import *
from pwn import *
import binascii
from Crypto.Util.number import bytes_to_long, long_to_bytes
Vp_t = long_to_bytes(2 * q)
res = binascii.unhexlify(res)
flag = xor(Vp_t, res[:257])
print(flag)
```
:::
:::success
corctf{1_b3t_y0u_d1dnt_4ctu411y_d0_th3_m4th_d1d_y0u?}
:::
## babyrsa (50 solves / 476 points)
discord is the best place to store secrets
:::spoiler **Source Code**
```python=
from Crypto.Util.number import bytes_to_long
n = 73542616560647877565544036788738025202939381425158737721544398356851787401183516163221837013929559568993844046804187977705376289108065126883603562904941748653607836358267359664041064708762154474786168204628181667371305788303624396903323216279110685399145476916585122917284319282272004045859138239853037072761
e = 0x10001
flag = bytes_to_long(open("flag.txt", "rb").read())
print(f"n = {n}")
print(f"e = {e}")
print(f"ct = {pow(flag, e, n)}")
print("""
Transcription of image:
735426165606478775655440367887380252029393814251587377215443983568517874011835161632
289108065126883603562904941748653607836358267359664041064708762154474786168204628181
9145476916585122917284319282272004045859138239853037072761
108294440701045353595867242719660522374526250640690193563048263854806748525172379331
341078269246532299656864881223
679098724593514422867704492870375465007225641192338424726642090768164214390632598250
39563231146143146482074105407
(n, p, q)
""")
```
:::
所以我們有 $p,q$ 的高低位，用雙變數的 coppersmith 便能求得中間的 bits。
:::spoiler **Script**
```python=
n = 73542616560647877565544036788738025202939381425158737721544398356851787401183516163221837013929559568993844046804187977705376289108065126883603562904941748653607836358267359664041064708762154474786168204628181667371305788303624396903323216279110685399145476916585122917284319282272004045859138239853037072761
e = 65537
ct = 2657054880167593054409755786316190176139048369036893368834913798649283717358246457720021168590230987384201961744917278479195838455294205306264398417522071058105245210332964380113841646083317786151272874874267948107036095666198197073147087762030842808562672646078089825632314457231611278451324232095496184838
p_h = 108294440701045353595867242719660522374526250640690193563048263854806748525172379331
p_l = 341078269246532299656864881223
q_h = 679098724593514422867704492870375465007225641192338424726642090768164214390632598250
q_l = 39563231146143146482074105407
def coron(pol, X, Y, k=2, debug=False):
"""
Returns all small roots of pol.
Applies Coron's reformulation of Coppersmith's algorithm for finding small
integer roots of bivariate polynomials modulo an integer.
Args:
pol: The polynomial to find small integer roots of.
X: Upper limit on x.
Y: Upper limit on y.
k: Determines size of lattice. Increase if the algorithm fails.
debug: Turn on for debug print stuff.
Returns:
A list of successfully found roots [(x0,y0), ...].
Raises:
ValueError: If pol is not bivariate
"""
if pol.nvariables() != 2:
raise ValueError("pol is not bivariate")
P.<x,y> = PolynomialRing(ZZ)
pol = pol(x,y)
# Handle case where pol(0,0) == 0
xoffset = 0
while pol(xoffset,0) == 0:
xoffset += 1
pol = pol(x+xoffset,y)
# Handle case where gcd(pol(0,0),X*Y) != 1
while gcd(pol(0,0), X) != 1:
X = next_prime(X, proof=False)
while gcd(pol(0,0), Y) != 1:
Y = next_prime(Y, proof=False)
pol = P(pol/gcd(pol.coefficients())) # seems to be helpful
p00 = pol(0,0)
delta = max(pol.degree(x),pol.degree(y)) # maximum degree of any variable
W = max(abs(i) for i in pol(x*X,y*Y).coefficients())
u = W + ((1-W) % abs(p00))
N = u*(X*Y)^k # modulus for polynomials
# Construct polynomials
p00inv = inverse_mod(p00,N)
polq = P(sum((i*p00inv % N)*j for i,j in zip(pol.coefficients(),
pol.monomials())))
polynomials = []
for i in range(delta+k+1):
for j in range(delta+k+1):
if 0 <= i <= k and 0 <= j <= k:
polynomials.append(polq * x^i * y^j * X^(k-i) * Y^(k-j))
else:
polynomials.append(x^i * y^j * N)
# Make list of monomials for matrix indices
monomials = []
for i in polynomials:
for j in i.monomials():
if j not in monomials:
monomials.append(j)
monomials.sort()
# Construct lattice spanned by polynomials with xX and yY
L = matrix(ZZ,len(monomials))
for i in range(len(monomials)):
for j in range(len(monomials)):
L[i,j] = polynomials[i](X*x,Y*y).monomial_coefficient(monomials[j])
# makes lattice upper triangular
# probably not needed, but it makes debug output pretty
L = matrix(ZZ,sorted(L,reverse=True))
if debug:
print("Bitlengths of matrix elements (before reduction):")
print(L.apply_map(lambda x: x.nbits()).str())
L = L.LLL()
if debug:
print("Bitlengths of matrix elements (after reduction):")
print(L.apply_map(lambda x: x.nbits()).str())
roots = []
for i in range(L.nrows()):
if debug:
print("Trying row {}".format(i))
# i'th row converted to polynomial dividing out X and Y
pol2 = P(sum(map(mul, zip(L[i],monomials)))(x/X,y/Y))
r = pol.resultant(pol2, y)
if r.is_constant(): # not independent
continue
for x0, _ in r.univariate_polynomial().roots():
if x0-xoffset in [i[0] for i in roots]:
continue
if debug:
print("Potential x0:",x0)
for y0, _ in pol(x0,y).univariate_polynomial().roots():
if debug:
print("Potential y0:",y0)
if (x0-xoffset,y0) not in roots and pol(x0,y0) == 0:
roots.append((x0-xoffset,y0))
return roots
a = 10^42
b = 10^42
P.<p,q> = PolynomialRing(ZZ)
pol = (p_h * 10^71 + p * 10^30 + p_l)*(q_h * 10^70 + q * 10^29 + q_l) - n # Should have a root at (x0,y0)
x0, y0 = coron(pol, a, b, k=2, debug=False)[0]
print(x0, y0)
p = (p_h * 10^71 + x0 * 10^30 + p_l)
q = n // p
assert n % p == 0
pt = pow(ct, pow(e, -1, (p-1)*(n//p - 1)), n)
print(pt)
```
:::
:::success
corctf{1_w4s_f0rc3d_t0_wr1t3_ch4ll5_4nd_1_h4d_n0_g00d_1d345_pl5_n0_bully_;-;}
:::
## babyrand (35 solves / 484 points)
you can't break an lcg with only 2 outputs right
:::spoiler **Source Code**
```python=
from random import randrange
from Crypto.Util.number import getPrime, long_to_bytes
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from hashlib import sha256
from os import urandom
flag = open("flag.txt", "rb").read()
def und():
p = getPrime(512)
x = randrange(p)
a = p ^ x ^ randrange(2**200)
b = p ^ x ^ randrange(2**200)
return p, a, b, x
p,a,b,x = und()
iv = urandom(16)
key = sha256(long_to_bytes(a) + long_to_bytes(b)).digest()[:16]
cipher = AES.new(key, AES.MODE_CBC, iv)
print(f"c1 = {x}")
print(f"c2 = {(x*a + b) % p}")
print(f"p = {p}")
print(f"iv = '{iv.hex()}'")
print(f"ct = '{cipher.encrypt(pad(flag, 16)).hex()}'")
```
:::
根據 $a,b$ 的生成方式，我們知道它們跟 $p \oplus x$ 都差不到 $2^{200}$。將原本的等式改寫成 $$\begin{align*}c_2 \equiv ax+b & \equiv \left(p \oplus x + \bar{a}\right)x + \left(p \oplus x + \bar{b}\right) & \\[5pt] & \equiv \left(p \oplus x + 1\right)x + \left(\bar{a}x+\bar{b}\right) & \pmod{p}\end{align*}$$ 從這裡便能夠得到 $\bar{a}x+\bar{b}$ 模 $p$ 的值，然後當作 hidden number problem 來解 $a, b$。
:::spoiler **Script**
```python=
c1 = 5365904711205493895182988721055598679508066289977091231731349423996531384326997250984304389796311073201846992254794801346573036775490182780952712232258774
c2 = 2351499357088933835557969576916974229915931074692169825269157710226395480997304497294813272746195475744137017453323338362896396977337638862808560417575150
p = 12118911800929768381158064532151564397584328623097191996086479213117076586014730135201334840794700976422626122702191630484231703678287738839516304757792517
px = p ^^ c1
_ = (c2 - px * (c1+1)) % p
### ?x + ? = _ (mod p)
def solve_HNP(a, b, k):
# http://www.isg.rhul.ac.uk/~sdg/igor-slides.pdf
N = len(a)
M = Matrix(RationalField(), N+1, N+1)
for i in range(N):
M[i, i] = p
M[N, i] = b[i]
M[N, N] = 1 / (2 ** (k + 1))
def babai(A, w):
A = A.LLL(delta=0.75)
G = A.gram_schmidt()[0]
t = w
for i in reversed(range(A.nrows())):
c = ((t * G[i]) / (G[i] * G[i])).round()
t -= A[i] * c
return w - t
closest = babai(M, vector(RationalField(), a + [0]))
return (closest[-1] * (2 ** (k + 1))) % p
for i in range(0, 100):
x = solve_HNP([_], [c1], i)
# print(x)
m = (_ - x*c1) % p
if x < 2^200 and m < 2^200:
break
a, b = px + x, px + m
assert (a*c1 + b) % p == c2
print(a, b)
```
:::
最後用以下的 script 拿到 flag。
:::spoiler **Script**
```python=
from output import *
from Crypto.Util.number import long_to_bytes
from Crypto.Cipher import AES
from hashlib import sha256
a = 6761187669407721882390134075659672676880474167244971288748329437058079452311926924852143504653500055140920258830257424765586078046533411504304464482300181
b = 6761187669407721882390134075659672676880474167244971288748329437058079452311926924852143504654630748191024213475615079914366989025007717791042043343928434
key = sha256(long_to_bytes(a) + long_to_bytes(b)).digest()[:16]
cipher = AES.new(key, AES.MODE_CBC, bytes.fromhex(iv))
flag = cipher.decrypt(bytes.fromhex(ct))
print(flag)
```
:::
:::success
corctf{c0ngr4tul4t10ns_y0u_4r3_n0w_p4rt_0f_th3_d3fund_f4n_club!}
:::
## babypad (29 solves / 487 points)
padding makes everything secure right
:::spoiler **Source Code**
```python=
from Crypto.Cipher import AES
from Crypto.Util import Counter
from Crypto.Util.Padding import pad, unpad
from Crypto.Util.number import bytes_to_long
import os
flag = open("/challenge/flag.txt").read().encode()
key = os.urandom(16)
def encrypt(pt):
iv = os.urandom(16)
ctr = Counter.new(128, initial_value=bytes_to_long(iv))
cipher = AES.new(key, AES.MODE_CTR, counter=ctr)
return iv + cipher.encrypt(pad(pt, 16))
def decrypt(ct):
try:
iv = ct[:16]
ct = ct[16:]
ctr = Counter.new(128, initial_value=bytes_to_long(iv))
cipher = AES.new(key, AES.MODE_CTR, counter=ctr)
pt = cipher.decrypt(ct)
unpad(pt, 16)
return 1
except Exception as e:
return 0
def main():
print(encrypt(flag).hex())
while True:
try:
print(decrypt(bytes.fromhex(input("> "))))
except Exception as e:
pass
main()
```
:::
題目有 padding 又有 oracle 可以用，一臉就是 padding oracle attack。回顧一下 CTR 的機制：
會根據 counter 生成 one-time-pad，然後跟明文做 xor。這邊的 decryption oracle 沿用同樣的 counter，接著 unpadding。可能出錯的就只有 padding 是錯的，我們可以根據這個從後面一個一個把 one-time-pad 給拿回來。
:::spoiler **Script**
```python=
from pwn import *
c = remote('babypad.be.ax', 1337)
res = c.recvline().strip().decode('utf-8')
enc = bytes.fromhex(res)
key = []
def n2b(n):
a = hex(n)[2:]
if len(a) % 2 == 1:
a = '0' + a
return bytes.fromhex(a)
start = 31
end = 15
for i in range(start, end, -1):
pad = start+1-i
prefix = enc[:i-1]
for n in range(256):
check = 0
for t in range(2):
test = prefix + n2b(t) + n2b(n ^ pad)
for j in range(start-i):
test += n2b(key[j] ^ pad)
assert len(test) == start + 1
c.sendline(test.hex())
r = c.recvline()
if b"1" in r:
check += 1
if check == 2:
key.insert(0, n)
break
print(key)
flag = ""
for ind in range(i, start + 1):
flag += chr(enc[ind] ^ key[ind-i])
print(flag)
```
:::
:::success
corctf{CTR_p4dd1ng?n0_n33d!}
:::
## LCG_k (25 solves / 489 points)
Can you sign my message for me?
:::spoiler **Source Code**
```python=
from Crypto.Util.number import bytes_to_long, inverse
from hashlib import sha256
from secrets import randbelow
from private import flag
from fastecdsa.curve import P256
G = P256.G
N = P256.q
class RNG:
def __init__(self, seed, A, b, p):
self.seed = seed
self.A = A
self.b = b
self.p = p
def gen(self):
out = self.seed
while True:
out = (self.A*out + self.b) % self.p
yield out
def H(m):
h = sha256()
h.update(m)
return bytes_to_long(h.digest())
def sign(m):
k = next(gen)
r = int((k*G).x) % N
s = ((H(m) + d*r)*inverse(k, N)) % N
return r, s
def verify(r, s, m):
v1 = H(m)*inverse(s, N) % N
v2 = r*inverse(s, N) % N
V = v1*G + v2*pub
return int(V.x) % N == r
seed, A, b = randbelow(N), randbelow(N), randbelow(N)
lcg = RNG(seed, A, b, N)
gen = lcg.gen()
d = randbelow(N)
pub = d*G
mymsg = b'i wish to know the ways of the world'
print('public key:', pub)
signed_hashes = []
for _ in range(4):
m = bytes.fromhex(input('give me something to sign, in hex>'))
h = H(m)
if m == mymsg or h in signed_hashes:
print("i won't sign that.")
exit()
signed_hashes.append(h)
r, s = sign(m)
print('r:', str(r))
print('s:', str(s))
print('now, i want you to sign my message.')
r = int(input('give me r>'))
s = int(input('give me s>'))
if verify(r, s, mymsg):
print("nice. i'll give you the flag.")
print(flag)
else:
print("no, that's wrong.")
```
:::
題目讓我們拿到任意選定的 $4$ 組簽章，這使得我們能夠推出 $k$ 的值。換句話說，我們有連續 $4$ 組 LCG 的產物。
:::spoiler **Script**
```python=
from pwn import *
from Crypto.Util.number import long_to_bytes, bytes_to_long, inverse
from hashlib import sha256
def H(m):
h = sha256()
h.update(m)
return bytes_to_long(h.digest())
N = 115792089210356248762697446949407573529996955224135760342422259061068512044369
c = remote('crypto.be.ax', 6002)
i, j = [], []
msg = ["00", "01", "02", "03"]
m = [b"\x00", b"\x01", b"\x02", b"\x03"]
for _ in range(4):
tmp = c.recvuntil("give me something to sign, in hex>")
if _ == 0:
print(tmp)
c.sendline(msg[_])
c.recvuntil("r:")
r = int(c.recvline().strip())
c.recvuntil("s:")
s = int(c.recvline().strip())
i.append((inverse(s, N) * H(m[_])) % N)
j.append((inverse(s, N) * r) % N)
print("i = {}".format(i))
print("j = {}".format(j))
mymsg = b"i wish to know the ways of the world"
print("H(m) = {}".format(H(mymsg)))
c.interactive()
```
:::
而未知的數字剛好也是 $4$ 個 $seed, A, b, d$，我們用 Groebner basis 找次數比較低的多項式，由於它們也是原本方程式的線性組合，所以 $seed, A, b, d$ 一樣是他們的根。好處是次數低比較有機會求出。簡單跑一下會發現方程式們是 $$\begin{align*} d^2+\square d+\square & = 0 \\ k + \square d + \square & = 0 \\ A + \square d + \square & = 0 \\ b + \square d + \square & = 0 \end{align*}$$ 二次方程式在 $\mathbb{Z}/N\mathbb{Z}$ 中一樣能解，看哪個根滿足 $dG = pub$ 即可。
有私鑰 $d$ 便能夠任意簽章，從而拿到 flag。
:::spoiler **Script**
```python=
p = 115792089210356248762697446949407573530086143415290314195533631308867097853951
N = 115792089210356248762697446949407573529996955224135760342422259061068512044369
R = Integers(N)
i = [79271462955603522200971110455229606977452988447711284222598945262856764471981, 16673835244879977416665872575661913638414723148602150817441632489744299381046, 72985304946047824662648574656592333236216360641157113043324449343190521554019, 71225158190076123067459831081781769727299059978325615294993154363719736002979]
j = [48224407385362577686232236737740103198739943989855810005919177592279550938910, 51456806970888375995288103108123414237327562138887229118959287166492159443493, 14768034644898465160883571212426517826918630924759383339338350083996555370080, 18900855619285550880747030929104933789226873607590994322799037588035058006422]
Hm = 81474710833905360053741854144396517950904965953892927531984947662279062100233
P.<k, A, b, d> = PolynomialRing(R)
G = []
ff = k
for _ in range(4):
G.append(ff - i[_] - j[_] * d)
ff = A*ff + b
B = Ideal(G).groebner_basis()
print(B)
Q.<x> = PolynomialRing(R)
f = x^2 + B[0].monomial_coefficient(d)*x + B[0].constant_coefficient()
dd = f.roots()[0][0]
print(dd)
kk = (-B[1].monomial_coefficient(d) * dd - B[1].constant_coefficient()) % N
AA = (-B[2].monomial_coefficient(d) * dd - B[2].constant_coefficient()) % N
bb = (-B[3].monomial_coefficient(d) * dd - B[3].constant_coefficient()) % N
print(kk)
print(AA)
print(bb)
ff = kk
for _ in range(4):
assert (ff - i[_] - j[_] * dd) % N == 0
ff = AA*ff+bb
a = -3
b = 41058363725152142129326129780047268409114441015993725554835256314039467401291
E = EllipticCurve(Zmod(p), [a, b])
G = E(48439561293906451759052585252797914202762949526041747995844080717082404635286, 36134250956749795798585127919587881956611106672985015071877198253568414405109)
k = int(ff)
r = int((k*G)[0]) % N
s = ((int(Hm) + int(dd) * int(r)) * pow(k, -1, N)) % N
print(r)
print(s)
```
:::
:::success
corctf{r3l4ted_n0nce5_4re_d4n6er0us_fde6ebafa842716a}
:::
## bank (25 solves / 489 points)
To keep up with the latest trends CoR is introducing a quantum bank for all your secure banking needs. Unfortunately no one on CoR actually knows how quantum computing works, least of all me...
:::spoiler **Source Code**
```python=
#!/usr/bin/python3
import numpy as np
import math, random
flag = open('flag.txt').read()
class Qubit:
def __init__(self, vector):
self.vec = vector
def x(self):
mat = np.array([[0, 1], [1, 0]])
self.vec = mat.dot(self.vec)
def y(self):
mat = np.array([[0, -1j], [1j, 0]])
self.vec = mat.dot(self.vec)
def z(self):
mat = np.array([[1, 0], [0, -1]])
self.vec = mat.dot(self.vec)
def h(self):
mat = np.array([[1/math.sqrt(2), 1/math.sqrt(2)], [1/math.sqrt(2), -1/math.sqrt(2)]])
self.vec = mat.dot(self.vec)
def rotate(self, angle):
mat = np.array([[1, 0], [0, np.exp(1j * angle)]])
self.vec = mat.dot(self.vec)
def measure(self, basis):
if basis == '01':
if random.random() < np.linalg.norm(self.vec[0]) ** 2:
self.vec = np.array([[1], [0]])
return '0'
else:
self.vec = np.array([[0], [1]])
return '1'
elif basis == '+-':
pvec = np.array([[1/math.sqrt(2)], [1/math.sqrt(2)]])
prob = np.linalg.norm(self.vec.T.dot(pvec)) ** 2
if random.random() < prob:
self.vec = pvec
return '+'
else:
self.vec = np.array([[1/math.sqrt(2)], [-1/math.sqrt(2)]])
return '-'
else:
raise ValueError('Invalid basis to measure on')
@staticmethod
def from_str(symbol):
if symbol == '0':
return Qubit(np.array([[1], [0]]))
elif symbol == '1':
return Qubit(np.array([[0], [1]]))
elif symbol == '+':
return Qubit(np.array([[1/math.sqrt(2)], [1/math.sqrt(2)]]))
elif symbol == '-':
return Qubit(np.array([[1/math.sqrt(2)], [-1/math.sqrt(2)]]))
raise ValueError('Invalid symbol to construct qubit with')
print('Welcome to the CoR bank!')
print("We're currently running a special promotion where new accounts receive one free dollar. Terms and conditions apply.")
choice = input('Would you like an account? (y/n) ')
if choice.lower() == 'n':
print('Well what did you connect for? Stop wasting my time')
exit()
elif choice.lower() != 'y':
print('Bruh')
exit()
symbols = ['0', '1', '+', '-']
bill = [random.choice(symbols) for _ in range(50)]
qubits = [Qubit.from_str(s) for s in bill]
print('New account made! Enjoy your $1.')
print()
print("bill = {}".format(''.join(bill)))
while True:
print('What would you like to do with your account?')
print()
print('1. Work with qubits')
print('2. Buy flag')
print('3. Quit')
choice = input('> ')
if choice == '1':
idx = int(input('Please input the index of the qubit you wish to work with: '))
while True:
print('What operation would you like to perform?')
print()
print('1. Apply X gate')
print('2. Apply Y gate')
print('3. Apply Z gate')
print('4. Apply Hadamard gate')
print('5. Apply rotation gate')
print('6. Measure qubit in 0/1 basis')
print('7. Measure qubit in +/- basis')
print('8. Verify qubit')
print('9. Back')
op = input('> ')
if op == '1':
qubits[idx].x()
elif op == '2':
qubits[idx].y()
elif op == '3':
qubits[idx].z()
elif op == '4':
qubits[idx].h()
elif op == '5':
angle = float(input('Input angle to rotate by (in radians): '))
if np.isnan(angle) or np.isinf(angle):
print('Pepega')
else:
qubits[idx].rotate(angle)
elif op == '6':
print('The qubit measured as', qubits[idx].measure('01'))
elif op == '7':
print('The qubit measured as', qubits[idx].measure('+-'))
elif op == '8':
actual = bill[idx]
if actual in '01':
measured = qubits[idx].measure('01')
else:
measured = qubits[idx].measure('+-')
if actual == measured:
print('Qubit successfully verified.')
else:
print('Incorrect qubit!')
elif op == '9':
break
else:
print('Invalid operation.')
exit()
elif choice == '2':
print('Flags cost $1.')
qstr = input('Enter your bill: ')
if qstr == ''.join(bill):
print('Congratulations!', flag)
else:
print('Are you trying to scam me?')
exit()
else:
print('Cya')
exit()
```
:::
一道閱讀測驗 ... ，我們有一堆隨機的 qubit，然後能夠對他們隨意翻轉以及測量。只不過測量後會變成測量的結果，也就是說我們不能夠多測幾次來降低測量的誤差。但僅僅一次的測量機會，是不是只能分辨出兩種 qubit 呢？
我們先不管三七二十一，強行先分辨 $0, 1$ 兩種 qubit。具體的方式就是調用選項 $6,8$。這時候 $+, -$ 兩個 qubit 會怎麼樣呢？兩者在測量時，變成 $0$ 的機率都恰有 $\frac{1}{2}$。接著 verify 時，根據剛剛變成的 qubit 回到 $+, -$！這代表說有 $\frac{1}{2}$ 的機率 verify 失敗。
那問題就簡單了，只要重複上面的步驟足夠多次，就能有高機率確認這個是不是 $0, 1$ 的 qubit。最後改用選項 $7,8$ 去分辨 $+, -$ 兩種 qubit。
:::spoiler **Script**
```python=
from pwn import *
c = remote('crypto.be.ax', 6005)
c.sendline('y')
bill = []
for _ in range(50):
c.sendline('1')
c.recvuntil('Please input the index of the qubit you wish to work with: ')
c.sendline(str(_))
check = True
for t in range(10):
c.sendline('6')
c.recvuntil('The qubit measured as ')
tmp = int(c.recvline().strip())
c.recvuntil('9. Back')
c.sendline('8')
c.recvline()
res = c.recvline()
if b"Incorrect" in res:
check = False
break
if check == True:
bill.append(str(tmp))
else:
c.sendline('7')
c.recvuntil('The qubit measured as ')
tmp = c.recvline().strip()
c.recvuntil('9. Back')
c.sendline('8')
c.recvline()
res = c.recvline()
if b"successful" in res:
if b"+" in tmp:
bill.append('+')
else:
bill.append('-')
else:
if b"+" in tmp:
bill.append('-')
else:
bill.append('+')
c.sendline('9')
print(_)
c.sendline('2')
ans = ''.join(bill)
c.sendline(ans)
c.interactive()
```
:::
:::success
corctf{4lw4ys_d3str0y_y0ur_f4k3s}
:::
## leave_it_to_chance (5 solves / 498 points)
Do you believe in the heart of the cards?
:::spoiler **Source Code**
```python=
#!/usr/bin/python3
from Crypto.Util.number import getPrime
from random import randrange, shuffle
flag = "corctf{wh0_n3eds_gue551ng_wh3n_y0u_have_l1ne4r_al6ebr4_526d95eadb9686bb}"
class Game():
KEY_LEN = 20
def __init__(self):
self.p = getPrime(128)
while self.p % 4 == 3:
self.p = getPrime(256)
x = randrange(self.p)
while pow(x, (self.p-1)//2, self.p) == 1:
x = randrange(self.p)
self.a = pow(x, (self.p-1)//4, self.p)
self.privgen()
self.signed = []
def privgen(self):
self.priv = [randrange(self.p) for _ in range(self.KEY_LEN)]
def sign(self, m):
s = 0
for i in range(len(self.priv)):
s += (pow(m, i, self.p) * self.priv[i]) % self.p
return s
def verify(self, m, s):
c = self.sign(m)
return c**4 % self.p == s
def getSig():
m = int(input("Enter the message you would like to sign, in hex> "), 16) % game.p
if m not in game.signed:
s = game.sign(m)
game.signed.append(m)
print(f"s: {s}")
print(f"Signature: {hex(s**4 % game.p)[2:]}")
hints = [-s % game.p, s*game.a % game.p, -s*game.a % game.p]
shuffle(hints)
guess = int(input("Enter a guess for s, in hex> "), 16)
if guess in hints:
hints.remove(guess)
print(f"Hints: {hints[0]} {hints[1]}")
else:
print("You already signed that.")
def verifyPair():
m = int(input("Enter m, in hex> "), 16)
s = int(input("Enter s, in hex> "), 16)
if game.verify(m, s):
print("Valid signature.")
else:
print("Invalid signature.")
def guessPriv():
inp = input("Enter the private key as a list of space-separated numbers> ")
guess = [int(n) for n in inp.split(" ")]
if guess == game.priv:
print(f"Nice. Here's the flag: {flag}")
else:
print("No, that's wrong.")
exit()
def menu():
print("Enter your choice:")
print("[1] Get a signature")
print("[2] Verify a message")
print("[3] Guess the private key")
print("[4] Exit")
options = [getSig, verifyPair, guessPriv, exit]
choice = int(input("Choice> "))
if choice - 1 in range(len(options)):
options[choice - 1]()
else:
print("Please enter a valid choice.")
game = Game()
welcome = f"""Welcome.
I will let you sign as many messages as you want.
If you can guess the private key, the flag is yours.
But you only have one chance. Make it count.
p = {game.p}
"""
print(welcome)
while True:
menu()
```
:::
我們首先簡單講一下這題server在幹嘛。
* 生成一個 $4k+1$ 型的質數 $p$, 一個四次方根 $a$ 以及 $31$ 次多項式 $P$ 的係數們。
* 給定 $n$，server 會告訴我們 $P(n)^4 \pmod{p}$，接著我們能夠選擇一個數 $k$，如果 $k!=n$ 且 $P(k)^4 = P(n)^4 \pmod{p}$，那麼 server 會告訴我們 $P(n)$，不然就只會的亂講個錯的。因此，我們其實有 $\frac{3}{4}$ 的機率拿到正確的 $P(n)$。無論如何，假設我們給 $x_i$ 拿到 $b_i$
* 目標是給出正確的係數，server 便會吐出 flag。
首先，若在茫茫 $x_1, x_2,\dots,x_n$ 中，我們在 input 是 $x_{k_1}, x_{k_2}, \dots, x_{k_e}$ 時猜錯。那麼構造多項式 $$E\left(x\right) = \prod\limits_{i=1}^{k}\left(x-x_{k_i}\right) \rightarrow P\left(x_i\right)E\left(x_i\right) = b_iE\left(x_i\right)$$
$LHS$ 是 $31+e$ 次的多項式，而 $RHS$ 是 $e$ 次多項式。我們只需要有 $32+2e$ 條式子即可。注意到因為我們只有 $\frac{1}{4}$ 的機率拿到拉基，所以大概會有 $4e$ 條式子，只需有 $$4e \ge 31+2e \rightarrow e \ge 16$$ 但我們可能很非洲，所以多取幾次比較保險。
:::spoiler **Sampling**
```python=
from pwn import *
from random import randrange
from util import *
from Crypto.Util.number import long_to_bytes
# c = remote("crypto.be.ax", 6001)
c = process("source.py")
c.recvuntil("p = ")
p = int(c.recvline().strip())
### Find a quartic root in Z/pZ
x = randrange(p)
while pow(x, (p-1)//2, p) == 1:
x = randrange(p)
a = pow(x, (p-1)//4, p)
### Get (i, P(i)) at some points
res = []
for i in range(1, 60):
c.recvuntil("Choice> ")
c.sendline('1')
c.sendline(hex(i)[2:].encode())
c.recvuntil("s: ")
s = int(c.recvline().strip())
# print(s)
c.recvuntil("Signature: ")
sig = int(c.recvline().strip(), 16)
# print(sig)
assert (s ** 4) % p == sig
tmp = modular_sqrt(sig, p)
assert pow(tmp, 2, p) == sig % p
_ = modular_sqrt(tmp, p)
assert pow(_, 4, p) == sig % p
roots = [_, (_*a) % p, (_*a*a) % p, (_*a*a*a) % p]
# print(roots)
for r in roots:
assert pow(r, 4, p) == sig % p
c.recvuntil("in hex> ")
c.sendline(long_to_bytes(roots[0]).hex())
c.recvuntil("Hints: ")
h = c.recvline().decode('utf-8').split(' ')
h0, h1 = int(h[0]), int(h[1])
roots.pop(0)
roots.remove(h0)
roots.remove(h1)
res.append(roots[0])
### Build the linear equation Ax = b
A = []
b = []
n = 20
e = 15
for i, fi in enumerate(res):
row = []
for _ in range(n+e):
row.append(pow(i+1, _, p))
for _ in range(e):
row.append((- pow(i+1, _, p) * fi) % p)
A.append(row)
b.append((pow(i+1, e, p) * fi) % p)
with open('output.txt', 'w') as out:
out.write("p = {}\n".format(p))
out.write("A = {}\n".format(A))
out.write("b = {}\n".format(b))
c.interactive()
```
:::
:::spoiler **Retrieve Polynomial**
```python=
p = #
A = #
b = #
F = GF(p)
A = Matrix(F, A)
b = vector(F, b)
x = A.solve_right(b)
R.<y> = PolynomialRing(F, 'y')
n, e = 20, 15
Q = x[0]
for i in range(1, n+e):
Q += x[i] * y^i
E = x[n+e]
for i in range(1, e):
E += x[n + e + i] * y^i
E += y^e
P = Q / E
priv = P.numerator().list()
print(' '.join([str(coef) for coef in priv]))
```
:::
:::success
corctf{wh0_n3eds_gue551ng_wh3n_y0u_have_l1ne4r_al6ebr4_526d95eadb9686bb}
:::
Sign in with Wallet
Connect another wallet