XYCTF-Crypto方向部分wp

时长一个月终于结束了，最后只做了一半多一道，还是太菜了，感觉自己如学

x0r

解答：

nc连接，输入1得iv和enc，输入2后分别将得到的iv和enc输入即可得到flag

factor1

题目：

1
2
3
4
5
6
7
8
9
10
11
import gmpy2
import hashlib
from Crypto.Util.number import *

p = getPrime(512)
q = getPrime(512)
d = getPrime(512)
e = gmpy2.invert(d, (p**3 - 1) * (q**3 - 1))
flag = "XYCTF{" + hashlib.md5(str(p + q).encode()).hexdigest() + "}"
print(e)
print(p * q)

解答：

因此通过连分数展开的思想得到k、d
令$x=p+q$, $temp=\frac{ed-1}{k}$

求解多项式即可得到x

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
# sage:
e = ...
pq = ...
pqx = pq ^ 3
fra = (e/pqx).continued_fraction()
for i in range(1, len(fra)):
    k, d = fra.numerator(i), fra.denominator(i)
    if (e*d - 1) % k == 0 and d > 2^250:
        break

temp = (e*d - 1) // k
pq3 = pqx - temp + 1
x = PolynomialRing(RationalField(), 'x').gen()
f = x^3-3*pq*x-pq3
p_q = int(f.roots()[0][0])

from Crypto.Util.number import *
from gmpy2 import iroot
import hashlib

flag = "XYCTF{" + hashlib.md5(str(p_q).encode()).hexdigest() + "}"
print(flag)

