NKCTF2024

NKCTF2024——Crypto——部分题解

Ez_Math

task.py

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

m1, m2 = bytes_to_long(flag[:len(flag)//2]), bytes_to_long(flag[len(flag)//2:])
p, q, r, s = [getStrongPrime(512) for _ in range(4)]
e = 0x10001

n = p * q * r * s
x = pow(q + r, p, n)
y = pow(p * q + r, p, n)
z = pow(s + 1, m1, s ** 3)
c = pow(m2, e * (s - 1), n)

print(f'{n = }')
print(f'{x = }')
print(f'{y = }')
print(f'{z = }')
print(f'{c = }')

# n = 16063619267258988011034805988633616492558472337115259037200126862563048933118401979462064790962157697989038876156970157178132518189429914950166878537819575544418107719419007799951815657212334175336430766777427972314839713871744747439745897638084891777417411340564312381163685003204182743581513722530953822420925665928135283753941119399766754107671729392716849464530701015719632309411962242638805053491529098780122555818774774959577492378249768503656934696409965037843388835948033129997732058133842695370074265039977902884020467413323500218577769082193651281154702147769044514475692164145099161948955990463002411473013
# x = 3021730035236300354492366560252387204933590210661279960796549263827016146230329262559940840168033978439210301546282150367717272453598367244078695402717500358042032604007007155898199149948267938948641512214616076878271433754986480186150178487625316601499002827958344941689933374158456614113935145081427421623647242719093642478556263121508238995676370877385638074444859047640771188280945186355013165130171802867101829647797879344213688981448535289683363612035513789240264618036062440178755665951650666056478493289870170026121826588708849844053588998886259091357236645819074078054595561158630194224419831088510266212458
# y = 8995787142441643101775260550632842535051686960331455373408888374295557050896156890779515089927839904014859222004906681231525326673182671984194300730575609496770604394218160422560576866112460837985407931067753009696969997384839637927957848613356269534870170452152926447601781637641134982178028922559652443398183848786034348994249923007092159192374765197460466878587635412657807328348343062302127490267456095927890461140420639805398464266081441243108883599713672104446500850203779995739675784794478089863001309614674686652597236324659979849324914804032046113978246674538411441434320732570934185579553749616238819583998
# z = 1283646988194723153191718393109711130382429329041718186548715246082834666179475883560020086589684603980734305610989683434078096863563033623169666389076830792095374856743015929373461198718962686411467443788047511292138922700655772772117855226419561159782734009961921473456332468653898105909729309377890721920937410781006337057478451806364879679045839945032594716202888196404203782734864187890231653321470085251
# c = 4988583141177813116287729619098477713529507701428689219486720439476625736884177254107631282807612305211904876847916760967188201601494592359879509876201418493870112712105543214178376471651715703062382025712952561985261461883133695993952914519494709871429166239968478488380137336776740647671348901626710334330855078254188539448122493675463406596681080368929986034772169421577420193671300532508625180845417164660544286332963072804192276425664877337357353975758574262657585309762422727680851018467657523970318042829660721433987195369353660020476598195375492128671951807024027929490113371463210453342974983253996717176870

分解n

$$
\because x \equiv (q+r)^p \mod n
$$

则
$$
x \equiv r^p \mod q
$$
同理
$$
y \equiv (pq + r)^p \mod n
$$
则
$$
y \equiv r^p \mod q
$$

$$
\therefore x - y \equiv 0 \mod q
$$

又因为
$$
x \equiv q+r \mod p
$$

$$
y \equiv r \mod p
$$

gcd(x-y-q,n) = kp

求解时候发现这个kp是1024bit,猜测这个kp实际上是$p\times q$,除掉$q$即可

求得$p,q$之后可以求$r,s$

求M1

$$
\because z \equiv (s + 1)^{m_1} \mod s^3
$$

则
$$
z \equiv 1^{m_1} + m_1s + \frac{m_1(m_1-1)}{2}s^2 \mod s^3
$$
模掉$s^2$得
$$
z \equiv 1 + m_1s \mod s^2
$$
这样就很容易求解$m_1$了

求解M2

$m_2$应该不大，直接在模p下求解

发现$e\times (s-1)$和$p-1$不互素，公因数为4

那么先求解出$(m_2) ^ 4 \mod p$

然后有限域开根

exp

from Crypto.Util.number import* 
import gmpy2

n = 16063619267258988011034805988633616492558472337115259037200126862563048933118401979462064790962157697989038876156970157178132518189429914950166878537819575544418107719419007799951815657212334175336430766777427972314839713871744747439745897638084891777417411340564312381163685003204182743581513722530953822420925665928135283753941119399766754107671729392716849464530701015719632309411962242638805053491529098780122555818774774959577492378249768503656934696409965037843388835948033129997732058133842695370074265039977902884020467413323500218577769082193651281154702147769044514475692164145099161948955990463002411473013
x = 3021730035236300354492366560252387204933590210661279960796549263827016146230329262559940840168033978439210301546282150367717272453598367244078695402717500358042032604007007155898199149948267938948641512214616076878271433754986480186150178487625316601499002827958344941689933374158456614113935145081427421623647242719093642478556263121508238995676370877385638074444859047640771188280945186355013165130171802867101829647797879344213688981448535289683363612035513789240264618036062440178755665951650666056478493289870170026121826588708849844053588998886259091357236645819074078054595561158630194224419831088510266212458
y = 8995787142441643101775260550632842535051686960331455373408888374295557050896156890779515089927839904014859222004906681231525326673182671984194300730575609496770604394218160422560576866112460837985407931067753009696969997384839637927957848613356269534870170452152926447601781637641134982178028922559652443398183848786034348994249923007092159192374765197460466878587635412657807328348343062302127490267456095927890461140420639805398464266081441243108883599713672104446500850203779995739675784794478089863001309614674686652597236324659979849324914804032046113978246674538411441434320732570934185579553749616238819583998
z = 1283646988194723153191718393109711130382429329041718186548715246082834666179475883560020086589684603980734305610989683434078096863563033623169666389076830792095374856743015929373461198718962686411467443788047511292138922700655772772117855226419561159782734009961921473456332468653898105909729309377890721920937410781006337057478451806364879679045839945032594716202888196404203782734864187890231653321470085251
c = 4988583141177813116287729619098477713529507701428689219486720439476625736884177254107631282807612305211904876847916760967188201601494592359879509876201418493870112712105543214178376471651715703062382025712952561985261461883133695993952914519494709871429166239968478488380137336776740647671348901626710334330855078254188539448122493675463406596681080368929986034772169421577420193671300532508625180845417164660544286332963072804192276425664877337357353975758574262657585309762422727680851018467657523970318042829660721433987195369353660020476598195375492128671951807024027929490113371463210453342974983253996717176870
e = 65537

q = gmpy2.gcd(x - y,n)
p = gmpy2.gcd(x - y - q,n) // q
r = y % p
s = n // p // q // r

temp = z % s**2
m1 = (temp - 1) // s
flag1 = long_to_bytes(int(m1))

dp = gmpy2.invert(e*(s-1)//4,p-1)
mp = pow(c,dp,p)

R.<x> = PolynomialRing(Zmod(p))
f = x ^ 4 - mp
res = f.roots()
for i in res:
    m2 = int(i[0])
    flag2 = long_to_bytes(int(m2))
    flag = flag1 + flag2
    print(flag)
    # nkctf{cb5b7392-cca4-4ce2-87e7-930cf6b29959}

GGH

task.sage

from sage.all import *
from flag import flag,n,delta

def hadamard_ratio(basis):
    dimension = basis.nrows()
    det_Lattice = det(basis)
    mult=1.0
    for v in basis:
        mult *= float(v.norm(2))
    hratio = (det_Lattice / mult) ** (1/dimension)
    return hratio

def get_key(n):
    l = 7
    k = ceil(sqrt(n) + 1) * l
    I = identity_matrix(n)
    while 1:
        V_ = random_matrix(ZZ,n, n, x=-l, y=l)
        V = V_ + I*k
        hada_ratio = hadamard_ratio(V)
        if hada_ratio > 0.86:
            U = unimodular_matrix(n)
            W = V * U
            return V, W
        else:
            continue

def unimodular_matrix(n):
    S = identity_matrix(n)
    X = identity_matrix(n)
    for i in range(n):
        for j in range(i,n):
            S[j, i] = choice([-1,1])
            X[i, j] = choice([-1,1])
    assert  det(S*X) == 1 or det(S*X) == -1
    return S*X

def get_error(n,delta):
    k = 4*delta -2
    tmp = []
    tmp += [delta - 2]*(n//k)
    tmp += [delta - 1]*( ((k-2)*n) // (2*k))
    tmp += [delta]*(n//k)
    tmp += [delta + 1]*( ((k-2)*n) // (2*k))
    return tmp

assert len(flag) == 44
assert delta < 20

V,W = get_key(n) 
gift = str(hex(randint(70, 80))).zfill(5).encode('utf-8')
flag =  gift + flag
print(flag)
m = [i for i in flag]
pad = [randint(-128, 127) for i in range(n-len(m)) ]
m = vector(ZZ, m + pad)
r = vector(get_error(n,delta))
c = m * W + r
assert floor((r).norm()) == delta*(floor(sqrt(n)))

with open('pubkey.txt', 'w') as f:
    f.write(str(W)) 

with open('ciphertext.txt', 'w') as f:
    f.write(str(c))

$$
\because c = mW + r
$$

很容易知道
$$
m = (c-r)\times W^{-1}
$$
其中$W$是$260\times 260$的矩阵，$m,r,c$是$1\times 260$的向量

通过$W$的规模可以知道$n = 260$

给了$delta < 20$，尝试爆破出r然后解密

exp

c = (14697, -103356, 74779, 95622, -11650, 524678, -258697, 388940, -399559, -437273, 267702, -978292, 686059, 835272, 809650, 759647, -573204, 989361, -696040, -694133, -831908, -477981, 724090, -1228907, -120150, -774399, -591584, -1291399, 254792, -134668, -109064, 198801, -749156, -816935, -1015728, -899139, 957539, 797980, 622496, 636293, 1795867, 688081, 1327891, 94650, -1563715, 789969, -2006496, 1400404, -1134347, -736944, 148919, -665150, -1081234, -973028, 881767, 3307694, -1584719, -805716, 1360628, -896122, -862741, -1014915, 848040, 8791, 1010424, -627001, -1915331, 1734060, -578582, -1250807, 1002361, -2555983, 382933, 876467, -517111, -890007, 1120942, 328836, 1070931, 3060471, 1282311, 900451, -1368524, 2383556, -100407, 1472198, -636598, 1481797, 1250775, 279604, -880140, 940241, 474972, 854830, -4072298, 440151, -622028, 2260879, -2738469, 974549, 103401, -2590853, -12923, -1612830, 1275543, -693632, -2681181, 536356, -199335, -638932, -3363587, 3897884, 1328506, -1114079, -553394, -2175335, -56629, 1842637, 48649, 1561646, 1874518, 514713, -1927387, -20432, -915037, -840193, 870019, 4671103, 1119753, 837031, 420138, 2875929, 1527979, 363294, -1591329, -2499404, -1504185, -161931, -1799591, 245185, 2222818, -3921583, -1357181, 453979, 1872321, -297401, 2490480, 2786635, -2838351, -737681, -2545091, -1696116, 425623, 147974, -1739229, -3945245, 1255070, -1820074, -2190869, -1254018, 2211542, 3565405, -1063183, 1179506, 1707422, 3324989, -105580, 4502495, 332793, -1505723, -493912, 756291, 2609637, -396470, 3318630, 1424448, -871428, -2341694, -1474359, 78429, 4140695, -1223022, 1726067, -1830797, 2252423, 634142, -1162911, 657946, 1161669, 314917, 637551, 128154, 1944407, 467548, -2980735, -1097568, -2143663, -251256, 2520771, -1815714, -1814059, 305958, -2599700, 1076361, -2794868, 2798862, -3126794, 2466492, 2951889, 2541846, -2737433, 2364461, 519766, 522438, -728868, -1180942, 1205432, 2089627, -844456, -427481, 1117668, 1503704, 4061528, -889185, 1678865, 4025442, 871542, -3081410, 2014316, 667040, -3925491, 1776813, 1304258, 2248592, 2204897, 1250071, 883217, -1259669, -2071139, -3292080, -1706324, 626620, 1202724, -361433, 1343175, 1486927, -2365569, 4589072, -2439656, -1727340, 2108002, -1245002, -1392031, -2058070, -814170, -116156, -878803, -1503880, 3505220, -891921)
c = vector(ZZ, c)

f = open("pubkey.txt","r").readlines()
W = []
for line in f:
    W.append(eval(str(line).strip()))
W = matrix(ZZ, W)

n = W.nrows()
def get_error(n,delta):
    k = 4*delta -2
    tmp = []
    tmp += [delta - 2]*(n//k)
    tmp += [delta - 1]*( ((k-2)*n) // (2*k))
    tmp += [delta]*(n//k)
    tmp += [delta + 1]*( ((k-2)*n) // (2*k))
    return tmp

for delta in range(1,20):
    r = vector(ZZ,get_error(n,delta))
    try:
        m = (c-r)*W^(-1)
        M = list(m)
        flag = bytes(M[:49])
        if b"nkctf" in flag:
            print(f"flag:{flag}")
            print(f"delta = {delta}")
    except:
        pass
# flag:b'00x4dnkctf{G0od_Y0u_Ar3_Kn0W_Ggh_Crypt0syst3m!!!}'
# delta = 7