2023-03-27   28 m   4.2 k0 visits

NKCTF Crypto wp

小做了一下NKCTF的题。（主要是好久没更了，找点东西水一水刷刷存在感XD）

baby_RSA

题目源码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
from Crypto.Util.number import *
nbit = 512
flag='****************************'

p=getPrime(nbit)
q=getPrime(nbit)
e=65537
n=p*q
m= bytes_to_long(bytes(flag.encode()))
P = pow(m,p,n)
Q = pow(m,q,n)
N=P*Q
phi_N=(P-1)*(Q-1)
d=inverse(e,phi_N)
dP=d%(P-1)
print('n = ',n)
print('N = ',N)
print('dP = ',dP)

已知和，我们可以把分解出来。

然后根据，有： 从而,

因此有： 根据上式直接coppersmith就能解出来。

解题代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
from Crypto.Util.number import *

n =  114101396033690088275999670914803472451228154227614098210572767821433470213124900655723605426526569384342101959232900145334500170690603208327913698128445002527020347955300595384752458477749198178791196660625870659540794807018881780680683388008090434114437818447523471527878292741702348454486217652394664664641
N =  1159977299277711167607914893426674454199208605107323826176606074354449015203832606569051328721360397610665453513201486235549374869954501563523028914285006850687275382822302821825953121223999268058107278346499657597050468069712686559045712946025472616754027552629008516489090871415609098178522863027127254404804829735621706042266140637592206366042515190385496909533329383212542170504864473944657824502882014292528444918055958758310544435120502872883857209880723535754528096143707324179005292445100655695427777453144657819474805882956064292780031599790769618615908501966912635232746588639924772530057835864082951499028
dP =  33967356791272818610254738927769774016289590226681637441101504040121743937150259930712897925893431093938385216227201268238374281750681609796883676743311872905933219290266120756315613501614208779063819499785817502677885240656957036398336462000771885589364702443157120609506628895933862241269347200444629283263
e=65537