"""
XYCTF{a83211a70e18145a59671c08ddc67ba4}

factor3

薅过来用

题目：

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

flag = b'XYCTF{*****}'
m = bytes_to_long(flag)
def gainPrime():
    while True:
        x = random.getrandbits(256)
        y = random.getrandbits(256)

        if y % 2 == 0:
            continue

        p = x ** 3 + 3 * y ** 3
        if p.bit_length() == 768 and p % 2 == 1 and isPrime(p):
            return p

p, q = gainPrime(), gainPrime()
N = p * q
phi = (p ** 2 + p + 1) * (q ** 2 + q + 1)
d = getPrime(320)
e = inverse(d, phi)
c = d**2^m

print(f"N: {N}")
print(f"e: {e}")
print(f"c: {c}")

解答：

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
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
#sage
import time

############################################
# Config
##########################################

debug = True
strict = False
helpful_only = True
dimension_min = 7 # stop removing if lattice reaches that dimension

############################################
# Functions
##########################################
# display stats on helpful vectors

def helpful_vectors(BB, modulus):
    nothelpful = 0
    for ii in range(BB.dimensions()[0]):
        if BB[ii,ii] >= modulus:
            nothelpful += 1
    print(nothelpful, "/", BB.dimensions()[0], " vectors are not helpful")

def matrix_overview(BB, bound):
    for ii in range(BB.dimensions()[0]):
        a = ('%02d ' % ii)
        for jj in range(BB.dimensions()[1]):
            a += '0' if BB[ii,jj] == 0 else 'X'
            if BB.dimensions()[0] < 60:
                a += ' '
        if BB[ii, ii] >= bound:
            a += '~'
        print(a)

  

def remove_unhelpful(BB, monomials, bound, current):
    if current == -1 or BB.dimensions()[0] <= dimension_min:
        return BB

    for ii in range(current, -1, -1):
        if BB[ii, ii] >= bound:
            affected_vectors = 0
            affected_vector_index = 0

            # let's check if it affects other vectors
            for jj in range(ii + 1, BB.dimensions()[0]):
                if BB[jj, ii] != 0:
                    affected_vectors += 1
                    affected_vector_index = jj

            if affected_vectors == 0:
                print("* removing unhelpful vector", ii)
                BB = BB.delete_columns([ii])
                BB = BB.delete_rows([ii])
                monomials.pop(ii)
                BB = remove_unhelpful(BB, monomials, bound, ii-1)
                return BB

            elif affected_vectors == 1:
                affected_deeper = True

                for kk in range(affected_vector_index + 1, BB.dimensions()[0]):
                
                    if BB[kk, affected_vector_index] != 0:
                        affected_deeper = False
  
                if affected_deeper and abs(bound - BB[affected_vector_index, affected_vector_index]) < abs(bound - BB[ii, ii]):
                    print("* removing unhelpful vectors", ii, "and", affected_vector_index)
                    BB = BB.delete_columns([affected_vector_index, ii])
                    BB = BB.delete_rows([affected_vector_index, ii])
                    monomials.pop(affected_vector_index)
                    monomials.pop(ii)
                    BB = remove_unhelpful(BB, monomials, bound, ii-1)
                    return BB
    return BB
    
def attack(N, e, m, t, X, Y):
    modulus = e
    PR.<x, y> = PolynomialRing(ZZ)
    a = N + 1
    b = N * N - N + 1
    f = x * (y * y + a * y + b) + 1
    gg = []
    
    for k in range(0, m+1):
        for i in range(k, m+1):
            for j in range(2 * k, 2 * k + 2):
                gg.append(x^(i-k) * y^(j-2*k) * f^k * e^(m - k))
    for k in range(0, m+1):
        for i in range(k, k+1):
            for j in range(2*k+2, 2*i+t+1):
                gg.append(x^(i-k) * y^(j-2*k) * f^k * e^(m - k))
                
    def order_gg(idx, gg, monomials):
        if idx == len(gg):
            return gg, monomials
        for i in range(idx, len(gg)):
            polynomial = gg[i]
            non = []
            for monomial in polynomial.monomials():
                if monomial not in monomials:
                    non.append(monomial)
            if len(non) == 1:
                new_gg = gg[:]
                new_gg[i], new_gg[idx] = new_gg[idx], new_gg[i]
                return order_gg(idx + 1, new_gg, monomials + non)    
    gg, monomials = order_gg(0, gg, [])
  
    nn = len(monomials)
    BB = Matrix(ZZ, nn)
    for ii in range(nn):
        BB[ii, 0] = gg[ii](0, 0)
        for jj in range(1, nn):
            if monomials[jj] in gg[ii].monomials():
                BB[ii, jj] = gg[ii].monomial_coefficient(monomials[jj]) * monomials[jj](X, Y)

    if helpful_only:
        # automatically remove
        BB = remove_unhelpful(BB, monomials, modulus^m, nn-1)
        # reset dimension
        nn = BB.dimensions()[0]
        if nn == 0:
            print("failure")
            return 0,0

    if debug:
        helpful_vectors(BB, modulus^m)
    # check if determinant is correctly bounded
    det = BB.det()
    bound = modulus^(m*nn)
    if det >= bound:
        print("We do not have det < bound. Solutions might not be found.")
        print("Try with highers m and t.")
        if debug:
            diff = (log(det) - log(bound)) / log(2)
            print("size det(L) - size e^(m*n) = ", floor(diff))
        if strict:
            return -1, -1
    else:
        print("det(L) < e^(m*n) (good! If a solution exists < N^delta, it will be found)")

    if debug:
        matrix_overview(BB, modulus^m)
    if debug:
        print("optimizing basis of the lattice via LLL, this can take a long time")
    BB = BB.LLL()
    if debug:
        print("LLL is done!")
    if debug:
        print("looking for independent vectors in the lattice")
        
    found_polynomials = False
    for pol1_idx in range(nn - 1):
        for pol2_idx in range(pol1_idx + 1, nn):
            PR.<a, b> = PolynomialRing(ZZ)
            pol1 = pol2 = 0
            for jj in range(nn):
                pol1 += monomials[jj](a,b) * BB[pol1_idx, jj] / monomials[jj](X, Y)
                pol2 += monomials[jj](a,b) * BB[pol2_idx, jj] / monomials[jj](X, Y)
            PR.<q> = PolynomialRing(ZZ)
            rr = pol1.resultant(pol2)
  
            if rr.is_zero() or rr.monomials() == [1]:
                continue
            else:
                print("found them, using vectors", pol1_idx, "and", pol2_idx)
                found_polynomials = True
                break
        if found_polynomials:
            break
    if not found_polynomials:
        print("no independant vectors could be found. This should very rarely happen...")
        return 0, 0
    rr = rr(q, q)
    # solutions
    soly = rr.roots()
    if len(soly) == 0:
        print("Your prediction (delta) is too small")
        return 0, 0
    soly = soly[0][0]
    ss = pol1(q, soly)
    solx = ss.roots()[0][0]
    return solx, soly
def inthroot(a, n):
    return a.nth_root(n, truncate_mode=True)[0]
N = 913125842482770239379848062277162627509794409924607555622246822717218133091223291889541294440266178282194506242444509803611492259403578922020590849630191477864719052980160940803309686069818208833547621252544423652489179493083138385424424384165228024273745733240109761707533778691158938848158094054261174692601673435971526522219273943464877956131040249169850420336023942653021547841666224446678539579529590840999008107782784268926145671962239929431694391039559247

e = 494518390582436635999115147756676313570637682518235195828939117782099618734167908630788943568232122157772909140885391963441876427590731524706959546524212914108888799081844320513851526790475333924396837458796755678072486028072639014677580265244176441153444956871730684233063789931539669072735599696830757690822185323538738397827461580678488181113667710378657058297572328491762536595872579603698945272140918157163640403488075948987156585480146162739943419183496337465468187233821931312507662218106713861638334075899266373256620752680354704533272722692596941861606161634082613228896420520465402725359166156632884432690715903666803067996854084671477445131853993177110154928274312496230096270510089973592664248613332000290545537840595645944390047611474888693558676781309912289044962293014118087259307560444929227407113819165713213046898243995956550944640168932947118400215917515277554126694376415569909534496134700668701465649939

X = 1 << 469

Y = 2 * inthroot(Integer(2 * N), 2)

res = attack(N, e, 4, 2, X, Y)

print(res)

b, c = res[1], N

Dsqrt =  inthroot(Integer(b^2-4*c),2)

p, q = (b + Dsqrt) // 2, (b - Dsqrt) // 2

assert p * q == N
print(p)
print(q)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import gmpy2
from Crypto.Util.number import *
p = 1079692686288325812308630934214667048073665141240195252583556389192093937087035206847129125872559936616225942097278411602071282941911673739879515157769270737229378250560113256396308250699296075273110248314981762673299506406938725953
q = 845727542734252771097508620366884787581346823455578404917525769041539439746914530374958818236462967773717478357930648479282951655380705183747821800053493097745787392338644671787997907165214166274630065657567039034950440073852768399
c = 4450931337369461482106945992542133557585962894030505065110870389112565329875502952762182372926117037373210509516570958483606566274369840551132381128665744266165792377925899683228751870742727716
N = p * q
phi = (p ** 2 + p + 1) * (q ** 2 + q + 1)
e = 494518390582436635999115147756676313570637682518235195828939117782099618734167908630788943568232122157772909140885391963441876427590731524706959546524212914108888799081844320513851526790475333924396837458796755678072486028072639014677580265244176441153444956871730684233063789931539669072735599696830757690822185323538738397827461580678488181113667710378657058297572328491762536595872579603698945272140918157163640403488075948987156585480146162739943419183496337465468187233821931312507662218106713861638334075899266373256620752680354704533272722692596941861606161634082613228896420520465402725359166156632884432690715903666803067996854084671477445131853993177110154928274312496230096270510089973592664248613332000290545537840595645944390047611474888693558676781309912289044962293014118087259307560444929227407113819165713213046898243995956550944640168932947118400215917515277554126694376415569909534496134700668701465649939

d = gmpy2.invert(e, phi)
m = d**2^c
print(long_to_bytes(m))

"""
b'XYCTF{I_love_to_read_the_crypto_paper_and_try_to_ak_them}'

