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)