ASIS CTF Finals 2021

25 Dec 2021

Challenge Name	Tags
Stairs	`rsa` `polynomial gcd`
nDLP	`discrete log`
RAS	`rsa` `coppersmith`
MDLP	`matrix` `discrete log`

Stairs

def encrypt(m, pubkey):
        e, n = 5, pubkey
        M = bytes_to_long(flag)
        m += M
        c = (pow(m, e, n) + m) % n
        return c

We can ask for an encryption of any message $m$, and we can also get the pubkey from the server.

solution

We can write the following relation:

\[(m + M)^e + m + M \equiv c \mod n\]

where $M$ is the flag. Then, notice that if we change the value of $m$ by encrypting different values, we can get polynomials with the same root of $M$. We can then use polynomial-GCD to obtain the flag.

from Crypto.Util.number import long_to_bytes

n = 11969239028597324985937815605967980703904020057529937313561771767499231724675137981821849110634019174336259137832049039870797118569676492881075797710081527231651032940869606619383856435920764396650542654001698984180986041908091644246743856500816705015854412395792980594069868364754826882340883681659369500943318700388734371607822606620557296489165555188855412324730432021010451513363121521981711506501471770040608116689859329681361824106928067713165236945198089824559799471985339923045413090006841840187828072429188270363207258596471618099234953286099589063195275840232687057584463177657444981514315367122975177687499
c0 = 1752810779308444677047172817063451933920438141772112755897132014698458816325527209344280863863089303090015329048013182444644279012644016158413062013636325918483715247799515440527976211654891820771968450242289058627465153029301018937879894875993471497647804530700880314025503287773626657474543858245192836605108336200320216373709866009787284877486784993545165790997535200276786013187436074658712003788426900488333960666418751713460673573153609904263209886266979104790763859909447239209833421896738666597696072867318641381805963877849205209051504010170446912364659755195787247856048960970821929525640707764241157086713 # encrypt 0
c1 = 11481837492163526387998702604267700606185532693055257820698010533959837729425853006078897715376566227777167811916980547469810617274465594649576921190780306540967808871000382609204971867678452903058460178602284048110850096680511916309824407924521794105241720061771925985015114452693693459267784245309130348908377357206637049247647267736637417305855444532149940656976953112098897288240434652341135807362793231174404171060553066569548882293941536250593325132620903634356142702088495815083181306551712985939669064466232259947765402826849578430542169141427722888148177376641710649423767034133685864156768130409781087140982 # encrypt 1
e = 5
P.<M> = PolynomialRing(Zmod(n))

def gcd(a,b):
    while b:
        a, b = b, a % b
    return a.monic()


poly1 = M^e + M - c0 # m = 0
poly2 = (M + 1)^e + M + 1 - c1 # m = 1

sol = gcd(poly1, poly2).small_roots()
print(long_to_bytes(sol))
# :::. The flag is: ASIS{7hI5_cryptOsySt3M_Iz_DeF1nit3lY_vUlNEr4bl3!?} .:::

Flag: `ASIS{7hI5_cryptOsySt3M_Iz_DeF1nit3lY_vUlNEr4bl3!?}`

nDLP

x = bytes_to_long(flag)
g = 685780528648223163108441
n = 12588567055208488159342105634949357220607702491616160304212767442540158416811459761519218454720193189
y = pow(g, x, n)
y = 9136134187598897896238293762558529068838567704462064643828064439262538588237880419716728404254970025

We need to solve the discrete log problem in $(\mathbb Z/n\mathbb Z)^*$, where $n$ is a composite number.

solution

We see that the bit length of $n$ is small, only 333 bits, so I decided to chuck it into yafu

***factors found***

P24 = 795045813258486756062581
P24 = 685825230919805430353639
P27 = 196506778231841265839577533
P27 = 117487902085160690512598387

Then, we can solve the discrete log problem mod each of these factors and combine with CRT.

from Crypto.Util.number import long_to_bytes

n = 12588567055208488159342105634949357220607702491616160304212767442540158416811459761519218454720193189
factors = [795045813258486756062581, 685825230919805430353639, 117487902085160690512598387, 196506778231841265839577533]
g = 685780528648223163108441
y = 9136134187598897896238293762558529068838567704462064643828064439262538588237880419716728404254970025
mods = []
for factor in factors:
    xp = discrete_log(y, Mod(g, factor))
    mods.append(xp)
    print(xp)
    
