This writeup is long overdue, sorry about that. I participated in ACSC finals, and solved nearly all crypto, as there was a cryptography challenge that was really more about SQL Injection than cryptography. To be more detailed, the exact same cryptogrpahic vulnerability is used in one of the cryptohack challenges (and it has very similar setups as well) so the cryptographic side of the challenge is next to none. I had some fun learning some basic SQL Injection and got close, but ultimately failed to solve the challenge. I did solve all others, including one that was solved only by me. This writeup will be relatively short and concise, as I do not have a lot of time on my hands.

 

The solutions codes are on the usual github, https://github.com/rkm0959/Cryptography_Writeups/tree/main/2021/ACSC  

 

RSA Stream

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
import gmpy2
from Crypto.Util.number import long_to_bytes, bytes_to_long, getStrongPrime, inverse
from Crypto.Util.Padding import pad
 
from flag import m
#m = b"ACSC{<REDACTED>}" # flag!
 
f = open("chal.py","rb").read() # I'll encrypt myself!
print("len:",len(f))
p = getStrongPrime(1024)
q = getStrongPrime(1024)
 
n = p * q
e = 0x10001
print("n =",n)
print("e =",e)
print("# flag length:",len(m))
m = pad(m, 255)
m = bytes_to_long(m)
 
assert m < n
stream = pow(m,e,n)
cipher = b""
 
for a in range(0,len(f),256):
  q = f[a:a+256]
  if len(q) < 256:q = pad(q, 256)
  q = bytes_to_long(q)
  c = stream ^ q
  cipher += long_to_bytes(c,256)
  e = gmpy2.next_prime(e)
  stream = pow(m,e,n)
 
open("chal.enc","wb").write(cipher)
 
 
 cs

 

We see that we are encrypting the given python file, so we know the plaintext and the ciphertext.

Since this is an XOR cipher, this implies that we know all the key streams used to encrypt the plaintext.

We note that the key streams are composed of $m^e \pmod{n}$ where $e$ are several primes. 

Of course, if we know $m^{e_1} \pmod{n}$ and $m^{e_2} \pmod{n}$ with $\gcd(e_1, e_2) = 1$, we can find $r_1, r_2$ such that $e_1r_1 + e_2r_2 = 1$.

Now we can finish calculating $m$ by simply using $$m \equiv m^{e_1 \cdot r_1} m^{e_2 \cdot r_2} \pmod{n}$$

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
length = 723
n = 30004084769852356813752671105440339608383648259855991408799224369989221653141334011858388637782175392790629156827256797420595802457583565986882788667881921499468599322171673433298609987641468458633972069634856384101309327514278697390639738321868622386439249269795058985584353709739777081110979765232599757976759602245965314332404529910828253037394397471102918877473504943490285635862702543408002577628022054766664695619542702081689509713681170425764579507127909155563775027797744930354455708003402706090094588522963730499563711811899945647475596034599946875728770617584380135377604299815872040514361551864698426189453
e = 65537
 
f = open("chal.py","rb")
inp = f.read()
f.close()
 
f = open("chal.enc", "rb")
outp = f.read()
f.close()
 
data = []
e = 65537
 
for i in range(0, 768, 256):
    cc = inp[i:i+256]
    if len(cc) < 256:
        cc = pad(cc, 256)
    res = bytes_to_long(cc) ^ bytes_to_long(outp[i:i+256])
    data.append([res, e])
    e = nextprime(e)
 
u = inverse(65537, 65539)
v = (65537 * u - 1) // 65539
 
m = (pow(data[0][0], u, n) * inverse(pow(data[1][0], v, n), n)) % n
 
print(long_to_bytes(m))    
 cs

 

CBCBC

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
#!/usr/bin/env python3
 
import base64
import json
import os
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad
from secret import hidden_username, flag
 
key = os.urandom(16)
iv1 = os.urandom(16)
iv2 = os.urandom(16)
 
 
def encrypt(msg):
    aes1 = AES.new(key, AES.MODE_CBC, iv1)
    aes2 = AES.new(key, AES.MODE_CBC, iv2)
    enc = aes2.encrypt(aes1.encrypt(pad(msg, 16)))
    return iv1 + iv2 + enc
 
 
def decrypt(msg):
    iv1, iv2, enc = msg[:16], msg[16:32], msg[32:]
    aes1 = AES.new(key, AES.MODE_CBC, iv1)
    aes2 = AES.new(key, AES.MODE_CBC, iv2)
    msg = unpad(aes1.decrypt(aes2.decrypt(enc)), 16)
    return msg
 
 
def create_user():
    username = input("Your username: ")
    if username:
        data = {"username": username, "is_admin": False}
    else:
        # Default token
        data = {"username": hidden_username, "is_admin": True}
    token = encrypt(json.dumps(data).encode())
    print("Your token: ")
    print(base64.b64encode(token).decode())
 
 
def login():
    username = input("Your username: ")
    token = input("Your token: ").encode()
    try:
        data_raw = decrypt(base64.b64decode(token))
    except:
        print("Failed to login! Check your token again")
        return None
 
    try:
        data = json.loads(data_raw.decode())
    except:
        print("Failed to login! Your token is malformed")
        return None
 
    if "username" not in data or data["username"] != username:
        print("Failed to login! Check your username again")
        return None
 
    return data
 
 
def none_menu():
    print("1. Create user")
    print("2. Log in")
    print("3. Exit")
 
    try:
        inp = int(input("> "))
    except ValueError:
        print("Wrong choice!")
        return None
 
    if inp == 1:
        create_user()
        return None
    elif inp == 2:
        return login()
    elif inp == 3:
        exit(0)
    else:
        print("Wrong choice!")
        return None
 
 
def user_menu(user):
    print("1. Show flag")
    print("2. Log out")
    print("3. Exit")
 
    try:
        inp = int(input("> "))
    except ValueError:
        print("Wrong choice!")
        return None
 
    if inp == 1:
        if "is_admin" in user and user["is_admin"]:
            print(flag)
        else:
            print("No.")
        return user
    elif inp == 2:
        return None
    elif inp == 3:
        exit(0)
    else:
        print("Wrong choice!")
        return None
 
 
def main():
    user = None
 
    print("Welcome to CBCBC flag sharing service!")
    print("You can get the flag free!")
    print("This is super-duper safe from padding oracle attacks,")
    print("because it's using CBC twice!")
    print("=====================================================")
 
    while True:
        if user:
            user = user_menu(user)
        else:
            user = none_menu()
 
 
if __name__ == "__main__":
    main()
 
 cs

 

We have a cipher that uses AES-CBC two times. From line 118 we see that padding oracle attacks still work.

If we write out the entire decryption process, we get that $$P_n = D_k(D_k(C_n) \oplus C_{n-1}) \oplus D_k(C_{n-1}) \oplus C_{n-2}$$ where $C_0 = IV_2$ and $C_{-1} = IV_1$. Note that $P_n$ can be easily controlled by $C_{n-2}$.

Therefore, the whole padding oracle attacks work, it's just that we need to change 2 blocks before the targeted block to perform the attack. The remaining parts are straightforward if you have solid understanding of padding oracle attack.

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
r = remote('167.99.77.49', 52171)
# r.interactive()
 
def read_menu(x):
    for _ in range(x):
        r.recvline()
 
read_menu(5)
 
read_menu(3)
r.sendline(b"1")
r.send(b"\n")
r.recvline()
token = r.recvline()
token = b64decode(token)
print(token)
print(len(token))
 
true_ptxt = [0] * 80
 
for i in range(64, 16, -16):
    for j in range(0, 16):
        for k in tqdm(range(0, 256)):
            if i == 64 and j == 0 and k == 0:
                continue
            query_token = token[:i-j-17]
            query_token += bytes([token[i-j-17] ^ k])
            for u in range(j):
                query_token += bytes([token[i-j-16+u] ^ true_ptxt[i-j+16+u] ^ (j+1)])
            query_token += token[i-16:i+16]
            read_menu(3)
            r.sendline(b"2")
            r.sendline(b"abc")
            r.sendline(b64encode(query_token))
            res = r.recvline()
            if b"Check your token again" not in res:
                true_ptxt[i+15-j] = k ^ (j+1)
                break
        print(bytes(true_ptxt))
 
print(bytes(true_ptxt))
 cs

 

Swap on Curve

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
from params import p, a, b, flag, y
 
x = int.from_bytes(flag, "big")
 
assert 0 < x < p
assert 0 < y < p
assert x != y
 
EC = EllipticCurve(GF(p), [a, b])
 
assert EC(x,y)
assert EC(y,x)
 
print("p = {}".format(p))
print("a = {}".format(a))
print("b = {}".format(b))
 
 cs

 