for k in range(1,e):
    if (e*dP-1)%k==0 and N%((e*dP-1)//k+1)==0:
        P=(e*dP-1)//k+1
        Q=N//P
        print(f'{P=}')
        print(f'{Q=}')

        R.<x>=PolynomialRing(Zmod(n))
        f=x^2-(P+Q)*x+P*Q
        res=f.small_roots()[0]
        print(long_to_bytes(int(res)))
        #b'NKCTF{Th1S_a_babyRSA_y0u_are_tql!!!}'

ezRSA

题目源码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
from Crypto.Util.number import *
from secret import flag

m1 = bytes_to_long(flag[:len(flag)//3])
m2 = bytes_to_long(flag[len(flag)//3:])

def gen():
    prime_list  = []
    for i in range(4):
        prime_list.append(getPrime(512))
    return sorted(prime_list)

prime_list = gen()
p,q,r,t = prime_list[0],prime_list[3],prime_list[1],prime_list[2]
e = 65537
n = p*q*r*t
phi = (p-1)*(q-1)*(r-1)*(t-1)
c1 = pow(m1,e,p*q)
p1 = getPrime(512)
q1 = getPrime(512)
N = p1*q1
c2 = pow(m2,p1,N)
c3 = pow(m2,q1,N)
print(f'n = {n}')
print(f'phi = {phi}')
print(f'c1 = {c1}')
print(f'N = {N}')
print(f'c2 = {c2}')
print(f'c3 = {c3}')

flag分成两个部分。m2的解法看似和baby_RSA类似，但直接求发现算不出来，看来需要设置coppersmith参数。因此先要解出m1算出flag长度。

第一部分给了muti-prime的n和phi，因此可以把n分解（网上找个脚本直接跑了），然后解出m1。然后计算出m2的长度为54bytes，从而算出X上限，然后根据，令beta=1，epsilon大约为0.08即可。

解题代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
from Crypto.Util.number import *
from math import gcd
from math import isqrt
from random import randrange

n = 8836130216343708623415307573630337110573363595188748983290313549413242332143945452914800845282478216810685733227137911630239808895196748125078747600505626165666334675100147790578546682128517668100858766784733351894480181877144793496927464058323582165412552970999921215333509253052644024478417393146000490808639363681195799826541558906527985336104761974023394438549055804234997654701266967731137282297623426318212701157416397999108259257077847307874122736921265599854976855949680133804464839768470200425669609996841568545945133611190979810786943246285103031363790663362165522662820344917056587244701635831061853354597
phi = 8836130216343708623415307573630337110573363595188748983290313549413242332143945452914800845282478216810685733227137911630239808895196748125078747600505622503351461565956106005118029537938273153581675065762015952483687057805462728186901563990429998916382820576211887477098611684072561849314986341226981300596338314989867731725668312057134075244816223120038573374383949718714549930261073576391501671722900294331289082826058292599838631513746370889828026039555245672195833927609280773258978856664434349221972568651378808050580665443131001632395175205804045958846124475183825589672204752895252723130454951830966138888560
c1 = 78327207863361017953496121356221173288422862370301396867341957979087627011991738176024643637029313969241151622985226595093079857523487726626882109114134910056673489916408854152274726721451884257677533593174371742411008169082367666168983943358876017521749198218529804830864940274185360506199116451280975188409
N = 157202814866563156513184271957553223260772141845129283711146204376449001653397810781717934720804041916333174673656579086498762693983380365527400604554663873045166444369504886603233275868192688995284322277504050322927511160583280269073338415758019142878016084536129741435221345599028001581385308324407324725353
c2 = 63355788175487221030596314921407476078592001060627033831694843409637965350474955727383434406640075122932939559532216639739294413008164038257338675094324172634789610307227365830016457714456293397466445820352804725466971828172010276387616894829328491068298742711984800900411277550023220538443014162710037992032
c3 = 9266334096866207047544089419994475379619964393206968260875878305040712629590906330073542575719856965053269812924808810766674072615270535207284077081944428011398767330973702305174973148018082513467080087706443512285098600431136743009829009567065760786940706627087366702015319792328141978938111501345426931078
e = 65537

def factorize_multi_prime(N, phi):
    """
    Recovers the prime factors from a modulus if Euler's totient is known.
    This method works for a modulus consisting of any number of primes, but is considerably be slower than factorize.
    More information: Hinek M. J., Low M. K., Teske E., "On Some Attacks on Multi-prime RSA" (Section 3)
    :param N: the modulus
    :param phi: Euler's totient, the order of the multiplicative group modulo N
    :return: a tuple containing the prime factors
    """
    prime_factors = set()
    factors = [N]
    while len(factors) > 0:
        # Element to factorize.
        N = factors[0]

        w = randrange(2, N - 1)
        i = 1
        while phi % (2 ** i) == 0:
            sqrt_1 = pow(w, phi // (2 ** i), N)
            if sqrt_1 > 1 and sqrt_1 != N - 1:
                # We can remove the element to factorize now, because we have a factorization.
                factors = factors[1:]

                p = gcd(N, sqrt_1 + 1)
                q = N // p

                if isPrime(p):
                    prime_factors.add(p)
                elif p > 1:
                    factors.append(p)

                if isPrime(q):
                    prime_factors.add(q)
                elif q > 1:
                    factors.append(q)

                # Continue in the outer loop
                break

            i += 1

    return tuple(prime_factors)

primes=factorize_multi_prime(n,phi)
primes=sorted(list(primes))
p,q=primes[0],primes[3]
d=inverse(e,(p-1)*(q-1))
m1=pow(c1,d,p*q)
flag1=long_to_bytes(m1)
print(flag1)
#b'NKCTF{it_i5_e45y_th4t_Kn0wn'
print(len(flag1))
#27

R.<x>=PolynomialRing(Zmod(N))
f=x^2-(c2+c3)*x+c2*c3
res=f.small_roots(X=2^432,beta=1,epsilon=0.08)
flag2=long_to_bytes(int(res[0]))
print(flag2)
#b'_phi_4nd_N_dec0mp0ses_N_w1th_th3_s4m3_c0mm0n_n_but_pq}'

#NKCTF{it_i5_e45y_th4t_Kn0wn_phi_4nd_N_dec0mp0ses_N_w1th_th3_s4m3_c0mm0n_n_but_pq}

eZ_Math

题目源码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
from Crypto.Util.number import getPrime, bytes_to_long
from secret import BITS, hints, flag

p = getPrime(BITS)
q = getPrime(BITS)
n = p * q
print(f'n = {n}')

e = 0x10001
c = pow(bytes_to_long(flag), e, n)
print(f'c = {c}')

print('Give you some boring pows:')
for i in range(len(hints)):
    print(hints[i])

除了n,e,c之外，输出还给了一些pow计算值：

1
2
3
4
5
6
7
8
pow(6, 42762902032363446334121451790132830028099011269558028556333775251728898854654431095595000922138958455510196735338223430882428451914478079186797153527810555787441234842366353864053114538165236037883914332840687123514412294276743506313011532002136735343280737244020115917460801848337792582496228600926958548903290, n) = 4
pow(6, 141997416965295486849546892322458652502850390670128808480582247784728456230996812361056958004801816363393016360646922983916999235770803618904474553309200419301820603229504955218189709387942156848904968053547462302189568831762401075340100029630332409419313772378068180267756675141584884876543484516408660699471038, n) = 9
pow(6, 163378867981477210016607618217525067516899896304907822758749135410592905658324027908854458465871295591148114728316034699358213461728042658497873130073105697195541220650688132150216266657024774867846925219967805863946774978900772828496605795631400777090954141000078238226487076065753781167791598816872139973922682, n) = 3
pow(5, 101651508435846472131121026992982127175369332865677196032272241712711171024515826370577416844824734811581351106736224929238579734879671732717639124571916168742336862493284572465162318403582113621582374924091725060981390318743531229548188092491836655143124663368239422819562367919547196053790207486164506763679128, n) = 4
pow(8, 7202269322818255506843028035725052687541091567764933235328308385449791332345247877549905289072216053144576876979686287212194040101112899704499548530779540409356827298148385589812450437990490353926475147376495772639210184768544932563432306664067058309318707174880146258394471096033723193568453520897758319446472, n) = 3
pow(6, 64144353048545169501182177685199245042148516904337042834500662877593348281981646643392501383208437683265295103007335146323642677871717118780195730291715833681161852263549530796079671807247854056825871499261030685271618441415115259469517298003205103014921105866030173876191202772506688873744342901390437823354935, n) = 8
pow(6, 21381451016181723167060725895066415014049505634779014278166887625864449427327215547797500461069479227755098367669111715441214225957239039593398576763905277893720617421183176932026557269082618018941957166420343561757206147138371753156505766001068367671640368622010057958730400924168896291248114300463479274451645, n) = 2
...

那么直接挑两对具有平方关系的值出来，根据指数之间的关系然后GCD即可得到，从而直接算出私钥即可。

解题代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
from Crypto.Util.number import *

n = 369520637995317866367336688225182965061898803879373674073832046072914710171302486913303917853881549637806426191970292829598855375370563396182543413674021955181862907847280705741114636854238746612618069619482248639049407507041667720977392421249242597197448360531895206645794505182208390084734779667749657408715621
c = 324131338592233305486487416176106472248153652884280898177125443926549710357763331715045582842045967830200123100144721322509500306940560917086108978796500145618443920020112366546853892387011738997522207752873944151628204886591075864677988865335625452099668804529484866900390927644093597772065285222172136374562043
e = 0x10001

t1=163378867981477210016607618217525067516899896304907822758749135410592905658324027908854458465871295591148114728316034699358213461728042658497873130073105697195541220650688132150216266657024774867846925219967805863946774978900772828496605795631400777090954141000078238226487076065753781167791598816872139973922682
t2=141997416965295486849546892322458652502850390670128808480582247784728456230996812361056958004801816363393016360646922983916999235770803618904474553309200419301820603229504955218189709387942156848904968053547462302189568831762401075340100029630332409419313772378068180267756675141584884876543484516408660699471038
t3=21381451016181723167060725895066415014049505634779014278166887625864449427327215547797500461069479227755098367669111715441214225957239039593398576763905277893720617421183176932026557269082618018941957166420343561757206147138371753156505766001068367671640368622010057958730400924168896291248114300463479274451645
t4=64144353048545169501182177685199245042148516904337042834500662877593348281981646643392501383208437683265295103007335146323642677871717118780195730291715833681161852263549530796079671807247854056825871499261030685271618441415115259469517298003205103014921105866030173876191202772506688873744342901390437823354935
kphi=GCD(t1*2-t2,t3*3-t4)
print(kphi)
d=inverse(e,kphi)
m=pow(c,d,n)
print(long_to_bytes(m))
#b'NKCTF{d15cr373_L0g_15_R3DuC710n_f0R_f4C70r1nG}'

ez_polynomial

题目源码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#sage
from Crypto.Util.number import *
flag = list(bytearray(''))
p = getPrime(16)
R.<y> = PolynomialRing(GF(p))
while True:
    P1 = R.random_element(degree=(ZZ.random_element(len(flag), 2*len(flag))))
    Q1 = R.random_element(degree=(ZZ.random_element(len(flag), 2*len(flag))))
    if P1.is_irreducible() and Q1.is_irreducible():
        P = P1
        Q = Q1
        break
e = 65537
N = P*Q
S.<x> = R.quotient(N)
c = S(flag) ^ e
print("P:" + str(p) + "\n")
print("N:" + str(N) + "\n")
print("C:" + str(c))

多项式RSA。直接脚本梭了。

解题代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
p= 40031
P = PolynomialRing(Zmod(p), name = 'x')
x = P.gen()
y = P.gen()
e = 65537
n = 24096*y^93 + 38785*y^92 + 17489*y^91 + 9067*y^90 + 1034*y^89 + 6534*y^88 + 35818*y^87 + 22046*y^86 + 12887*y^85 + 445*y^84 + 26322*y^83 + 37045*y^82 + 4486*y^81 + 3503*y^80 + 1184*y^79 + 38471*y^78 + 8012*y^77 + 36561*y^76 + 19429*y^75 + 35227*y^74 + 10813*y^73 + 26341*y^72 + 29474*y^71 + 2059*y^70 + 16068*y^69 + 31597*y^68 + 14685*y^67 + 9266*y^66 + 31019*y^65 + 6171*y^64 + 385*y^63 + 28986*y^62 + 9912*y^61 + 10632*y^60 + 33741*y^59 + 12634*y^58 + 21179*y^57 + 35548*y^56 + 17894*y^55 + 7152*y^54 + 9440*y^53 + 4004*y^52 + 2600*y^51 + 12281*y^50 + 22*y^49 + 17314*y^48 + 32694*y^47 + 7693*y^46 + 6567*y^45 + 19897*y^44 + 27329*y^43 + 8799*y^42 + 36348*y^41 + 33963*y^40 + 23730*y^39 + 27685*y^38 + 29037*y^37 + 14622*y^36 + 29608*y^35 + 39588*y^34 + 23294*y^33 + 757*y^32 + 20140*y^31 + 19511*y^30 + 1469*y^29 + 3898*y^28 + 6630*y^27 + 19610*y^26 + 11631*y^25 + 7188*y^24 + 11683*y^23 + 35611*y^22 + 37286*y^21 + 32139*y^20 + 20296*y^19 + 36426*y^18 + 25340*y^17 + 36204*y^16 + 37787*y^15 + 31256*y^14 + 505*y^13 + 27508*y^12 + 20885*y^11 + 32037*y^10 + 31236*y^9 + 7929*y^8 + 27195*y^7 + 28980*y^6 + 11863*y^5 + 16025*y^4 + 16389*y^3 + 570*y^2 + 36547*y + 10451
c =3552*x^92 + 6082*x^91 + 25295*x^90 + 35988*x^89 + 26052*x^88 + 16987*x^87 + 12854*x^86 + 25117*x^85 + 25800*x^84 + 30297*x^83 + 5589*x^82 + 23233*x^81 + 14449*x^80 + 4712*x^79 + 35719*x^78 + 1696*x^77 + 35653*x^76 + 13995*x^75 + 13715*x^74 + 4578*x^73 + 37366*x^72 + 25260*x^71 + 28865*x^70 + 36120*x^69 + 7047*x^68 + 10497*x^67 + 19160*x^66 + 17939*x^65 + 14850*x^64 + 6705*x^63 + 17805*x^62 + 30083*x^61 + 2400*x^60 + 10685*x^59 + 15272*x^58 + 2225*x^57 + 13194*x^56 + 14251*x^55 + 31016*x^54 + 10189*x^53 + 35040*x^52 + 7042*x^51 + 29206*x^50 + 39363*x^49 + 32608*x^48 + 38614*x^47 + 5528*x^46 + 20119*x^45 + 13439*x^44 + 25468*x^43 + 30056*x^42 + 19720*x^41 + 21808*x^40 + 3712*x^39 + 25243*x^38 + 10606*x^37 + 16247*x^36 + 36106*x^35 + 17287*x^34 + 36276*x^33 + 1407*x^32 + 28839*x^31 + 8459*x^30 + 38863*x^29 + 435*x^28 + 913*x^27 + 36619*x^26 + 15572*x^25 + 9363*x^24 + 36837*x^23 + 17925*x^22 + 38567*x^21 + 38709*x^20 + 13582*x^19 + 35038*x^18 + 31121*x^17 + 8933*x^16 + 1666*x^15 + 21940*x^14 + 25585*x^13 + 840*x^12 + 21938*x^11 + 20143*x^10 + 28507*x^9 + 5947*x^8 + 20289*x^7 + 32196*x^6 + 924*x^5 + 370*x^4 + 14849*x^3 + 10780*x^2 + 14035*x + 15327

#分解N
q1, q2 = n.factor()
q1, q2 = q1[0], q2[0]

#求φ，注意求法，
phi = (p**q1.degree() - 1) * (p**q2.degree() - 1)
assert gcd(e, phi) == 1
d = inverse_mod(e, phi)
m = pow(c,d,n)

#取多项式系数
flag = bytes(m.coefficients())
print("Flag: ", flag.decode())
#NKCTF{We_HaV3_n0th1ng_But_dr3amS}

fake_MT & real_MT

不知道为什么出了两个一样的题，没看出来源码有啥区别。用一个脚本都能解。

题目源码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
import random
import signal

def guess_number_1():
    randoms = []
    for _ in range(208):
        randoms.append(random.getrandbits(96))

    print("randoms = "+str(randoms))
    number = str(random.getrandbits(96))
    guess = str(input("Guess after number:"))
    if guess != number:
        print("Wrong Number! Guess again.")
        exit(0)

def guess_number_2():
    number = str(random.getrandbits(96))
    randoms = []
    for _ in range(627):
        randoms.append(random.getrandbits(32))

    print("randoms = "+str(randoms))
    guess = str(input("Guess pre number:"))
    if guess != number:
        print("Wrong Number! Guess again.")
        exit(0)

def guess_number_3():

    def _int32(x):
        return int(0xFFFFFFFF & x)  
    def init(seed):
        mt = [0] * 624
        mt[0] = seed
        for i in range(1, 624):
            mt[i] = _int32(1812433253 * (mt[i - 1] ^ mt[i - 1] >> 30) + i)
        return mt[-1]
    number = random.getrandbits(32)
    print("last number = "+ str(init(number)))
    guess = int(str(input("Guess seed number:")))
    if guess != number:
        print("Wrong Number! Guess again.")
        exit(0)

def guess_number_4():
    def extract_number(y):
        y = y ^ y >> 11
        y = y ^ y << 7 & 2636928640
        y = y ^ y << 15 & 4022730752
        y = y ^ y >> 18
        return y&0xffffffff

    number = random.getrandbits(32)
    print("extract number = "+ str(extract_number(number)))
    guess = int(str(input("Guess be extracted number:")))
    if guess != number:
        print("Wrong Number! Guess again.")
        exit(0)
    

print("Welcome to the Mersenne Twister basic challenge. Please try to solve 20 challenges in 60 seconds.")
signal.alarm(60)

for i in range(20):
    print("Round: "+str(i+1))
    random.choice([guess_number_1,guess_number_2,guess_number_3,guess_number_4])()
    print("Good job!")

flag = open('/flag').read()
print("Congratulations on passing the challenge. This is your flag: " + str(flag))

需要解决四个跟MT19937随机数有关的问题。问题1是前向预测，问题2是后向预测，这两个直接调库就能解。问题3需要还原初始化种子，我们可以很轻松地写出逆过程。问题4是提取算法，对应库里面的temper方法，直接把面的untemper拿过来解即可。

解题脚本：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
from pwn import *
from Crypto.Util.number import *
from extend_mt19937_predictor import ExtendMT19937Predictor

context.log_level = 'debug'

sh=remote('node2.yuzhian.com.cn',32881)
#sh=process(['python3','task.py'])
l64 = lambda      :u64(sh.recvuntil("\x7f")[-6:].ljust(8,"\x00"))
l32 = lambda      :u32(sh.recvuntil("\xf7")[-4:].ljust(4,"\x00"))
sla = lambda a,b  :sh.sendlineafter(str(a),str(b))
sa  = lambda a,b  :sh.sendafter(str(a),str(b))
lg  = lambda name,data : sh.success(name + ": 0x%x" % data)
se  = lambda payload: sh.send(payload)
rl  = lambda      : sh.recvline()
rv  = lambda n    : sh.recv(n)
sl  = lambda payload: sh.sendline(payload)
ru  = lambda a     :sh.recvuntil(str(a))
rud = lambda a     :sh.recvuntil(str(a),drop=True)

def solve1(rands):
	pre = ExtendMT19937Predictor()
	for num in rands:
		pre.setrandbits(num,96)
	guess=pre.predict_getrandbits(96)
	sla('Guess after number:',str(guess))

def solve2(rands):
	pre = ExtendMT19937Predictor()
	for num in rands:
		pre.setrandbits(num,32)
	for _ in rands:
		pre.backtrack_getrandbits(32)
	guess=pre.backtrack_getrandbits(96)
	sla('Guess pre number:',str(guess))

def solve3(num):
	mod=2**32
	inv=inverse(1812433253,mod)
	mt=num
	for i in range(623,0,-1):
		mt=((mt-i)*inv)%mod
		mt=mt^mt>>30
	sla('Guess seed number:',str(mt))


def solve4(num):
	def untemper(y):
		y ^= (y >> 18)
		y ^= (y << 15) & 0xefc60000
		y ^= ((y << 7) & 0x9d2c5680) ^ ((y << 14) & 0x94284000) ^ ((y << 21) & 0x14200000) ^ ((y << 28) & 0x10000000)
		y ^= (y >> 11) ^ (y >> 22)
		return y
	sla('Guess be extracted number:',str(untemper(num)))

rl()
for _ in range(20):
	rl()
	line=rl().decode().strip()
	#print(line)
	if '[' in line:
		rands=eval(line.split('randoms = ')[-1].replace('L',''))
		if len(rands)==208:
			solve1(rands)
		elif len(rands)==627:
			solve2(rands)
		else:
			print('error!')
			exit(0)
	elif 'last' in line:
		number=int(line.split('last number = ')[-1].replace('L',''))
		solve3(number)
	elif 'extract' in line:
		number=int(line.split('extract number = ')[-1].replace('L',''))
		solve4(number)
	else:
		print('error!')
		exit(0)
	rl()

sh.interactive()
#NKCTF{29a35b27-b745-4a57-bb5c-b7d67553bf2e}

eZ_Bl⊕ck

题目源码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
from Crypto.Util.strxor import strxor as xor
import os
from secret import flag

def round(s, k):
    l, r = s[:16], s[16:]
    l_, r_ = xor(xor(r, k), l), l
    return l_ + r_

def encode(s, k):
    t = s
    for i in range(8):
        t = round(t, k[i])
    return t

r = os.urandom(32)
print(r)

key = [os.urandom(16) for _ in range(8)]

print(encode(r, key))
m = flag.strip(b'NKCTF{').strip(b'}').replace(b'-',b'')
print(encode(m, key))

定义了一个类似于Feistel结构的轮加密，但里面只涉及到异或运算。通过简单分析可以推出，第轮加密后满足，。其中，是若干轮密钥的异或。而题目提供了一对已知明文和密文，因此可以直接算出第8轮时的，。然后反解flag密文即可。

解题代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
from Crypto.Util.strxor import strxor as xor

test=b"t\xf7\xaa\xac\x9d\x88\xa4\x8b\x1f+pA\x84\xacHg'\x07{\xcc\x06\xc4i\xdd)\xda\xc9\xad\xa9\xe8\x1fi"
enc_test=b"'{<z}\x91\xda\xc5\xd5S\x8b\xfa\x9f~]J\x0f\xf4\x9a\x1e\xe0\xef\x129N\xe7a\x928+\xe0\xee"
enc_flag=b'8\x1f"\x83B4\x86)\xce\xebq3\x06\xa0w\x16U\x04M/w\xa1\x8f;)M\xdd~\x11:\xe3\xb3'

l0,r0=test[:16],test[16:]
l8,r8=enc_test[:16],enc_test[16:]
K1=xor(l8,r0)
K2=xor(r8,xor(l0,r0))

flag2=xor(enc_flag[:16],K1)
flag1=xor(xor(enc_flag[16:],K2),flag2)
print(flag1+flag2)
#b'1ccd5ceec96d4caf8ce59a512b3d0655'
#NKCTF{1ccd5cee-c96d-4caf-8ce5-9a512b3d0655}

easy_high

题目源码：

1
2
3
4
5
6
7
8
9
10
11
from Crypto.Util.number import *
flag = ''

p, q = getPrime(1024), getPrime(1024)
N = p * q
p0 = p ^ (bytes_to_long(flag)<<444)
m = bytes_to_long(flag)
c = pow(m, 65537, N)
print('c=',c)
print('N=',N)
print('p0=',p0)

p0相当于给出了p的低444位。但是根据相关的攻击理论，p位数泄露需要达到至少一半左右才能用coppersmith攻击。

我们可以猜测flag不超过60字节，即480位，这样的话p0还会泄露出一部分的高位。两者综合起来可以满足coppersmith的要求。因此，只需要爆破猜测flag长度即可。

解题代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
from Crypto.Util.number import *

c= 4881545863615247924697512170011400857004555681758106351259776881249360423774694437921554056529064037535796844084045263140567168171628832384672612945806728465127954937293787045302307135365408938448006548465000663247116917564500525499976139556325841597810084111303039525833367199565266613007333465332710833102978756654324956219855687611590278570749890543277201538208370370097424105751568285050703167350889953331829275262932104042040526209179357770495596739361176548337593674366015027648541293309465113202672923556991818236011769228078267484362980348613669012975963468592763463397575879215173972436831753615524193609612
N= 17192509201635459965397076685948071839556595198733884616568925970608227408244870123644193452116734188924766414178232653941867668088060274364830452998991993756231372252367134508712447410029668020439498980619263308413952840568602285764163331028384281840387206878673090608323292785024372223569438874557728414737773416206032540038861064700108597448191546413236875600906013508022023794395360001242071569785940215873854748631691555516626235191098174739613181230094797844414203694879874212340812119576042962565179579136753839946922829803044355134086779223242080575811804564731938746051591474236147749401914216734714709281349
p0= 149263925308155304734002881595820602641174737629551638146384199378753884153459661375931646716325020758837194837271581361322079811468970876532640273110966545339040194118880506352109559900553776706613338890047890747811129988585025948270181264314668772556874718178868209009192010129918138140332707080927643141811

plow=p0&(2^444-1)
for flaglen in range(20,60):
	phigh=p0>>(444+8*flaglen)
	R.<x>=PolynomialRing(Zmod(N))
	f=phigh*2^(444+8*flaglen)+x*2^444+plow
	res=f.monic().small_roots(X=2^(8*flaglen),beta=0.4)
	if len(res)>0:
		p=phigh*2^(444+8*flaglen)+res[0]*2^444+plow
		p=int(p)
		if N%p==0:
			q=N//p
			d=inverse(65537,(p-1)*(q-1))
			m=pow(c,d,N)
			print(long_to_bytes(m))
			exit(0)

#b'NKCTF{F10wrs_hVe_r3strDay}'

Raven

题目源码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#!/usr/bin/env sage
# Problem by rec, with a bad raven.
import os, hashlib
from Crypto.Util.number import *
from Crypto.Cipher import AES

def Raven(n: int, secret: bytes):
    H = lambda x: hashlib.md5(os.urandom(8) + x).digest()

    p = getPrime(728)
    R.<z> = PolynomialRing(GF(p))

    seed = H(secret)
    f = R(
        [bytes_to_long(secret)] + [bytes_to_long(H(seed)) for _ in range(n - 1)]
    )
    x = [getRandomRange(2, p - 1) for _ in range(n)]
    y = [ZZ(f(xi)^2 + getPrime(256)) for xi in x]

    pairs = list(zip(x, y))
    return p, pairs

flag = b'#####'
key = os.urandom(16)
cipher = AES.new(key=key, IV=bytes(range(16)), mode=AES.MODE_CBC)
ct = cipher.encrypt(flag + os.urandom(16 - len(flag) % 16))
p, pairs = Raven(4, key)

print(f"{p = }\n{pairs = }\n{ct = }")

定义了一个多项式, 其中是要求的值。给了四组数据, 其中为小噪声。这里我们先把展开： 可以观察到系数和噪声均为256位左右，而p为728位，那么应该是用格来解了。根据以上关系，可以构造出格：

利用LLL能够规约出一个短向量。尽管常数项系数有噪声误差，但可以通过其它项系数算出来。

最后AES解密即可。

解题代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
p = 1018551160851728231474335384388576586031917743463656622083024684199383855595168341728561337234276243780407755294430553694832049089534855113774546001494743212076463713621965520780122783825100696968959866614846174188401153
pairs = [(615358616404864757405587650175842125441380884418119777842292095751090237848084440177153221092040264723889917863863854377665802549748720692225139890884830475485512763149974948701807492663962748292710803434009673589337265, 84982753624462868217739962129526665082932464631118597651920986288766037499319751354013335054886685186857222944776560264528363811382359242656883760986496856164448940929282013856762706210675691655747370624405968909408102), (528363810186974800127873139379943131424126521611531830591311656948009967709310974894584084912262479395720199930206495204352231804549705720854271566421006481173043064265399467682307971910488405265826107365679757755866812, 496810092723839642457928776423789418365006215801711874210443222720529161066621876103037104247173440072986344011599384793861949574577559989016501090247331146721371126871470611440468688947950954988175225633457347666551944), (68711183101845981499596464753252121346970486988311398916877579778110690480447199642602267233989256728822535174215153145632158860662954277116345331672194812126361911061449082917955000137698138358926301360506687271134873, 995428771589393162202488762223106955302099250561593105620410424291405842350539887383005328242236156038373244928147473800972534658018117705291472213770335998508454938607290279268848513727721410314612261163489156360908800), (61574167546312883246262193556029081771904529137922128124933785599227801608271357738142074310192454183183340219301304405636497744152219785042075198056952749425345561162612590170550454476602892138914473795478531165181812, 618169326093802548516842299173393893046765466917311052414967158839652012130855552015876657514610755108820971877570295328618373296493668146691687291894702228119875561585283226588768969944781923428807766632578060221034862)]
ct = b"|2\xf0v7\x05Y\x89\r]\xe93s\rr)#3\xe9\x90%Z\x9a\xd9\x9ck\xba\xec]q\xb8\xf2'\xc8e~fL\xcf\x93\x00\xd6^s-\xc9\xd6M"

from Crypto.Util.number import *
from Crypto.Cipher import AES
from gmpy2 import iroot

Fp=GF(p)
mat=Matrix(ZZ,12,12)

for i in range(8):
	mat[i,i]=1
for i in range(4):
	mat[i+8,i+8]=p

for i in range(4):
	x,y=pairs[i]
	for j in range(7):
		mat[j,i+8]=ZZ(Fp(x)^j)
	mat[7,i+8]=-y

ml=mat.LLL()
res=[ -x for x in ml[1]]
#print(res)
c=int(iroot(int(res[6]),2)[0])
b=res[5]//(2*c)
a=(res[4]-b*b)//(2*c)
s=res[1]//(2*a)
key=long_to_bytes(int(s))
cipher = AES.new(key=key, IV=bytes(range(16)), mode=AES.MODE_CBC)
flag=cipher.decrypt(ct)
print(flag)
#b'Message from raven: nkctf{..escape..} \xc2\x01\x80\xd5\x07\x10\x89\xc7\x81m'

ez_LargeCG

题目源码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
from gmpy2 import next_prime
from Crypto.Util.number import getPrime, isPrime, bytes_to_long
import random
from secret import flag

def init():
    primes = []
    p = 1
    while len(primes) < 100:
        p = next_prime(p)
        primes.append(int(p))
    return primes

def genMyPrimeA(bits):
    while True:
        g = 2
        while g < 2 ** bits:
            g *= random.choice(primes)
        g += 1
        if isPrime(g):
            return g

def genMyPrimeB(bits):
    while True:
        g = 2
        while g < 2 ** bits:
            g *= random.choice(primes)
        g -= 1
        if isPrime(g):
            return g

def gen(st, n, a, b, c, d):
    A = [st + 2023, st + 2024, st + 2025]
    for i in range(6**666):
        A.append((a * A[-3] + b * A[-2] + c * A[-1] + d) % n)
    return A

primes = init()
p1 = getPrime(256)
print(p1)
q1 = 1
while p1 > q1:
    q1 = genMyPrimeA(256)
print(q1)
p2 = getPrime(256)
q2 = 1
while p2 > q2:
    q2 = genMyPrimeB(256)
n1 = p1 * q1
n2 = p2 * q2
print(f'n1 = {n1}')
print(f'n2 = {n2}')

r = getPrime(512)
print(f'r = {r}')

A = gen(bytes_to_long(flag), r, p1, q1, p2, q2)
print(f'A[-3] = {A[-3]}')
print(f'A[-2] = {A[-2]}')
print(f'A[-1] = {A[-1]}')

可以发现光滑，光滑，因此可以用相应方法分解。然后gen里面6**666太大，需要转化为矩阵幂进行求解，即： 解题代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
from Crypto.Util.number import *

'''
python3 -m primefac -vs -m=p-1 39755206609675677517559022219519767646524455449142889144073217274247893104711318356648198334858966762944109142752432641040037415587397244438634301062818169
Z155  =  P77 x P78  =  92946439027877993602295703905130336736159270745389239059083263513478865293549 x 427721675251610827084310512123962488210068003845592404231631542730839819224381

python3 -m primefac -vs -m=p+1 30725253491966558227957591684441310073288683324213439179377278006583428660031769862224980605664642101191616868994066039054762100886678504154619135365646221
Z155  =  P78 x P78  =  106481130516780473105954611077340189174861459077145246394800660809527032990637 x 288551157776490110472645044398395422160196115791981535735903775378294599329633
'''
n1 = 39755206609675677517559022219519767646524455449142889144073217274247893104711318356648198334858966762944109142752432641040037415587397244438634301062818169
n2 = 30725253491966558227957591684441310073288683324213439179377278006583428660031769862224980605664642101191616868994066039054762100886678504154619135365646221
r = 7948275435515074902473978567170931671982245044864706132834233483354166398627204583162848756424199888842910697874390403881343013872330344844971750121043493
A_3 = 6085327340671394838391386566774092636784105046872311226269065664501131836034666722102264842236327898770287752026397099940098916322051606027565395747098434
A_2 = 1385551782355619987198268805270109182589006873371541520953112424858566073422289235930944613836387546298080386848159955053303343649615385527645536504580787
A_1 = 2529291156468264643335767070801583140819639532551726975314270127875306069067016825677707064451364791677536138503947465612206191051563106705150921639560469

p1=92946439027877993602295703905130336736159270745389239059083263513478865293549
q1=427721675251610827084310512123962488210068003845592404231631542730839819224381
p2=106481130516780473105954611077340189174861459077145246394800660809527032990637
q2=288551157776490110472645044398395422160196115791981535735903775378294599329633

a,b,c,d=p1,q1,p2,q2
mat=[[0,0,a,0],[1,0,b,0],[0,1,c,0],[0,0,1,1]]
mat=Matrix(Zmod(r),mat)
M=mat^(6**666)
v=vector(Zmod(r),[A_3,A_2,A_1,d])
res=v*M^-1
assert res[0]+1==res[1]
flag=long_to_bytes(int(res[0]-2023))
print(flag)
b'NKCTF{y0u_kN0w_r5A_&_LCg_&_Ma7r1X_s0_w3ll!!!}'

baby_classical

题目源码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
import string
import re
import numpy as np
flag = ''
print('flag length:',len(flag))
dic = string.ascii_uppercase+string.ascii_lowercase+string.digits+'+/'
f1nd = lambda x : dic.find(x)
class KeyEncryption:
    def __init__(self, m: int, fillchar: str="z", key: np.ndarray=None):
        self.m = m
        self.key = key
        self.dicn2s = {i: dic[i] for i in range(64)}
        self.dics2n = dict(zip(self.dicn2s.values(), self.dicn2s.keys()))
        self.fillchar = self.dics2n[fillchar]
    def setM(self, m: int) -> None:
        assert m > 0
        self.m = m
    def setKey(self, key: np.ndarray=None) -> None:
        if key is None:
            while key is None or KeyEncryption.modInv(np.linalg.det(key)) == -1:
                key = np.random.randint(0, 65, size=(self.m, self.m))
            print("random matrix：\n", key)
        else:
            assert KeyEncryption.modInv(np.linalg.det(key)) != -1
        self.key = key
    @staticmethod
    def modInv(x: int):
        y = 0
        while y < 64:
            y += 1
            if (x * y) % 64 == 1:
                return y
        return -1
    def _loopCrypt(self, long: np.ndarray, K: np.ndarray) -> np.ndarray:
        ans = np.array([])
        for i in range(long.shape[0] // self.m):
            ans = np.mod(np.hstack((
                ans, 
                np.dot(long[i*self.m:i*self.m+self.m], K)
            )), 64)
        return ans.astype(np.int64)
    def encrypt(self, plaintext: np.ndarray):
        assert self.m !=None and self.key is not None
        if plaintext.shape[0] % self.m:
            plaintext = np.hstack((
                plaintext, 
                [self.fillchar] *(self.m - plaintext.shape[0] % self.m)
            ))
        return self._loopCrypt(plaintext, self.key)
    def translate(self, s, to: str):
        if to == "text":
            return "".join([self.dicn2s[si] for si in s])
        elif to == "num":
            s = s.replace(" ", "")
            return np.array([self.dics2n[si] for si in s])
def getKey(key):
  he = KeyEncryption(m=3)
  he.setKey()              
  nums = he.translate(key, "num")
  res = he.encrypt(nums)
  enkey = ''.join(dic[i] for i in res.tolist())
  print('Encrypt key:',enkey)
  return enkey
if __name__ == '__main__':
  fir1 = ' '.join(map(lambda _:_[::-1],re.split("[ { _ } ]" , flag.swapcase())))
  ciphertext1 = ''
  key = ""  
  enkey = getKey(key)
  _enkey=[f1nd(i) for i in key]
  print('key lengeh:',len(_enkey))
  j = 0
  for i in fir1:
    if f1nd(i)>=0:
      ciphertext1 += dic[(f1nd(i) + _enkey[j % len(_enkey)])%64]
    else:
      ciphertext1 += i
    j += 1
  ciphertext = ciphertext1.replace(' ','_')
  print('ciphertext:%s{%s}' % (ciphertext[0:5],ciphertext[6:-1]))

分析源码可以知道主要是对flag做了一个类似于维吉尼亚的移位，然而不知道key。需要先根据encrypt key来求出key。而在_loopCrypt里，把key的每一个子块与一个3*3的矩阵进行了相乘来返回对应的密文。而这个矩阵是已知的，那么解密直接乘上逆矩阵就好了。求出key之后，把flag密文移位回来，并做一些形式的变换即可。

解题代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
import string
import re
import numpy as np

dic = string.ascii_uppercase+string.ascii_lowercase+string.digits+'+/'
f1nd = lambda x : dic.find(x)

n=64
m=3
Zn=Zmod(n)
mat=Matrix(Zn,[[13,37,10],
 [15,17,41],
 [13,0,10]])
enc_key='pVvRe/G08rLhfwa'
ct='1k2Pe{24seBl4_a6Ot_fp7O1_eHk_Plg3EF_g/JtIonut4/}'

enc_key_block=[ enc_key[m*i:m*(i+1)] for i in range(len(enc_key)//m)]
key=''
for block in enc_key_block:
	enc_num=vector(Zn,[f1nd(x) for x in block])
	m_num=enc_num*mat^-1
	key+=''.join([ dic[m] for m in m_num])
print(key)
#W3ar3N0wayBackz
key=key[:14]
_enkey=[f1nd(i) for i in key]

tmp=''
for i,c in enumerate(ct):
	if c in dic:
		tmp+=dic[(f1nd(c)-_enkey[i%len(_enkey)])%64]
	else:
		tmp+=c
print(tmp)
flag=' '.join(map(lambda _:_[::-1],re.split("[ { _ } ]" , tmp.swapcase())))
flag=flag.replace(' ','_')
flag='%s{%s}'%(flag[:5],flag[6:-1])
print(flag)
#NKCTF{ClaSsic_c0de_d0l1s_aRe_r3a1ly_int3reSting}

complex_matrix

题目源码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
from Crypto.Util.number import *
import gmpy2 as gy
flag = ''

k = 400
p, q = getPrime(741), getPrime(741)
N = p * q
phi = (p-1) * (q-1)
_flag = bytes_to_long(flag)
p, q = getPrime(1024), getPrime(1024)
d_array = [getPrime(k) for _ in range(4)] 
e_array = [inverse(i, phi) for i in d_array]
c = pow(_flag, 65537, N)
print('N:',N)
print('e:',e_array)
print('c:',c)
#N: 71841248095369087024928175623295380241516644434969868335504061065977014103487197287619667598363486210886674500469383623511906399909335989202774281795855975972913438448899231650449810696539722877903606541112937729384851506921675290984316325565141178015123381439392534417225128922398194700511937668809140024838070124095703585627058463137549632965723304713166804084673075651182998654091113119667582720831809458721072371364839503563819080226784026253
#e: [65128799196671634905309494529154568614228788035735808211836905142007976099865571126946706559109393187772126407982007858423859147772762638898854472065889939549916077695303157760259717113616428849798058080633047516455513870697383339784816006154279428812359241282979297285283850338964993773227397528608557211742425548651971558377656644211835094019462699301650412862894391885325969143805924684662849869947172175608502179438901337558870349697233790535, 58756559706647121529575085912021603170286163639572075337348109911506627489265537716060463072086480156516641723700802217411122982693536541892986623158818442274840863016647800896033363360822503445344748132842451806511693779600370832206455202293028402486647422212959763287987847280322100701242139127654031151565924132562837893975505159702015125483479126108892709063135006366792197127007229210558758401679638300464111782814561428899998471531067163715, 34828685390969672139784723764579499920301439564705391196519314224159563070870933754477650614819514127121146216049444888554338415587165719098661141454627820126445291802801256297252654045398330613075575527685542980264993711077876535643646746742646371967302159565887123638001580042027272379341650995728849759541960087953160211696369079708787543303742132161742979856720539914370868829868891655221361545648778590685232034703220732697083024449894197969, 26717968456600556973167180286909817773394160817933525240720067057464671317174201540556176814203780603153696663101158205367554829261808020426363683474848952397963507069306452835776851274959389849223566030857588019845781623271395012194869024566879791449466064832273531795430185178486425688475688634844530106740480643866537205900809400383304665727460014210405339697947582657505028211149470787536144302545259243549176816653560626044921521516818788487]
#c: 39297018404565022956251803918747154798377576057123078716166221329195959669756819453426741569480551313085435037629493881038383709458043802420338889323233368852331387845200216275712388921820794980987541224782392553528127093154957890356084331463340193478391679540506421250562554424770350351514435220782124981277580072039637811543914983033300225131364246910828188727043248991987332274929827173923543187017105236008487756190002204169623313222748976369

尝试了一下单组数据使用boneh durfee attack,发现行不通。然后发现是muti public exponent with small private exponent and common modulus，针对该问题的攻击由Aono提出，paper在此。

crypto-attacks仓库已经集成了有该攻击的实现，就拿过来改改用用咯。

这题代码就不贴了，大家自行摸索吧。

1
b'NKCTF{F10w3r_Hav3_r3start_Day_N0_Man_iS_Y0ung_Aga1n}'

NKCTF Crypto wp

https://litao6666.github.io/202303/acd9a838.html

Author

zealot

Posted on

2023-03-27

Updated on

2023-03-27

Licensed under

Catalogue

×