print(long_to_bytes(CRT(mods, [factor-1 for factor in factors])))
# ASIS{D!5Cre73_L09_iN_Zn_I5_3aSy?!}

Flag: `ASIS{D!5Cre73_L09_iN_Zn_I5_3aSy?!}`

RAS

from Crypto.Util.number import *
from flag import flag

def genparam(nbit):
	while True:
		a, b = getRandomRange(2, nbit), getRandomRange(32, nbit)
		if (a ** b).bit_length() == nbit:
			return a ** b

def genkey(nbit):
	p, q = [_ + (_ % 2) for _ in [genparam(nbit) for _ in '01']]
	while True:
		P = p + getPrime(31)
		if isPrime(P):
			while True:
				Q = q + getPrime(37)
				if isPrime(Q):
					return P, Q

def encrypt(m, pubkey):
	e = 0x10001
	assert m < pubkey
	c = pow(m, e, pubkey)
	return c

nbit = 512
P, Q = genkey(nbit)
pubkey = P * Q
flag = bytes_to_long(flag)
enc = encrypt(flag, pubkey)
print(f'pubkey = {pubkey}')
print(f'enc = {enc}')

Two 512 bit primes are generated by first generating two values $p, q$ of the form $a^b$, where $a$ is in the range 2-512, and $b$ is in the range 32-512. Then, the primes are generated by adding small primes to $p$ and $q$ so that the result is prime.

solution

The small range for $a$ and $b$ means there are a very limited amount of values that $p$ or $q$ can be. We start by generating all possible values for them:

possible = []
for a in range(2, 512):
    for b in range(32, 512):
        if (a ** b).bit_length() == 512:
            possible.append(a**b)
            
print(len(possible))
# 74

Now, what we can do is bruteforce combinations of these values and see if their product is close to $n$. This works because if we expand out $(p + k_1)(q + k_2)$, we get:

\[pq + k_1q + k_2p + k_1k_2\]

and so if we subtract $pq$, the resulting value will be very small, much less than the 1024 bit modulus.

import itertools
pubkey = 56469405750402193641449232753975279624388972985036568323092258873756801156079913882719631252209538683205353844069168609565141017503581101845476197667784484712057287713526027533597905495298848547839093455328128973319016710733533781180094847568951833393705432945294907000234880317134952746221201465210828955449
enc = 11104433528952071860984483920122173351342473018268740572598132083816861855404615534742178674185812745207876206939230069251889172817480784782618716608299615251541018034321389516732611030641383571306414414804563863131355221859432899624060128497648444189432635603082478662202695641001726208833663163000227827283

for p, q in itertools.combinations(possible, r=2):
    if (pubkey - p*q).nbits() < 600:
        print(p,q)
        
# 7503181809956767523746965523445045476257163607925774521504848419053281285592652527357937939189782711610752940844746826826913644756871296753402978970975383 7526061233844414054658272333288124411685335071877284335907504995816228844305448573362353388854643200579154642450347983868657774168720289858354164292124672

Now that we have the values for $p$ and $q$, notice that the bivariate polynomial:

\[(p + k_1)(q + k_2) - n\]

which has small roots $k_1$ and $k_2$. We’ll use defund’s implementation to solve for these small roots, and then we should be able to factor $n$. The rest is basic RSA.

import itertools
from Crypto.Util.number import long_to_bytes

def small_roots(f, bounds, m=1, d=None):
	if not d:
		d = f.degree()

	R = f.base_ring()
	N = R.cardinality()
	
	f /= f.coefficients().pop(0)
	f = f.change_ring(ZZ)

	G = Sequence([], f.parent())
	for i in range(m+1):
		base = N^(m-i) * f^i
		for shifts in itertools.product(range(d), repeat=f.nvariables()):
			g = base * prod(map(power, f.variables(), shifts))
			G.append(g)

	B, monomials = G.coefficient_matrix()
	monomials = vector(monomials)

	factors = [monomial(*bounds) for monomial in monomials]
	for i, factor in enumerate(factors):
		B.rescale_col(i, factor)

	B = B.dense_matrix().LLL()

	B = B.change_ring(QQ)
	for i, factor in enumerate(factors):
		B.rescale_col(i, 1/factor)

	H = Sequence([], f.parent().change_ring(QQ))
	for h in filter(None, B*monomials):
		H.append(h)
		I = H.ideal()
		if I.dimension() == -1:
			H.pop()
		elif I.dimension() == 0:
			roots = []
			for root in I.variety(ring=ZZ):
				root = tuple(R(root[var]) for var in f.variables())
				roots.append(root)
			return roots

	return []

