记录一下以前的一些比赛，这里感谢striving大佬，好多都是问的他哈哈哈哈。

杭师大

一步到喂

佩尔方程求解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
from gmpy2 import invert

def solve_pell(N):
    cf = continued_fraction(sqrt(N))
    for i in range(10000):
        denom = cf.denominator(i)
        numer = cf.numerator(i)
        if numer*numer - N * denom*denom == 1 :
            return numer, denom
    return None, None
d=105279230912868770223946474836383391725923
a=1293023064232431070902426583269468463
x,y=solve_pell(d//a)
print(x)
print(y)
assert 1293023064232431070902426583269468463*pow(x,2)==105279230912868770223946474836383391725923*pow(y,2)+1293023064232431070902426583269468463
p=9850212100620338486478343799784951721581757936621772924971218807300819701941457605399099898870264241518769370682330612103782092302148525012450902351701339
q=10749429992014823019923966246896511618886613763258781706004694804949547801668777655988055847885755337127548775758133804022361510427909703124161450470578543
c=66847321508502017574023222490247591875197038421108556106531660421662626233521063441647157067220450229816184622038471812597874582613385516838920632450015292570673816423432903604941781889308906893966588610214614726388822851471695742453496232748358301888465563812947038856742838097152549971517159475947566599664
phi=(p-1)*(q-1)
d=invert(x,phi)
print(pow(c,d,p*q))
#HZNUCTF{D0_y0u_know_p3ll_3qu4tion!!!}

checkin

连续24000次开方

quadratic_residue和cipolla

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
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
import tqdm
from Crypto.Util.number import *
from sympy.ntheory.modular import crt

def square_root_of_quadratic_residue(n, modulo):
    """Square root of quadratic residue

    Solve the square root of quadratic residue using Cipolla's algorithm with Legendre symbol
    Returns:
        int -- if n is a quadratic residue,
                   return x, such that x^{2} = n (mod modulo)
               otherwise, return -1
    """
    if modulo == 2:
        return 1
    if n % modulo == 0:
        return 0
    Legendre = lambda n: pow(n, modulo - 1 >> 1, modulo)
    if Legendre(n) == modulo - 1:
        return -1
    t = 0
    while Legendre(t ** 2 - n) != modulo - 1:
        t += 1
    w = (t ** 2 - n) % modulo
    return (generate_quadratic_field(w, modulo)(t, 1) ** (modulo + 1 >> 1)).x

def generate_quadratic_field(d, modulo=0):
    """Generate quadratic field number class

    Returns:
        class -- quadratic field number class
    """
    assert (isinstance(modulo, int) and modulo >= 0)

    class QuadraticFieldNumber:
        def __init__(self, x, y):
            self.x = x % modulo
            self.y = y % modulo

        def __mul__(self, another):
            x = self.x * another.x + d * self.y * another.y
            y = self.x * another.y + self.y * another.x
            return self.__class__(x, y)

        def __pow__(self, exponent):
            result = self.__class__(1, 0)
            if exponent:
                temporary = self.__class__(self.x, self.y)
                while exponent:
                    if exponent & 1:
                        result *= temporary
                    temporary *= temporary
                    exponent >>= 1
            return result

        def __str__(self):
            return '({}, {} \\sqrt({}))'.format(self.x, self.y, d)

    return QuadraticFieldNumber

n = 22114546923564420607945063747927422619774890007937503484905798897563036431278699718161460968350749338680452479484253816646632515078192048118109272532310403715802657061990320170724360874028667484527150185159662403573637809180151665727445208585725264186578429094937215068881079399747998551453944363665401263
c = 7274219309267176700435453490636404568410293850833252412471984274955007037941820465929958008672185817002749418809077052781794306899476543760452010370102811167685901654480233874375880047900499814304539829706786470978714629827690730256369200773772396109793338097451559255985268375731804819829315168807228186
h = 1463929459818798711929811606552273520156490689917243949474579232718301828387871678397965433435537694532920957475947201372279363554005600100100224291888130
hint = 5610276127312766429915480651516095336201056367031530733662980757514427535721885723009367286870294772595629284861923351543396909892645845139050780691701736
# b'HZNUCTF{80f937af-6542-4142-b957-09534839da4d}'

e = 1 << 24_000
q = hint // 2024 + 2022
p = n // q
res1 = [c]
total = []
for _ in tqdm.tqdm(range(24_000)):
    tmp, res1 = res1, []
    for ct in tmp:
        mm = square_root_of_quadratic_residue(ct, p)
        if mm not in total:
            total.append(mm)
        else:
            continue
        if p - mm not in total:
            total.append(p - mm)
        else:
            continue
        if mm == 1 or mm == p - 1 or mm == -1:
            continue
        res1 += [mm, p - mm]
    res1 = list(set(res1))
res1 = res1[-2:]

res2 = c
for i in tqdm.tqdm(range(24000)):
    res2 = pow(res2, (q + 1) // 4, q)
res2 = [res2, p - res2]

for i in res1:
    for j in res2:
        m = crt([p, q], [i, j])[0]
        m = long_to_bytes(int(m))
        if b'HZNUCTF' in m:
            print(m)
            break
# b'HZNUCTF{80f937af-6542-4142-b957-09534839da4d}\x97\x86w@b\x1e\xa36\xc7\xe4H5g5\x13\xca\x0f,<\xa6\xb5\x16\x9ey\x92$\xd9\xd6\xa2~\x9f\xdagO\xbd\\3\x14\xfc\x05\xb8\x1f\r\xae2S\x1eA\x90\xaf'

nothing

sm2签名

hnp问题

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
from string import *
from hashlib import *
from gmssl import sm2
alp=ascii_letters+digits
print(alp)
def proof_of_work(end,sha):
    for a in alp:
        for b in alp:
            for c in alp:
                for d in alp:
                    start=a+b+c+d
                    s=(start+end).encode()
                    Sha=sha256(s).hexdigest()
                    if Sha==sha:
                        return start
from pwn import *

io=remote('43.156.230.30',10001)
context.log_level='debug'
io.recvuntil('sha256(XXXX+')
end=io.recvuntil(') == ')[:-5].decode()
print(end)
sha=io.recvuntil('\n')[:-1].decode()
print(sha)
xxxx=proof_of_work(end,sha)
io.recvuntil('[+] Plz tell me XXXX: ')
io.sendline(xxxx)
io.recvuntil('ready?[y/n]\n[*] ')
io.sendline('y')
R=[]
S=[]
n=0xFFFFFFFEFFFFFFFFFFFFFFFFFFFFFFFF7203DF6B21C6052B53BBF40939D54123
for _ in range(55):
    io.sendline('1')
    io.recvuntil('[+] U can get my signature\n')
    io.recvuntil('[+] ')
    rs=io.recvuntil('\n')[:-1].decode().zfill(128)
    r,s=int(rs[:64],16),int(rs[64:],16)
    R.append(r)
    S.append(s)  #ri,si
    #s(1+d)=k-r*d mod n
    #s+(s+r)*d=k mod n
    
M=Matrix(55+2,55+2)
M=Matrix(QQ,M)
for i in range(55):
    M[i,i]=n
    M[-2,i]=S[i]+R[i]
    M[-1,i]=S[i]
M[-2,-2]=2**245/n
M[-1,-1]=2**245
v=M.LLL()[1]
sk=int(v[-2]*n/(2**245))
sk=n-sk  #sk  #格子

sm2_easy = sm2.CryptSM2('1', '1')  #sm2
pk = sm2_easy._kg(sk, sm2_easy.ecc_table['g']) #
io.sendline('3')
io.recvuntil('I will give you the flag you want!(hexadecimal format)\n[*] ')
print(pk)
io.sendline(hex(sk))
io.recvall()

NKCTF招新赛

baby_RSA

考点：

  1. 已知e,dp,ne,dp,n分解nn
  2. 费马小定理，数论推导
  3. coppersmith攻击

第一步：已知dp=dmod  (p−1)d_p=d \mod {(p-1)}，所以e∗dp=e∗dmod  (p−1)e*d_p=e*d \mod {(p-1)}。

根据RSA参数之间的关系有：e∗d=1mod  (p−1)∗(q−1)e*d=1\mod{(p-1)*(q-1)}，那么e∗d=1mod  p−1e*d=1\mod{p-1}。

所以e∗dp=1mod  p−1e*d_p=1\mod{p-1}，即存在kk使得e∗dp−1=k∗(p−1)e*d_p-1=k*(p-1)，注意到dp<p−1d_p<p-1，那么k<ek<e。

那么通过枚举kk可以得到p=1+(e∗dp−1)//kp=1+(e*d_p-1)//k。

第二步：有c1=mpmod  n,c2=mqmod  nc_1=m^p\mod{n},c_2=m^q\mod{n}

根据同余以及费马小定理(ap−1=1mod  p)(a^{p-1}=1\mod{p})，有：c1=mmod  p,c2=mmod  qc_1=m\mod{p},c_2=m\mod{q}。

构造多项式：有f(m)=m2−(c1+c2)∗m+c1∗c2mod  nf(m)=m^2-(c_1+c_2)*m+c_1*c_2\mod{n}

第三步：coppersmith攻击可以帮助求解f(x0)=y0mod  Nf(x_0)=y_0\mod{N},其中x0<Xx_0<X，XX是一个上界。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
n =  114101396033690088275999670914803472451228154227614098210572767821433470213124900655723605426526569384342101959232900145334500170690603208327913698128445002527020347955300595384752458477749198178791196660625870659540794807018881780680683388008090434114437818447523471527878292741702348454486217652394664664641
N =  1159977299277711167607914893426674454199208605107323826176606074354449015203832606569051328721360397610665453513201486235549374869954501563523028914285006850687275382822302821825953121223999268058107278346499657597050468069712686559045712946025472616754027552629008516489090871415609098178522863027127254404804829735621706042266140637592206366042515190385496909533329383212542170504864473944657824502882014292528444918055958758310544435120502872883857209880723535754528096143707324179005292445100655695427777453144657819474805882956064292780031599790769618615908501966912635232746588639924772530057835864082951499028
dP =  33967356791272818610254738927769774016289590226681637441101504040121743937150259930712897925893431093938385216227201268238374281750681609796883676743311872905933219290266120756315613501614208779063819499785817502677885240656957036398336462000771885589364702443157120609506628895933862241269347200444629283263
from gmpy2 import *
e=65537
#已知e,dp,n分解n
#dp =d mod p-1
#e*dp =1 +k*(p-1)
for i in range(1,e):
    if (e*dP-1)%i==0:
        P=1+ (e*dP-1)//i
        if N%P==0:
            print(P)
'''
P=37269067352457630263351774206178494913957088859822110344334922741582406663357663275001777826744534556652993452577088773275825539553907027527722045884489297259984687894496505265384077983882580247333972954704644517469999916574893996324149548980338301147983367163067556434434982470623587914250041142380667816331
assert N%P==0
Q=N//P
R.<x>=Zmod(n)[]
f=x^2-(P+Q)*x+P*Q
flag=f.small_roots(X=2^300)
print(flag)
'''
#NKCTF{Th1S_a_babyRSA_y0u_are_tql!!!}

eZ_Math

考点：

  1. 数论推导，欧拉定理，rsa参数之间的关系等

题目给了很多aiximod  n=ci{a_i}^{x_i}\mod{n}={c_i}

注意到ai,cia_i,c_i都很小，而且有的aia_i是幂指关系：如4=22,8=234=2^2,8=2^3,在不同的底数下，也存在相同的cic_i。

我们可以找到其中一组幂指关系的：a1,a2=a1ba_1,a_2={a_1}^b，并且cic_i相同的。

那么此时a1x1=c1mod  na_1^{x_1}=c_1\mod{n}，a2x2=a1b∗x2=c1mod  n{a_2}^{x_2}={a_1}^{b*x_2}=c_1\mod{n}

显然此时有：x1=b∗x2mod  phix_1=b*x_2\mod{phi}，（欧拉定理、或该循环群的阶为phi)

此时可以得到phi的一个倍数kphi=x1−b∗x2kphi=x_1-b*x_2

得到d=e−1mod  kphid=e^{-1}\mod{kphi} (用phi的倍数求私钥与phi等价，可由欧拉定理得)

然后解rsa即可。

1
2
3
4
5
6
7
8
9
10
a1=21606807968454766520529084107175158062623274703294799705984925156349373997035743632649715867216648159433730630939058861636582120303338699113498645592338621228070481894445156769437351313971471061779425442129487317917630554305634797690296919992201174927956121524640438775183413288101169580705360562693274958339417
b1=68789042322037899901399142739922213531190892214327212247633649397602243027562329029767224931385807659445647908974735092145336602662873465734923450809783198772444106655438821950560058413359621316189435942839212247873870560114926459781136160541556773230183543715576244986800296759341282346581691226676298068904581
n = 369520637995317866367336688225182965061898803879373674073832046072914710171302486913303917853881549637806426191970292829598855375370563396182543413674021955181862907847280705741114636854238746612618069619482248639049407507041667720977392421249242597197448360531895206645794505182208390084734779667749657408715621
c = 324131338592233305486487416176106472248153652884280898177125443926549710357763331715045582842045967830200123100144721322509500306940560917086108978796500145618443920020112366546853892387011738997522207752873944151628204886591075864677988865335625452099668804529484866900390927644093597772065285222172136374562043
from gmpy2 import *
phi=a1-3*b1
e=65537
d=invert(e,phi)
from Crypto.Util.number import *
print(long_to_bytes(pow(c,d,n)))

fake_MT、real_MT

考点：

  1. MT19937的预测、逆向，部件的逆向
  2. pwntools自动化脚本

1.可以参考https://www.anquanke.com/post/id/205861?display=mobile学习，很经典！很有意思

2.pwntools基本用法：接发数据等等

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
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
from randcrack import *
from gmpy2 import invert
from random import Random


# right shift inverse
def inverse_right(res, shift):
    tmp = res
    bits = len(bin(res)[2:])
    for i in range(bits // shift):
        tmp = res ^ tmp >> shift
    return tmp


# right shift with mask inverse
def inverse_right_values(res, shift, mask):
    tmp = res
    bits = len(bin(res)[2:])
    for i in range(bits // shift):
        tmp = res ^ tmp >> shift & mask
    return tmp


# left shift inverse
def inverse_left(res, shift):
    tmp = res
    bits = len(bin(res)[2:])
    for i in range(bits // shift):
        tmp = res ^ tmp << shift
    return tmp


# left shift with mask inverse
def inverse_left_values(res, shift, mask):
    tmp = res
    bits = len(bin(res)[2:])
    for i in range(bits // shift):
        tmp = res ^ tmp << shift & mask
    return tmp

#extract_recover
def extract_recover(y):
    y = inverse_right(y, 18)
    y = inverse_left_values(y, 15, 4022730752)
    y = inverse_left_values(y, 7, 2636928640)
    y = inverse_right(y, 11)
    return y


def backtrace(cur):
    high = 0x80000000
    low = 0x7fffffff
    mask = 0x9908b0df
    state = cur
    for i in range(3, -1, -1):
        tmp = state[i + 624] ^ state[i + 397]
        # recover Y,tmp = Y
        if tmp & high == high:
            tmp ^= mask
            tmp <<= 1
            tmp |= 1
        else:
            tmp <<= 1
        # recover highest bit
        res = tmp & high
        # recover other 31 bits,when i =0,it just use the method again it so beautiful!!!!
        tmp = state[i - 1 + 624] ^ state[i + 396]
        # recover Y,tmp = Y
        if tmp & high == high:
            tmp ^= mask
            tmp <<= 1
            tmp |= 1
        else:
            tmp <<= 1
        res |= (tmp) & low
        state[i] = res
    return state


def recover_state(out):
    state = []
    for i in out:
        i = inverse_right(i, 18)
        i = inverse_left_values(i, 15, 4022730752)
        i = inverse_left_values(i, 7, 2636928640)
        i = inverse_right(i, 11)
        state.append(i)
    return state
#逆向


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


def invert_right(res, shift):
    tmp = res
    bits = len(bin(res)[2:])
    for i in range(bits // shift):
        res = tmp ^ res >> shift
    return _int32(res)


def recover(last):
    n = 1 << 32
    inv = invert(1812433253, n)
    for i in range(623, 0, -1):
        last = ((last - i) * inv) % n
        last = invert_right(last, 30)
    return last
#逆向twist


def guess_1(randoms):  # 预测
    rc = RandCrack()
    for i in randoms:
        temp = i
        while temp != 0:
            rc.submit(temp % pow(2, 32))
            temp >>= 32
    number = rc.predict_getrandbits(96)
    return number


def guess_2(randoms):
    partS = recover_state(randoms)
    state = backtrace([0] * 4 + partS)[:624]
    prng = Random()
    prng.setstate((3, tuple(state + [0]), None))
    nn = prng.getrandbits(32)
    number = prng.getrandbits(96)
    return number


def guess_3(last_number):
    seed = recover(last_number)
    return seed


def guess_4(ex_number):
    return extract_recover(ex_number)


from pwn import *

io = remote('node.yuzhian.com.cn',30279)
context.log_level='debug'

io.send('1')  #按任意键开始？

for i in range(20):
    io.recvuntil("Round: " + str(i + 1) + '\n')
    Line = io.recvuntil('\n')[:-1].decode()
    if 'randoms = ' in Line:
        randoms = eval(Line[9:].replace('L',''))  #去除L
        io.recvuntil('Guess ')
        tag = io.recvuntil(' number:').decode()
        print(tag)
        if 'after' in tag:
            io.sendline(str(guess_1(randoms)))
        if 'pre' in tag:
            io.sendline(str(guess_2(randoms)))
    if 'last number = ' in Line:
        last_number = int(Line[14:])
        io.recvuntil('Guess seed number:')
        io.sendline(str(guess_3(last_number)))
    if 'extract number = ' in Line:
        ex_number = int(Line[17:])
        io.recvuntil('Guess be extracted number:')
        io.sendline(str(guess_4(ex_number)))
io.recvall()

easyrsa

考点：

  1. 数论推导
  2. coppersmith攻击

第一问：n=p∗q∗s∗tn=p*q*s*t，phi=(p−1)∗(q−1)∗(s−1)∗(t−1)phi=(p-1)*(q-1)*(s-1)*(t-1)

首先可以求出d=e−1mod  phid=e^{-1}\mod{phi}，而c=memod  p∗qc=m^e\mod{p*q}

由欧拉定理有：cd=mmod  p∗qc^d=m\mod{p*q}

即：f(x)=cd−xmod  p∗qmod  nf(x)=c^d-x\mod{p*q}\mod{n}，mm较小。

利用coppersmith攻击求出x。

第二问同babyrsa。

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
from gmpy2 import *

n = 8836130216343708623415307573630337110573363595188748983290313549413242332143945452914800845282478216810685733227137911630239808895196748125078747600505626165666334675100147790578546682128517668100858766784733351894480181877144793496927464058323582165412552970999921215333509253052644024478417393146000490808639363681195799826541558906527985336104761974023394438549055804234997654701266967731137282297623426318212701157416397999108259257077847307874122736921265599854976855949680133804464839768470200425669609996841568545945133611190979810786943246285103031363790663362165522662820344917056587244701635831061853354597
phi = 8836130216343708623415307573630337110573363595188748983290313549413242332143945452914800845282478216810685733227137911630239808895196748125078747600505622503351461565956106005118029537938273153581675065762015952483687057805462728186901563990429998916382820576211887477098611684072561849314986341226981300596338314989867731725668312057134075244816223120038573374383949718714549930261073576391501671722900294331289082826058292599838631513746370889828026039555245672195833927609280773258978856664434349221972568651378808050580665443131001632395175205804045958846124475183825589672204752895252723130454951830966138888560
c1 = 78327207863361017953496121356221173288422862370301396867341957979087627011991738176024643637029313969241151622985226595093079857523487726626882109114134910056673489916408854152274726721451884257677533593174371742411008169082367666168983943358876017521749198218529804830864940274185360506199116451280975188409
e = 65537
#c1 = m^e mod p*q
#m1 = c1^d mod p*q*r*t
#m1 = m mod p*q √
d = invert(e, phi)
c = int(pow(c1, d, n))
PR.< x > = PolynomialRing(Zmod(n))
f = c - x #c-x=k*p*q
f = f.monic()
x0 = f.small_roots(X=2^300,beta=0.4,epsilon=0.015)[0]
print(x0)
#NKCTF{it_i5_e45y_th4t_Kn0wn

N = 157202814866563156513184271957553223260772141845129283711146204376449001653397810781717934720804041916333174673656579086498762693983380365527400604554663873045166444369504886603233275868192688995284322277504050322927511160583280269073338415758019142878016084536129741435221345599028001581385308324407324725353
c2 = 63355788175487221030596314921407476078592001060627033831694843409637965350474955727383434406640075122932939559532216639739294413008164038257338675094324172634789610307227365830016457714456293397466445820352804725466971828172010276387616894829328491068298742711984800900411277550023220538443014162710037992032
c3 = 9266334096866207047544089419994475379619964393206968260875878305040712629590906330073542575719856965053269812924808810766674072615270535207284077081944428011398767330973702305174973148018082513467080087706443512285098600431136743009829009567065760786940706627087366702015319792328141978938111501345426931078

PR.< x > = PolynomialRing(Zmod(N))
f = x^2-(c2+c3)*x+c2*c3
f = f.monic()
x0 = f.small_roots(X=2^440,beta=0.4,epsilon=0.015)[0]
print(x0)
#_phi_4nd_N_dec0mp0ses_N_w1th_th3_s4m3_c0mm0n_n_but_pq}

eZ_Bl⊕ck

考点

  1. Feistel结构
  2. 异或

可以参考：http://striving.mapleice.top/index.php/archives/150/第三题学习

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

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

kn1=strxor(r[16:],c1[:16])

l1=strxor(kn1,c2[:16])
print(l1)

kn2=strxor(strxor(r[16:],r[:16]),c1[16:])
r1=strxor(strxor(kn2,c2[16:]),l1)
print(r1)

#NKCTF{1ccd5cee-c96d-4caf-8ce5-9a512b3d0655}

ez_polynomial

考点：

  1. 典型的多项式rsa

可以参考:https://blog.csdn.net/m0_57291352/article/details/124850426学习

1
2
3
4
5
6
7
8
9
10
11
12
13
14
p=40031
R.<y> = PolynomialRing(GF(p))
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
e = 65537
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)
S.<x> = R.quotient(N)
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
m=C^d
for i in m:
    print(chr(int(i)),end='')

Raven

挺有意思的一个题目，多项式的系数都比较小。所以可以看作是一个6次的一元多项式。造格子出系数（不过不知道为啥d不能直接出，这里是先出a,b,c。再单独二元copper求d）。

涉及到格基规约和二元coppersimth，较为复杂，先自行研究。

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
p = 
pairs = 

K=2**520
M=[[0 for i in range(12)] for j in range(12)]  #M=[[0]*12]*12
for i in range(4):
    for j in range(7):
        M[j][i]=p-pow(pairs[i][0],6-j,p)
    M[7+i][i]=p
    M[11][i]=pairs[i][1]
for i in range(7):
    M[i][4+i]=1
M[-1][-1]=K
M=Matrix(M)
L=M.LLL()
for i in L:
    if int(i[-1])==K:
        print(i)
        sol=i*M^-1
sol=[int(i) for i in sol[:7]]
print(sol)
from gmpy2 import *
a=int(iroot(sol[0],2)[0])
b=sol[1]//(2*a)
c=(sol[2]-b*b)//(2*a)
print(a,b,c)
#d=256836945952994885035467059118377791095

二元coppersmith恢复key

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
import itertools


# 一种求多项式小根问题的方法
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 []

r3=38110026992499584203762396049303607649993098725357412914752750999593537061009
x3=68711183101845981499596464753252121346970486988311398916877579778110690480447199642602267233989256728822535174215153145632158860662954277116345331672194812126361911061449082917955000137698138358926301360506687271134873
y3=995428771589393162202488762223106955302099250561593105620410424291405842350539887383005328242236156038373244928147473800972534658018117705291472213770335998508454938607290279268848513727721410314612261163489156360908800
p=1018551160851728231474335384388576586031917743463656622083024684199383855595168341728561337234276243780407755294430553694832049089534855113774546001494743212076463713621965520780122783825100696968959866614846174188401153

a,b,c=(248509346369130391242170998803167584710,34130269465266010935033619912669159600,190347116220905792012773821811284452644)
A=a*x3*x3*x3+b*x3*x3+c*x3
# 设置一个基于整数环的多项式,一元或者多元
P.< x, y >= PolynomialRing(Zmod(p))
# f为多项式
f = (A+x)*(A+x)+y-y3
# bounds为根的最大值,粗略范围即可
bounds =(2^128,2^256)
# m,d选填
m = 3
d = 4
roots = small_roots(f, bounds, m, d)
print(roots)

解AES

1
2
3
4
5
6
7
8
from Crypto.Util.number import *
from Crypto.Cipher import AES

key=256836945952994885035467059118377791095
cipher = AES.new(key=long_to_bytes(key), IV=bytes(range(16)), mode=AES.MODE_CBC)

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"
print(cipher.decrypt(ct))

easy_high

考点：

  1. 异或
  2. 已知p的部分比特的coppersmith攻击

参考学习coppersmith攻击的经典应用：已知p的部分比特，已知部分明文，已知部分私钥低位等。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
p0=149263925308155304734002881595820602641174737629551638146384199378753884153459661375931646716325020758837194837271581361322079811468970876532640273110966545339040194118880506352109559900553776706613338890047890747811129988585025948270181264314668772556874718178868209009192010129918138140332707080927643141811

p1=p0%(2**444)  #低位
b=p0.bit_length()-250
p2=(p0>>b)<<b
N=17192509201635459965397076685948071839556595198733884616568925970608227408244870123644193452116734188924766414178232653941867668088060274364830452998991993756231372252367134508712447410029668020439498980619263308413952840568602285764163331028384281840387206878673090608323292785024372223569438874557728414737773416206032540038861064700108597448191546413236875600906013508022023794395360001242071569785940215873854748631691555516626235191098174739613181230094797844414203694879874212340812119576042962565179579136753839946922829803044355134086779223242080575811804564731938746051591474236147749401914216734714709281349
'''
PR.< x > = PolynomialRing(Zmod(N))
f = p1+p2+x*2^444
f=f.monic()
x0 = f.small_roots(X=2 ^ 340, beta=0.4)[0]
print(x0)
'''
x0=1414640121010865756473118885903739629697184780736973873076436168814438323477468170166972852648894898
p=p1+p2+x0*2**444
q=N//p
phi=(p-1)*(q-1)
from gmpy2 import *
from Crypto.Util.number import *
d=invert(65537,phi)
c=4881545863615247924697512170011400857004555681758106351259776881249360423774694437921554056529064037535796844084045263140567168171628832384672612945806728465127954937293787045302307135365408938448006548465000663247116917564500525499976139556325841597810084111303039525833367199565266613007333465332710833102978756654324956219855687611590278570749890543277201538208370370097424105751568285050703167350889953331829275262932104042040526209179357770495596739361176548337593674366015027648541293309465113202672923556991818236011769228078267484362980348613669012975963468592763463397575879215173972436831753615524193609612
print(long_to_bytes(pow(c,d,N)))

eZ_LargeCG

考点

  1. p+1光滑

  2. p-1光滑

  3. 线性递推->矩阵快速幂

可以参考http://striving.mapleice.top/index.php/archives/141/第四题学习

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
'''
#p-1光滑
python primefac -vs -m=p-1 xxx
'''
p=427721675251610827084310512123962488210068003845592404231631542730839819224381
n1=39755206609675677517559022219519767646524455449142889144073217274247893104711318356648198334858966762944109142752432641040037415587397244438634301062818169
q=n1//p
q1=max(p,q)
p1=min(p,q)
'''
#p+1光滑
python primefac -vs -m=p+1 xxx
'''
p=106481130516780473105954611077340189174861459077145246394800660809527032990637
q=288551157776490110472645044398395422160196115791981535735903775378294599329633
q2=max(p,q)
p2=min(p,q)

#线性递推 快速幂
r = 7948275435515074902473978567170931671982245044864706132834233483354166398627204583162848756424199888842910697874390403881343013872330344844971750121043493
A = 6085327340671394838391386566774092636784105046872311226269065664501131836034666722102264842236327898770287752026397099940098916322051606027565395747098434
B = 1385551782355619987198268805270109182589006873371541520953112424858566073422289235930944613836387546298080386848159955053303343649615385527645536504580787
C = 2529291156468264643335767070801583140819639532551726975314270127875306069067016825677707064451364791677536138503947465612206191051563106705150921639560469

a,b,c,d=p1,q1,p2,q2
M=matrix(Zmod(r),[[c,b,a,1],
                  [1,0,0,0],
                  [0,1,0,0],
                  [0,0,0,1]])
N=matrix(Zmod(r),[[C,B,A,d]])
N=N.T
nn=6**666
M=M^nn
print(M^-1*N)

print(long_to_bytes(718268686893438084080386300782696916434605242000201123193568557324202508308322958959518435405441886593296740-2023))

complex_matrix

考点：

  1. 扩展维纳攻击（四维）

可以参考https://huangx607087.online/2021/03/01/LatticeNotes6/学习

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
from Crypto.Util.number import *

n = 71841248095369087024928175623295380241516644434969868335504061065977014103487197287619667598363486210886674500469383623511906399909335989202774281795855975972913438448899231650449810696539722877903606541112937729384851506921675290984316325565141178015123381439392534417225128922398194700511937668809140024838070124095703585627058463137549632965723304713166804084673075651182998654091113119667582720831809458721072371364839503563819080226784026253
e = 65537
c = 39297018404565022956251803918747154798377576057123078716166221329195959669756819453426741569480551313085435037629493881038383709458043802420338889323233368852331387845200216275712388921820794980987541224782392553528127093154957890356084331463340193478391679540506421250562554424770350351514435220782124981277580072039637811543914983033300225131364246910828188727043248991987332274929827173923543187017105236008487756190002204169623313222748976369
e1, e2, e3, e4 = (
65128799196671634905309494529154568614228788035735808211836905142007976099865571126946706559109393187772126407982007858423859147772762638898854472065889939549916077695303157760259717113616428849798058080633047516455513870697383339784816006154279428812359241282979297285283850338964993773227397528608557211742425548651971558377656644211835094019462699301650412862894391885325969143805924684662849869947172175608502179438901337558870349697233790535,
58756559706647121529575085912021603170286163639572075337348109911506627489265537716060463072086480156516641723700802217411122982693536541892986623158818442274840863016647800896033363360822503445344748132842451806511693779600370832206455202293028402486647422212959763287987847280322100701242139127654031151565924132562837893975505159702015125483479126108892709063135006366792197127007229210558758401679638300464111782814561428899998471531067163715,
34828685390969672139784723764579499920301439564705391196519314224159563070870933754477650614819514127121146216049444888554338415587165719098661141454627820126445291802801256297252654045398330613075575527685542980264993711077876535643646746742646371967302159565887123638001580042027272379341650995728849759541960087953160211696369079708787543303742132161742979856720539914370868829868891655221361545648778590685232034703220732697083024449894197969,
26717968456600556973167180286909817773394160817933525240720067057464671317174201540556176814203780603153696663101158205367554829261808020426363683474848952397963507069306452835776851274959389849223566030857588019845781623271395012194869024566879791449466064832273531795430185178486425688475688634844530106740480643866537205900809400383304665727460014210405339697947582657505028211149470787536144302545259243549176816653560626044921521516818788487)

A = [
    [1, -n, 0, n ^ 2, 0, 0, 0, -n ^ 3, 0, 0, 0, 0, 0, 0, 0, n ^ 4],
    [0, 1, -1, -n, -1, 0, n, n ^ 2, -1, 0, n, 0, n, 0, -n ^ 2, -n ^ 3],
    [0, 0, 1, -n, 0, n, 0, n ^ 2, 0, n, 0, 0, 0, -n ^ 2, 0, -n ^ 3],
    [0, 0, 0, 1, 0, -1, -1, -n, 0, -1, -1, 0, 0, n, n, n ^ 2],
    [0, 0, 0, 0, 1, -n, -n, n ^ 2, 0, 0, 0, -n ^ 2, 0, 0, 0, -n ^ 3],
    [0, 0, 0, 0, 0, 1, 0, -n, 0, 0, 0, n, -1, 0, n, n ^ 2],
    [0, 0, 0, 0, 0, 0, 1, -n, 0, 0, 0, n, 0, n, 0, n ^ 2],
    [0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, -1, 0, -1, -1, -n],
    [0, 0, 0, 0, 0, 0, 0, 0, 1, -n, -n, n ^ 2, -n, n ^ 2, n ^ 2, -n ^ 3],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, -n, 0, -n, 0, n ^ 2],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, -n, 0, 0, -n, n ^ 2],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, -n],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, -n, -n, n ^ 2],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, -n],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, -n],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]]
