N1CTF2021
| Challenge | Tags |
|---|---|
| checkin | Coppersmith, Math |
| n1token1 | HNP, Quadratic Sieve |
| n1token2 | Linear Algebra |
checkin
task.py
from Crypto.Util.number import *
from secret import flag
p = getPrime(512)
q = getPrime(512)
n = p*q
x = 2021*p+1120*q
h = (inverse(x,n)+x)%n
e = 65537
c = pow(bytes_to_long(flag), e, n)
print('n =', n)
print('c =', c)
print('h =', h)
print('p0 =', p >> 490)
# n = 124592923216765837982528839202733339713655242872717311800329884147642320435241014134533341888832955643881019336863843062120984698416851559736918389766033534214383285754683751490292848191235308958825702189602212123282858416891155764271492033289942894367802529296453904254165606918649570613530838932164490341793
# c = 119279592136391518960778700178474826421062018379899342254406783670889432182616590099071219538938202395671695005539485982613862823970622126945808954842683496637377151180225469409261800869161467402364879561554585345399947589618235872378329510108345004513054262809629917083343715270605155751457391599728436117833
# h = 115812446451372389307840774747986196103012628652193338630796109042038320397499948364970459686079508388755154855414919871257982157430015224489195284512204803276307238226421244647463550637321174259849701618681565567468929295822889537962306471780258801529979716298619553323655541002084406217484482271693997457806
# p0 = 4055618
Solution
$h=\frac{1}{x}+x$
$\Rightarrow x^2-h\cdot x+1(mod\ n)$
We can get high bits of q through the known p high bits.
$x=2021\cdot p+1120\cdot q=(2021\cdot(2^{490}\cdot p_0+p_1)+1120\cdot(2^{490}\cdot q_0+q_1))$
The unknown part of x is less than 501 bits
small_roots can solve this with epsilon=0.02
It’s higher than the theoretical bound, may be LLL sometimes do better.
n = 124592923216765837982528839202733339713655242872717311800329884147642320435241014134533341888832955643881019336863843062120984698416851559736918389766033534214383285754683751490292848191235308958825702189602212123282858416891155764271492033289942894367802529296453904254165606918649570613530838932164490341793
c = 119279592136391518960778700178474826421062018379899342254406783670889432182616590099071219538938202395671695005539485982613862823970622126945808954842683496637377151180225469409261800869161467402364879561554585345399947589618235872378329510108345004513054262809629917083343715270605155751457391599728436117833
h = 115812446451372389307840774747986196103012628652193338630796109042038320397499948364970459686079508388755154855414919871257982157430015224489195284512204803276307238226421244647463550637321174259849701618681565567468929295822889537962306471780258801529979716298619553323655541002084406217484482271693997457806
p0 = 4055618
q0 = None
head = n>>(1024-22)
for i in range(2**22):
if (i*p0)>>22 == head:
q0 = i
break
PR.<x> = PolynomialRing(Zmod(n))
g = x+2021*2^490*p0+1120*2^490*q0
f = g^2-h*g+1
root = ZZ(f.small_roots(X=2^500, beta=1, epsilon=0.02)[0])
x0 = root+2021*2^490*p0+1120*2^490*q0
diff = isqrt(x0^2-4*2021*1120*n)
p = (x0+diff)//4042
q = (x0-diff)//2240
phi = (p-1)*(q-1)
d = inverse_mod(0x10001, phi)
m = pow(c, d, n)
print(bytes.fromhex(hex(m)[2:]))
n1token1
task.py
from Crypto.Util.number import *
import random
from secret import flag
def gettoken(c):
X = 0
while ((pow(X, (p-1)//2, p)!=1) or (pow(X, (q-1)//2, q)!=1)):
X = 1
while X.bit_length() < 920:
X *= random.choice(primes)
xp = pow(X, (p + 1)//4, p)
xq = pow(X, (q + 1)//4, q)
xp = random.choice([xp,-xp%p])
xq = random.choice([xq,-xq%q])
x = c * (xp*inverse(q,p)*q + xq*inverse(p,q)*p) % n
return x
def getmyPrime(nbits):
p = getPrime(nbits)
while(p%4==1):
p = getPrime(nbits)
return p
primes = random.sample(sieve_base, 920)
p = getmyPrime(512)
q = getmyPrime(512)
e = 65537
n = p*q
c = pow(bytes_to_long(flag), e, n)
with open("output.txt", "w")as f:
f.write("n = " + str(n) + "\n")
for i in range(920):
f.write("Token #"+str(i+1)+': '+str(gettoken(c))+'\n')
Solution
The token generating as follow,
$tk_i = c\cdot \sqrt{X_i}(mod\ n)$
$\Rightarrow tk_i^2\cdot(c^{-2})=X_i(mod\ n)$ Where $X<2^{940}$
So we can solve this hidden number problem to recover $X_i$.
$\Rightarrow tk_0^2\cdot (tk_i^2)^{-1}=X_0\cdot X_i^{-1}(mod\ n)$
Rewriting the $X_i$ with primes’ exponent, and solve the kernel of exponent matrix in $F_2$ (only care parity)
Finally, we can construct $a^2=b^2(mod\ n)$, it’s probably get the factors of n.
from Crypto.Util.number import *
from functools import reduce
f = open('output.txt', 'r')
f.read(4)
n = int(f.readline())
tk = []
for _ in range(920):
tk_ = f.readline()
st = tk_.index(':')
tk.append(int(tk_[st+1:]))
def solver_hnp(s):
L = matrix(QQ, 101, 101)
L[0, 0] = 2^(940-1024)
for _ in range(100):
L[0, _+1] = s[_]**2%n
L[_+1, _+1] = n
basis = L.LLL()[1]
g = reduce(GCD, basis[1:])
c_ = basis[0]*2^(1024-940)//g
return c_
c_ = solver_hnp(tk[:100])
if (c_*tk[0]**2)%n > 2^940:
c_ = -c_
X = []
for tk_ in tk:
X.append((tk_**2*(c_)%n))
primes = set()
for x in X:
facs = list(factor(x))
for item in facs:
primes.add(item[0])
primes = list(primes)
ch = []
for x in X:
u = [0]*920
facs = list(factor(x))
for item in facs:
u[primes.index(item[0])] = item[1]
ch.append(u)
std = vector(ZZ, ch[0])
Ch = []
for i in range(1, len(ch)):
Ch.append(std-vector(ch[i]))
A = matrix(Zmod(2), Ch)
ker = vector(ZZ, list(A.left_kernel().matrix()[0]))
res = ker*matrix(ZZ, Ch)
a = 1; b = 1
for i in range(len(ker)):
if ker[i]:
a *= tk[0]
b *= tk[i+1]
for i in range(len(res)):
if res[i] > 0:
b *= pow(primes[i], res[i]//2, n)
else:
a *= pow(primes[i], abs(res[i])//2, n)
p = GCD(a+b, n)
q = n//p
Fp = GF(p)
Fq = GF(q)
phi = (p-1)*(q-1)
d = inverse_mod(0x10001, phi)
c2 = inverse_mod(X[0], n)*tk[0]**2%n
m2 = pow(c2, d, n)
mp = Fp(m2).nth_root(2, all=True)
mq = Fq(m2).nth_root(2, all=True)
for i in mp:
for j in mq:
m = crt([int(i), int(j)], [p, q])
print(long_to_bytes(m))
n1token2
task.py
import random
from secret import flag
assert FLAG.startswith('n1ctf{')
assert FLAG.endswith('}')
SECRET = bytes.fromhex(FLAG[6:-1])
assert len(SECRET) == 16
p = 251
e = [1, 20, 113, 149, 219]
y = b''
for x in range(1, p):
coeff = [random.choice(e)] + list(SECRET)
y += bytes([sum(c * pow(x, i, p) for i, c in enumerate(coeff)) % p])
print(f'Token: {y.hex()}')
Solution
We can use the prod idea to solve multiple choices problem
assume $F(x)=\sum_{i=1}\limits^{16}a_ix^i$
So the relation can be write as follow,
$\prod_{i=0}\limits^4(F(x_j)+e_i-y_j)=0$
$a_0+a_1\cdot F(x_j)+a_2\cdot F^2(x_j)+a_3\cdot F^3(x_j)+a_4\cdot F^4(x_j)+a_5\cdot F^5(x_j)=0$
Considering $F^j(x)$ as independent polynomial, there are total 245 unknow coefficients.
With 250 tokens, solving the matrix to recover all coefficient.
token = 'ae47d3533e10b444374ebd35f578103f94c327b5959f4580b0dc4701d089f22c282acfed2626bd9ced919547dacc96c18595468952cbedbcf518b5ec0fbc0437ea8e3bd77c5f01f73b555cc97a382df1ce28b4af7f9a5ab9c47e055044f47463c4f33bebdd4d6965599c71720b5a549a8246cb200dc4e2dccfc4765c0ac266a8a5385172aa47f834db737a3bcc725ae5a1ec8b76d1ca4800da10450b04543377efa5428584efdfdf55282e0e4410ae7848a0217a7d66f2d6c06c846a4755867dbdf61c70646f67debf44839a342e5f64e3abd2c9f5b66656edc8004cea987503793f7e07e3b60af4852e03177cae1e8ee605aab76d3a70df4e1e'
p = 251
e = [1, 20, 113, 149, 219]
A = []
v = []
Z.<x> = PolynomialRing(Zmod(p))
for i in range(0, len(token), 2):
tk = int(token[i:i+2], 16)
a = []
for e_ in e:
a.append(e_-tk)
f = (x+a[0])*(x+a[1])*(x+a[2])*(x+a[3])*(x+a[4])
coeff = (list(f))[::-1]
x0 = i//2+1
u = []
for _ in range(81):
u.append(coeff[0]*x0^_)
for _ in range(65):
u.append(coeff[1]*x0^_)
for _ in range(49):
u.append(coeff[2]*x0^_)
for _ in range(33):
u.append(coeff[3]*x0^_)
for _ in range(17):
u.append(coeff[4]*x0^_)
v.append(-coeff[-1])
A.append(u)
A = matrix(Zmod(p), A)
v = vector(Zmod(p), v)
sol = A.solve_right(v)
secret = bytes(sol[-16:]).hex()
print(secret)