板子的论文：1160.pdf (iacr.org)

happy_to_solve1

题目：

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


def get_happy_prime():
    p = getPrime(512)
    q = sympy.nextprime(p ^ ((1 << 512) - 1))
    return p, q


m = bytes_to_long(flag)
p, q = get_happy_prime()
n = p * q
e = 65537
print(n)
print(pow(m, e, n))

解答：

由异或性质得：如果a>b，且a为二进制全为1,那么a^b=a-b
所以((1<<512)-1)^p=(1<<1024)-p。 设p^((1<<512)-1)的下一个素数与p^((1<<512)-1)相差r， 则$q=(1<<512-1)-p+r$， $p+q=1<<512-1+r$， $p+q\approx 1<<512$， $n=pq=(\frac{p+q}{2})^{2}-(\frac{p-q}{2})^{2}$， 将$p+q$带入得$p-q\approx\sqrt{(p+q)^{2}-4n}$， 所以$p\approx\frac{(1<<1024)+\sqrt{(1<<1024)^{2}}-4n}{2}$， 根据n%p=0向后爆破 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
n = 24852206647750545040640868093921252282805229864862413863025873203291042799096787789288461426555716785288286492530194901130042940279109598071958012303179823645151637759103558737126271435636657767272703908384802528366090871653024192321398785017073393201385586868836278447340624427705360349350604325533927890879
c = 14767985399473111932544176852718061186100743117407141435994374261886396781040934632110608219482140465671269958180849886097491653105939368395716596413352563005027867546585191103214650790884720729601171517615620202183534021987618146862260558624458833387692782722514796407503120297235224234298891794056695442287