Q = [n ^ 2, n ^ 1.5, n ^ 2.4, n, n ^ 2.4, n ^ 1.9, n ^ 1.9, n ^ 0.5, n ^ 2.4, n ^ 1.9, n ^ 1.9, n ^ 1.4, n ^ 1.9,
     n ^ 1.4, n ^ 1.4, 1]
P = [1, e1, e2, e1 * e2, e3, e1 * e3, e2 * e3, e1 * e2 * e3, e4, e1 * e4, e2 * e4, e1 * e2 * e4, e3 * e4, e1 * e3 * e4,
     e2 * e3 * e4, e1 * e2 * e3 * e4]
A, P, Q = matrix(ZZ, A), diagonal_matrix(ZZ, P), diagonal_matrix(ZZ, Q)
A = P * A * Q
w = vector(ZZ, A.LLL()[0])
v = w * A ^ (-1)
phi = int(e1 * v[1] // v[0])
print(hex(phi))
d = inverse(e, phi)
print(long_to_bytes(pow(c, d, n)))

baby_classical

看着复杂，把题目函数都理一遍，其实就一个矩阵运算，类维吉尼亚加密

考点：

  1. python
  2. 矩阵运算
  3. 维吉尼亚加密
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
import string

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

enc_key='pVvRe/G08rLhfwa'

res=[f1nd(i) for i in enc_key]
res=[res[i:i+3] for i in range(0,len(res),3)]
print(res)
K= matrix(Zmod(64),[[13 ,37 ,10],
 [15 ,17 ,41],
 [13  ,0 ,10]])
long=[]
for i in res:
    r=matrix(Zmod(64),[i])
    l=r*K^-1
    print(l)
    for j in l[0]:
        long.append(int(j))
print(long)
dicn2s={i: dic[i] for i in range(64)}
dics2n = dict(zip(dicn2s.values(), dicn2s.keys()))
print(dics2n)
key=''.join([dicn2s[i] for i in long])[:-1]
print(key) #W3ar3N0wayBack

c='1k2Pe{24seBl4_a6Ot_fp7O1_eHk_Plg3EF_g/JtIonut4/}'
c=c.replace('_',' ')
flag=''
j=0
for i  in c:
    if i in dic:
        flag+=dic[ (f1nd(i)-f1nd(key[j%len(key)]) )%64 ]
    else:
        flag+=i
    j+=1
print(flag)
flag=flag.replace('}','_').replace('{','_').replace(' ','_').split('_')
flag='_'.join([i[::-1] for i in flag])
print(flag.swapcase())
#NKCTF{ClaSsic_c0de_d0l1s_aRe_r3a1ly_int3reSting}

N1CTF招新赛

ezezez

知识点：椭圆曲线，数论，Related Message Attack

语言：sagemath

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
from Crypto.Util.number import *
a = 259416965926853287275013962386631097709
n = 8963244108103857378610478915798540027754205184635651624801332901515870452435977078824267979279218575027152343028911705254378598817260939339516835322386427
gy = [1896722249337161391193797083807118705857637064141055866260977430130447249097804719101078827699386498665026965515554644281163046869672493999194358926022865, 1971472878970365404484102034878792535366624572891039926216530789642810299559238977732710681752685090332485586910206690093655977703795335533365202958013518, 4074555112002157403114317690671003025383051142150876016519408756236925988856478235258960189636836867363451314784889114354880607055705753428890566240606935]
#y^2=x^3+ax+b mod n
magic = bytes_to_long(b'N1Junior_CheckIn')
e=24
gx1=magic
b=(gy[1]*gy[1]-gx1*gx1*gx1-a*gx1)%n #求出b

#fx=y0^2-(x^e)^3-a(x^e)-b
#gx=y2^2-((x+magic)^e)^3-a( (x+magic)^e )-b
def gcd(g1, g2):
    while g2:
        g1, g2 = g2, g1 % g2
    return g1.monic()
PR.<x>=PolynomialRing(Zmod(n))
fx=gy[0]*gy[0]-x^(3*e)-a*x^e-b
gx=gy[2]*gy[2]-(x+magic)^(3*e)-a*((x+magic)^e)-b
print(gcd(fx,gx))