p = 7503181809956767523746965523445045476257163607925774521504848419053281285592652527357937939189782711610752940844746826826913644756871296753402978970975383 
q = 7526061233844414054658272333288124411685335071877284335907504995816228844305448573362353388854643200579154642450347983868657774168720289858354164292124672
n = 56469405750402193641449232753975279624388972985036568323092258873756801156079913882719631252209538683205353844069168609565141017503581101845476197667784484712057287713526027533597905495298848547839093455328128973319016710733533781180094847568951833393705432945294907000234880317134952746221201465210828955449
c = 11104433528952071860984483920122173351342473018268740572598132083816861855404615534742178674185812745207876206939230069251889172817480784782618716608299615251541018034321389516732611030641383571306414414804563863131355221859432899624060128497648444189432635603082478662202695641001726208833663163000227827283
e = 65537

P.<k1, k2> = PolynomialRing(Zmod(n))
poly = (p + k1) * (q + k2) - n
k1, k2 = small_roots(poly, (2^32, 2^40))[0]
p += k1
q += k2
d = pow(e, -1, (p-1)*(q-1))
print(long_to_bytes(int(pow(c, d, n))))
# ASIS{RAS_iZ_51mpl!FI3D_RSA_sY573M!}

Flag: `ASIS{RAS_iZ_51mpl!FI3D_RSA_sY573M!}`

MDLP

from sage.all import *
from Crypto.Util.number import *
from secret import gen_prime, gen_base_matrix, flag

def keygen(nbit, l):
    #
    ## Create the n-bit prime and base square matrix of size l over Ring Z_p
    #
    p = gen_prime(nbit)
    A = gen_base_matrix(p, l)

    d = randint(2, p)
    Q = A ** d
    pubkey = (p, A, Q)
    privkey = d
    return pubkey, privkey

def encrypt(M, pubkey):
    p, A, Q = pubkey
    l = A.nrows()
    assert M.nrows() == l
    r = randint(2, p)
    C, D = A ** r, Q ** r
    E = D * M
    return C, E