import gmpy2
from Crypto.Util.number import *
e=65537
t1=1<<1024
p=(2**512+gmpy2.iroot((2**1024-4*n,2)[0])//2
p=int(p)
while n%p!=0:
    p=gmpy2.next_prime(p)
q=n//p
phi=(p-1)*(q-1)
d=gmpy2.invert(e,phi)
m=pow(c,d,n)
print(long_to_bytes(m))

"""
b'XYCTF{3f22f4efe3bbbc71bbcc999a0a622a1a23303cdc}'

happy_to_solve2

题目：

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


def get_happy_prime():
    while 1:
        p = int("".join([random.choice("123") for _ in range(512)]))
        q = int("".join([random.choice("567") for _ in range(512)]))
        if isPrime(p) and isPrime(q):
            return (p,q)

m = bytes_to_long(flag)
p ,q= get_happy_prime()
n = p * q
e = 65537
print(n)
print(pow(m, e, n))

解答：

用$pq\equiv 10\mod{10^{i}}$ DFS 搜寻

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
import gmpy2
from itertools import product
from Crypto.Util.number import long_to_bytes

n = 697906506747097082736076931509594586899561519277373830451275402914416296858960649459482027106166486723487162428522597262774248272216088755005277069446993003521270487750989061229071167729138628583207229945902389632065500739730301375338674342457656803764567184544685006193130563116558641331897204457729877920989968662546183628637193220770495938729301979912328865798266631957128761871326655572836258178871966196973138373358029531478246243442559418904559585334351259080578222274926069834941166567112522869638854253933559832822899069320370733424453856240903784235604251466010104012061821038897933884352804297256364409157501116832788696434711523621632436970698827611375698724661553712549209133526623456888111161142213830821361143023186927163314212097199831985368310770663850851571934739809387798422381702174820982531508641022827776262236373967579266271031713520262606203067411268482553539580686495739014567368858613520107678565628269250835478345171330669316220473129104495659093134763261751546990704365966783697780787341963138501
c = 153383826085102296581238539677668696644156148059026868813759015106139131297135097831661048493079405226972222492151356105759235749502324303047037349410709021152255315429280760639113724345836532087970918453353723090554450581657930847674930226113840172368662838756446364482977092478979838209396761279326533419699056209983721842484996150025403009644653678928025861445324715419893797015875541525590135843027312322236085581571452084477262582966972702577136904385741443870527205640874446616413917231260133364227248928492574610248881137364204914001412269740461851747883355414968499272944590071623223603501698004227753335552646715567802825755799597955409228004284739743749531270833084850113574712041224896044525292591264637452797151098802604186311724597450780520140413704697374209653369969451501627583467893160412780732575085846467289134920886789952338174193202234175299652687560232593212131693456966318670843605238958724126368185289703563591477049105538528244632434869965333722691837462591128379816582723367039674028619947057144546
e = 65537

def base10(ss):
    r = 0
    for x in ss[::-1]:
        r = r * 10 + x
    return r
  
def dfs(ps, qs, mod):
    if base10(ps) * base10(qs) == n:
        yield base10(ps), base10(qs)
        return
    for pp, qq in product((1, 2, 3), (5, 6, 7)):
        p = base10(ps + [pp])
        q = base10(qs + [qq])
        if p * q % mod == n % mod:
            yield from dfs(ps + [pp], qs + [qq], mod * 10)
  

p, q = next(dfs([], [], 1))
phi = (p - 1) * (q - 1)
d = gmpy2.invert(e, phi)
m = pow(c, d, n)
print(long_to_bytes(m))
"""
XYCTF{7f4b2241951976ce5ef6df44503209059997e5085d1bc21f6bef4d9effb29fd0}

参考：https://blog.maple3142.net/2024/03/03/osu-gaming-ctf-2024-writeups/#no-dorchadas

Sign1n[签到] & Sign1n_Revenge

两个签到的b不一样，莫非是传说中的动态附件？
题解就b不一样，这里就放一个的了

题目：

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
from Crypto.Util.number import *
from tqdm import *
import gmpy2
flag=b'XYCTF{uuid}'
flag=bytes_to_long(flag)
leak=bin(int(flag))
while 1:
    leak += "0"
    if len(leak) == 514:
        break

def swap_bits(input_str):
    input_list = list(input_str[2:])
    length = len(input_list)

    for i in range(length // 2):
        temp = input_list[i]
        input_list[i] = input_list[length - 1 - i]
        input_list[length - 1 - i] = temp

    return ''.join(input_list)

input_str = leak
result = swap_bits(input_str)
a=result

def custom_add(input_str):
    input_list = list(input_str)
    length = len(input_list)
    
    for i in range(length):
        input_list[i] = str((int(input_list[i]) + i + 1) % 10)

    result = ''.join(input_list)
    return result


input_str = a
result = custom_add(input_str)
b=result
print(b)

解答：

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
b = 12345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567891134567789113445678012235677900133457889012456679901245577801223567790012355788911245667890134456789122355788001245578891223566790113445778902335578800123457889122346778011344567991223557880012346788912335667991134457789122355788001244578891223467799012455688912234667900133557889022356678901344578801233467789112355779912234577990233556780113
b = str(b)
print(b)
  

from Crypto.Util.number import *

def custom_add(input_str):
    input_list = list(input_str)
    length = len(input_list)
    for i in range(length):
        input_list[i] = str((int(input_list[i]) - i - 1) % 10)
    result = ''.join(input_list)
    return result[[扩展维纳攻击]]

a = custom_add(b)
print(a)

def swap_bits(input_str):
    input_list = list(input_str[2:])
    length = len(input_list)
    
    for i in range(length // 2):
        temp = input_list[i]
        input_list[i] = input_list[length - 1 - i]
        input_list[length - 1 - i] = temp
        
    return ''.join(input_list)
f = swap_bits(a)
print(f)
# 去掉末尾的0
binary = 0b1011000010110010100001101010100010001100111101100110000001100100011010100110010001100100110000101100011001100100010110100110001001101010011011100111000001011010011010000110110011000110011000000101101011000010011011100110011001101100010110100110000001100000011100100110100001101110011100101100001001110000011000100110111001110000011010001111101
print(long_to_bytes(binary))

"""
b'XYCTF{02522ac2-1578-46c0-a736-009479a81784}'

BabyRSAMAX

题目：

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

flag = b'XYCTF{******}'
e = '?'
def getBabyPrime(nbits):
    while True:
        p = 1
        while p.bit_length() <= nbits:
            p *= choice(sieve_base)
        
        if isPrime(p+1):
            return p+1

p = getBabyPrime(512)
q = getBabyPrime(512)
n = p*q
gift1 = (pow(p,e,n)-pow(q,e,n)) % n
gift2 = pow(p+q,e,n)

t = 65537
x = bytes_to_long(e)
y = pow(x, t, n)

m = bytes_to_long(flag)
c = powmod(m, e, n)

print(f'n = {n}')
print(f'gift1 = {gift1}')
print(f'gift2 = {gift2}')
print(f'c = {c}')
print(f'y = {y}')

解答：

$g1=p^{e}-q^{e}\mod{n}$
$g2=(p+q)^{e}\mod{n}=p^{e}+q^{e}\mod{n}$
$g1+g2=2p^{e}\mod{n}$
$g2-g1=2q^{e}\mod{n}$
$\therefore p = gcd(g1+g2,n)$
$\therefore q = gcd(g2-g1,n)$

一路算下去发现e与phi不互素，于是模n下对c开4次方

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

n = 39332423872740210783246069030855946244104982381157166843977599780233911183158560901377359925435092326653303964261550158658551518626014048783435245471536959844874036516931542444719549997971482644905523459407775392702211086149279473784796202020281909706723380472571862792003687423791576530085747716706475220532321
g1 = 4549402444746338327349007235818187793950285105091726167573552412678416759694660166956782755631447271662108564084382098562999950228708300902201571583419116299932264478381197034402338481872937576172197202519770782458343606060544694608852844228400457232100904217062914047342663534138668490328400022651816597367310
g2 = 111061215998959709920736448050860427855012026815376672067601244053580566359594802604251992986382187891022583247997994146019970445247509119719411310760491983876636264003942870756402328634092146799825005835867245563420135253048223898334460067523975023732153230791136870324302259127159852763634051238811969161011462
c = 16938927825234407267026017561045490265698491840814929432152839745035946118743714566623315033802681009017695526374397370343984360997903165842591414203197184946588470355728984912522040744691974819630118163976259246941579063687857994193309554129816268931672391946592680578681270693589911021465752454315629283033043
y = 1813650001270967709841306491297716908969425248888510985109381881270362755031385564927869313112540534780853966341044526856705589020295048473305762088786992446350060024881117741041260391405962817182674421715239197211274668450947666394594121764333794138308442124114744892164155894256326961605137479286082964520217
  

pe = ((g1+g2)//2)%n
qe = ((g2-g1)//2)%n
p = gmpy2.gcd(pe,n)
q = gmpy2.gcd(qe,n)
print(p,q)
print(p*q==n)
phi=(p-1)*(q-1)
t = 65537
x = pow(y,gmpy2.invert(t,phi),n)
e = x

print(long_to_bytes(e))
e = 4096
phi = phi//4

#sage
#以下是实现开二次方的函数
def multiplication(x1,y1,x2,y2,w,p):  
    x=(x1*x2+y1*y2*w)%p  
    y=(x1*y2+x2*y1)%p  
    return x,y  
  
# 获取w,使得w = -1 mod p, w是复数元的平方  
def get_w(c,p):  
    a=randint(1,p)  
    w=pow(a, 2) - c  
    while pow(w,(p - 1)//2,p)!=p-1:  
        a=randint(1,p)  
        w=pow(a,2)-c  
    return w,a  
def Cipolla_algorithm(c,p):  
    #主体部分  
    w,a=get_w(c,p)  
    power=(p+1)//2  
    x1=a  
    y1=1  
    x=1  
    y=0  
    while(power!=0):  
        if(power!=(p+1)//2):  
            x1,y1=multiplication(x1,y1,x1,y1,w,p)  
        if(power & 1):  
            x,y=multiplication(x,y,x1,y1,w,p)  
        power>>=1  
    return x
#以下sage直接对cn开两次二次方，因为只有四个解所以偷懒了
cn = pow(c,4*15340221468921505548397362128123138214101003260229144051087454992413006131615185800769124140840468748
23035337005158475621433705623268639417140515158078335142054666787229183797173181186377993649280,n)
cp = cn%p
Cipolla_algorithm(cn,p)%p
166353789373057352195268573847472134983952212264580315606750168640904529917560511398152614100259694276272602506054433757749654828608600573448732931745676174

sage: Cipolla_algorithm(cn,p)%p
1320925615378691609936673193334302667304516095065655944868325562479391795804424371343552922650946388889883899419614130483678902025
sage: Cipolla_algorithm(cn,p)%p
166353789373057352195268573847472134983952212264580315606750168640904529917560511398152614100259694276272602506054433757749654828608600573448732931745676174
sage: Cipolla_algorithm(166353789373057352195268573847472134983952212264580315606750168640904529917560511398152614100259694276272602506054433757749654828608600573448732931745676174,p)%p
0
sage: Cipolla_algorithm(1320925615378691609936673193334302667304516095065655944868325562479391795804424371343552922650946388889883899419614130483678902025,p)%p
36344540379246669047243921781711114415694316462518391812884210045
sage: Cipolla_algorithm(1320925615378691609936673193334302667304516095065655944868325562479391795804424371343552922650946388889883899419614130483678902025,p)%p
166353789373057352195268575168397750362643822201253508941052835945420624983216456266478176543306949701450304802363434626984929302798183530544471602540368154

1
2
3
4
#长度较短的通常会是flag，直接尝试最短的，得到flag
print(long_to_bytes(36344540379246669047243921781711114415694316462518391812884210045))
"""
b'XYCTF{Rabin_is_so_biggggg!}'

实现开二次方的函数来源：https://www.cnblogs.com/Lovechan/articles/17517915.html

fakeRSA

题目：

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

flag = b'XYCTF{******}'
n = ZZ(bytes_to_long(flag))
p = getPrime(int(320))
print(p)

G = Zmod(p)

def function(X, Y, Z):
    def part(a, b, c):
        return vector([9 * a - 36 * c, 6 * a - 27 * c, b])
    def parts(n):
        Gx.<a, b, c> = G[]
        if n == 0: return vector([a, b, c])
        mid = parts(n // 2)
        result = mid(*mid)
        if n % 2 == 0: return result
        else: return part(*result)
    return parts(n)(X, Y, Z)

print(function(69, 48, 52))

解答：

hint中提到jordan标准型，现学又加一

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

p = 1849790472911267366045392456893126092698743308291512220657006129900961168811898822553602045875909
K = Zmod(p)
A = matrix(K, [[9, 0, -36], [6, 0, -27], [0, 1, 0]])
u = vector(K, (69, 48, 52))
v = vector(
    K,
    (
        1431995965813617415860695748430644570118959991271395110995534704629241309597572003500157255135707,
        1011565891130611736600822618382801465506651972373410962205810570075870804325974377971089090196019,
        784497518859893244278116222363814433595961164446277297084989532659832474887622082585456138030246,
    ),
)
J, P = A.jordan_form(transformation=True)
# A^n*v=u
# A=PJP^-1
# J^n*vv=uu
print(J)
vv = ~P * v
uu = ~P * u
a, b, c = uu
aa, bb, cc = vv
n = (18 * bb * c - 18 * b * cc) / (6 * c * cc)
print(long_to_bytes(int(n)))

"""
[3 1 0]
[0 3 1]
[0 0 3]
b'XYCTF{y0u_finally_f0und_t3h_s3cr3ts!!}'

random_rr

题目：

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

from random import randint
flag=b'XYCTF{uuid}'
flag = bytes_to_long(flag)
n = 472993274721871037103726599805149366727531552333249750035977291933239067588481589544777397613192273114354221827196579379954069925604091911249655707080927769808587176515295614018992848517984372306879552247519117116110554431341268358177159108949791969262793325836353834899335531293329721598226413212541536002401507477776699642647348576111445702197483449777741566350285229621935507081895389023444249054515395783080003733803406382744631528246608154546123270319561514117323480441428953306734274538511770278887429407127143049023747710881993279361892937905382946820141513009017756811296722630617325141162244806884220212939955235410280899112731530527048274396186038160728562551536558223235783656985493518204710943916486379681906506757757594165379493317173050550893487151879681122510523721157284728808336110950008840684602353984682117748018347433177541603140491131603068512706893984834735290809952944273565203183330739252949245209529232254867201402656024997949207918675051941911990640248052951780195402390132237903538546705181463959793972284823588987652138458328270662652334799233015314673544813649692428544375538627858921763941533600553536579901589575693816746953261108022490849251974419402753031545629158199093099096735356165044275617408697
rr = 11898141078345200236264081467585899457224809417108457314508072413792599039332439547789237898270544336909458761754683941320649771736625000667170176071314483
def generate():
    fw = open("random", "w")
    for i in range(648):
        fw.write(str(random.getrandbits(32))+"\n")
    fw.close()
generate()
key = str(random.getrandbits(32))
key1= int(str(key)[0])
ks = [randint(0, rr**(i+key1-1)) for i in range(16)]
c1 = pow(sum(k*flag**i for i, k in enumerate(ks)), 127, n)
c2 = pow(flag, 65537, n)
ks = [pow(69, k+key, rr**(i+key1)) for i, k in enumerate(ks)]
print(f"{ks = }")
print(f"{c1 = }")
print(f"{c2 = }")

解答：

现学
翻译开始：elementary number theory - Discrete logarithm modulo powers of a small prime - Mathematics Stack Exchange
首先，对于给定的小素数 ( p )，解决形如$ax \equiv b \pmod{p}$的同余方程相对容易，这里假设 ( a ) 和 ( b ) 都不是 ( p ) 的倍数。例如，对于任何偶数指数 ( x )，都有$2x \equiv 28 \pmod{3}$成立。

其次，如果对于某个整数幂$s \geq 1$，存在解$a^{x} \equiv b \pmod{p^s}$，那么解也存在于$p^{s-1}$ 中，一直回溯到 ( p )，也就是
$a^{x} \equiv b \pmod{p^s}⟹a^{x} \equiv b \pmod{p^{s-1}}⟹…⟹a^{x} \equiv b \pmod{p}$

Eric Bach（1984年）提出了一个类似于多项式的 Hensel 提升算法的算法，用于在上述同余方程链中向后推进。他的目的是比较对于一般模数$n$求解离散对数问题和因数分解问题的难度，所以这里我们只关注他的工作的一部分。

在此算法中，我们使用模运算下的整数环$\mathbb{Z}$，并且$\mathbb{Z}_n$表示模$n$的整数环。$\mathbb{Z}^*_n$表示其单位元的乘法群，而$\mathbb{Z}^+_n$表示其加法群。需要注意的是，加法群是循环的，有$n$个元素，而乘法群的元素个数由欧拉函数$\phi(n)$给出（计算与$n$互素的介于 0 和$n-1$的整数个数）。

接下来，考虑$n = p^s$是素数的幂次方，其中$s \geq 1$。其单位元群的元素个数可以通过以下方式计算：对于奇素数$p$的情况，乘法群是循环的，其阶数为$(p-1)p^{s-1}$，并且存在一个模$n$的原根。

现在，Bach 从奇素数$p$的情况开始讨论，因此我们知道存在一个同构映射：

易见，对于给定的 $k \in \mathbb{Z}^_{p^s}$，要找到其在第一个因子上的投影，只需将 $k$ 对 $p$ 取模即可。 剩余算法的核心在于展示一个多项式时间可计算的同态投影 $\theta$，将乘法群 $\mathbb{Z}^_{p^s}$ 同态映射到加法群 $\mathbb{Z}^+_{p^{s-1}}$： 一旦我们得到了这个函数，将模 $p$ 下的解 $a^{x_{1}} \equiv b \mod p$ 提升到 $\mathbb{Z}^*_{p^s}$ 中的解 $a^{x_{s}} \equiv b \mod p^s$ 就变得相当自然。需要注意的是，$x_s \equiv x_1 \mod (p-1)$。 将投影 $\theta$ 应用到上述“高阶”同余式中，将会导向到加法群 $\mathbb{Z}^+_{p^{s-1}}$ 中的以下问题： 这个问题可以通过扩展欧几里得算法，在 $\mathbb{Z}_{p^{s-1}}$ 中求解 $\theta(a)$ 的倒数来解决。 如果我们通过中国剩余定理找到一个整数 $x_s$，满足以下两个条件： 那么我们就完成了，因为根据同构关系：

最后，Bach 给出了投影函数$\theta$的公式：

$\theta(k) = \left[ \frac{k^{(p-1)p^{s-1} - 1}}{p^s} \right] \pmod{p^{s-1}}$

这个函数的复杂度在于$p$和$s$的对数阶，如果分子（方括号中整数表达式的分子）在模$p^{2s-1}$下计算，则此函数是多项式时间的。我们需要这么多的基数$p$位数，以便在除以$p^s$后得到正确的模$p^{s-1}$的余数。除法的准确性由欧拉对费马小定理的推广所暗示。

因为$\phi(p^s) = (p-1)p^{s-1}$
所以找一个$x_s$同时满足$x_{s}\equiv x_1 \mod (p-1)$和$x_s \equiv c \mod p^{s-1}$
使$a^{x_{1}+k(p-1)p^{s-1}} \equiv b \mod p^s$

翻译结束（）
以下代码

首先梅森旋转找出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
from hashlib import md5
from randcrack import RandCrack

with open(r'random', 'r') as f:
    l = f.readlines()
l = [int(i.strip()) for i in l]
t = []

for i in range(24,648):
    t.append(l[i])

rc = RandCrack()

for i in t:
    rc.submit(i)
    
key = str(rc.predict_getrandbits(32))
key1= int(str(key)[0])
print(key)
print(key1)

"""
3168111950
3

然后一个同态映射到加法群，根据c1和c2模n下构造两个多项式环，gcd得到n
注意最后减去k多加的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
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
ks = [...]
c1 = ...
c2 = ...
n = ...
rr = ...
key = 3168111950
key1 = 3

#sage
from Crypto.Util.number import *
import gmpy2
import logging


def _polynomial_hgcd(ring, a0, a1):
    assert a1.degree() < a0.degree()

    if a1.degree() <= a0.degree() / 2:
        return 1, 0, 0, 1

    m = a0.degree() // 2
    b0 = ring(a0.list()[m:])
    b1 = ring(a1.list()[m:])
    R00, R01, R10, R11 = _polynomial_hgcd(ring, b0, b1)
    d = R00 * a0 + R01 * a1
    e = R10 * a0 + R11 * a1
    if e.degree() < m:
        return R00, R01, R10, R11

    q, f = d.quo_rem(e)
    g0 = ring(e.list()[m // 2:])
    g1 = ring(f.list()[m // 2:])
    S00, S01, S10, S11 = _polynomial_hgcd(ring, g0, g1)
    return S01 * R00 + (S00 - q * S01) * R10, S01 * R01 + (S00 - q * S01) * R11, S11 * R00 + (S10 - q * S11) * R10, S11 * R01 + (S10 - q * S11) * R11


def fast_polynomial_gcd(a0, a1):

    assert a0.parent() == a1.parent()

    if a0.degree() == a1.degree():
        if a1 == 0:
            return a0
        a0, a1 = a1, a0 % a1
    elif a0.degree() < a1.degree():
        a0, a1 = a1, a0

    assert a0.degree() > a1.degree()
    ring = a0.parent()


    while True:
        logging.debug(f"deg(a0) = {a0.degree()}, deg(a1) = {a1.degree()}")
        _, r = a0.quo_rem(a1)
        if r == 0:
            return a1.monic()

        R00, R01, R10, R11 = _polynomial_hgcd(ring, a0, a1)
        b0 = R00 * a0 + R01 * a1
        b1 = R10 * a0 + R11 * a1
        if b1 == 0:
            return b0.monic()

        _, r = b0.quo_rem(b1)
        if r == 0:
            return b1.monic()

        a0 = b1
        a1 = r


def omega(x, p, e):
    numerator = (pow(x, (p - 1) * p**(e-1), p**(2 * e - 1)) - 1) % p**(2 * e - 1)
    denominator = pow(p, e)
    ans = (int(numerator) // int(denominator)) % p**(e-1)
    return ans

coeff = []
for i, k in enumerate(ks):
    base = omega(69, rr, i+key1)
    target = omega(k, rr, i+key1)
    kk = target * gmpy2.invert(base, rr**(i + key1 - 1)) % rr**(i + key1 - 1)-key#多了个key要在这里减掉

    coeff.append(kk)

x = PolynomialRing(Zmod(n), 'x').gen()

f1 = 0
for i, k in enumerate(coeff):
    f1 += k*x**i

f1 = f1**127 - c1
f2 = x**65537 - c2

h = fast_polynomial_gcd(f1, f2)
m = -h[0] / h[1]
print(long_to_bytes(int(m)))

"""
b'XYCTF{ba76e13f-269e-4481-baf0-4a50ad17f891}'

参考：bi0sCTF 2024 - Giap’s Blog (giapppp.github.io)

LCG_and_HNP

花了一天多的时间认真啃了啃LCG

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
#sage
p=183640370379099520304414468793633666661
a=36108041497607074474855679331694767924
b=65925932211985158779695144876342622462
out=[34, 95, 100, 114, 16, 23, 17, 118, 115, 29, 73, 47, 12, 133, 78, 30, 30, 73, 87, 15, 85, 47, 20, 136, 6, 106, 74, 27, 116, 8]
c=6003642257316152022364486167163125577018867662610595926973616937741281227891381713617380

out.insert(0,0)
for i in range(len(out)):
    out[i] <<= 120
A = [1]
B = [0]
for i in range(1, len(out)-1):
    A.append(a*A[i-1] % p)
    B.append((a*B[i-1]+a*out[i]+b-out[i+1]) % p)
A = A[1:]
B = B[1:]

Ai = matrix(A)
Bi = matrix(B)
Mi = matrix.identity(len(out)-2)*p
K = ZZ(pow(2,128-8))
M = matrix.block([[Mi,ZZ(0),ZZ(0)],[Ai,ZZ(1),ZZ(0)],[Bi,ZZ(0),K]])

ll = M.LLL()[0]
l1 = ll[-2]
h1 = out[1]
s1 = l1+h1
#for s1=a*seed+b%m
seed = ((s1-b)*inverse_mod(a,p))%p
print(seed)
"""
98265113854859913689289076942864611315

土法炼钢的又一天

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
seed = 98265113854859913689289076942864611315

from Crypto.Util.number import *

class LCG:
    def __init__(self, seed, a, b, p):
        self.seed = seed
        self.a = a
        self.b = b
        self.p = p

    def next(self):
        self.seed = (self.seed * self.a + self.b) % self.p
        return self.seed >> (self.p.bit_length() - 8)
  
p=183640370379099520304414468793633666661
a=36108041497607074474855679331694767924
b=65925932211985158779695144876342622462
c=6003642257316152022364486167163125577018867662610595926973616937741281227891381713617380
  
out = []
lcg = LCG(seed, a, b, p)
for i in range(30):
    out.append(lcg.next())
key = ""
while 1:
    key += str(lcg.next())
    if int(key) >= c:
        break

print(long_to_bytes(c^int(key)))

"""
b'XYCTF{2h1_21_ZHi_5h0u_yU_zI_xI3_l@0}'

九转第八层压缩包密码

题目：

1
2
3
4
5
6
7
8
9
10
from Crypto.Util.number import bytes_to_long, getPrime
flag=b"password{xxxxx}"
p,q= getPrime(1024),getPrime(1024)
n = p * q
e = 65537
m = bytes_to_long(flag)
c = pow(m,e,n)
print("n=",n)
print("c=",c)
print("p^q=",p^q)

解答：

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
n= 22424440693845876425615937206198156323192795003070970628372481545586519202571910046980039629473774728476050491743579624370862986329470409383215065075468386728605063051384392059021805296376762048386684738577913496611584935475550170449080780985441748228151762285167935803792462411864086270975057853459586240221348062704390114311522517740143545536818552136953678289681001385078524272694492488102171313792451138757064749512439313085491407348218882642272660890999334401392575446781843989380319126813905093532399127420355004498205266928383926087604741654126388033455359539622294050073378816939934733818043482668348065680837
c= 1400352566791488780854702404852039753325619504473339742914805493533574607301173055448281490457563376553281260278100479121782031070315232001332230779334468566201536035181472803067591454149095220119515161298278124497692743905005479573688449824603383089039072209462765482969641079166139699160100136497464058040846052349544891194379290091798130028083276644655547583102199460785652743545251337786190066747533476942276409135056971294148569617631848420232571946187374514662386697268226357583074917784091311138900598559834589862248068547368710833454912188762107418000225680256109921244000920682515199518256094121217521229357
leak = 14488395911544314494659792279988617621083872597458677678553917360723653686158125387612368501147137292689124338045780574752580504090309537035378931155582239359121394194060934595413606438219407712650089234943575201545638736710994468670843068909623985863559465903999731253771522724352015712347585155359405585892
e = 65537
import gmpy2
from Crypto.Util.number import *

def pq_high_xor():
    stack = [(0, 0, "", "")]  # Initialize stack with starting parameters
    while stack:
        lp, lq, p, q = stack.pop()
        tp0 = int(p + (1024-lp) * "0", 2)
        tq0 = int(q + (1024-lq) * "0", 2)
        tp1 = int(p + (1024-lp) * "1", 2)
        tq1 = int(q + (1024-lq) * "1", 2)

        if tp0 * tq0 > n or tp1 * tq1 < n:
            continue
        if lp == leak_bits:
            pq.append(tp0)
            continue

        if xor[lp] == "1":
            stack.append((lp+1, lq+1, p + "0", q + "1"))
            stack.append((lp+1, lq+1, p + "1", q + "0"))
        else:
            stack.append((lp+1, lq+1, p + "0", q + "0"))
            stack.append((lp+1, lq+1, p + "1", q + "1"))

leak_bits = 1024
xor = bin(leak)[2:].zfill(1024)
pq = []
pq_high_xor()

p = int(pq[0])
q = int(pq[1])
phi = (p-1)*(q-1)
d = gmpy2.invert(e,phi)
print(long_to_bytes(pow(c,d,n)))

"""
b'password{pruning_algorithm}'

九转第九层压缩包密码

题目：

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

p = getPrime(512)
q = getPrime(512)
n = p * q
e = 65537

list = []
for _ in range(2):
    a, b = randint(0, 2**8), randint(0, 2**256)
    list.append(a * p + b * q)

password = b"xxxxx"
c = pow(bytes_to_long(password), e, n)
print(f'{n = }')
print(f'{c = }')
print(f'{list = }')

解答：

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
from Crypto.Util.number import *
import gmpy2
import math
n = 107803636687595025440095910573280948384697923215825513033516157995095253288310988256293799364485832711216571624134612864784507225218094554935994320702026646158448403364145094359869184307003058983513345331145072159626461394056174457238947423145341933245269070758238088257304595154590196901297344034819899810707
c = 46049806990305232971805282370284531486321903483742293808967054648259532257631501152897799977808185874856877556594402112019213760718833619399554484154753952558768344177069029855164888168964855258336393700323750075374097545884636097653040887100646089615759824303775925046536172147174890161732423364823557122495
list = [618066045261118017236724048165995810304806699407382457834629201971935031874166645665428046346008581253113148818423751222038794950891638828062215121477677796219952174556774639587782398862778383552199558783726207179240239699423569318, 837886528803727830369459274997823880355524566513794765789322773791217165398250857696201246137309238047085760918029291423500746473773732826702098327609006678602561582473375349618889789179195207461163372699768855398243724052333950197]
ab = list[1]-list[0]
l0 = list[0]
l1 = list[1]

for i in range(1,2**8):
    t1=l1*i
    for j in range(1,2**8):
        t0 = l0*j
        if gmpy2.gcd(abs(t1-t0),n) != 1:
            p = gmpy2.gcd(abs(t1-t0),n)
            break

e = 65537
q = n//p
phi = (p-1)*(q-1)
d = gmpy2.invert(e,phi)
print(long_to_bytes(pow(c,d,n)))

"""
b'game_over'
XYCTF-Crypto方向部分wp
http://example.com/2024/04/28/XYCTF/
作者
AlLvia
发布于
2024年4月28日
许可协议