# ASIS CTF Finals 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!?} .:::


# 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?!}


# 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!}


# 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!}