Basically we have to solve $$y^2 = x^3 + ax + b, \quad x^2 = y^3 + ay + b$$ which can be done by doing algebra to change it into a one variable polynomial equation, or using resultants to achieve the same goal. I used the latter option, also using what I learned from joseph (https://twitter.com/josep68_) in CryptoHack discord. Sometimes the resultant function on Sagemath doesn't work for some reason I don't fully understand, but you can get around this by using sylvester matrix trickery. 

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
'''
from sage.matrix.matrix2 import Matrix 
def resultant(f1, f2, var):
    return Matrix.determinant(f1.sylvester_matrix(f2, var))
p = 10224339405907703092027271021531545025590069329651203467716750905186360905870976608482239954157859974243721027388367833391620238905205324488863654155905507
a = 4497571717921592398955060922592201381291364158316041225609739861880668012419104521771916052114951221663782888917019515720822797673629101617287519628798278
b = 1147822627440179166862874039888124662334972701778333205963385274435770863246836847305423006003688412952676893584685957117091707234660746455918810395379096
# y^2 = x^3 + ax+b
# x^2 = y^3 + ay+b
POL.<x, y> = PolynomialRing(GF(p))
f = y * y - x * x * x - a * x - b
g = x * x - y * y * y - a * y - b 
res = resultant(f, g, y)
print(res.roots())
'''
 
 
p = 10224339405907703092027271021531545025590069329651203467716750905186360905870976608482239954157859974243721027388367833391620238905205324488863654155905507
a = 4497571717921592398955060922592201381291364158316041225609739861880668012419104521771916052114951221663782888917019515720822797673629101617287519628798278
b = 1147822627440179166862874039888124662334972701778333205963385274435770863246836847305423006003688412952676893584685957117091707234660746455918810395379096
 
# y^2 = x^3 + ax+b
# x^2 = y^3 + ay+b
 
val = [(7701093676539600849545233775656266124024393901117284843908110961515787578426141185510163529087490707005602090170967486760425035325079989548242482516345996, 1), (7677785116435727686649964446582280200653867847347508329665823423662012251739816682685754769395346602260506848926697976097716406737781893094340049957504162, 1), (3418100096957777329641522385874601707957378769808441636922695882579741403099793135186593317827442718653892790484853393209667843889446155946725442732255448, 1)]
 
for a, b in val:
    print(long_to_bytes(a))
 cs

 

Two Rabin

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
import random
from Crypto.Util.number import *
from Crypto.Util.Padding import pad
 
from flag import flag
 
p = getStrongPrime(512)
q = getStrongPrime(512)
n = p * q
B = getStrongPrime(512)
 
m = flag[0:len(flag)//2]
print("flag1_len =",len(m))
 
m1 = bytes_to_long(m)
m2 = bytes_to_long(pad(m,128))
 
assert m1 < n
assert m2 < n
 
c1 = (m1*(m1+B)) % n
c2 = (m2*(m2+B)) % n
 
print("n =",n)
print("B =",B)
print("c1 =",c1)
print("c2 =",c2)
 
# Harder!
 
m = flag[len(flag)//2:]
print("flag2_len =",len(m))
 
m1 = bytes_to_long(m)
m1 <<= ( (128-len(m))*8 )
m1 += random.SystemRandom().getrandbits( (128-len(m))*8 )
 
m2 = bytes_to_long(m)
m2 <<= ( (128-len(m))*8 )
m2 += random.SystemRandom().getrandbits( (128-len(m))*8 )
 
assert m1 < n
assert m2 < n
 
c1 = (m1*(m1+B)) % n
c2 = (m2*(m2+B)) % n
 
print("hard_c1 =",c1)
print("hard_c2 =",c2)
 
 
 cs

 

We have two separate problems, each of which needs to be solved to get the flag.

 

For the first problem, there is a known linear relation between the two messages since the pad is not random. Therefore, the two equations given can both be written as a polynomial equation of a single variable, which means that the system can be solved by polynomial GCD or basic algebra as both equations are only quadratic. I chose the latter option for some reason :P

 

For the second problem, the padding is small but they are random. Therefore, we can write the first message as $x$ and the second message as $x+y$ where $y$ is some small value. Since we have two quadratic equations on $x, y$, we can use resultants again to make a polynomial equation on $y$ only. Since $y$ is small, this polynomial equation can be solved via coppersmith's attack. After getting $y$, we now have two quadratic equations where $x$ is the only variable, which can be solved similarly as the first problem. 

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
flag1_len = 98
n = 105663510238670420757255989578978162666434740162415948750279893317701612062865075870926559751210244886747509597507458509604874043682717453885668881354391379276091832437791327382673554621542363370695590872213882821916016679451005257003326444660295787578301365987666679013861017982035560204259777436442969488099
B = 12408624070212894491872051808326026233625878902991556747856160971787460076467522269639429595067604541456868927539680514190186916845592948405088662144279471
c1 = 47149257341850631803344907793040624016460864394802627848277699824692112650262968210121452299581667376809654259561510658416826163949830223407035750286554940980726936799838074413937433800942520987785496915219844827204556044437125649495753599550708106983195864758161432571740109614959841908745488347057154186396
c2 = 38096143360064857625836039270668052307251843760085437365614169441559213241186400206703536344838144000472263634954875924378598171294646491844012132284477949793329427432803416979432652621257006572714223359085436237334735438682570204741205174909769464683299442221434350777366303691294099640097749346031264625862
 
flag2_len = 98
hard_c1 = 73091191827823774495468908722773206641492423784400072752465168109870542883199959598717050676487545742986091081315652284268136739187215026022065778742525832001516743913783423994796457270286069750481789982702001563824813913547627820131760747156379815528428547155422785084878636818919308472977926622234822351389
hard_c2 = 21303605284622657693928572452692917426184397648451262767916068031147685805357948196368866787751567262515163804299565902544134567172298465831142768549321228087238170761793574794991881327590118848547031077305045920819173332543516073028600540903504720606513570298252979409711977771956104783864344110894347670094
 
P = PolynomialRing(Zmod(n), 'x')
x = P.gen()
 
 
f = x * (x + B) - c1
mul = (1 << (8 * (128 - flag1_len)))
cc = bytes_to_long(b"\x1e" * 30)
 
g = (mul * x + cc) * (mul * x + cc + B) - c2
g = g.monic()
 
h = f - g 
cc = h.coefficients()
 
m = (int(cc[0]) * inverse(int(n - cc[1]), n)) % n
flag1 = long_to_bytes(m)
 
'''
from sage.matrix.matrix2 import Matrix 
def resultant(f1, f2, var):
    return Matrix.determinant(f1.sylvester_matrix(f2, var))
n = 105663510238670420757255989578978162666434740162415948750279893317701612062865075870926559751210244886747509597507458509604874043682717453885668881354391379276091832437791327382673554621542363370695590872213882821916016679451005257003326444660295787578301365987666679013861017982035560204259777436442969488099
B = 12408624070212894491872051808326026233625878902991556747856160971787460076467522269639429595067604541456868927539680514190186916845592948405088662144279471
flag2_len = 98
hard_c1 = 73091191827823774495468908722773206641492423784400072752465168109870542883199959598717050676487545742986091081315652284268136739187215026022065778742525832001516743913783423994796457270286069750481789982702001563824813913547627820131760747156379815528428547155422785084878636818919308472977926622234822351389
hard_c2 = 21303605284622657693928572452692917426184397648451262767916068031147685805357948196368866787751567262515163804299565902544134567172298465831142768549321228087238170761793574794991881327590118848547031077305045920819173332543516073028600540903504720606513570298252979409711977771956104783864344110894347670094
POL.<x, y> = PolynomialRing(Zmod(n))
f = x * (x + B) - hard_c1
g = (x + y) * (x + y + B) - hard_c2
res = resultant(f, g, x)
print(res)
POL.<y> = PolynomialRing(Zmod(n))
h = y^4 + 79890495413921998317755749042148232336863396932303122279875240130974185840791225375990895444267582903006871773965303045933569843994868097491212523442101173551279596449914721209311144221088483103651821516943100935730831208926818636117783500717523025942791406004609937226219367532136778920138824547343785869589*y^2 + 51092857055466673249380987427595244393604870491102664532822637562859699012127822437087645886784256843354629922356917208150074797607882719481678015312190222601448915412917964775219154717370030324105055787501129672958587186322761301111111401381772704665208028130495822463025972061040003730113313298834567354767
print(h.small_roots(X = (1 << 240), beta = 1.0, epsilon = 0.025))''
y_cands = [1637558660573652475698054766420163959191730746581158985657024969935597275, 105663510238670420757255989578978162666434740162415948750279893317701612062865075870926559751210244886747509597507458509604874043682717453885668881354391379276091832437791327382673554621542363370695590872213882821916016679451005257003324807101635213925825667932900258849901826251288979045274120411473033890824]
POL.<x> = PolynomialRing(Zmod(n))
for y in y_cands:
    f = x * (x + B) - hard_c1
    g = (x + y) * (x + y + B) - hard_c2
    h = f - g
    print(h)
    cc = h.coefficients()
    print(cc)
    x = - cc[0] / cc[1]
    print(h(x))
    x = int(x)
    print("result", x)
    print(int(x * (x + B) - hard_c1) % n)
    print(int((x+y)*(x+y+B)-hard_c2) % n)
    break
'''
x1 = 37412309942286574006158913496010620267687663146876352767622106656129986496651165862840203148321069273733293624726376167460944865534151793748073347584719705531628535234167400567407324714477822390166015938266208084466510307154956915004073076813624952897284616411776573796324151099101617608303133521659321079317
x1 = n - B - x1
 
print((x1 * (x1+ B) - hard_c1) % n)
 
 
m = x1 >> 240
flag2= long_to_bytes(m)
print(flag2)
 
print(flag1 + flag2)
 cs

 

Wonderful Hash

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
import os
import string
from Crypto.Cipher import AES, ARC4, DES
 
BLOCK = 16
 
 
def bxor(a, b):
  res = [c1 ^ c2 for (c1, c2) in zip(a, b)]
  return bytes(res)
 
 
def block_hash(data):
  data = AES.new(data, AES.MODE_ECB).encrypt(b"\x00" * AES.block_size)
  data = ARC4.new(data).encrypt(b"\x00" * DES.key_size)
  data = DES.new(data, DES.MODE_ECB).encrypt(b"\x00" * DES.block_size)
  return data[:-2]
 
 
def hash(data):
  length = len(data)
  if length % BLOCK != 0:
    pad_len = BLOCK - length % BLOCK
    data += bytes([pad_len] * pad_len)
    length += pad_len
  block_cnt = length // BLOCK
  blocks = [data[i * BLOCK:(i + 1) * BLOCK] for i in range(block_cnt)]
  res = b"\x00" * BLOCK
  for block in blocks:
    res = bxor(res, block_hash(block))
  return res
 
 
def check(cmd, new_cmd):
  if len(cmd) != len(new_cmd):
    return False
  if hash(cmd) != hash(new_cmd):
    return False
  for c in new_cmd:
    if chr(c) not in string.printable:
      return False
  return True
 
 
cmd = (b"echo 'There are a lot of Capture The Flag (CTF) competitions in "
       b"our days, some of them have excelent tasks, but in most cases "
       b"they're forgotten just after the CTF finished. We decided to make"
       b" some kind of CTF archive and of course, it'll be too boring to "
       b"have just an archive, so we made a place, where you can get some "
       b"another CTF-related info - current overall Capture The Flag team "
       b"rating, per-team statistics etc'")
 
 
def menu():
  print("[S]tore command")
  print("[E]xecute command")
  print("[F]iles")
  print("[L]eave")
  return input("> ")
 
 
while True:
  choice = menu()
  if choice[0] == "S":
    new_cmd = input().encode()
    if check(cmd, new_cmd):
      cmd = new_cmd
    else:
      print("Oops!")
      exit(1)
  elif choice[0] == "E":
    os.system(cmd)
  elif choice[0] == "F":
    os.system(b"ls")
  elif choice[0] == "L":
    break
  else:
    print("Command Unsupported")
    exit(1)
 
 cs

 

We require some sort of a hash collision. Since the hash is simply XOR of the hash of each blocks, this problem is equivalent to finding $x_1, x_2, \cdots,  x_k$ given sets $X_1, X_2, \cdots, X_k$ such that the following holds. $$x_i \in X_i, \quad \oplus_{i=1}^k x_i = 0$$ Of course, if $k=2$ this is the well-known birthday problem. 

 

While I'm not sure if this was required for this challenge, this problem has been studied before. It's in the 2002 CRYPTO paper "A Generalized Birthday Problem", and it has been explained by barkingdog in his blog post https://www.secmem.org/blog/2020/08/19/A-Generalized-Birthday-Problem/. Using this, we can solve the problem in $\mathcal{O}(2^{n/(1+\log_2 k)})$. The basic idea is to make a binary tree and solve the problem "partially" (make LSBs zero) as we go upwards. For more details, consult the blog post above or the 2002 paper. 

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
r = remote('wonderful-hash.chal.acsc.asia', 10217)
 
for i in range(5):
    print(r.recvline())
ans = b'cat flag        DxriPBQeGgXmjlewgmpxnBnWbfoxGirrLUtUlukpPmjqMOlCBmaOIXXqKIGXoFJsdVGypWXGdXcPScZXFQPbnigusUZZdrxpCyMeGgKGqzJQIzbRqThOJXNgPPNXdPjIOtRhGKBXJDlYDGMfcnyAIojYUJaFyUhzjlsSQHZPasglvQOWIyVoYELtFwJQSsBPsNpvcKZYuKWBrEHwDQLkpCYWkbNIHPTHxbPqrzDgcXCnVvJKeIzkiMKqPhUwDRIe                                                                                                                                                 '
r.sendline("S")
r.sendline(ans)
for i in range(4):
    print(r.recvline())
 
r.sendline("E")
for i in range(10):
    print(r.recvline())
 
## main sol
BLOCK = 16
 
def bxor(a, b):
    res = [c1 ^ c2 for (c1, c2) in zip(a, b)]
    return bytes(res)
 
 
def block_hash(data):
    data = AES.new(data, AES.MODE_ECB).encrypt(b"\x00" * AES.block_size)
    data = ARC4.new(data).encrypt(b"\x00" * DES.key_size)
    data = DES.new(data, DES.MODE_ECB).encrypt(b"\x00" * DES.block_size)
    return data[:-2]
 
 
def hash(data):
    length = len(data)
    if length % BLOCK != 0:
        pad_len = BLOCK - length % BLOCK
        data += bytes([pad_len] * pad_len)
        length += pad_len
    block_cnt = length // BLOCK
    blocks = [data[i * BLOCK:(i + 1) * BLOCK] for i in range(block_cnt)]
    res = b"\x00" * BLOCK
    for block in blocks:
        res = bxor(res, block_hash(block))
    return res
 
def get_random_block():
    res = "".join([rand.choice(string.ascii_letters) for _ in range(16)])
    return res.encode()
 
cmd = (b"echo 'There are a lot of Capture The Flag (CTF) competitions in "
       b"our days, some of them have excelent tasks, but in most cases "
       b"they're forgotten just after the CTF finished. We decided to make"
       b" some kind of CTF archive and of course, it'll be too boring to "
       b"have just an archive, so we made a place, where you can get some "
       b"another CTF-related info - current overall Capture The Flag team "
       b"rating, per-team statistics etc'")
 
# 27 
 
print(len(cmd))
 
target = bytes_to_long(hash(cmd))
 
fin_blocks = []
block0 = b"cat flag" + b" " * 8
fin_blocks.append(block0)
 
target ^= bytes_to_long(block_hash(block0))
 
back_blocks = []
for i in range(9):
    back_blocks.append(b" " * 16)
    target ^= bytes_to_long(block_hash(b" "*16))
back_blocks.append(b" ")
target ^= bytes_to_long(block_hash(b" " + bytes([15] * 15)))
 
 
# now we need 16 blocks
 
grounds = []
for i in range(16):
    cur = []
    for j in range(6000):
        val = get_random_block()
        cc = block_hash(val)
        cc = bytes_to_long(cc)
        if i == 7:
            cc ^= target
        cur.append([[val], cc])
    grounds.append(cur)
 
def merger(l, r, tot): # merging [l, r) to have tot zeros
    print("WORKING", l, r, tot)
    global grounds
    if l + 1 == r:
        return grounds[l]
    cc1 = merger(l, (l+r)//2, tot - 12)
    cc2 = merger((l+r) // 2, r, tot - 12)
    print(l, (l+r)//2, len(cc1))
    print((l+r)//2, r, len(cc2))
    LEFT = {}
    for i in range(len(cc1)):
        res = cc1[i][1] % (1 << tot)
        if res in LEFT.keys():
            arr = LEFT[res]
            arr.append(i)
            LEFT[res] = arr
        else:
            LEFT[res] = [i]
    ret = []
    for i in range(len(cc2)):
        res = cc2[i][1] % (1 << tot)
        if res in LEFT.keys():
            arr = LEFT[res]
            for idx in arr:
                xred = cc1[idx][1] ^ cc2[i][1]
                vals = cc1[idx][0] + cc2[i][0]
                ret.append([vals, xred])
    return ret
 
fin = merger(0, 16, 48)
print(fin[0])
 
ret = fin[0][0]
 
sol = fin_blocks + ret + back_blocks
 
gogo = b""
for block in sol:
    gogo += block
 
print(gogo)
print(len(gogo))
 
print(hash(gogo))
print(hash(cmd))
 cs

 

Share The Flag

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#!/usr/bin/env python3
import os
import random
import string
 
 
with open('flag.txt', 'rb') as f:
    FLAG = f.read().strip()
assert FLAG.startswith(b'ACSC{')
assert FLAG.endswith(b'}')
SECRET = FLAG[5:-1]
assert len(SECRET) == 16
 
p = 251
 
def random_letters(n):
    return ''.join(random.choices(string.ascii_lowercase, k=n)).encode()
 
print("""\
.----------------.
| Share the flag |
'----------------'
 
Welcome to our flag-sharing service.
We understand some of you couldn't resist sharing flags with others,
but it is STRICTLY PROHIBITED by the rules.
In order to satisfy your desire...
We made the official flag sharing service for you,
with a new algorithm inspired by Shamir Secret Sharing.
 
""")
 
# You'll need at least `threshold` shares to unlock the flag
threshold = 32
 
# Admin holds `len(SECRET) + 1` shares.
nshares = threshold - (len(SECRET) + 1)
 
# Splitting the flag
padding = random_letters(threshold - len(SECRET))
coeff = list(SECRET + padding)
 
xs = bytes(random.sample(range(1, p), k=nshares))
ys = bytes(sum(c * pow(x, i, p) for i, c in enumerate(coeff)) % p for x in xs)
print(f'X: {xs.hex()}')
print(f'Y: {ys.hex()}')
 
 cs

 

This will be explained further later when I upload the CVP repository updates. 

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
def SVP_oracle(mat):
    M = mat.BKZ(block_size = 30)
    return M
 
def solve(mat, lb, ub):
    num_var  = mat.nrows()
    num_ineq = mat.ncols()
 
    max_element = 0 
    for i in range(num_var):
        for j in range(num_ineq):
            max_element = max(max_element, abs(mat[i, j]))
 
    # sanity checker
    if len(lb) != num_ineq:
        print("Fail: len(lb) != num_ineq")
        return None, None 
 
    if len(ub) != num_ineq:
        print("Fail: len(ub) != num_ineq")
        return None, None 
 
    for i in range(num_ineq):
        if lb[i] > ub[i]:
            print("Fail: lb[i] > ub[i] at index", i)
            return None, None 
 
    if num_var != num_ineq:
        print("Fail: This time, we require num_var = num_ineq")
        return None, None
    
    N = (num_var + num_ineq) // 2
    
    # heuristic for number of solutions
    DET = abs(mat.det())
    num_sol = 1
    for i in range(N):
        num_sol *= (ub[i] - lb[i] + 1)
    
    if DET == 0:
        print("Fail: Zero Determinant")
        return None, None
    else:
        num_sol //= DET
        # + 1 added in for the sake of not making it zero...
        print("Expected Number of Solutions : ", num_sol + 1)
 
    # recentering + scaling process begins
    max_diff = max([ub[i] - lb[i] for i in range(N)])
    applied_weights = []
 
    for i in range(N):
        ineq_weight = max_diff // (ub[i] - lb[i])
        applied_weights.append(ineq_weight)
        for j in range(N):
            mat[j, i] *= ineq_weight
        lb[i] *= ineq_weight
        ub[i] *= ineq_weight
 
    target = vector([(lb[i] + ub[i]) // 2 for i in range(N)])
 
    embedding = 251
 
    Kannan = Matrix(ZZ, N+1, N+1)
    for i in range(0, N):
        for j in range(0, N):
            Kannan[i, j] = mat[i, j]
        Kannan[i, N] = 0
    for i in range(0, N):
        Kannan[N, i] = target[i]
    Kannan[N, N] = embedding
 
    # SVP time
    result = SVP_oracle(Kannan)
 
    # finding solution
    fin_result = None 
    for i in range(N+1):
        isok = True
        if abs(result[i, N]) != embedding:
            isok = False
        result_vector = result[i]
        if result[i, N] == embedding:
            result_vector = -result_vector
            # now result = actual_vector - target
        for j in range(N):
            if (lb[j] <= result_vector[j] + target[j] <= ub[j]) == False:
                isok = False
        if isok == False:
            continue
        print("Found Vector!!")
        fin_result = result_vector[:N] + target
    
    if fin_result == None:
        print("Fail: could not solve...")
        return None, None
    
    return fin_result, applied_weights
 
 
 
# r = remote('share-the-flag.chal.acsc.asia', 37896)
# r.interactive()
 
p = 251
X = bytes.fromhex("02d4623be12c8f01cb2ebe5f837c1d")
Y = bytes.fromhex("bbdc06ceb34da7b16336b007dc5492")
X2 = bytes.fromhex("2fb9e753b237e68d35e266b0f01c9e")
Y2 = bytes.fromhex("20c0be9140f5a33d71b9e82f8f9409")
X3 = bytes.fromhex("f42e3ee10edeade0a3804a22e86a63")
Y3 = bytes.fromhex("c7224da73d9d96254f94136d9a65f1")
X4 = bytes.fromhex("37c9b07870283dd3f6198c46f027dd")
Y4 = bytes.fromhex("8101a88a365526e8faf417b79599a0")
X5 = bytes.fromhex("b0342cb7b3f5a022d927f9019a1bf3")
Y5 = bytes.fromhex("e2666d892955494775aa3c96c441f5")
X6 = bytes.fromhex("e56bf4f9e746252dbacb93a0a95087")
Y6 = bytes.fromhex("cbb43831857333b2c4663ba2c9189a")
X7 = bytes.fromhex("99ca36b1633cf3d903d8e6291f1bdc")
Y7 = bytes.fromhex("25180068651818171d10422dbdb395")
 
M = Matrix(GF(p), 105, 128)
vec = []
for i in range(105):
    x, y = 0, 0
    if i < 15:
        x = int(X[i])
        y = int(Y[i])
    elif i < 30:
        x = int(X2[i - 15])
        y = int(Y2[i - 15])
    elif i < 45:
        x = int(X3[i - 30])
        y = int(Y3[i - 30])
    elif i < 60:
        x = int(X4[i - 45])
        y = int(Y4[i - 45])
    elif i < 75:
        x = int(X5[i - 60])
        y = int(Y5[i - 60])
    elif i < 90:
        x = int(X6[i - 75])
        y = int(Y6[i - 75])
    elif i < 105:
        x = int(X6[i - 90])
        y = int(Y6[i - 90])
 
    vec.append(y)
    for j in range(16):
        M[i, j] = (x ** j) % p
    if i < 15:
        for j in range(16):
            M[i, j + 16] = (x ** (j + 16)) % p
    elif i < 30:
        for j in range(16):
            M[i, j + 32] = (x ** (j + 16)) % p
    elif i < 45:
        for j in range(16):
            M[i, j + 48] = (x ** (j + 16)) % p
    elif i < 60:
        for j in range(16):
            M[i, j + 64] = (x ** (j + 16)) % p
    elif i < 75:
        for j in range(16):
            M[i, j + 80] = (x ** (j + 16)) % p
    elif i < 90:
        for j in range(16):
            M[i, j + 96] = (x ** (j + 16)) % p
    elif i < 105:
        for j in range(16):
            M[i, j + 112] = (x ** (j + 16)) % p
 
vec = vector(GF(p), vec)
 
bas = M.right_kernel().basis()
print(len(bas))
v = M.solve_right(vec)
 
# v + bas -> all in 97 ~ 122
 
M = Matrix(ZZ, 151, 151)
lb = [0] * 151
ub = [0] * 151
 
for i in range(23):
    for j in range(128):
        M[i, j] = int(bas[i][j])
    M[i, 128 + i] = 1
for i in range(128):
    M[23 + i, i] = p
for i in range(128):
    if i >= 16:
        lb[i] = int(97 - int(v[i]))
        ub[i] = int(122 - int(v[i]))
    else:
        lb[i] = int(32-int(v[i]))
        ub[i] = int(128-int(v[i]))
for i in range(23):
    lb[i + 128] = 0
    ub[i + 128] = p
 
fin_result, applied_weights = solve(M, lb, ub)
 
flag = ''
 
for i in range(16):
    flag += chr((fin_result[i] // applied_weights[i] + int(v[i]) + 251 * 30) % 251)
 
print("ACSC{" + flag + "}")
 cs

 

저작자표시 비영리

'CTF' 카테고리의 다른 글

TSGCTF 2021 Writeups  (0) 2021.10.03
DUCTF 2021 Writeups  (0) 2021.09.26
CryptoCTF Writeups (DoRSA, Polish)  (0) 2021.08.05
GoogleCTF Quals 2021 Crypto Writeups  (1) 2021.07.19
zer0lfsr 2021 Full Writeup (0CTF/TCTF 2021)  (2) 2021.07.05

main.pdf
3.41MB

쓰기 시작한지는 꽤 되었는데

  • 회사 + 연구 + CTF하면서 시간이 잘 안나서 + 게을러져서 (...) 진도가 안빠지고
  • 이대로 두었다가는 지금까지 쓴 부분도 공개가 너무 늦어질 것 같고
  • 사실 지금까지 쓴 부분만 잘 이해해도 문제 해결에 지장이 없어서

미리 올립니다. 솔직히 머리 속에는 어떻게 글을 써야하는지 아는데 실제로 글을 쓰려면 막막해서 슬프네요 :(

 

그래도 이거 올리고 사람들이 좀 읽어주면 이 글을 다시 쓸 motivation을 얻을 것 같기도 하고 잘 모르겠습니다

 

LaTeX 형식은 Evan Chen의 Napkin에서 가져왔습니다. 참고하세요.

저작자표시 비영리

'PS > PS 정수론 가이드' 카테고리의 다른 글

12. 개인적인 후기, 그리고 그 이후의 이야기  (6) 2021.01.06
11. more on multiplicative functions  (0) 2021.01.04
10. 소수의 개수 빠르게 세기  (1) 2021.01.04
9. 유클리드 알고리즘의 활용  (2) 2021.01.03
8. 원시근, 이산로그, 이산제곱근  (3) 2021.01.02

4번 문제를 5시가 되기 직전에 해결했다. 사진은 7시 쯤 찍었다.

5번은 긁기는 쉬운데 만점을 받는 사람이 없길래 그냥 건드리지 않았다. 4번도 풀었고 ^__^

 

1번 : 원 안의 점 

naive 하게 $-R \le x, y \le R$인 점을 모두 시도하면 $\mathcal{O}(R^2)$ 풀이가 나온다. 

답을 $\mathcal{O}(R)$에 구하기 위해서는, $x$ 하나를 고정하고 가능한 $y$의 개수를 $\mathcal{O}(1)$에 구하면 된다.

$x^2+y^2 \le R^2-1 \iff -\sqrt{R^2-1-x^2} \le y \le \sqrt{R^2 -1-x^2}$임을 계산하면, 가능한 $y$의 개수가 $$2 \lfloor \sqrt{R^2 - 1 - x^2} \rfloor + 1$$임을 알 수 있다. 이는 sqrt 함수를 사용하거나 이분탐색을 해서 빠르게 계산할 수 있다. 

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <bits/stdc++.h>
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ldb;
const ll mod = 1e9 + 7;
 
ll calc(ll x)
{
    ll lef=0, rig=1e9, best=0, mid;
    while(lef<=rig)
    {
        mid = (lef + rig) / 2;
        if(mid * mid <= x) 
        {
            best = mid;
            lef = mid + 1;
        }
        else rig = mid - 1;
    }
    return best;
}
 
void solve(void)
{
    ll R, ans=0; cin >> R;
    for(ll i=-R+1 ; i<=R-1 ; i++)
        ans += 2 * calc(R * R - 1 - i * i) + 1;
    cout << ans << endl;
}
 
 
int main(void)
{
    fio; ll i, tc; cin >> tc;
    for(i=1 ; i<=tc ; i++) 
    {
        cout << "Case #" << i << endl;
        solve(); // endl in solve
    }
    return 0;
}
 cs

 

2번 : 직8각형

점 $(x_1, y_1), \cdots (x_8, y_8)$이 있을 때, 적당한 $X, Y$를 골라서 이 점들을 $$(X, Y), (X, Y+K), (X+K, Y+2K), (X+2K, Y+2K)$$ $$(X+3K, Y+K), (X+3K, Y), (X+2K, Y-K), (X+K, Y-K)$$와 같도록 해야 한다. 각 8개의 점을 직8각형의 8개의 점에 대응시키는 방법에는 총 $8!$가지가 있다. 이러한 방법을 하나 고정시키고 생각하자.

 

예를 들어, $(x_1, y_1), \cdots , (x_8, y_8)$이 위 8개의 점과 순서대로 대응된다고 가정하자. 이 경우, 움직여야 하는 총 거리는 $$|x_1 - X| + |y_1 - Y| + |x_2 - X| + |y_2 - (Y+K)| + |x_3 - (X+K)| + |y_3 - (Y+2K)|$$ $$+|x_4 - (X+2K)| + |y_4 - (Y+2K)| + |x_5 - (X+3K)| + |y_5 - (Y+K)| + |x_6 - (X+3K)| + |y_6 - Y|$$ $$+|x_7 - (X+2K)| + |y_7 - (Y-K)| + |x_8 - (X+K)| + |y_8 - (Y-K)|$$가 되며, 우리의 목표는 이 식의 최솟값을 구하는 것이다.

첫 번째 관찰은 위 식에서 $X, Y$가 각각 독립적으로 나온다는 것이다. 위 식에서 $X$가 등장하는 부분만 살펴보면, $$|X-x_1| + |X-x_2| + |X - (x_3-K)| + |X - (x_4-2K)|$$ $$+ |X - (x_5-3K)| + |X - (x_6-3K)| + |X - (x_7 - 2K)| + |X - (x_8 -K)|$$ 두 번째 관찰은, $x_i$들과 $K$가 이미 알고 있는 값이므로, 이 식은 이미 알고 있는 값 $c_1, c_2, \cdots, c_8$에 대해 $$\sum_{i=1}^8 |X - c_i|$$ 형태로 쓸 수 있다는 것이다. 이 식은 $X$가 $c_i$들의 "중간"에 있을 때 최솟값을 가진다.

확인하고 싶다면, 위 식을 그래프로 그려보자. 또한, 이 때 최솟값은 $c_i$들 중 최대 4개에서 최소 4개를 뺀 값이 됨을 확인할 수 있다.

$Y$에 대한 부분도 이렇게 최솟값을 구할 수 있으며, 두 결과를 합치면 식의 최솟값을 구할 수 있다. 이를 $8!$번 반복하면 해결.

 

시간복잡도는 $n$이 점의 개수라고 하면, $\mathcal{O}(n! \cdot n \log n)$ 정도로 볼 수 있을 것이다.

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <bits/stdc++.h>
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ldb;
const ll mod = 1e9 + 7;
 
pair<ll, ll> pts[8]; ll K;
ll x[8], y[8];
ll difx[8] = {0, 0, 1, 2, 3, 3, 2, 1};
ll dify[8] = {0, 1, 2, 2, 1, 0, -1, -1};
 
void solve(void)
{
    ll i, ans=1e18; cin >> K; 
    for(i=0 ; i<8 ; i++) cin >> pts[i].first >> pts[i].second;
    sort(pts, pts+8);
    do
    {   
        for(i=0 ; i<8 ; i++) x[i] = pts[i].first - difx[i] * K;
        for(i=0 ; i<8 ; i++) y[i] = pts[i].second - dify[i] * K;
        sort(x, x+8); sort(y, y+8);
        ll cur = 0;
        for(i=4 ; i<8 ; i++) cur += (x[i] + y[i]);
        for(i=0 ; i<4 ; i++) cur -= (x[i] + y[i]);
        ans = min(ans, cur);
    } while(next_permutation(pts, pts+8));
    cout << ans << endl;
}
 
int main(void)
{
    fio; ll i, tc; cin >> tc;
    for(i=1 ; i<=tc ; i++) 
    {
        cout << "Case #" << i << endl;
        solve(); // endl in solve
    }
    return 0;
}
 cs

 

3번 : 산탄총

정말 피곤한 문제였다. 진짜 부분합만 알면 풀 수 있는데, 깔끔하게 안 풀어서 그런지 계산이 너무 귀찮았다.

이제부터 모든 것을 수식으로 설명한다. 하지만 실제로 문제를 풀거나 이 풀이를 읽을 때는 그림을 그려가면서 생각하는 것이 좋을 것이다.

 

배열은 1-index를 사용하여, $1 \le i, j \le N$에 배열 $a$가 채워졌다고 생각하도록 하겠다.

 

우선, 목표로 하는 함수인 $$ \text{score}(Y, X) = \sum_{|y-Y| + |x-X| \le K-1} (K-|y-Y|-|x-X|) \cdot a[y][x]$$를 정의하면, 우리의 목표는 $\text{score}$의 최댓값을 찾는 것이다. 우선 $Y$ 또는 $X$가 $-K$ 미만이거나 $N+K$ 초과면, $\text{score}$ 함수가 $0$이 됨을 확인할 수 있다.

그러니 $-K \le X, Y \le N+K$인 경우만 계산하면 된다. 우리의 궁극적인 목표는 $\text{score}$ 함수를 이 범위 전체에 대해서 $\mathcal{O}((N+K)^2) = \mathcal{O}(N^2)$ 시간에 계산하는 것이다. 이를 위해서는 $\text{score}$ 함수가 $(Y, X)$가 한 칸 움직였을 때 어떻게 변화하는지 알아볼 필요가 있다. 

$$\text{score}(Y, X) - \text{score}(Y, X-1)$$ $$= \sum_{|y-Y| + |x-X| \le K-1} (K-|y-Y|-|x-X|) \cdot a[y][x] - \sum_{|y-Y| + |x-X+1| \le K-1} (K - |y-Y| - |x-X+1|) \cdot a[y][x]$$

이 값을 분석하는 가장 좋은 방법은 각 $(y, x)$에 대해 $a[y][x]$의 계수를 찾는 것이다. 그림을 그려 풀 때도 비슷하다.

 

우선 생각해보면 $|y-Y|+|x-X|$와 $|y-Y|+|x-(X-1)|$이 모두 $K$ 이하인 경우, $a[y][x]$의 계수는 $$|x-X+1| - |x-X|$$가 된다. 이 값은 $x \ge X$에서 $1$이고 $x \le X-1$에서 $-1$임을 알 수 있다. 

$|y-Y|+|x-X|$나 $|y-Y|+|x-(X-1)|$ 중 하나라도 $K+1$ 이상인 경우, 둘 다 $K$ 이상이 되어 계수는 $0$이다. 즉,

$$\text{score}(Y, X) - \text{score}(Y, X-1) = \sum_{|y-Y| + |x-X| \le K-1, x \ge X} a[y][x] - \sum_{|y-Y| + |x-X+1| \le K-1, x \le X-1} a[y][x] $$가 되고, 비슷한 원리로 계산하면 $$\text{score}(Y, X) - \text{score}(Y-1, X) = \sum_{|y-Y|+|x-X| \le K-1, y \ge Y} a[y][x] - \sum_{|y-Y+1|+|x-X| \le K-1,  y \le Y-1} a[y][x]$$를 얻는다. 그러니까 이제 필요한 것은 네 종류의 "삼각형 부분합"이며, 이들 역시 같은 방법으로 계산이 가능하다.

 

예를 들어, "1사분면에 대한 삼각형 부분합"을 $$Q1(Y, X) = \sum_{|y-Y| + |x-X| \le K-1, y \le Y, x \ge X} a[y][x]$$라 하자. 이 값을 계산하기 위하여, 다시 인접한 $Q1$ 값의 차이를 계산해보면, $$Q1(Y, X) - Q1(Y, X-1) = \sum_{|y-Y| + |x-X| \le K-1, y \le Y, x \ge X} a[y][x] - \sum_{|y-Y| + |x-X+1| \le K-1, y \le Y, x \ge X-1} a[y][x]$$인데, $a[y][x]$의 계수를 생각해보면 다음과 같은 결과를 얻을 수 있다. 그림을 그려서 생각하는 게 편하다.

  • $x \ge X, y \le Y$이고 $(Y-y) + (x-X) = |y-Y|+|x-X| = K-1$이면 계수가 $+1$
  • $x = X-1$이고 $Y-K+1 \le y \le Y$면 계수가 $-1$
  • 나머지 경우에 대해서는 전부 계수가 $0$

첫 번째 경우에 대한 합은 "대각선 부분합"이고, 두 번째 경우에 대한 합은 "일직선 부분합"이니, 전부 부분합 테크닉으로 빠르게 구할 수 있다.

그러니 $Q1(Y, X-1)$이 있으면 $Q1(Y, X)$를 구할 수 있고, 비슷한 계산으로 $Q1(Y-1, X)$이 있으면 $Q1(Y, X)$를 빠르게 구하는 식을 얻을 수 있다.

 

$Q1(-K, -K)$를 naive 하게 직접 구한 후 위 방법을 적용하면 모든 $Y, X$에 대해 $Q1(Y, X)$를 $\mathcal{O}(N^2)$에 구할 수 있다.

이를 각 4개의 사분면에 대해서 적용할 수 있고, 이제 $\text{score}$ 역시 전부 $\mathcal{O}(N^2)$에 구할 수 있다. 

 

당연하지만 이 문제에서는 index가 범위를 벗어나는 것에 대한 처리가 매우 귀찮고 중요하다.

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
#include <bits/stdc++.h>
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ldb;
const ll mod = 1e9 + 7;
 
ll K, N;
ll val[1811][1811];
ll DIAG1[1811][1811]; // NW SE
ll DIAG2[1811][1811]; // NE SW
ll WE[1811][1811];
ll NS[1811][1811];
ll CALC[1811][1811];
ll QUAD[4][1811][1811];
 
void rset(void)
{
    memset(val, 0, sizeof(val));
    memset(DIAG1, 0, sizeof(DIAG1));
    memset(DIAG2, 0, sizeof(DIAG2));
    memset(WE, 0, sizeof(WE));
    memset(NS, 0, sizeof(NS));
    memset(CALC, 0, sizeof(CALC));
    memset(QUAD, 0, sizeof(QUAD));
}
 
ll NS_p(ll Y1, ll Y2, ll X)
{
    Y1 = min(Y1, N + 2 * K);
    Y2 = max(Y2, 0LL);
    return NS[Y1][X] - NS[Y2][X];
}
 
ll WE_p(ll Y, ll X1, ll X2)
{
    X1 = min(X1, N + 2 * K);
    X2 = max(X2, 0LL);
    return WE[Y][X1] - WE[Y][X2];
}
 
ll getdiag1(ll Y1, ll X1)
{
    if(Y1 < 0 || X1 < 0) return 0;
    else if(Y1 <= N+2*K && X1 <= N+2*K) return DIAG1[Y1][X1];
    else
    {
        ll offset = max(Y1 - (N + 2 * K), X1 - (N + 2 * K));
        Y1 -= offset; X1 -= offset;
        if(Y1 < 0 || X1 < 0) return 0;
        else return DIAG1[Y1][X1];
    }
}
 
ll DIAG1_p(ll Y1, ll X1, ll Y2, ll X2)
{
    return getdiag1(Y1, X1) - getdiag1(Y2, X2);
}
 
ll getdiag2(ll Y1, ll X1)
{
    if(Y1 < 0 || X1 > N + 2 * K) return 0;
    else if(Y1 <= N+2*K && X1 >= 0) return DIAG2[Y1][X1];
    else 
    {
        ll offset = max(Y1 - (N + 2 * K), -X1);
        Y1 -= offset; X1 += offset;
        if(Y1 < 0 || X1 < 0 || X1 > N + 2 * K) return 0;
        else return DIAG2[Y1][X1];
    }
}
 
ll DIAG2_p(ll Y1, ll X1, ll Y2, ll X2)
{
    return getdiag2(Y1, X1) - getdiag2(Y2, X2);
}
 
ll getval(ll Y, ll X)
{
    if(X<=0 || X>N+2*K || Y<=0 || Y>N+2*K) return 0;
    return val[Y][X];
}
 
void finish_QUAD0(void)
{
    ll i, j;
    for(i=0 ; i<=K-1 && i<=1 ; i++)
        for(j=0 ; i+j<=K-1 ; j++)
            QUAD[0][1][1] += getval(1-i, 1+j);
    for(i=1 ; i<=N+2*K ; i++)
    {
        for(j=1 ; j<=N+2*K ; j++)
        {
            if(i == 1 && j == 1) continue;
            if(j == 1) // get from top
            {
                QUAD[0][i][j] = QUAD[0][i-1][j] 
                               + WE_p(i, j+K-1, j-1)
                               - DIAG1_p(i-1, j+K-1, i-K-1, j-1);
 
            }
            else // get from left
            {
                QUAD[0][i][j] = QUAD[0][i][j-1]
                               + DIAG1_p(i, j+K-1, i-K, j-1) 
                               - NS_p(i, i-K, j-1);
            }
        }
    }
}
 
void finish_QUAD1(void)
{
    ll i, j;
    for(i=0 ; i<=K-1 && i<=1 ; i++)
        for(j=0 ; i+j<=K-1 && j<=1; j++)
            QUAD[1][1][1] += getval(1-i, 1-j);
    for(i=1 ; i<=N+2*K ; i++)
    {
        for(j=1 ; j<=N+2*K ; j++)
        {
            if(i == 1 && j == 1) continue;
            if(j == 1) // get from top
            {
                QUAD[1][i][j] = QUAD[1][i-1][j]
                              + WE_p(i, j, j-K)
                              - DIAG2_p(i-1, j-K+1, i-K-1, j+1);
            }
            else // get from left
            {
                QUAD[1][i][j] = QUAD[1][i][j-1]
                              + NS_p(i, i-K, j)
                              - DIAG2_p(i, j-K, i-K, j);
            }
        }
    }
}
 
void finish_QUAD2(void)
{
    ll i, j;
    for(i=0 ; i<=K-1 ; i++)
        for(j=0 ; i+j<=K-1 && j<=1 ; j++)
            QUAD[2][1][1] += getval(1+i, 1-j);
    for(i=1 ; i<=N+2*K ; i++)
    {
        for(j=1 ; j<=N+2*K ; j++)
        {
            if(i == 1 && j == 1) continue;
            if(j == 1) // get from top
            {
                QUAD[2][i][j] = QUAD[2][i-1][j]
                              + DIAG1_p(i+K-1, j, i-1, j-K)
                              - WE_p(i-1, j, j-K);
            }
            else // get from left
            {
                QUAD[2][i][j] = QUAD[2][i][j-1]
                              + NS_p(i+K-1, i-1, j) 
                              - DIAG1_p(i+K-1, j-1, i-1, j-K-1);
            }
        }
    }
}
 
void finish_QUAD3(void)
{
    ll i, j;
    for(i=0 ; i<=K-1 ; i++)
        for(j=0 ; i+j<=K-1 ; j++)
            QUAD[3][1][1] += val[1+i][1+j];
    for(i=1 ; i<=N+2*K ; i++)
    {
        for(j=1 ; j<=N+2*K ; j++)
        {
            if(i == 1 && j == 1) continue;
            if(j == 1) // get from top
            {
                QUAD[3][i][j] = QUAD[3][i-1][j]
                              + DIAG2_p(i+K-1, j, i-1, j+K)
                              - WE_p(i-1, j+K-1, j-1);
            }
            else // get from left
            {
                QUAD[3][i][j] = QUAD[3][i][j-1]
                              + DIAG2_p(i+K-1, j, i-1, j+K)
                              - NS_p(i+K-1, i-1, j-1);
            }
        }
    }
}
 
void solve(void)
{
    ll i, j; rset(); cin >> N >> K;
    for(i=1 ; i<=N ; i++)
        for(j=1 ; j<=N ; j++)
             cin >> val[K+i][K+j];
    for(i=0 ; i<=N+2*K ; i++)
    {
        for(j=0 ; j<=N+2*K ; j++)
        {
            if(i!=0 && j!=0) DIAG1[i][j] = DIAG1[i-1][j-1] + val[i][j];
            if(i!=0) DIAG2[i][j] = DIAG2[i-1][j+1] + val[i][j];
            if(j!=0) WE[i][j] = WE[i][j-1] + val[i][j];
            if(i!=0) NS[i][j] = NS[i-1][j] + val[i][j];
        }
    }
    finish_QUAD0(); finish_QUAD1(); finish_QUAD2(); finish_QUAD3();
    for(i=1 ; i<=K ; i++)
    {
        for(j=1 ; j<=K ; j++)
        {
            ll dist = abs(i-1) + abs(j-1);
            if(dist <= K-1) CALC[1][1] += (K - dist) * val[i][j];
        }
    }
    for(i=1 ; i<=N+2*K ; i++)
    {
        for(j=1 ; j<=N+2*K ; j++)
        {
            if(i == 1 && j == 1) continue;
            if(j == 1) // get from top
            {
                CALC[i][j] = CALC[i-1][j];
                CALC[i][j] += (QUAD[2][i][j] + QUAD[3][i][j] - NS_p(i+K-1, i-1, j));
                CALC[i][j] -= (QUAD[0][i-1][j] + QUAD[1][i-1][j] - NS_p(i-1, i-K-1, j));
            }
            else // get from left 
            {
                CALC[i][j] = CALC[i][j-1];
                CALC[i][j] += (QUAD[0][i][j] + QUAD[3][i][j] - WE_p(i, j+K-1, j-1));
                CALC[i][j] -= (QUAD[1][i][j-1] + QUAD[2][i][j-1] - WE_p(i, j-1, j-K-1));
            }
        }
    }
    ll ans = 0;
    for(i=1 ; i<=N+2*K ; i++)
        for(j=1 ; j<=N+2*K ; j++)
            ans = max(ans, CALC[i][j]);
    cout << ans << endl;
}
 
int main(void)
{
    fio; ll i, tc; cin >> tc;
    for(i=1 ; i<=tc ; i++) 
    {
        cout << "Case #" << i << endl;
        solve(); // endl in solve
    }
    return 0;
}
 cs

 

4번 : 패턴 매칭

부분문제 2까지는 최근 IOI 선발고사에서 나온 문제와 같고, 이 아이디어를 확장하면 문제를 해결할 수 있다.

 

저 동치 조건을 깔끔하게 나타낼 방법을 찾는 것이 이 문제를 해결하는 핵심이다.

결론부터 말하자면, 각 문자열의 각 문자에 대해서 "마지막으로 그 문자가 나온 위치까지의 거리"를 생각하면 동치 조건이 깔끔해진다. 예를 들어, 

 

superguesser의 경우 순서대로 마지막으로 그 문자가 나온 위치까지 거리가 -1, -1, -1, -1, -1, -1, 5, 4, 8, 1, 3, 7가 된다.

abcdefbdaade도 역시 순서대로 마지막으로 그 문자가 나온 위치까지 거리가 -1, -1, -1, -1, -1, -1, 5, 4, 8, 1, 3, 7가 된다.

 

단, -1은 이전에 그 문자가 나오지 않았음을 의미한다.  

또한, 이 두 문자열은 동치임을 직접 확인할 수 있으며, 일반적으로도 이렇게 두 문자열의 동치 여부를 확인할 수 있음을 증명할 수 있다.

 

이제 가장 "자연스러운" 접근은, 문자열을 위와 같이 숫자 형태로 전환시킨 다음, KMP를 쓰는 것이다. 

이 접근은 다 좋은데, -1을 처리하는 것에 약간의 신경을 써야 한다. 예를 들어, KMP를 쓰면 기본적으로 하는 접근이 $[i-fail[i]+1, i]$가 전체 문자열의 prefix와 같다는 것이다. 여기서 다음 문자를 확인하여 이 prefix를 연장시킬 수 있는지 확인해야 한다. 만약 실제 prefix에서 $fail[i]$번째 문자에 대응되는 값이 -1이라면, 이는 이 문자가 prefix에서 지금까지 등장하지 않은 문자임을 의미한다. 이를 확인하기 위해서는 단순히 $i+1$번째 문자에 대응되는 값이 -1임을 확인하면 안되고, 그 값이 -1이거나 $fail[i]$를 초과하는지 확인해야 한다. 즉, KMP에서 지금 확인하고 있는 suffix의 범위를 넘어가는 경우를 역시 고려해주어야 한다.

 

여기까지 생각하면 KMP 코드를 거의 그대로 가져와서 부분문제 2까지 해결할 수 있다.

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include <bits/stdc++.h>
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ldb;
const ll mod = 1e9 + 7;
 
string s; ll N, K;
string pat[31111];
ll pogs[2222222];
ll fail[511], pog[511];
ll rec_s[26], rec_p[26];
 
void precompute(void)
{
    ll i;
    for(i=0 ; i<26 ; i++) rec_s[i] = -1;
    for(i=0 ; i<s.length() ; i++)
    {
        int cur = s[i] - 'a';
        if(rec_s[cur] == -1) pogs[i] = -1;
        else pogs[i] = i - rec_s[cur];
        rec_s[cur] = i;
    }
}
 
ll calc(ll idx)
{
    ll i, j=0; 
    for(i=0 ; i<26 ; i++) rec_p[i] = -1;
    memset(fail, 0, sizeof(fail));
    for(i=0 ; i<pat[idx].length() ; i++)
    {   
        int cur = pat[idx][i] - 'a';
        if(rec_p[cur] == -1) pog[i] = -1;
        else pog[i] = i - rec_p[cur];
        rec_p[cur] = i;
    }
    for(i=1 ; i<pat[idx].length() ; i++)
    {
        while(1)
        {
            if(j == 0) break;
            if(pog[i] == pog[j]) break;
            if(pog[j] == -1 && pog[i] > j) break;
            j = fail[j-1];
        }
        if((pog[i] == pog[j]) || (pog[j] == -1 && pog[i] > j)) fail[i]=++j;
    }
    ll ret=0; j=0;
    for(i=0 ; i<s.length() ; i++)
    {
        while(j>0 && !(pogs[i] == pog[j] || (pog[j] == -1 && pogs[i] > j))) j=fail[j-1];
        if((pogs[i] == pog[j]) || (pog[j] == -1 && pogs[i] > j))
        {
            if(j==pat[idx].length()-1) { ret++; j=fail[j]; }
            else j++;
        }
    }
    return ret;
}
 
void solve(void)
{
    cin >> N >> K; ll i, ans = 0; cin >> s; precompute();
    for(i=1 ; i<=K ; i++) cin >> pat[i];
    for(i=1 ; i<=K ; i++) ans += i * calc(i);
    cout << ans << endl;
}
 
int main(void)
{
    fio; ll i, tc; cin >> tc;
    for(i=1 ; i<=tc ; i++) 
    {
        cout << "Case #" << i << endl;
        solve(); // endl in solve
    }
    return 0;
}
 cs

 

이제 패턴이 여러 개 존재하니, KMP를 Aho-Corasick으로 바꾸어주면 된다. Trie의 각 노드에는

  • 기본적인 정보인 failure link, output link, count, 끝 정점인지 여부 
  • 현재 보고 있는 문자열의 길이 (-1을 처리하기 위함이다)
  • 그리고 각 경우에 대응되는 다음 노드의 포인터

를 저장한다. 이때, 다음 노드를 확인하기 위해 사용하는 것은 알파벳 자체가 아니라 해당 알파벳의 마지막 등장 위치까지의 거리다. 

각 노드에 저장되어 있는 문자열의 길이 정보에 따라서, 내가 -1을 사용해야 하는지 실제 등장 위치까지의 거리를 사용해야 하는지가 달라진다.  

 

위 KMP 풀이와 Aho-Corasick 알고리즘을 잘 이해하고 있다면, 풀이를 변형하는 것은 어렵지 않다. 코드는 https://blog.myungwoo.kr/101를 참고했다. 

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
#include <bits/stdc++.h>
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ldb;
const ll mod = 1e9 + 7;
 
string s; ll N, K;
string pat[31111];
struct Trie
{
    map<ll, Trie*> S;
    Trie* fail;
    Trie* output;
    ll cur_len;
    ll count; bool is_end;
    Trie() { S.clear(); fail=nullptr; output=nullptr; count=0; cur_len=0; is_end=false; }
    ~Trie() { S.clear(); }
};
Trie* end_node[31111];
queue<Trie*> Q;
vector<Trie*> ord;
 
ll rec_p[26], rec_s[26];
ll pog[31111], pogs[2222222];
map<ll, Trie*>::iterator it;
 
void solve(void)
{
    ord.clear(); cin >> N >> K; ll i, j, ans = 0; cin >> s;
    memset(pog, 0, sizeof(pog));
    memset(pogs, 0, sizeof(pogs));
    for(i=1 ; i<=K ; i++) cin >> pat[i];
    Trie *root = new Trie;
    // Step 1 : Build the Trie
    for(i=1 ; i<=K ; i++)
    {
        Trie *now = root;
        for(j=0 ; j<26 ; j++) rec_p[j] = -1;
        for(j=0 ; j<pat[i].length() ; j++)
        {   
            int cur = pat[i][j] - 'a';
            if(rec_p[cur] == -1) pog[j] = -1;
            else pog[j] = j - rec_p[cur];
            rec_p[cur] = j;
        }
        for(j=0 ; j<pat[i].length() ; j++)
        {
            if(now->S.find(pog[j]) == now->S.end()) {
                now->S[pog[j]] = new Trie;
            }
            now->S[pog[j]]->cur_len = now->cur_len + 1;
            now = now->S[pog[j]];
        }
        now->is_end = true;
        end_node[i] = now;
    }
    // Queue Setup
    for(it = root->S.begin() ; it != root->S.end() ; it++) {
        it->second->fail = root;
        Q.push(it->second);
    }
    // Fail Setup
    while(!Q.empty())
    {
        Trie *cur = Q.front(); Q.pop();
        if(cur->is_end) cur->output = cur;
        else cur->output = cur->fail->output;
        for(it = cur->S.begin() ; it != cur->S.end() ; it++) {
            ll cur_step = it->first;
            Trie *nxt = it->second;
            nxt->fail = cur->fail;
            while(1)
            {
                if(nxt->fail == root) break;
                ll len = nxt->fail->cur_len;
                ll true_step = cur_step;
                if(true_step > len) true_step = -1;
                if(nxt->fail->S.find(true_step) != nxt->fail->S.end()) break;
                nxt->fail = nxt->fail->fail;
            }
            ll true_step = cur_step;
            ll len = nxt->fail->cur_len;
            if(true_step > len) true_step = -1;
            if(nxt->fail->S.find(true_step) != nxt->fail->S.end()) 
                nxt->fail = nxt->fail->S[true_step];
            Q.push(nxt);
        }
    }
    // start finding
    Trie *now = root;
    for(i=0 ; i<26 ; i++) rec_s[i] = -1;
    for(i=0 ; i<s.length() ; i++)
    {
        int cur = s[i] - 'a';
        if(rec_s[cur] == -1) pogs[i] = -1;
        else pogs[i] = i - rec_s[cur];
        rec_s[cur] = i;
    }
    for(i=0 ; i<s.length() ; i++)
    {
        ll cur_step = pogs[i];
        while(1)
        {
            if(now == root) break;
            ll true_step = cur_step;
            if(true_step > now->cur_len) true_step = -1;
            if(now->S.find(true_step) != now->S.end()) break;
            now = now->fail;
        }
        ll true_step = cur_step;
        if(true_step > now->cur_len) true_step = -1;
        if(now->S.find(true_step) != now->S.end()) now=now->S[true_step];
        if(now->output) now->output->count++;
    }
    // finish
    Q.push(root);
    while(!Q.empty())
    {
        Trie *cur=Q.front(); Q.pop();
        ord.push_back(cur);
        for(it = cur->S.begin() ; it != cur->S.end() ; it++) Q.push(it->second);
    }
    reverse(ord.begin(), ord.end());
    for(i=0 ; i<ord.size() ; i++)
        if(ord[i]->is_end && ord[i]->fail->output)
            ord[i]->fail->output->count+=ord[i]->count;
    for(i=1 ; i<=K ; i++) ans += i * end_node[i]->count;
    delete root;
    cout << ans << endl;
}
 
int main(void)
{
    fio; ll i, tc; cin >> tc;
    for(i=1 ; i<=tc ; i++) 
    {
        cout << "Case #" << i << endl;
        solve(); // endl in solve
    }
    return 0;
}
 cs

 

저작자표시 비영리

'PS > 대회 후기' 카테고리의 다른 글

SCPC 2021 1차 예선 풀이  (0) 2021.07.16
ACM-ICPC Seoul Regional 2020  (0) 2020.11.20
SCPC 2020 본선 후기  (5) 2020.11.09
ACM-ICPC Seoul Regional Preliminary 2020  (0) 2020.10.19
SCPC 2020 2차 예선 풀이  (1) 2020.09.05

Guest Writeup : https://blog.cryptohack.org/cryptoctf2021-hard

저작자표시 비영리

'CTF' 카테고리의 다른 글

DUCTF 2021 Writeups  (0) 2021.09.26
ACSC Crypto Writeups  (0) 2021.09.26
GoogleCTF Quals 2021 Crypto Writeups  (1) 2021.07.19
zer0lfsr 2021 Full Writeup (0CTF/TCTF 2021)  (2) 2021.07.05
zer0lfsr 2021 Quick Solutions/Thoughts  (0) 2021.07.05

https://www.youtube.com/watch?v=Z-lCE23e12I&list=OLAK5uy_lzJXyds7tiw-cUS9Zg9wXRSiWpNJM6i7s 

 

 

저작자표시 비영리

'취미' 카테고리의 다른 글

공부를 2주동안 하지 않은 이야기  (0) 2020.07.18
Squarepusher - Beep Street  (0) 2019.11.27
2019/11/16 ~ 2019/11/17 CHUNITHM 성과 정리  (0) 2019.11.17
2019/06/17~ 2019/06/21 CHUNITHM 성과 정리  (0) 2019.06.23

https://www.youtube.com/watch?v=8gRkCVy8he8  

https://github.com/rkm0959/rkm0959_presents/blob/main/lattice_survey.pdf  

 

저작자표시 비영리

'Cryptography' 카테고리의 다른 글

KZG, ASVC, Stateless Cryptocurrencies  (0) 2022.05.20
Groth16 + Powers of Tau + Tornado Cash  (0) 2022.03.14
Inequality Solving with CVP  (0) 2021.03.26
Sigma Protocol  (0) 2021.02.15
Schnorr's Protocol & Signature  (0) 2021.02.13

I played GoogleCTF Quals as a member of Super Guesser. We reached 9th place, which is good enough for a place in the Finals!

I solved all five cryptography problems, one (pythia) with barkingdog. While this was good work, I'm still sad that I couldn't solve the misc "cryptography" problem due to lack of time and creativity (and probably work ethic as well). Here's how we solved the cryptos.

 

NOTE : All challenges from GoogleCTF are open sourced, so check them here. https://github.com/google/google-ctf/tree/master/2021

exploit codes for all five challenges can be found on https://github.com/rkm0959/Cryptography_Writeups/tree/main/2021

 

tiramisu (28 solves)

Step 1 : Basic Analysis

We start by reading some golang codes. We see that the code roughly does the following 

  • We receive the server's ECDSA public key and the encrypted flag message.
  • The flag is encrypted with AES, using the key derived by HMAC with the ECDSA secret key.
  • We can send our ECDSA public key, which would normally allow us to compute the shared secret.
  • Using this shared secret, we send an authenticated encrypted message to the server.
  • The server checks if we sent a valid encryption, and replys with another valid encryption with different IV.

Step 2 : Reducing the Problem and Finding Attack Vector

First, note that HMAC with a strong hash like sha256 is very hard if not impossible to break. 

Therefore, we should probably look deeper into the inner workings of the ECDSA implementation.

Especially, since the flag is encrypted with a HMAC-derived key, we must recover ECDSA secret key at some point.

This immediately implies that the following message is a very scorching hot take.

 

hot take machine

 

After realizing that people are actually solving this problem, we look more into the ECDSA. 

We see that there are actually two curves supported in this implementation, as shown in this code.

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
func (server *Server) EstablishChannel(clientHello *pb.ClientHello) error {
    // Load peer key.
    peer, err := proto2ecdsaKey(clientHello.Key)
    if err != nil {
        return err
    }
 
    // Key sanity checks.
    if !peer.Curve.IsOnCurve(peer.X, peer.Y) {
        return fmt.Errorf("point (%X, %X) not on curve", peer.X, peer.Y)
    }
 
    // Compute shared secret.
    P := server.key.Params().P
    D := server.key.D.Bytes()
    sharedX, _ := server.key.ScalarMult(new(big.Int).Mod(peer.X, P), new(big.Int).Mod(peer.Y, P), D)
 
    masterSecret := make([]byte, server.key.Params().BitSize/8)
    sharedX.FillBytes(masterSecret)
 
    // Derive AES+MAC session keys.
    server.channel, err = newAuthCipher(masterSecret, channelCipherKdfInfo, channelMacKdfInfo)
    if err != nil {
        return fmt.Errorf("newAuthCipher()=%v, want nil error", err)
    }
    return nil
}
 cs

 

Now we see the vulnerability! The server checks our point lies on our curve, but then takes the coordinates modulo $P$, which is the modulo from the server's curve. Since there are no restrictions on the coordinate size, by Chinese Remainder Theorem, we have a complete control over the final coordinates taken modulo $P$. The server takes this faulty point and multiply it by $D$, the ECDSA secret key.

 

Step 3 : The Invalid Curve Attack

Turns out that the problem now reduces to a known attack called the invalid curve attack. 

Basically, when we work on the Weierstrass curve $y^2 = x^3 + ax + b$, the standard implementations for adding and doubling points never uses the value of $b$. It only uses the value of $a$ and the one or two points of the input. 

Therefore, if the server considers a point $(X, Y)$ and considers it as a point on $y^2 = x^3 + ax + b$ while multiplying a scalar to it, it actually performs valid scalar multiplication, although the computation is on the point $y^2 = x^3 + ax + b'$, where $$b' \equiv Y^2 - X^3 - aX \pmod{p}$$

 

Since we have full control on $(X, Y)$, the result after the coordinates are taken modulo $P$, we can actually select any curves of the form $y^2 = x^3 - 3x + b$. To exploit this even further, we can use the small subgroup attack. Consider we take find a curve $y^2 = x^3 - 3x + b$ which has an order which is a multiple of a small prime $m$. We can then take a point $(X, Y)$ on this curve with order $m$. If we send this point, the shared secret will be the first coordinate of a scalar multiple of $(X, Y)$, which there are only at most $m$ candidates. 

 

Since we can easily determine if our guess for a shared secret is valid by checking whether we receive a reply or not, we can test all $m$ candidates. However, the shared secret is just the first coordinate of the elliptic curve point. This means we will actually get two possible candidates for $D \pmod{m}$, so something like $D \equiv \pm l \pmod{m}$, since the additive inverse of a point has the same first coordinate. 

 

If we gather a lot of such information, we will be able to find a sufficiently small candidates for $D$ by Chinese Remainder Theorem.

To do so, we choose the "signs" in each modulo relation, compute $D$ by Chinese Remainder Theorem, and repeat.

 

Step 4. Implementation and Finish

  • Choosing the Modulo $m$ - Prime : I chose the modulo $m$ to be prime, since they give a lot of information in a sense that $m$ will have GCD 1 with all the previous modulos I used. If you get $\pmod{m_1}$ and $\pmod{m_2}$ information, then you will get $\pmod{\text{lcm}(m_1, m_2)}$ information in total by Chinese Remainder Theorem. Therefore, having $\gcd(m_1, m_2) = 1$ usually helps.
  • Choosing the Modulo $m$ - Size : This is quite important. If we take larger $m$, the number of modulo relations we need to take becomes smaller. This implies that we have an easier offline bruteforce of choosing signs, computing Chinese Remainder parts, and either ECDSA public key verification or AES decryption. However, choosing larger $m$ also implies that we have to search more elliptic curves to find a appropriate one, and we also need to interact with the server more to decide what $D \pmod{m}$ can be. If we take small $m$, everything becomes the opposite. I chose $m$ to be a prime between $300$ and $1000$. In my case, 25 relations were sufficient to find $2^{25}$ candidates for $D$, which is definitely a feasible number of candidates for final offline bruteforce.
  • Multiprocessing : I used it to speedup both the server computation and the offline bruteforce. 
  • Trick from rbtree : Instead of bruteforcing the signs, one can just solve for $D^2$ by CRT and take sqrt. In this case, you would need twice more information on $D \pmod{m}$, but you don't need the extra bruteforce. Great idea from rbtree, shared after contest!

 

pythia (65 solves)

This was a tricky problem for me, as I found the solution nearly immediately but struggled to write the exploit. 

 

Step 1 : Basic Analysis

  • There are a total of $26^3$ possible passwords, each corresponding to a 16 bytes AES-GCM key.
  • There is a password (key) we have to find. We must do it using around 48 queries of the following type.
  • We can send some nonce/ciphertext/tag to be AES-GCM decrypted with the key without any associated data.
  • The only response we get from the queries are whether or not the decryption process was successful.

Note that there are actually 150 queries and 3 passwords, but since each three problems are independent, we can just focus on one.

 

Step 2 : Reducing the Problem and Finding Attack Vector

In these types of problems, it's best to halve the number of candidates by each query.

To do so, we have to figure out how to build some nonce/ciphertext/tag that accepts all of the keys from a given set.

If we can do this, we can simply perform a "binary search" to get each password. This is a good time to look at how AES-GCM works. 

 

Step 3 : AES-GCM and Polynomial Fun

Here, we only consider the case where there are no associated data and we have 12 byte nonce. Everything is in $GF(2^{128})$.

Let $K$ be the key, $C = C_0 || C_1 || \cdots || C_{n-1}$ the ciphertext, and $IV$ the nonce. We now calculate $$H = AES_K(0^{128}), \quad J_0 = IV || 0^{31} || 1, \quad L = 0^{64} || len(C)$$

The tag $T$ is now calculated as $T = C_0 H^{n+1} + C_1 H^n + \cdots + L \cdot H + AES_K(J_0)$. 

 

Let's fix $IV= 0^{96}$. If we know $K$ and $n$, then we can calculate $H, J_0, L, AES_K(J_0)$. 

Now we want the polynomial coefficients $C_0, C_1, \cdots, C_{n-1}, T$ such that $$C_0 H^{n+1} + C_1 H^n + \cdots + L \cdot H + T = AES_K(J_0)$$ for a given set of $K$. To be exact, if we have $K_1, K_2, \cdots , K_m$ as a target set of keys, we compute the corresponding $H_1, H_2, \cdots , H_m$.

Then, we will try to find $n, C_0, C_1, \cdots , C_{n-1}, T$ such that $$C_0 H_t^{n+1} + C_1 H_t^n + \cdots + C_{n-1} H_t^2 + L H_t + T = AES_{K_t}(J_0)$$ for each $1 \le t \le m$. This is starting to look like Lagrange interpolation, with the caveat that $L$ is determined by $n$.

 

Take $n=m$. Let $f(x) = C_0 x^{m+1} + \cdots + C_{m-1} x^2 + L x + T$, which is a polynomial we want to find.

Our desired $f$ must satisfy $f(H_t) = AES_{K_t}(J_0)$ for each $1 \le t \le m$.

This $f$ can be found directly with Lagrange interpolation, and $f$ will have degree at most $m-1$. However, we have to set $f$'s coefficient of $x$ to be equal to $L$. This can be done by adding some scalar multiple of $g = (x-H_1)(x-H_2) \cdots (x-H_m)$.

 

However, if this $g$ has the coefficient of $x$ equal to $0$, we cannot control this coefficient by adding $g$.

In this case, we have to control it by multiplying some random degree 1 polynomial.

Finally, note that we can put any number of zero blocks at the front of the ciphertext to meet the length requirement if $\deg f < m+1$. 

 

There are a lot of methods to handle these sepcial cases, (i.e. $g$ can't control the coefficient) and the solution writeen by barkingdog is a bit different from what I wrote as well. He handled these cases by simply adding a few random points for the interpolation part of $f$.

This makes $g$ and it's coefficients much more random, making it unlikely for the coefficient to be zero.

I would like to note that is error is a very unlikely case, so not error-handling these special cases won't hurt. 

 

Step 4 : Implementation Details

  • Fast Interpolation : If we try to find $C_i, T$ with a system of linear equations, the algorithm will take $\mathcal{O}(n^3)$ time which is quite slow. A relatively naive lagrange interpolation takes $\mathcal{O}(n^2)$ time. I suggest just using SageMath's lagrange polynomial function.
  • Binary Search : If we just use standard binary search, we would have to compute $f$ for a set of $26^3/2$ keys. This is quite large for us to handle, and it may not even fit the payload size. Since we have much more than $\log(26^3) < 15$ queries per password, we can try to make our interpolation computation easier at the cost of using more queries. Here is one way to do so - we divide the set of $26^3$ keys into $40$ batches of size around $440$. We find which batch the key is in, and then use standard binary search. This fits in the query limit quite tightly. Note that if we found the batch that has the key, we do not need to check the other batches. 
  • Cache : Note that the payload to test whether the key is in a certain set can be precomputed beforehand. Therefore, by using a cache or hashmap or whatever, we can save ourselves from repeating the same computation over and over again. This is especially useful when we are testing the $40$ batches - we will test the same batches for all three passwords, and computing the payload for all of them takes quite a while. By saving these payloads, we can save quite a lot of time on the exploit. 
  • AES-GCM : endian stuff are very confusing to figure out, so you have to really concentrate

 

h1 (23 solves)

Step 1 : Basic Analysis

  • We have some ECDSA looking stuff (it's actually just elliptic curve operations with Jacobians)
  • We have some signatures, but we do not know any public key.
  • Alice has sent two messages and signatures, but one of the messages contain the unknown flag.
  • Bob has sent two messages and signatures, and we know both messages and their hashes.
  • We also know the AES encrypted messages (one contains flag) with the shared secret as the key.
  • The ECDSA nonce is yelling loudly at us to attack it which we obviously have to do.

Step 2 : Reducing the Problem and Finding Attack Vector

Obviously there is something going on with the custom RNG, and it becomes apparent if we read the code. 

 

1
2
3
4
5
6
7
8
9
10
11
12
13
def RNG(nbits, a, b):
    nbytes = nbits // 8
    B = os.urandom(nbytes)
    return a * sum([B[i] * b ** i for i in range(len(B))]) % 2**nbits
 
def Sign(msg, d):
    h = hashlib.sha512(msg)
    z = Transform(int.from_bytes(h.digest(), 'big'), h.digest_size*8)
    k = RNG(n.bit_length(), 16843009, 4294967296)
    x1, y1, z1 = Multiply(G, k)
    r = (x1 * pow(z1, -2, mod) % mod) % n
    s = pow(k, -1, n) * (z + r * d) % n
    return r, s
 cs

 

We see that $n$ is $512$ bits, and our RNG call uses $b = 2^{32}$. Therefore, in the RNG call, the nonce can be written as $$ \sum_{i=0}^{15} a \cdot byte_i \cdot 2^{32i}$$ since all values from $i \ge 16$ becomes $0$ modulo $2^{512}$. Note that $255a < 2^{32}$, so no modulo operations are needed.

 

Since each $byte_i$ has 8 bit of "entropy", in total the RNG has only 128 bits of "entropy", which is horrible.

This also means that each complete message/signature pair gives us around 384 bits of information on the secret key.

Since we have two such pairs for Bob's secret key $db$, we should be able to extract this value.

 

Clearly, computing the shared secret solves the problem, so we just need the public key of Alice. 

This is not hard, as given one complete message/signature you can recover the public key. This is even in wikipedia.

NOTE : There may be more than one public key possible, so try all of them to find the flag.

 

Therefore, clearly getting the secret key $db$ is the hardest part of the challenge, unless you are rkm0959 who doesn't know fundamentals.

 

rkm0959 wonders how to get da (private) while he only needs Qa (public)

 

Step 3 : Yet Another Inequality Solving with CVP!

Consider the message, signature pair $(r_1, s_1, z_1)$ and $(r_2, s_2, z_2)$, where $z$'s are the hashes. We know $$ \left( \sum_{i=0}^{15} a \cdot byte_{1, i} \cdot 2^{32i} \right) \cdot s_1 \equiv z_1 + r_1 d \pmod{n}$$ $$ \left( \sum_{i=0}^{15} a \cdot byte_{2, i} \cdot 2^{32i} \right) \cdot s_2 \equiv z_2 + r_2 d \pmod{n}$$ Since we can, we will remove $d$ from this system by writing $$ \left( \sum_{i=0}^{15} a \cdot r_2 \cdot byte_{1, i} \cdot 2^{32i} \right) \cdot s_1 - \left( \sum_{i=0}^{15} a \cdot r_1 \cdot byte_{2, i} \cdot 2^{32i} \right) \cdot s_2 \equiv z_1r_2 - z_2r_1 \pmod{n}$$ Now we can consider $33$ variables $byte_{1, i}, byte_{2, i}, t$ for $0 \le i \le 15$, and use the $33$ inequalities $$\left( \sum_{i=0}^{15} a \cdot r_2 \cdot byte_{1, i} \cdot 2^{32i} \right) \cdot s_1 - \left( \sum_{i=0}^{15} a \cdot r_1 \cdot byte_{2, i} \cdot 2^{32i} \right) \cdot s_2 + tn =  z_1r_2 - z_2r_1 $$ $$ 0 \le byte_{1, i}, byte_{2, i} \le 255$$ and plug this into Inequality Solving with CVP repository. This gives us $db$ and it solves the problem. 

 

tonality (30 solves)

Step 1 : Basic Analysis

  • We get the ECDSA public key $P = dG$ and two messages.
  • We can send a integer $t$, and we get the signature of first message signed with private key $td$.
  • We now have to forge any signature of the second message with private key $d$. 

 

Step 2 : Finding Attack Vector, and "Wishful Thinking"

There's nothing really going on in this problem, so we just need to use the first query very well.

Denote the two messages $m_0, m_1$ and their hashes $z_0, z_1$. Denote the integer we will send as $t$. 

 

We will receive the signature $r_0, s_0$ such that the point $$ (z_0 / s_0) G + (r_0 / s_0) tP $$ has the first coordinate equal to $r_0$. Here, the integer division is done modulo $n$, the order of elliptic curve.

 

We now have to forge a signature $r_1, s_1$ such that the point $$ (z_1 / s_1) G + (r_1 / s_1)P$$ has the first coordinate equal to $r_1$. Here, the integer division is done modulo $n$, the order of elliptic curve. 

 

We wish to solve this in the easiest way possible - and this will happen when $$ z_0/s_0 = z_1/s_1 , \quad (r_0 / s_0)t = (r_1/s_1), \quad r_0 = r_1$$ which can be rearranged as $$t = z_0 / z_1, \quad r_1 = r_0, \quad s_1 = z_1s_0/z_0$$ and submitting this to the server solves the problem.

 

story (32 solves)

Step 1 : Basic Analysis

  • We have to send a sufficiently large UTF-8 string to the server.
  • We receive the CRC16, CRC32, CRC64 values of the sent string back.
  • We also receive the desired CRC16, CRC32, CRC64 values from the server.
  • We have to make a string with the desired CRC values, with the same lowercase text as the original string.

Step 2 : Finding Attack Vector

The obvious problem is that CRCs are not meant to be an encryption of some sort. They satisfy the powerful relation $$crc(x) \oplus crc(y)  \oplus crc(z) = crc(x \oplus y \oplus z)$$ which can be used to solve this problem relatively easily. 

 

There are several ways to solve this problem, maybe even using finite field representation of CRC. However, I still think the method in Step 3 is much easier to deal with than dealing endian issues and figuring out which polynomial is actually used to compute CRC.

 

Step 3 : Exploiting with Linearity

Denote $x_{16}, x_{32}, x_{64}$ be the CRC values of "a" * 256.

Also, for each $0 \le i \le 255$, we denote $x'_{i, 16}, x'_{i, 32}, x'_{i, 64}$ as the CRC values of "a" * 256 but the $i$th 'a' is changed to 'A'. 

These values can be computed by 257 server interactions, and the CRC computation is of course deterministic. 

 

Now we can build the CRC values of any length 256 string with 'a' and 'A' only. We start with $x_{16}, x_{32}, x_{64}$, and if the $i$th character is 'A' instead of 'a', we XOR the values $x'_{i, 16} \oplus x_{16}, x'_{i, 32} \oplus x_{32}, x'_{i, 64} \oplus x_{64}$ to our CRC result. 

 

Now changing 'a' to 'A' appropriately for the result CRC to match the target is something like a subset sum problem with bitstring XOR.

Of course, looking at each bit separately, this is nothing more than a system of linear equations over $\mathbb{F}_2$.

 

We solve this, find the locations where we have to change the lowercase/uppercase, and get the flag.

저작자표시 비영리

'CTF' 카테고리의 다른 글

ACSC Crypto Writeups  (0) 2021.09.26
CryptoCTF Writeups (DoRSA, Polish)  (0) 2021.08.05
zer0lfsr 2021 Full Writeup (0CTF/TCTF 2021)  (2) 2021.07.05
zer0lfsr 2021 Quick Solutions/Thoughts  (0) 2021.07.05
LINE CTF Crypto Writeups  (0) 2021.03.22

대충 1시간 30분 정도 쓴 것 같다.

 

1번. 친구들

친구 관계가 일부 주어졌고, 친구의 친구 역시 친구로 간주할 때 "친구 관계인 maximal 그룹"의 개수를 구하는 문제다.

이는 사람을 정점으로, 친구 관계를 간선으로 볼 때 연결 컴포넌트의 개수를 구하는 문제와 같다. disjoint set 자료구조로 쉽게 해결할 수 있다.

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <bits/stdc++.h>
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ldb;
const ll mod = 1e9 + 7;
 
int n;
int d[111111];
int par[111111];
 
int find(int x)
{
    if(par[x] == x) return x;
    return par[x] = find(par[x]);
}
 
void unite(int u, int v)
{
    u = find(u);
    v = find(v);
    if(u == v) return;
    par[u] = v;
}
 
void solve(void)
{
    int i, ans = 0; cin >> n;
    for(i=1 ; i<=n ; i++) cin >> d[i];
    for(i=1 ; i<=n ; i++) par[i] = i;
    for(i=1 ; i<=n ; i++)
        if(i+d[i]<=n) unite(i, i+d[i]);
    for(i=1 ; i<=n ; i++) if(i == find(i)) ans++;
    cout << ans;
}
 
int main(void)
{
    fio; int tc; cin >> tc;
    for(int i=1 ; i<=tc ; i++) 
    {
        cout << "Case #" << i << endl;
        solve(); cout << endl;
    }
    return 0;
}
 cs

 

2번. 이진수

$b_i = a_{i-t} | a_{i+t}$로 정의된 bit string $b$가 주어졌을 때, 사전순으로 가장 앞선 $a$를 구하는 문제다.

단, index가 가능한 범위 밖인 경우 값은 $0$이라고 생각하도록 한다. 또한, 조건을 만족하는 $a$가 존재함은 보장된다. 

 

먼저 $b_i = 0$이면 $a_{i-t} = a_{i+t} = 0$임이 강제되며, 이렇게 둘 경우 $b_i = 0$ 역시 만족함을 알 수 있다. 

이에 해당되는 $a$의 bit에 0을 넣는 것을 확정하고 나면, 이제 $b_i = 1$ 형태의 조건들만 남았다. 

이들은 결국 $a$의 두 bit 중 적어도 하나가 1이라는 의미고, 이는 직관적으로 봤을 때 1을 더 넣으면 넣을수록 만족하기 쉬운 조건이다.

그러니, 앞서 0으로 확정된 bit가 아닌 임의의 bit에 대해서는 그냥 1로 두면 조건을 만족하는 $a$가 될 것이다.

 

이제 문제는 사전순으로 가장 앞선 $a$를 구하는 건데, 이런 문제가 그렇듯 앞부터 보면서 0을 넣을 수 있는지 판별하면 된다.

$a_i = 0$이 가능한지 고려해보자. 먼저 $a_i = 0$이 앞서 확정되었다면 굳이 고려를 할 필요도 없다.

만약 $i-t$가 범위에 있고 $b_{i-t} = 1$이라면, $a_{i-2t}$ 또는 $a_i$가 $1$이 되어야 한다. $a_{i-2t}=0$이라면, 여기서 $a_i = 1$이 강제된다. 

만약 $i+t$가 범위에 있고 $b_{i+t}=1$이라면, $a_i$ 또는 $a_{i+2t}$가 $1$이 되어야 한다. $a_{i+2t}$가 이미 $0$으로 확정되었다면, 여기서 $a_i = 1$이 강제된다.

이를 제외한 경우에서는, $a_i = 0$을 해도 문제가 되지 않는다. $a_i$가 영향을 주는 $b$의 값은 $b_{i-t}$, $b_{i+t}$이며, 이들의 값을 $a_i = 0$으로 두면서도 정확하게 맞춰줄 수 있기 때문이다. 특히, 마음에 걸릴 수 있는 유일한 부분이 $a_i = 0$으로 두면서 후에 $a_{i+2t}$를 $1$로 둔 것인데, 애초에

  • $a_i = 1$로 두면 무조건 $a_i = 0$으로 두는 것보다 사전순으로 뒤고, 그러니 $a_i = 0$인게 이득이고
  • $a_{i+2t}$는 확정되지 않은 bit이므로 $a_{i+2t} = 1$으로 두었다고 해서 조건을 만족하는 게 "어려워지지 않는다"

애초에 이 경우에는 $a_i = 0$으로 두고 확정된 bit를 제외한 뒤의 모든 bit를 1로 두면 조건을 만족하게 되어있다.

어쨌든 이런 식으로 bit를 계산하면 $\mathcal{O}(n)$에 모든 계산을 할 수 있다. 2번 문제인 것 치고는 약간 까다로웠다. 

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <bits/stdc++.h>
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ldb;
const ll mod = 1e9 + 7;
 
// b[i] = a[i-t] | a[i+t]
 
int n, t, a[55555], b[55555];
string s;
 
void solve(void)
{
    int i; cin >> n >> t >> s;
    for(i=1 ; i<=n ; i++) b[i] = s[i-1] - '0';
    for(i=1 ; i<=n ; i++) a[i] = -1;
    for(i=1 ; i<=n ; i++)
    {
        if(b[i] == 0)
        {
            if(i+t<=n) a[i+t] = 0;
            if(i-t>=1) a[i-t] = 0;
        }
    }
    for(i=1 ; i<=n ; i++)
    {
        if(a[i] != -1) continue;
        if(i-t>=1 && (i<=2*t || a[i-2*t] == 0)) a[i] = 1;
        else if(i+t<=n && (i+2*t>n || a[i+2*t]==0)) a[i] = 1;
        else a[i] = 0;
    }
    for(i=1 ; i<=n ; i++) cout << a[i];
}
 
int main(void)
{
    fio; int tc; cin >> tc;
    for(int i=1 ; i<=tc ; i++) 
    {
        cout << "Case #" << i << endl;
        solve(); cout << endl;
    }
    return 0;
}
 cs

 

3번. No Cycle

사이클이 생기지 않도록 간선의 방향을 결정하는데, 사전순 조건이 있다. 즉, 앞쪽에서 입력받은 간선들은 최대한 입력받은 순서를 유지하도록 해야한다. 

이 문제 역시 사전순 문제에서 항상 등장하는 방법인, 앞부터 보면서 답을 맞춰나가는 방법을 사용한다. 결국 우리가 풀어야하는 문제는 

  • 방향 그래프 $G$와 지금 당장 방향을 정해야 하는 간선 $e$, 그리고 뒤에 추가할 무방향 간선의 배열 $E$가 주어져있다.
  • $e$를 입력받은 순서로 방향을 줄 때, $E$의 간선들의 방향을 잘 설정하여 $e, E$를 전부 추가한 뒤에도 그래프에 사이클이 없도록 할 수 있는가? 

이 문제를 해결할 수 있다면, 본 문제 역시 위 문제를 각 간선에 대하여 해결하는 것을 반복하여 해결할 수 있다.

즉, 입력으로 방향 그래프 $G$와 무방향 간선 $e_1, e_2, \cdots, e_k$가 들어온다면,

  • $G, e_1, [e_2, \cdots, e_k]$에 대해 문제를 해결. 그 후 결정된 방향에 맞게 $G_1 \gets G + \vec{e_1}$.
  • $G_1, e_2, [e_3, \cdots , e_k]$에 대해 문제를 해결. 그 후 결정된 방향에 맞게 $G_2 \gets G + \vec{e_2}$.
  • 반복하면서 최종적으로 $G_{k-1}, e_k, []$에 대하여 문제를 해결하는 것으로 마무리.

물론, 위 과정에서 각 간선은 그리디하게 가능하면 입력 순서대로 방향을 잡아야 한다. 

 

Claim : $G$가 DAG고, $E$가 추가할 무방향 간선들이라고 하자. $E$의 간선들의 방향을 잘 정하여 $E$를 추가한 뒤에도 $G$가 DAG이도록 할 수 있다.

Proof of Claim : $G$를 위상정렬하고, 위상정렬 순서로 방향을 주면 된다. 증명 끝.

 

결국 위에서 논의한 $G, e, E$에 대한 문제는 사실 $G + e$가 DAG인지, 즉 사이클이 없는지 판별하는 문제와 같다.

$G$ 역시 DAG이므로, $G + e$에 사이클이 있는지 판별하는 문제는 $G$에 특정 경로가 존재하는지 판별하는 문제와 같다.

즉, $e$가 $u$에서 $v$로 가는 간선이라면, $G + e$의 사이클 존재 유무는 $G$에서 $v$에서 $u$로 가는 경로의 존재 여부와 같다.

 

결론적으로, 간선 $u \rightarrow v$가 주어졌다면 현재 그래프에서 $v \rightarrow u$ 경로가 존재하는지 보고,

  • 존재한다면 순서를 뒤집어서 $v \rightarrow u$로 두고 이 간선을 그래프에 추가
  • 그렇지 않다면 순서를 그대로 두고 간선을 그래프에 추가

하는 것을 반복하면 된다. 대충 $\mathcal{O}(K(N+M+K))$ 정도에 돌 것이다. 아마 자료구조 빡세게 쓰면 subquadratic 될듯? 아니면 말고

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <bits/stdc++.h>
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ldb;
const ll mod = 1e9 + 7;
 
vector<int> edge[511];
pair<int, int> E[4333];
queue<int> Q;
int vis[555];
int n, m, k;
 
int work(int u, int v)
{
    int i; for(i=1 ; i<=n ; i++) vis[i] = 0;
    vis[v] = 1; Q.push(v); 
    while(!Q.empty())
    {
        int c = Q.front(); Q.pop();
        for(i=0 ; i<edge[c].size() ; i++)
        {
            if(vis[edge[c][i]] == 0)
            {
                vis[edge[c][i]] = 1;
                Q.push(edge[c][i]);
            }
        }
    }
    if(vis[u]) return 1;
    return 0;
}
 
void solve(void)
{
    int i, u, v;
    cin >> n >> m >> k;
    for(i=1 ; i<=n ; i++) edge[i].clear();
    for(i=1 ; i<=m ; i++)
    {
        cin >> u >> v;
        edge[u].push_back(v);
    }
    for(i=1 ; i<=k ; i++)
    {
        cin >> u >> v;
        E[i] = make_pair(u, v);
    }
    for(i=1 ; i<=k ; i++)
    {
        u = E[i].first;
        v = E[i].second;
        int res = work(u, v);
        cout << res;
        if(res == 0) edge[u].push_back(v);
        else edge[v].push_back(u);
    }
}
 
 
int main(void)
{
    fio; int tc; cin >> tc;
    for(int i=1 ; i<=tc ; i++) 
    {
        cout << "Case #" << i << endl;
        solve(); cout << endl;
    }
    return 0;
}
 cs

 

4번. 예약 시스템

$2 \times m$ 직사각형에 사람들을 배치한다. 사람들은 총 $n$개의 그룹으로 나뉘어 있으며, 각 그룹에는 5명 이상이 있다. 

각 사람들은 스트레스 지수 $w$를 갖는데, 자신의 이웃에 자신과 다른 그룹에 속하는 사람이 있다면 그런 사람의 수와 $w$의 곱만큼 스트레스가 오른다.

우리의 목표는 스트레스 지수의 총합을 최소화하는 것이다. 제한은 전체적으로 큰 편이다. 

 

동적계획법을 쓰기 어렵게 생긴 제한인만큼, 한방에 문제를 푸는 방법이 필요해보인다. 

 

그룹 $S$ 하나를 고정해보자. $S$의 사람들이 스트레스를 느낄 때는, $S$와 $S^C$가 한 변을 공유할 때다.

그러니까 $S$의 둘레의 (단, 직사각형의 둘레는 제외한다) 길이가 길면 길수록 $S$ 전체의 스트레스가 커진다.

이는 $S$의 사람들이 뭉쳐있어야 스트레스가 적을 것 같다는 직관과도 거의 같은 결과다. 

 

"$S$의 둘레"를 생각해보면, 전체 직사각형의 길이 2의 세로변을 잠깐 무시하고 생각해보면

  • $S$의 크기가 짝수인 경우, 직사각형 형태를 이루도록 하면 둘레가 4가 된다.
  • 특히, 이 경우 $S$에서 서로 다른 4명의 사람들이 정확히 $S^C$의 한 사람과 만나게 된다. 이 사람들은 스트레스 지수가 작을수록 좋다.
  • $S$의 크기가 홀수인 경우, 직사각형에 하나 튀어나온 형태를 만들면 둘레가 5가 된다.
  • 특히, 이 경우 $S$에서 서로 다른 4명의 사람들이 $S^C$의 사람과 만나게 된다. 4명 중 정확히 한 명은 $S^C$를 두 명 만나고, 나머지는 한 명 만난다.
  • 물론, 두 명 만나는 사람의 스트레스 지수가 가장 작아야하며, 나머지의 스트레스 지수 역시 작을수록 좋다.

그리고 조금 열심히 생각해보면 이게 진짜 최적임을 납득할 수 있다. 또한, 홀수 크기의 그룹이 짝수개 존재하므로, 홀수 크기의 그룹끼리 서로 맞닿아 직사각형을 이루도록 하면 배치 역시 어렵지 않다. 이제 문제는 길이 2의 세로변을 처리하는 것이다. 길이 2의 세로변에 걸쳐서 $S$를 배치한다면, $S$에서 스트레스를 받는 4명 중 2명은 (이들은 4명 중에서 스트레스가 많은 두 명일 것이다) 전체 직사각형의 세로변의 도움을 받아 스트레스를 받지 않아도 된다. 

 

단순하게 생각하면, 여기서도 "가장 이득을 보는 그룹"을 양쪽 끝에 배치하여 세로변의 도움을 받을 수 있도록 하면 된다.

그런데 이게 이렇게 단순하지는 않은 게, 배치를 양쪽 끝에 하면 앞서 언급한 최적의 배치를 만드는 것이 어려울 수 있기 때문이다.

홀수 크기의 그룹이 정확히 2개 있고, 짝수 크기의 그룹이 여러 개 있다고 하자. 만약 홀수 크기의 그룹 2개가 양쪽 끝에 놓인다면, 짝수 크기 그룹을 직사각형 형태로 사용할 수 없고, 직사각형에서 양쪽에 한 개씩 튀어나온 형태로 사용해야 한다. 이때 짝수 크기 그룹에서 희생을 더 해야한다. 나머지 경우에서는 어떤 크기의 그룹을 양쪽에 배치해도, 우리가 생각하는 "최적의 배치"가 (직사각형 최대한 사용, 홀수 크기 2개 직사각형으로 만들기) 가능하다. 이제 열심히 케이스 분류.

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <bits/stdc++.h>
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ldb;
const ll mod = 1e9 + 7;
 
 
ll n, m;
vector<ll> even_save;
vector<ll> odd_save;
 
void solve(void)
{
    int i, j; 
    ll sz, val, ans=0, subt=0, odd=0, even=0, saved, ex = 0; 
    cin >> n >> m;
    vector<ll> cc;
    for(i=1 ; i<=n ; i++)
    {  
        cin >> sz; cc.clear(); cc.resize(sz);
        for(j=0 ; j<sz ; j++) cin >> cc[j];
        sort(cc.begin(), cc.end());
        if(!(sz & 1))
        {
            val = cc[0] + cc[1] + cc[2] + cc[3];
            saved = cc[2] + cc[3];
            ex += cc[0] + cc[1];
            ans += val; even++;
            even_save.push_back(saved);
        }
        else
        {
             val = 2 * cc[0] + cc[1] + cc[2] + cc[3];
            saved = cc[2] + cc[3]; 
            ans += val; odd++; 
            odd_save.push_back(saved);   
        }
    }
    sort(even_save.begin(), even_save.end());
    reverse(even_save.begin(), even_save.end());
    sort(odd_save.begin(), odd_save.end());
    reverse(odd_save.begin(), odd_save.end());
    if(even >= 2) subt = max(subt, even_save[0] + even_save[1]);
    if(even >= 1 && odd >= 1) subt = max(subt, even_save[0] + odd_save[0]);
    if(odd >= 2 && (odd >= 4 || n == 2)) subt = max(subt, odd_save[0] + odd_save[1]);
    if(odd == 2 && n >= 3)
        subt = max(subt, odd_save[0] + odd_save[1] - ex);
    even_save.clear(); odd_save.clear();
    cout << ans - subt;
}
 
int main(void)
{
    fio; int tc; cin >> tc;
    for(int i=1 ; i<=tc ; i++) 
    {
        cout << "Case #" << i << endl;
        solve(); cout << endl;
    }
    return 0;
}
 cs

 

5번. 차이

주어진 조건을 두 변수 사이의 간선이라고 보면, 연결 컴포넌트에 안에서는 모든 차이 계산이 가능하다. 

문제가 되는 것은 사이클, 특히 한바퀴 돌았는데 합이 0이 되지 않는 사이클이다. 이 경우, 사이클에 도달할 수 있는 모든 정점들은 모순된 상태가 된다.

 

그러니, disjoint set 자료구조를 가져왔을 때 대강

  • 두 정점이 같은 disjoint set에 속하지 않으면 Not Connected
  • 두 정점이 같은 disjoint set에 속하는데 여기에 모순된 cycle이 있으면 Conflict
  • 두 정점이 같은 disjoint set에 속하고 모순도 없으면 계산이 가능

함을 알 수 있다. 연결관계 자체만 봤을 때 disjoint set은 자명하고, 모순을 찾거나 계산을 하는 것이 문제다.

 

계산을 하기 위해서, 각 disjoint set의 대표 노드를 하나 두고 각 원소가 그 대표 노드의 값보다 얼마나 큰지 저장한다. 

원소들 사이의 차이는 알지만 원소 자체의 값은 모르니, 대표 노드의 값을 하나의 변수로 보고 차이만 저장하자는 의미다. 

 

이제 간선, 즉 하나의 등식이 추가되었다고 가정하자. 

  • 만약 두 정점이 같은 disjoint set에 있다면, 모순이 있는지 바로 확인할 수 있다. 저장된 값의 차이가 입력된 값과 다르면 모순이다.
  • 두 정점이 다른 disjoint set에 있다면, 이번에 추가된 등식은 두 disjoint set의 대표 노드 값 사이의 차이를 제공하는 정보가 된다. 이 경우, 두 disjoint set 중 하나의 대표를 전체의 새로운 대표로 정한다. 그 후, 흡수되는 집합의 각 원소들에 대해서 새로운 대표의 값과의 차이를 계산해야 한다. 이는 새로 얻어진 등식을 활용하여 할 수 있을 것이다. 물론, 두 disjoint set 중 이미 모순된 집합이 있다면 새로운 집합 역시 모순이 있다. 

두 disjoint set을 합치는 과정에서 걸리는 시간이 흡수되는 집합의 크기에 비례함을 알 수 있다. 그러므로, 작은 집합을 큰 집합에 흡수시키는 small-to-large 알고리즘을 사용하면 빠른 시간에 문제를 해결할 수 있다. 또한, 각 집합을 std::set 자료구조로 저장해야 집합의 순회가 쉽다. 

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include <bits/stdc++.h>
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ldb;
const ll mod = 1e9 + 7;
 
ll ans[111111];
int par[111111];
int sz[111111];
int doom[111111];
set<int> idx[111111];
set<int>::iterator it;
ll n, k;
 
int find(int x)
{
    if(par[x] == x) return x;
    return par[x] = find(par[x]);
}
 
void unite(int uu, int vv, int u, int v, ll val)
{
    if(sz[uu] < sz[vv])
    {
        swap(uu, vv);
        swap(u, v);
        val = -val;
    }
    sz[uu] += sz[vv];
    doom[uu] |= doom[vv];
    ll dif = -val - ans[v] + ans[u];
    for(it = idx[vv].begin() ; it != idx[vv].end() ; it++)
    {
        int loc = (*it);
        ans[loc] += dif;
        par[loc] = uu;
        idx[uu].insert(loc);
    }
    idx[vv].clear();
}
 
void solve(void)
{
    int i, whi, u, v, uu, vv; ll val;
    cin >> n >> k;
    for(i=1 ; i<=n ; i++) idx[i].clear();
    for(i=1 ; i<=n ; i++) ans[i] = 0, par[i] = i, sz[i] = 1, doom[i] = 0;
    for(i=1 ; i<=n ; i++) idx[i].insert(i);
    for(i=1 ; i<=k ; i++)
    {
        cin >> whi >> u >> v;
        if(whi == 1)
        {
            cin >> val;
            uu = find(u);
            vv = find(v);
            if(uu == vv && ans[u] - ans[v] != val) doom[uu] = 1;
            if(uu != vv) unite(uu, vv, u, v, val);
        }
        else if(whi == 2)
        {
            uu = find(u);
            vv = find(v);
            if(uu != vv) cout << "NC\n";
            if(uu == vv && doom[uu] == 1) cout << "CF\n";
            if(uu == vv && doom[uu] == 0) cout << ans[u] - ans[v] << "\n";
        }
    }
}
 
int main(void)
{
    fio; int tc; cin >> tc;
    for(int i=1 ; i<=tc ; i++) 
    {
        cout << "Case #" << i << endl;
        solve(); cout << endl;
    }
    return 0;
}
 cs
저작자표시 비영리

'PS > 대회 후기' 카테고리의 다른 글

SCPC 2021 2차 예선 풀이  (1) 2021.08.07
ACM-ICPC Seoul Regional 2020  (0) 2020.11.20
SCPC 2020 본선 후기  (5) 2020.11.09
ACM-ICPC Seoul Regional Preliminary 2020  (0) 2020.10.19
SCPC 2020 2차 예선 풀이  (1) 2020.09.05

티스토리툴바