from Crypto.Util.number import bytes_to_long, getStrongPrime
from random import getrandbits
FLAG = bytes_to_long(b"ASCWG{XXXX}")
p = getStrongPrime(512)
a, b, c = getrandbits(256), getrandbits(256), getrandbits(256)
x = getrandbits(512)
y = FLAG*x % p
f1 = (a*x*y + b*x - c*y + a*b) % p
f2 = (a*x*y - a*b*x + c*y - a*b*c) % p
f3 = (a*x*y + a*b*x - b*y + a*c) % p
print(f"{a=}\n{b=}\n{c=}\n{p=}")
print(f"{f1=}\n{f2=}\n{f3=}")
Solution
So we have equation below
f1=axy+bx−cy+abf2=axy−abx+cy−abcf3=axy+abx−by+ac
So basically we need to recover x and y and we know a, b, and c. The idea i used to solve the challenge is by eliminating the variable. Here is the proof
f1−f2=kx−ly+df2−f3=mx−ny+e
Variables k, m, l, n, d, and e are known so the next step is by doing lcm on one of the coefficent on x or y. After that just eliminate the variable and back to modulus part. For example i eliminate variable x so now we need to work only with variable y and some known constant which are k, d, and e.
k∗y−d=emodpk∗y=e+dmodpy=(e+d)∗k−1modp
After getting y next we just need to substitute y and one of initial equation to get x. To get flag we just need to inverse the x then multiply with y. Here is script i used to solve the challenge
Flag : ASCWG{4tt@ck_7h3_Id3@l_w0RlD_0f_Gr0e6N2r$$}
Sign Hell (300 pts)
Description
Given challenge below
import os
FLAG = os.getenv("FLAG", "ASCWG{XXXX}")
def get_prime():
while True:
p = 1
for _ in range(9):
p *= getrandbits(64)
if is_prime(p+1):
return p+1
def sign(M):
S1 = int(pow(g,k,p))
S2 = int(((M - a*S1)*inverse_mod(k,p-1))) % (p-1)
return S1, S2
def verify(M, S1, S2):
return pow(A,S1,p)*pow(S1,S2,p) % p == pow(g,M,p)
p = get_prime()
g = primitive_root(p)
a = secret = int.from_bytes(FLAG.encode(), "big")
A = pow(g,a,p)
k = getrandbits(256)
while gcd(k, p-1) != 1:
k = getrandbits(256)
public = p,g,A
private = p,g,secret
print(f"Public: ", public)
while True:
m = int.from_bytes(os.urandom(32), "big")
S1, S2 = sign(m)
print(S1, S2, m)
Solution
So we can recover the flag by utilizing 2 pair of signature. First we need to substract s2 on each pair
But since there is chance that s1 and k are not coprime with p-1 we can still get the flag by repeating request until get the flag. Here is script i used to solve the challenge
from Crypto.Util.number import *
from math import gcd
from pwn import *
while True:
r = remote("34.154.18.2", 6951)
r.recvuntil(b"Public: ")
value = r.recvline().strip()
exec(f"p, g, A = {value.decode()}")
s1_1, s2_1, m1 = list(map(int,r.recvline().decode().split(" ")))
s1_2, s2_2, m2 = list(map(int,r.recvline().decode().split(" ")))
r.close()
n = p - 1
s2_diff = (s2_1 - s2_2) % n
s1_inv = inverse(s1_2//(gcd(s1_2,n)), n)
list_s = [m1, m2]
for k_try in (list_s[0] - list_s[1], list_s[0] + list_s[1], -list_s[0] - list_s[1], -list_s[0] + list_s[1]):
try:
k_inv = (s2_diff * inverse(k_try,n) ) % n
k = inverse(k_inv, n)
a = (((s2_1 * k) - m1) * s1_inv) % n
flag = -a % n
for i in range(1,100000):
tmp = flag // i
tmp = long_to_bytes(tmp)
if(b"ASCWG" in tmp):
print(tmp)
break
except Exception as e:
continue
Flag : ASCWG{R3uS31n9_G4m4l_NoNc3_S19n1n9_1s_50o_B4d_d9ae71c5}
Power Times (600 pts)
Description
Given challenge below
import os
import time
FLAG = os.getenv("FLAG", "ASCWG{XXXX}").encode()
def gen_prime():
while True:
p = 2
for _ in range((2<<2)+1):
p *= getrandbits(58)
if is_prime(p+1):
return p+1
def encrypt():
rand_val = getrandbits(256)
x = G(rand_val)
h = g^x
y = G.random_element()
s = h^y
c1 = g^y
m = G(int.from_bytes(FLAG, byteorder="big"))
c2 = m*s
return (q, g, h, c1, c2), x
if __name__ == "__main__":
q = gen_prime()
G = GF(q, modulus="primitive")
g = G.gen()
print(encrypt()[0])
Solution
We can see that generated prime is smooth, so we can do discrete log by using Pohlig-Hellman algorithm. In this challenge i use sage to do the discrete log. After getting x we just need to power c1 with x then inverse it. After that just multiply c2 with inverse value then get flag. Here is the script i used to solve the challenge
from Crypto.Util.number import *
# get values from service
q, g, h, c1, c2 = (875224290892889410253168846038019495397845981839895578503538762070606629236318636299280667067488152448925123623980445977018237347103987840918389215641601, 53, 668470863937718723825354309435934649904792238682832221264120364357988404177550549769338892561589799679349995460516437572438684131831080306276964600141039, 470878962668317620809812946691419181909240344358287048400184661683087768031571681980489293375447027465015614359318228582735903960499464295349483276943379, 431842574173304880865818550579295915213571302015965986053503318188592141963759191137818608526476403184681573593979962710727636081373213496309873939220545)
gp = GF(q)
cp = gp(h)
g1 = gp(g)
x = discrete_log(cp, g1)
x = 51569899004643158586115894615877127399796211204579510660966346446530141286946
tmp = pow(c1, x, q)
result = (c2 * inverse(tmp, q)) % q
print(long_to_bytes(result))