I played Asian Cyber Security Challenge 2021 this weekend and finished in 55th/483 place. I solved some crypto challenges and here’s how I solve them.
RSA stream [121 solves]
1import gmpy2
2from Crypto.Util.number import long_to_bytes, bytes_to_long, getStrongPrime, inverse
3from Crypto.Util.Padding import pad
4
5from flag import m
6#m = b"ACSC{<REDACTED>}" # flag!
7
8f = open("chal.py","rb").read() # I'll encrypt myself!
9print("len:",len(f))
10p = getStrongPrime(1024)
11q = getStrongPrime(1024)
12
13n = p * q
14e = 0x10001
15print("n =",n)
16print("e =",e)
17print("# flag length:",len(m))
18m = pad(m, 255)
19m = bytes_to_long(m)
20
21assert m < n
22stream = pow(m,e,n)
23cipher = b""
24
25for a in range(0,len(f),256):
26 q = f[a:a+256]
27 if len(q) < 256:q = pad(q, 256)
28 q = bytes_to_long(q)
29 c = stream ^ q
30 cipher += long_to_bytes(c,256)
31 e = gmpy2.next_prime(e)
32 stream = pow(m,e,n)
33
34open("chal.enc","wb").write(cipher)
cipher is calculated by XORing stream and q.
Since q is known (chal.py), we can recover stream $( = m^e \mod n ).$
Each stream is encrypted by different e, so we can also recover m by applying Common Modulus Attack.
1from Crypto.Util.Padding import pad
2
3import gmpy2
4
5from toyotama import *
6
7length = 723
8n = 30004084769852356813752671105440339608383648259855991408799224369989221653141334011858388637782175392790629156827256797420595802457583565986882788667881921499468599322171673433298609987641468458633972069634856384101309327514278697390639738321868622386439249269795058985584353709739777081110979765232599757976759602245965314332404529910828253037394397471102918877473504943490285635862702543408002577628022054766664695619542702081689509713681170425764579507127909155563775027797744930354455708003402706090094588522963730499563711811899945647475596034599946875728770617584380135377604299815872040514361551864698426189453
9e = 65537
10# flag length: 97
11
12with open("chal.enc", "rb") as f:
13 enc = f.read()
14
15with open("chal.py", "rb") as f_:
16 f = f_.read()
17
18q1 = f[:256]
19q2 = f[256:512]
20c1 = enc[:256]
21c2 = enc[256:512]
22
23C1 = XOR(q1, c1)
24C2 = XOR(q2, c2)
25
26C1 = b2i(C1)
27C2 = b2i(C2)
28
29e1 = 0x10001
30e2 = int(gmpy2.next_prime(e1))
31
32m = common_modulus_attack(e1, e2, C1, C2, n)
33m = i2b(m)
34print(m)
ACSC{changing_e_is_too_bad_idea_1119332842ed9c60c9917165c57dbd7072b016d5b683b67aba6a648456db189c}
Swap on Curve [34 solves]
The challenge is very simple. We’re given an elliptic curve ${\rm E} / {\mathbb F}_p: y^2 = x^3 + ax + b$
1from params import p, a, b, flag, y
2
3x = int.from_bytes(flag, "big")
4
5assert 0 < x < p
6assert 0 < y < p
7assert x != y
8
9EC = EllipticCurve(GF(p), [a, b])
10
11assert EC(x, y)
12assert EC(y, x)
13
14print("p = {}".format(p))
15print("a = {}".format(a))
16print("b = {}".format(b))
From above constraints, we get
$$ \begin{cases} y^2 = x^3 + ax + b \ x^2 = y^3 + ay + b \ \end{cases} \begin{aligned} &\Longrightarrow x^2 = y(y^2 + a) + b \ &\Longrightarrow (x^3 + ax + b)(x^3 + ax + a + b)^2 = (x^2 - b)^2 \end{aligned} $$
We can get $x$ just by solving this equation. Be careful that this equation is over ${\mathbb F}_p$.
1p = 10224339405907703092027271021531545025590069329651203467716750905186360905870976608482239954157859974243721027388367833391620238905205324488863654155905507
2a = 4497571717921592398955060922592201381291364158316041225609739861880668012419104521771916052114951221663782888917019515720822797673629101617287519628798278
3b = 1147822627440179166862874039888124662334972701778333205963385274435770863246836847305423006003688412952676893584685957117091707234660746455918810395379096
4
5PR.<x> = PolynomialRing(GF(p))
6f = (x^2-b)^2 - (x^3+a*x+b)*(x^3+a*x+a+b)^2
7
8for X in f.roots(multiplicities=False):
9 print(bytes.fromhex(f'{int(X):x}'))
ACSC{have_you_already_read_the_swap<-->swap?}
すわっぷ⇔すわっぷ
Two Rabin [20 solves]
chal.py
1import random
2from Crypto.Util.number import *
3from Crypto.Util.Padding import pad
4
5from flag import flag
6
7p = getStrongPrime(512)
8q = getStrongPrime(512)
9n = p * q
10B = getStrongPrime(512)
11
12m = flag[0 : len(flag) // 2]
13print("flag1_len =", len(m))
14
15m1 = bytes_to_long(m)
16m2 = bytes_to_long(pad(m, 128))
17
18assert m1 < n
19assert m2 < n
20
21c1 = (m1 * (m1 + B)) % n
22c2 = (m2 * (m2 + B)) % n
23
24print("n =", n)
25print("B =", B)
26print("c1 =", c1)
27print("c2 =", c2)
28
29# Harder!
30
31m = flag[len(flag) // 2 :]
32print("flag2_len =", len(m))
33
34m1 = bytes_to_long(m)
35m1 <<= (128 - len(m)) * 8
36m1 += random.SystemRandom().getrandbits((128 - len(m)) * 8)
37
38m2 = bytes_to_long(m)
39m2 <<= (128 - len(m)) * 8
40m2 += random.SystemRandom().getrandbits((128 - len(m)) * 8)
41
42assert m1 < n
43assert m2 < n
44
45c1 = (m1 * (m1 + B)) % n
46c2 = (m2 * (m2 + B)) % n
47
48print("hard_c1 =", c1)
49print("hard_c2 =", c2)
This challenge has 2 stages and both stages have 2 ciphertexts and encrypted using Rabin cryptosystem. In the former stage, the relation between $c_1, c_2$ can be expressed as
$$ \begin{aligned} f_1 &= x(x+B) - c_1 \ f_2 &= (2^{240}x+{\rm pad}) (2^{240}x+{\rm pad} + B) - c_2. \end{aligned} $$
We can recover $x (= m_1)$ by calculating GCD of $f_1, f_2$ because both $f_1$ and $f_2$ have the same root. (This method is known as Franklin-Reiter related-message attack.)
The latter stage is a little bit harder. We cannot apply the same way because the padding of m1, m2 is unknown.
It seems impossible to recover m, but Coppersmith’s short pad attack seems to be effective.
solve.sage
1def pgcd(a, b):
2 if b == 0:
3 return a.monic()
4 else:
5 return pgcd(b, a % b)
6
7
8def short_pad_attack(c1, c2, n, B):
9 PRxy.<x,y> = PolynomialRing(Zmod(n))
10 PRx.<xn> = PolynomialRing(Zmod(n))
11 PRZZ.<xz,yz> = PolynomialRing(Zmod(n))
12
13 g1 = x * (x + B) - c1
14 g2 = (x + y) * (x + y + B) - c2
15
16 q1 = g1.change_ring(PRZZ)
17 q2 = g2.change_ring(PRZZ)
18
19 h = q2.resultant(q1)
20 h = h.univariate_polynomial()
21 h = h.change_ring(PRx).subs(y=xn)
22 h = h.monic()
23
24 diff = h.small_roots(X=2^240, beta=1, epsilon=1/40)
25
26 return diff
27
28n = 105663510238670420757255989578978162666434740162415948750279893317701612062865075870926559751210244886747509597507458509604874043682717453885668881354391379276091832437791327382673554621542363370695590872213882821916016679451005257003326444660295787578301365987666679013861017982035560204259777436442969488099
29B = 12408624070212894491872051808326026233625878902991556747856160971787460076467522269639429595067604541456868927539680514190186916845592948405088662144279471
30c1 = 47149257341850631803344907793040624016460864394802627848277699824692112650262968210121452299581667376809654259561510658416826163949830223407035750286554940980726936799838074413937433800942520987785496915219844827204556044437125649495753599550708106983195864758161432571740109614959841908745488347057154186396
31c2 = 38096143360064857625836039270668052307251843760085437365614169441559213241186400206703536344838144000472263634954875924378598171294646491844012132284477949793329427432803416979432652621257006572714223359085436237334735438682570204741205174909769464683299442221434350777366303691294099640097749346031264625862
32hard_c1 = 73091191827823774495468908722773206641492423784400072752465168109870542883199959598717050676487545742986091081315652284268136739187215026022065778742525832001516743913783423994796457270286069750481789982702001563824813913547627820131760747156379815528428547155422785084878636818919308472977926622234822351389
33hard_c2 = 21303605284622657693928572452692917426184397648451262767916068031147685805357948196368866787751567262515163804299565902544134567172298465831142768549321228087238170761793574794991881327590118848547031077305045920819173332543516073028600540903504720606513570298252979409711977771956104783864344110894347670094
34
35
36# The former
37PR.<x> = PolynomialRing(Zmod(n))
38padding = int.from_bytes(b"\x1e" * 0x1e, 'big')
39f1 = x*(x+B) - c1
40x_ = 2^240*x + padding
41f2 = x_*(x_+B) - c2
42x1 = pgcd(f1, f2)
43X1 = int(-x1.coefficients()[0])
44print(bytes.fromhex(f"{X1:x}"))
45
46
47# The latter
48for padding in short_pad_attack(hard_c1, hard_c2, n, B):
49 g1 = x*(x+B) - hard_c1
50 g2 = (x+padding)*(x+padding+B) - hard_c2
51 x2 = pgcd(g1, g2)
52 X2 = int(-x2.coefficients()[0])
53 print(bytes.fromhex(f"{X2:x}"))
ACSC{Rabin_cryptosystem_was_published_in_January_1979_ed82c25b173f38624f7ba16247c31d04ca22d8652da4a1d701b0966ffa10a4d1_ec0c177f446964ca9595c187869312b2c0929671ca9b7f0a27e01621c90a9ac255_wow_GJ!!!}