def msg_to_matrix(p, msg):
    l = len(msg)
    return matrix(Zmod(p), [[bytes_to_long(msg[0:l//4]), bytes_to_long(msg[l//4:l//2])], 
            [bytes_to_long(msg[l//2:3*l//4]), bytes_to_long(msg[3*l//4:l])]])

nbit, l = 256, 2
pubkey, privkey = keygen(nbit, l)
p, A, Q = pubkey
M = msg_to_matrix(p, flag)
ENC = encrypt(M, pubkey)

print(f'pubkey = {pubkey}')
print(f'ENC = {ENC}')

The cryptosystem is effectively Elgamal but for matrices. We need to solve the discrete log problem in the matrix multiplication group over $\mathbb{F}_p$.

solution

Firstly, we notice that $p$ is very smooth:

p = 94413310751917369305079812653655619566021075449954923397392050181976939189891
print(factor(p-1))

# 2 * 5 * 103 * 131 * 139 * 149 * 181 * 223 * 263 * 313 * 337 * 347 * 349 * 359 * 389 * 409 * 479 * 509 * 547 * 599 * 613 * 643 * 751 * 757 * 773 * 787 * 797^2 * 839 * 857 * 877

so solving dlog in $(\mathbb Z/p\mathbb Z)^*$ should be trivial.

Next, we need to look at the matrices themselves. One useful tool to look at is the Jordan Normal form, as it has a simpler structure.

The Jordan Normal Form (JNF) of a matrix $A$ are matrices $J, B$ where $A = B^{-1}JB$, and where $J$ is composed of “blocks”.

What’s also useful about the JNF is that if we raise $A$ to the power of, say 2, we get:

\[A^2 = (B^{-1}JB)(B^{-1}JB)\]

where the $B^{-1}$ and $B$ cancel, leaving:

\[\begin{eqnarray} A^2 &=& (B^{-1}J * JB)\\ &=& B^{-1}J^2B \end{eqnarray}\]

and we can extend this to any exponent, therefore:

\[A^e = B^{-1}J^eB\]

In our case, the JNF of our generator matrix $A$ is:

p = 94413310751917369305079812653655619566021075449954923397392050181976939189891
A = Matrix(GF(p), [[38199337272663519912859864066101528484023656231849338967558894235177040565160, 39708167173513090810083500967474691943646789486489990958101592717502452906918],[ 8216211510625558273096642057121313417997488994504871245106775381995665925783, 56213973479253849392219948587554091081997419218105584429833155946799898624740]])

J, B = A.jordan_form(transformation=True)

print(J)
print(B)
# [94413310751917369305079812653655619566021075449954923397392050181976939189890|  0]
# [                                                                            0| 10]
# [                                                                            1  1]
# [87623995352552381250887192970771931741890383724533687361049906196161683629037 28199551609049423271269518815501961376449870982396032312131738394343665352759]

Notice that $J$ in this case is a 2 $\times$ 2 diagonal matrix, meaning it is of the form:

\[\begin{bmatrix} a & 0\\ 0 & b \end{bmatrix}\]

and if we raise it to the power of $e$, the resulting matrix will be:

\[\begin{bmatrix} a^e & 0\\ 0 & b^e \end{bmatrix}\]

and we know from above that $A^e = Q = B^{-1}J^eB$, meaning if we work out $J^e$, we will be able to get the values of $a^e$. From here, we can simply solve the discrete log problem in $(\mathbb Z/p\mathbb Z)^*$, which we established above is trivial due to $p$ being smooth.

and working out $J^e$ isn’t too hard:

\[\begin{eqnarray} Q &=& B^{-1}J^eB\\ B^{-1}QB &=& J^e \end{eqnarray}\]

All that’s left is to decrypt using standard Elgamal encryption with knowledge of the private key.

from Crypto.Util.number import long_to_bytes

p = 94413310751917369305079812653655619566021075449954923397392050181976939189891
A = [[38199337272663519912859864066101528484023656231849338967558894235177040565160, 39708167173513090810083500967474691943646789486489990958101592717502452906918],[ 8216211510625558273096642057121313417997488994504871245106775381995665925783, 56213973479253849392219948587554091081997419218105584429833155946799898624740]]
Q = [[61709241598677561125021718690991651934557899286972116933820920757636771220273,  1945367449329759288724720626216309893787847192907494307536759223359193510642], [37495232301500074672571996664644922614693962264764098174213150757616575323566,  7348269231944161963123250652171976847627786311806728904368575861561449853500]]
C = [[47566868540912475779105819546118874217903268597017385039977593878486632022506, 86073162301954995219912739344010659248720823814557810528618517154406350653517], [23443866424088482893369441934221448179896589659663581973508963775891809430857, 74567333640177484678138574534395714128854315440076840728428649074147859070975]] 
E = [[56937964695156855099385034285428853461603799261684034842341841781057485084327, 82459328835322885824854425864023809222717401981993182346342472865578156162544], [85092677346274708324092648597361729755305119435989183201786866456596369562681, 22228861714953585357281182780002271505668586948202416054453861940155538803489]]

A, Q, C, E = [Matrix(GF(p), x) for x in [A,Q,C,E]]
J, B = A.jordan_form(transformation=True)

Je = B^-1 * Q * B
d = discrete_log(Je[1][1], Mod(J[1][1], p)) # top left is 1, x = 0 which is obviously not right, so we need to use bottom right
print(d)
assert A^d == Q
D = C^d
# E = D * M
M = (D.solve_right(E))
flag = b""
print(M)
for row in list(M):
    for m in row:
        flag += long_to_bytes(int(m))

print(flag)
# ASIS{PuBl1c-K3y_CRyp70sy5tEm_B4S3d_On_Tw0D!m3nSiOn_DLP!}

ASIS CTF Finals 2021

Stairs

solution

Flag: ASIS{7hI5_cryptOsySt3M_Iz_DeF1nit3lY_vUlNEr4bl3!?}

nDLP

solution

Flag: ASIS{D!5Cre73_L09_iN_Zn_I5_3aSy?!}

RAS

solution

Flag: ASIS{RAS_iZ_51mpl!FI3D_RSA_sY573M!}

MDLP

solution

Flag: ASIS{PuBl1c-K3y_CRyp70sy5tEm_B4S3d_On_Tw0D!m3nSiOn_DLP!}

Flag: `ASIS{7hI5_cryptOsySt3M_Iz_DeF1nit3lY_vUlNEr4bl3!?}`

Flag: `ASIS{D!5Cre73_L09_iN_Zn_I5_3aSy?!}`

Flag: `ASIS{RAS_iZ_51mpl!FI3D_RSA_sY573M!}`

Flag: `ASIS{PuBl1c-K3y_CRyp70sy5tEm_B4S3d_On_Tw0D!m3nSiOn_DLP!}`