把最近打的几个比赛记录在一起

黄河流域技能挑战赛2025

因式分解

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

from secret import flag,a,b,c

m = bytes_to_long(flag)

p = getPrime(256)

q = getPrime(256)

n = p * q

e = 65537

_q = int(bin(q)[2:][::-1] , 2)

c = pow(m,e,n)

print('n =',n)

print('c =',c)

'''

n = 7688109450918412752403544831281002390909833419780604228031807748258766149305710928557842935597759373483911172486806200079137977020089610947423466744079981

c = 6470273779347221033316093386019083111753019159457126878637258794718443144439812725263309232245307744208957171971247518708231996986359926490571921925899978

'''

assert a**3+b**3+c**3 == 3*a*b*c

gift = secert**3 - 9*secert + 8

print(gift)

assert 3*(p ^ _q) == a + b + c

\#16174454302590604301534105361719250538317088773024913985896374029052621214070408075926265229111851489902642328975085914458074453963086159246933939207642987161923181946601656883349077418380372857072224674380642689142603970810010050
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import string

from secret import hint

from secret import encrypt

import random

dicts = string.ascii_lowercase +"{=}"

key = (''.join([random.choice(dicts) for i in range(4)])) * 8

assert(len(hint) == 32)

assert(len(key) == 32)

cipher = encrypt(hint, key)

print(cipher)

\# cp=wmaunapgimjfpopeblvup=aywqygb

首先题目给了两个附件

1
_q = int(bin(q)[2:][::-1] , 2)

这里可以看到题目给我们的是q的二进制逆序值

1
3*(p ^ _q) == a + b + c

在看到这一步，如果我们知道p^_q的值我们就可以通过剪枝来求到flag了，那么接下来就是要求a+b+c的值

这里先说我自己的解法（感觉算非预期XD）

1
gift = secert**3 - 9*secert + 8

我们知道gift的值，那么就可以求出secret的大小

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
from decimal import Decimal, getcontext

def find_secret(gift):

  getcontext().prec = 100  

  

  

  

  d_gift = Decimal(gift)

  

  

  secret_approx = d_gift ** (Decimal(1)/Decimal(3))

  

  

  secret = round(secret_approx)

  

  

  calculated_gift = secret**3 - 9*secret + 8

  

  if calculated_gift == gift:

    return secret

  else:

    for delta in [-1, 1, -2, 2, -3, 3]:

      test_secret = secret + delta

      if test_secret**3 - 9*test_secret + 8 == gift:

        return test_secret

    raise ValueError("Exact integer solution not found")

gift = 16174454302590604301534105361719250538317088773024913985896374029052621214070408075926265229111851489902642328975085914458074453963086159246933939207642987161923181946601656883349077418380372857072224674380642689142603970810010050

secret = find_secret(gift)

print(f"{secret}")
#25289672915296952421286820568694528489788342353673740247988495109991492893326

这里的secret是254bit与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
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
from Crypto.Util.number import *

import sys

sys.setrecursionlimit(1500)

pxorq = 25289672915296952421286820568694528489788342353673740247988495109991492893326

n = 7688109450918412752403544831281002390909833419780604228031807748258766149305710928557842935597759373483911172486806200079137977020089610947423466744079981

c = 6470273779347221033316093386019083111753019159457126878637258794718443144439812725263309232245307744208957171971247518708231996986359926490571921925899978

e = 65537

pxorq = str(bin(pxorq)[2:]).zfill(256)

 

def find(ph,qh,pl,ql):

  l = len(ph)

  tmp0 = ph + (256-2*l)*"0" + pl

  tmp1 = ph + (256-2*l)*"1" + pl

  tmq0 = qh + (256-2*l)*"0" + ql

  tmq1 = qh + (256-2*l)*"1" + ql

  if(int(tmp0,2)*int(tmq0,2) > n):

    return 

  if(int(tmp1,2)*int(tmq1,2) < n):

    return

  if(int(pl,2)*int(ql,2) % (2**(l-1)) != n % (2**(l-1))):

    return

  if(l == 128):

    pp0 = int(tmp0,2)

    if(n % pp0 == 0):

      pf = pp0

      qf = n//pp0

      phi = (pf-1)*(qf-1)

      d = inverse(e,phi)

      m1 = pow(c,d,n)

      print(long_to_bytes(m1))

      exit()

  else:

    if(pxorq[l] == "1" and pxorq[255-l] == "1"):

      find(ph+"1",qh+"0","1"+pl,"0"+ql)

      find(ph+"0",qh+"0","1"+pl,"1"+ql)

      find(ph+"1",qh+"1","0"+pl,"0"+ql)

      find(ph+"0",qh+"1","0"+pl,"1"+ql)

    elif(pxorq[l] == "1" and pxorq[255-l] == "0"):

      find(ph+"1",qh+"0","0"+pl,"0"+ql)

      find(ph+"0",qh+"0","0"+pl,"1"+ql)

      find(ph+"1",qh+"1","1"+pl,"0"+ql)

      find(ph+"0",qh+"1","1"+pl,"1"+ql)

    elif(pxorq[l] == "0" and pxorq[255-l] == "1"):

      find(ph+"0",qh+"0","1"+pl,"0"+ql)

      find(ph+"0",qh+"1","0"+pl,"0"+ql)

      find(ph+"1",qh+"0","1"+pl,"1"+ql)

      find(ph+"1",qh+"1","0"+pl,"1"+ql)

    elif(pxorq[l] == "0" and pxorq[255-l] == "0"):

      find(ph+"0",qh+"0","0"+pl,"0"+ql)

      find(ph+"1",qh+"0","0"+pl,"1"+ql)

      find(ph+"0",qh+"1","1"+pl,"0"+ql)

      find(ph+"1",qh+"1","1"+pl,"1"+ql)

find("1","1","1","1")
#flag{80a59062-9bbf-99a3-6af0-a24e94032163}

预期的解法肯定是要我们求出hint先

我们可以先通过爆破四字节key+猜测一下’secret’在字符串中进行判断

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
from itertools import product

dicts = "abcdefghijklmnopqrstuvwxyz{=}"
cipher = "cp=wmaunapgimjfpopeblvup=aywqygb"



for key in product(dicts, repeat=4):
    key = ''.join(key) * 8
    plain = ''
    for i in range(len(cipher)):
        c = dicts.index(cipher[i])
        k = dicts.index(key[i])
        p = (c - k) % 29
        plain += dicts[p]
    if "secret" in plain:
        print("Key:", key[:4])
        print("Plaintext:", plain)
        break

# tellasecret{a=secert}keepsilentt

这里我们知道a=secert，这里的a可以通过上述的方法求出，那么我们还要求出b，c

我们先移项 a3 + b3 + c3 − 3abc = 0 那么就有 a3 + b3 + c3 − 3abc = (a + b + c)(a2 + b2 + c2 − ab − bc − ca) = 0 这里a + b + c显然是不可能为0的，那么只有(a2 + b2 + c2 − ab − bc − ca)为0

这里不难想到利用平方差公，将上式乘2，即 (2a2 + 2b2 + 2c2 − 2ab − 2bc − 2ca) = 0

(a − b)2 + (b − c)2 + (c − a)2 = 0

到这里b,c也就求出了，只有当a=b=c的时候等式成立

1
3*(p ^ _q) == a + b + c

那么这里的p^_q可解

sandwitch

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

import gmpy2

flag = b'flag{fake_flag}'

assert len(flag) == 39

p = getPrime(512)

q = getPrime(512)

n = p * q

e = 0x3

pad1 = b'easy_problem'

pad2 = b'How_to_solve_it'

c = pow(bytes_to_long(pad1 + flag + pad2),e,n)

print(f'n = {n}')

print(f'c = {c}')

'''

n = 130210658110511504736422597261591182174531847806532340762131145212035478695205314931974421838392310731226415266775095601890938846830080329061111533796518633011922277343217149648494987341818402753017296362015915834670450122261511337212801488239810623226740266516836721952886027130703886460578247562781194524199

c = 58274335440051115211211273605191310114692293785750437685473044454042062899661976407492451518086227780147882738264722645944582899451063113444881286175099872016956825274378613983870549046907444680021237171113596116147511706486372974792692071549068969896395366667516390709069131700584308236332248449116109156503

'''

c ≡ (pad1 + flag + pad2) mod  n

这里在看到题目给出的条件

1
2
3
flag_len = 39 
pad2 = b'How_to_solve_it'
pad2_len = 15

那么我们就知道了pad1和pad2的长度

上式就可以变换为 c ≡ (pad154 + flag15 + pad2) mod  n 然后我们直接打cooper就可以

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 gmpy2

n = 130210658110511504736422597261591182174531847806532340762131145212035478695205314931974421838392310731226415266775095601890938846830080329061111533796518633011922277343217149648494987341818402753017296362015915834670450122261511337212801488239810623226740266516836721952886027130703886460578247562781194524199

c = 58274335440051115211211273605191310114692293785750437685473044454042062899661976407492451518086227780147882738264722645944582899451063113444881286175099872016956825274378613983870549046907444680021237171113596116147511706486372974792692071549068969896395366667516390709069131700584308236332248449116109156503

pad1 = b'easy_problem'

pad2 = b'How_to_solve_it'

pad1 = bytes_to_long(pad1)

pad2 = bytes_to_long(pad2)

PR.<x> = PolynomialRing(Zmod(n))

f = (pad1*256**54+x*256**15+pad2)^3-c

f = f.monic()

res = f.small_roots(X=256^39,beta=1,epsilon=0.04)

if(res != []):

  print(long_to_bytes(int(res[0])))
 #b'flag{A_C0pper5mi1tH_4Ues7iOn_SplIt_Pad}'

这里还有另一种解法，是在SHCTF中学到的

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

n = 130210658110511504736422597261591182174531847806532340762131145212035478695205314931974421838392310731226415266775095601890938846830080329061111533796518633011922277343217149648494987341818402753017296362015915834670450122261511337212801488239810623226740266516836721952886027130703886460578247562781194524199

c = 58274335440051115211211273605191310114692293785750437685473044454042062899661976407492451518086227780147882738264722645944582899451063113444881286175099872016956825274378613983870549046907444680021237171113596116147511706486372974792692071549068969896395366667516390709069131700584308236332248449116109156503

e = 3

pad1 = b'easy_problem'  

flag_len = 39  

pad2 = b'How_to_solve_it'  

A = bytes_to_long(pad1)

C = bytes_to_long(pad2)

B = 256 ** len(pad2)  

shift = (flag_len + len(pad2)) * 8 

A_shift = A * (256 ** (flag_len + len(pad2)))

R.<x> = PolynomialRing(Zmod(n))

f = (A_shift + x * B + C)^e - c

f = f.monic()

X = 2^(flag_len * 8)  

beta = 0.9

epsilon = 0.03

roots = f.small_roots(X=X, beta=beta, epsilon=epsilon)

if roots:

  flag = long_to_bytes(int(roots[0]))

  print(flag)

else:

  print("No roots found")

#flag{A_C0pper5mi1tH_4Ues7iOn_SplIt_Pad}

Lattice

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

from Crypto.Cipher import AES

import os

from secret import flag

import numpy as np

def gen(q, n, N, sigma):

  t = np.random.randint(0, high=q // 2, size=n)

  s = np.concatenate([np.ones(1, dtype=np.int32), t])

  A = np.random.randint(0, high=q // 2, size=(N, n))

  e = np.round(np.random.randn(N) * sigma**2).astype(np.int32) % q

  b = ((np.dot(A, t) + e).reshape(-1, 1)) % q

  P = np.hstack([b, -A])

  return P, s

def enc(P, M, q):

  N = P.shape[0]

  n = len(M)

  r = np.random.randint(0, 2, (n, N))

  Z = np.zeros((n, P.shape[1]), dtype=np.int32)

  Z[:, 0] = 1

  C = np.zeros((n, P.shape[1]), dtype=np.int32)

  for i in range(n):

    C[i] = (np.dot(P.T, r[i]) + (np.floor(q / 2) * Z[i] * M[i])) % q

  return C

q = 127

n = 3

N = int(1.1 * n * np.log(q))

sigma = 1.0

P, s = gen(q, n, N, sigma)

def prep(s):

  return np.array([int(b) for char in s for b in f"{ord(char):08b}"], dtype=np.int32)

C = enc(P, prep(hint), q)

P = P.tolist()

C = C.tolist()

print(f"{P=}")

print(f"{C=}")

'''

P=[[87, -27, -52, -29], [57, -41, -24, -60], [76, -17, -55, -37], [75, -46, -33, -21], [121, -55, -33, -34], [47, -4, -34, -45], [112, -33, -44, -16], [74, -44, -5, -25], [20, -21, -16, -49], [89, -21, -54, -24], [18, -23, -53, -1], [35, -40, -4, -29], [105, -54, -2, -8], [44, -24, -43, -36], [111, -15, -15, -54]]

C=[[24, 75, 81, 85], [24, 14, 85, 102], [115, 1, 5, 21], [58, 118, 104, 77], [65, 42, 101, 103], [33, 38, 50, 67], [7, 81, 38, 58], [117, 101, 54, 11], [44, 29, 81, 8], [59, 114, 70, 121], [62, 13, 9, 105], [11, 43, 97, 23], [39, 82, 75, 97], [122, 113, 14, 30], [70, 102, 116, 5], [58, 44, 61, 20], [73, 119, 59, 28], [119, 68, 57, 122], [61, 91, 83, 44], [103, 29, 1, 73], [47, 60, 120, 125], [17, 126, 14, 21], [104, 8, 78, 123], [72, 121, 54, 74], [48, 104, 49, 66], [72, 56, 27, 69], [34, 110, 41, 54], [33, 54, 74, 44], [70, 65, 11, 113], [122, 3, 69, 35], [58, 7, 39, 64], [59, 106, 49, 66], [77, 92, 87, 92], [95, 21, 96, 83], [67, 55, 30, 73], [99, 54, 18, 90], [101, 102, 126, 107], [81, 46, 104, 83], [38, 24, 94, 60], [114, 105, 76, 97], [22, 115, 20, 67], [40, 72, 110, 65], [111, 92, 106, 117], [5, 123, 21, 96], [41, 14, 23, 114], [113, 75, 43, 65], [56, 3, 61, 48], [40, 101, 16, 114], [42, 84, 95, 13], [36, 110, 91, 107], [4, 13, 60, 74], [24, 80, 125, 76], [123, 26, 27, 119], [31, 87, 6, 123], [61, 106, 73, 120], [66, 10, 36, 65], [91, 38, 46, 9], [121, 20, 106, 48], [123, 21, 78, 27], [22, 74, 55, 110], [47, 49, 118, 76], [30, 10, 16, 118], [43, 19, 52, 61], [100, 9, 37, 35], [20, 102, 111, 94], [116, 63, 55, 43], [13, 110, 42, 14], [46, 65, 71, 28], [82, 5, 76, 74], [86, 34, 117, 84], [28, 44, 82, 50], [76, 79, 77, 11], [68, 39, 51, 89], [83, 93, 95, 2], [54, 108, 101, 82], [99, 90, 122, 37], [16, 92, 79, 12], [67, 86, 24, 36], [80, 94, 106, 59], [50, 56, 95, 98], [33, 68, 89, 40], [74, 124, 14, 82], [88, 93, 54, 93], [51, 17, 124, 31], [17, 17, 45, 35], [113, 71, 76, 44], [48, 6, 120, 4], [36, 91, 108, 11], [2, 41, 58, 72], [42, 59, 51, 81], [73, 22, 79, 27], [85, 35, 29, 98], [76, 76, 37, 22], [82, 29, 42, 27], [75, 114, 37, 106], [40, 69, 53, 73], [39, 44, 33, 121], [94, 85, 92, 54], [91, 77, 124, 46], [108, 31, 101, 84], [35, 33, 97, 45], [99, 32, 17, 14], [1, 66, 11, 35], [78, 100, 95, 81], [73, 49, 14, 37], [70, 9, 107, 2], [84, 98, 92, 62], [123, 87, 87, 110], [3, 81, 111, 28], [20, 2, 91, 37], [93, 101, 77, 93], [27, 16, 31, 105], [95, 81, 87, 17], [10, 103, 21, 102], [81, 57, 118, 82], [15, 92, 60, 71], [16, 84, 126, 49], [35, 26, 2, 120], [70, 86, 45, 9], [29, 8, 40, 66], [99, 77, 14, 9], [12, 70, 50, 52], [21, 21, 85, 54], [91, 94, 100, 85], [9, 42, 47, 14], [117, 55, 17, 99], [53, 45, 4, 72], [49, 10, 27, 121], [108, 61, 73, 42], [121, 42, 41, 71], [49, 63, 50, 117], [5, 78, 24, 101], [0, 117, 21, 46], [90, 43, 47, 32], [74, 85, 118, 84], [13, 73, 18, 66], [95, 24, 120, 18], [94, 21, 111, 34], [66, 68, 80, 21], [102, 49, 57, 55], [25, 85, 107, 98], [8, 18, 88, 12], [18, 6, 86, 82], [18, 91, 126, 115], [26, 11, 30, 35], [88, 78, 76, 74], [51, 75, 76, 15], [60, 24, 72, 27], [91, 72, 44, 104], [84, 113, 39, 116], [41, 83, 91, 74], [84, 17, 94, 119], [46, 95, 85, 5], [109, 58, 71, 42], [126, 29, 114, 73], [27, 70, 7, 125], [121, 66, 97, 111], [8, 21, 10, 57], [15, 62, 65, 8], [101, 79, 32, 74], [69, 42, 38, 58], [65, 81, 72, 16], [20, 81, 1, 126], [91, 111, 69, 33], [56, 84, 65, 66], [47, 78, 43, 100], [43, 90, 80, 25], [46, 55, 10, 60], [116, 110, 49, 116], [72, 115, 38, 104], [79, 43, 74, 106], [86, 113, 84, 76], [102, 2, 119, 3], [126, 25, 83, 44], [37, 83, 46, 40], [13, 75, 101, 101], [76, 93, 3, 63], [69, 9, 84, 37], [103, 47, 106, 80], [72, 104, 85, 19], [124, 118, 34, 81], [57, 25, 52, 119], [44, 56, 63, 90], [123, 46, 124, 31], [19, 116, 23, 77], [126, 78, 37, 93], [34, 95, 43, 98], [37, 90, 32, 97], [106, 8, 80, 8], [90, 5, 113, 68], [99, 40, 39, 18], [90, 37, 48, 45], [56, 13, 76, 6], [68, 33, 52, 102], [62, 45, 29, 123], [100, 21, 73, 92], [92, 18, 118, 23], [84, 86, 42, 83], [107, 8, 71, 52], [114, 106, 78, 85], [10, 120, 115, 119], [27, 49, 124, 16], [65, 40, 48, 37], [69, 42, 8, 29], [35, 39, 55, 102], [58, 19, 41, 75], [17, 2, 113, 12], [8, 34, 72, 75], [91, 32, 19, 52], [62, 50, 109, 78], [9, 115, 35, 50], [42, 83, 78, 41], [34, 94, 97, 58], [56, 73, 25, 115], [55, 12, 16, 86], [97, 95, 30, 92], [47, 105, 70, 68], [50, 18, 51, 23], [46, 57, 80, 29], [4, 66, 123, 24], [55, 53, 26, 36], [71, 59, 104, 91], [94, 3, 1, 34], [57, 8, 85, 102], [89, 73, 115, 25], [13, 38, 81, 76], [104, 30, 81, 104], [55, 101, 95, 101], [69, 65, 5, 11], [123, 105, 84, 125], [38, 110, 4, 28], [112, 115, 92, 71], [90, 120, 112, 39], [50, 18, 107, 71], [95, 63, 118, 93], [93, 111, 59, 55], [17, 15, 2, 88], [78, 126, 37, 12], [56, 112, 53, 12], [65, 34, 82, 100], [9, 94, 72, 99], [78, 76, 43, 91], [7, 88, 107, 31], [43, 91, 97, 4], [113, 112, 36, 15], [8, 97, 23, 84], [65, 92, 31, 63], [54, 38, 119, 103], [89, 50, 57, 50], [61, 37, 87, 0], [21, 35, 44, 22], [20, 32, 95, 116], [10, 94, 103, 84], [59, 29, 7, 50], [98, 33, 87, 33], [7, 96, 36, 67], [85, 10, 35, 98], [65, 49, 19, 62], [56, 67, 14, 91], [30, 49, 111, 77], [121, 49, 108, 119], [89, 67, 115, 69], [65, 8, 0, 82], [117, 57, 117, 23], [23, 38, 2, 98], [60, 28, 94, 93], [23, 65, 8, 114], [121, 105, 122, 40], [120, 12, 21, 112], [55, 51, 2, 77], [48, 41, 113, 62], [66, 82, 117, 119], [4, 15, 5, 21], [41, 14, 12, 80], [23, 61, 106, 16], [23, 53, 122, 68], [6, 54, 5, 101], [69, 49, 7, 79], [17, 70, 64, 88], [103, 30, 76, 31], [108, 82, 90, 109], [55, 56, 113, 37], [93, 99, 126, 44], [1, 46, 105, 124], [55, 54, 35, 115], [0, 89, 53, 97], [67, 111, 107, 80], [92, 122, 40, 64], [75, 2, 126, 118], [90, 84, 43, 74], [101, 69, 60, 17], [104, 10, 4, 122], [94, 4, 115, 91], [15, 11, 111, 105], [9, 7, 32, 101], [77, 18, 55, 56], [66, 7, 117, 108], [116, 121, 33, 66], [32, 41, 83, 125], [60, 52, 70, 58], [125, 54, 93, 15], [70, 19, 10, 58], [83, 94, 61, 126], [95, 85, 80, 44], [25, 89, 117, 74], [12, 17, 63, 87], [118, 80, 96, 26], [6, 97, 79, 38], [97, 3, 107, 95], [7, 82, 106, 92], [83, 100, 119, 95], [81, 26, 99, 56], [25, 60, 51, 122], [56, 18, 22, 84], [9, 72, 107, 114], [80, 97, 92, 52], [108, 47, 58, 46], [9, 47, 7, 47], [115, 68, 91, 7], [14, 120, 87, 122], [97, 15, 40, 79], [5, 92, 85, 93], [4, 97, 73, 63], [25, 22, 92, 108], [88, 4, 34, 86], [0, 43, 21, 57], [67, 90, 36, 50], [15, 126, 37, 12], [92, 73, 96, 71], [76, 107, 27, 115], [79, 8, 68, 55], [38, 12, 120, 126], [54, 46, 7, 69], [72, 114, 93, 60], [59, 98, 27, 102], [50, 76, 87, 19], [77, 107, 29, 40], [36, 73, 21, 123], [36, 89, 82, 74], [24, 73, 118, 86], [58, 89, 115, 106], [12, 27, 33, 72], [28, 94, 21, 26], [0, 79, 48, 110], [72, 62, 82, 57], [65, 84, 114, 97], [80, 68, 52, 52], [119, 35, 103, 101], [10, 67, 68, 69], [101, 17, 54, 40], [98, 46, 21, 42], [30, 39, 56, 118], [27, 33, 77, 114], [66, 74, 61, 63], [23, 13, 14, 47], [88, 30, 122, 119], [15, 58, 55, 52], [56, 27, 47, 45], [119, 95, 59, 14], [84, 69, 5, 83], [21, 35, 39, 36], [10, 92, 68, 17], [79, 67, 111, 38], [36, 1, 4, 117], [117, 30, 5, 7], [112, 15, 115, 123], [54, 47, 18, 93], [102, 111, 3, 68], [91, 91, 5, 44], [123, 118, 57, 32], [12, 121, 31, 103], [114, 52, 105, 12], [100, 28, 117, 102], [51, 42, 12, 124], [47, 1, 42, 47], [28, 3, 22, 100], [103, 105, 119, 24], [101, 59, 13, 78], [79, 36, 61, 54], [11, 46, 75, 116], [31, 73, 118, 0], [92, 32, 0, 124], [77, 85, 25, 90], [29, 21, 74, 7], [3, 66, 11, 8], [112, 91, 50, 53], [45, 113, 99, 123], [35, 65, 85, 22], [108, 99, 42, 1], [103, 113, 116, 72], [125, 74, 112, 24], [75, 79, 80, 12], [83, 44, 94, 86], [64, 20, 0, 8], [104, 126, 31, 120], [85, 75, 61, 74], [36, 93, 36, 102], [70, 54, 101, 83], [90, 46, 109, 83], [112, 126, 114, 23], [16, 123, 97, 62], [118, 86, 108, 53], [99, 18, 2, 18], [103, 3, 38, 8], [99, 49, 123, 81], [37, 75, 89, 53], [34, 77, 27, 122], [29, 8, 40, 66], [119, 13, 64, 83], [4, 108, 116, 121], [49, 87, 1, 92], [15, 63, 80, 62], [27, 81, 100, 83], [7, 90, 16, 0], [13, 50, 61, 65], [51, 64, 76, 5], [55, 100, 106, 66], [52, 102, 105, 2], [49, 34, 89, 116], [24, 55, 11, 27], [91, 48, 73, 38], [27, 5, 1, 126], [66, 55, 80, 19], [52, 118, 104, 43], [36, 1, 111, 60], [65, 4, 34, 17], [54, 22, 0, 39], [52, 30, 64, 62], [26, 40, 32, 86], [93, 71, 41, 47], [77, 23, 15, 9], [11, 20, 51, 31], [64, 50, 37, 50], [17, 49, 80, 37], [119, 115, 115, 50], [20, 86, 27, 5], [101, 65, 17, 78], [56, 25, 125, 56], [16, 118, 2, 96], [114, 108, 69, 121], [14, 37, 76, 101], [113, 124, 121, 82], [43, 120, 35, 94], [82, 67, 23, 43], [9, 79, 47, 122], [39, 28, 110, 31], [35, 48, 27, 16], [72, 8, 115, 66], [54, 46, 122, 19], [77, 77, 30, 74], [58, 63, 81, 96], [6, 122, 75, 63], [115, 31, 119, 110], [82, 86, 89, 1], [79, 100, 6, 110], [117, 67, 15, 13], [4, 15, 63, 0], [106, 108, 122, 107], [34, 72, 0, 114], [20, 0, 32, 56], [121, 104, 66, 3], [86, 28, 76, 84], [85, 9, 60, 45], [95, 80, 78, 65], [39, 85, 50, 49], [42, 103, 36, 90], [70, 99, 116, 117], [34, 15, 40, 52], [24, 49, 19, 31], [98, 90, 95, 89], [63, 45, 40, 77], [114, 14, 30, 106], [10, 35, 116, 9], [103, 111, 112, 16], [71, 112, 71, 32], [77, 31, 105, 64], [84, 87, 24, 67], [1, 27, 123, 57], [104, 29, 87, 123], [110, 39, 67, 7], [28, 70, 108, 113], [96, 9, 101, 36], [13, 28, 6, 13], [69, 81, 89, 26], [79, 113, 77, 91], [112, 62, 104, 117], [109, 95, 55, 83], [78, 68, 98, 14], [73, 79, 96, 12], [108, 39, 97, 49], [27, 111, 106, 100], [82, 70, 9, 36], [48, 31, 90, 70], [99, 92, 45, 35], [55, 100, 31, 37], [75, 17, 69, 35], [12, 38, 119, 112], [103, 34, 63, 76], [26, 19, 91, 111], [74, 122, 12, 78], [64, 117, 16, 60], [2, 97, 122, 106], [62, 79, 56, 30], [71, 47, 13, 22], [38, 78, 116, 16], [87, 28, 94, 76], [77, 126, 94, 116], [83, 46, 104, 90], [5, 95, 13, 26], [47, 10, 46, 115], [82, 19, 91, 70], [111, 72, 49, 65], [18, 103, 59, 72], [17, 37, 56, 24], [19, 120, 24, 64], [28, 40, 11, 20], [18, 19, 80, 62], [37, 11, 74, 14], [109, 97, 75, 72], [116, 65, 52, 121], [95, 63, 82, 122], [88, 93, 54, 93], [77, 30, 65, 121], [99, 121, 42, 87], [62, 52, 44, 6], [79, 60, 55, 4], [96, 64, 6, 20], [94, 114, 90, 8], [123, 98, 29, 27], [116, 84, 31, 80], [9, 77, 45, 45], [120, 33, 63, 15], [51, 44, 66, 25], [2, 46, 72, 94], [107, 113, 50, 46], [115, 64, 126, 85], [64, 10, 28, 78], [84, 112, 64, 103], [59, 114, 15, 82], [65, 122, 104, 89], [113, 122, 21, 11], [69, 106, 19, 78], [42, 93, 125, 0], [7, 123, 82, 70], [103, 114, 62, 92], [15, 30, 78, 114], [4, 78, 111, 60], [40, 80, 34, 55], [3, 87, 120, 27], [122, 64, 3, 122], [24, 49, 31, 81], [26, 43, 100, 19], [52, 78, 2, 97], [116, 45, 15, 33], [21, 119, 92, 86], [28, 118, 71, 24], [106, 15, 0, 79], [36, 4, 52, 73], [22, 43, 8, 60], [96, 22, 9, 100], [19, 64, 26, 96], [97, 61, 22, 39], [6, 112, 76, 38], [58, 6, 97, 94], [103, 87, 87, 101], [17, 49, 80, 37], [117, 33, 26, 8], [59, 108, 78, 91], [113, 28, 30, 44], [119, 78, 72, 20], [49, 101, 77, 2], [26, 18, 35, 7], [34, 38, 99, 37], [45, 52, 90, 27], [108, 31, 118, 67], [3, 37, 29, 88], [111, 96, 12, 111], [91, 111, 106, 100], [52, 78, 117, 80], [14, 51, 87, 0], [1, 52, 116, 1], [117, 2, 33, 48], [57, 0, 48, 34], [59, 14, 84, 63], [82, 83, 8, 82], [58, 100, 32, 33], [75, 29, 112, 103], [0, 49, 45, 54], [94, 9, 51, 110], [54, 61, 27, 47], [88, 89, 23, 37], [73, 43, 0, 32], [123, 6, 35, 78], [73, 72, 119, 64], [81, 46, 11, 102], [42, 124, 47, 8], [50, 66, 3, 40], [116, 7, 51, 20], [47, 112, 99, 7], [42, 37, 86, 89], [18, 74, 78, 101], [57, 85, 75, 7], [26, 90, 35, 10], [72, 126, 10, 77], [55, 12, 5, 78], [37, 87, 85, 96], [91, 9, 114, 68], [79, 76, 44, 20], [84, 52, 63, 56], [95, 9, 22, 117], [96, 38, 50, 67], [43, 114, 45, 56], [94, 21, 74, 107], [92, 82, 81, 71], [40, 10, 10, 90], [20, 18, 15, 56], [72, 2, 30, 22], [50, 31, 123, 20], [85, 40, 115, 115], [93, 1, 48, 47], [111, 118, 45, 34], [9, 122, 37, 121], [60, 27, 77, 41], [122, 38, 22, 39], [115, 66, 74, 126], [77, 67, 90, 78], [96, 3, 53, 52], [5, 26, 120, 101], [45, 100, 72, 6], [106, 56, 87, 77], [52, 68, 102, 95], [1, 13, 36, 33], [58, 27, 35, 8], [52, 5, 38, 35], [102, 82, 63, 47], [24, 71, 119, 43], [11, 36, 90, 13], [11, 93, 27, 23], [4, 107, 26, 125], [85, 9, 5, 13], [116, 25, 55, 119], [73, 82, 73, 2], [40, 123, 77, 41], [10, 98, 51, 111], [23, 79, 120, 54], [56, 18, 22, 84], [61, 115, 51, 109], [33, 5, 12, 121], [8, 81, 35, 70], [22, 39, 103, 2], [38, 74, 66, 126], [83, 20, 117, 85], [8, 32, 91, 98], [37, 31, 94, 119], [7, 30, 45, 43], [68, 16, 124, 97], [86, 124, 37, 21], [29, 101, 15, 30], [27, 31, 52, 45], [47, 37, 102, 3], [117, 49, 54, 89], [48, 94, 126, 66], [42, 115, 63, 104], [14, 74, 6, 112], [68, 125, 4, 5], [66, 3, 78, 52], [108, 33, 6, 77], [77, 99, 16, 52], [61, 78, 73, 70], [108, 106, 124, 0], [23, 35, 119, 118], [125, 124, 37, 65], [69, 30, 61, 110], [77, 10, 120, 118], [53, 121, 24, 30], [87, 32, 29, 63], [54, 64, 1, 3], [16, 59, 104, 25], [30, 6, 59, 102], [43, 120, 35, 94], [89, 13, 69, 39], [87, 78, 100, 14], [83, 17, 14, 4], [24, 49, 31, 81], [73, 32, 72, 10], [0, 22, 61, 54], [81, 42, 70, 13], [108, 56, 52, 2], [25, 99, 116, 72], [66, 23, 18, 102], [121, 115, 47, 12], [96, 37, 123, 48], [64, 69, 4, 39], [78, 38, 124, 31], [27, 69, 10, 70], [5, 29, 2, 85], [30, 45, 56, 7], [31, 25, 120, 61], [36, 89, 89, 118], [98, 63, 18, 21], [121, 83, 36, 57], [60, 5, 86, 17], [121, 55, 117, 58], [12, 96, 4, 27], [119, 63, 124, 37], [96, 27, 45, 91], [42, 119, 8, 103], [104, 42, 68, 37], [104, 55, 41, 38], [120, 3, 50, 87], [120, 121, 20, 67], [58, 123, 50, 28], [103, 62, 58, 20], [97, 27, 89, 102], [7, 51, 56, 108], [73, 60, 10, 77], [56, 72, 103, 69], [101, 89, 18, 66], [115, 35, 80, 36], [98, 103, 39, 63], [29, 126, 67, 76], [27, 97, 15, 79], [36, 6, 17, 90], [126, 54, 101, 42], [115, 66, 74, 126], [78, 80, 62, 83], [60, 11, 31, 88], [16, 73, 108, 13]]

'''

key = os.urandom(16)

encrypted = AES.new(key=key, iv=iv, mode=AES.MODE_CBC).encrypt(b"".join([pad(i.encode(), 16) for i in flag]))

print(leak)

print(key)

print(encrypted)

'''

-3.257518803980229925210589904230583482986646342139415561576950148286382674434770529248486501793457710730252401258721482142654716015216299244487794967600132597049154513815052213387666360825101667524635777006510550117512116441539852315185793280311905620746025669520152068447372368293640072502196959919309286241

b'\x8fj\x94\x98-\x1fd\xd5\x89\xbe\xa9*Tu\x90\xb7'

b'\x9fT@\xbc\x82\x8esQ\x1e\xd8\x1d\xdb\x9b\xb4\xf8rU\xc8\xa0\xcb\xaf H\xa9.\x04\x1e\xd2\x92\x1f\x0fBja-\x965x\xa8@\xc9x\xf9\xaf\x87\xd1\xa5}\xfc\x1b\xe0#\xc3m\xc9\x8973\x1c\x1f\x13\x8f\xb2a\xae\xa9]\xb9\xc2\xe8\x83A\x80\x13g\xc9a\x1c<\x8a\x9c&\xd9\xbd\x06\xef\xba9\xb0\x03\x9f\x022\xc9\x13\x9a\xffXPG\xc6o\xc0\xeaV7)XG9L\x84N7U\xe3Wn0G\x8e\xd3\x04(\n\x08\xb9\x17\xe6\xf1\xaa\xb7\x8a@$\x16\x13\x06A\x00\xc9Z\xdf\x7fQ\xc9\x08\xb4\xf3P\xfcpe\xe2\xeb\x96\x0e(-\xde\x17\xd1\x01\x1c_\x82\x8b\x9fw\xc8\x86\xfbw\xb5\xf7\xd0\xc8\x1784\xe3?\x00\x0b.)\xb7\xbc\x8e{\xe0\xae\x8d$\x0f\x19\'\xb6\xee@d\x00\xd9\x84\x8c\x0e\xa3,\xc6a\xa3\xba*1\xfd<\xfd\x18\xd6\x9e\x8c4\x8e#\xfd\xbd&0R\xeddE,\xed\xb6\x1e\x00\x11\xa6K\xd3\x1dT\x8c5\x8e\x00\xea\x10\xe9\'u"B#\xa1#\xd8\xe3\xf5j\xbc\x94M\xda\xe3\xcb*\xf0W1\xa0\x80\x1d\xfc\xbfo\x01?(da\r\xb6\x86\xd0\x90\x88Z\xa1`B\x89\x89\x89\xb3v\xa5\xf0\xe0\x0c\x8e\xcc+P\xfc\xfd#\x83\xe9\x93\x96\n\xf2\xa5\xfb\xc3\xc5\xaa\x9e\x89\x93\xb6\xf5\xea\x8c%NY\xc3\x0eR\xfas\xa1\x13\xf2/*\xce\x8b_:_r\xeb\xbe\x0b\x8a\x8c\x97\x7f|m}\xae\xa9I\x95\xcc\xe7\x80\xa5yC4\x1f5\xa4P\xc5\xbf.\xf9V\xe8|\xbb\xc3\xcb\x98&\'JB\x99\x94\xc0\r$\x0b\xbe48u\xeb\xca\xa1\xfbb\xd8_R\x97\x8e\xaeI\xfc\xc2\xb2\xd2#@\xec\x16\xf1\xd7eCQ\x1cO\x13\xca\xb5\xd3\x1a\xb1\xf1_D\x80\x06\xa5\xbe\xbev\xbd\xd6\xbb\x9a\xc9x\x9cf:\xcb>\xa2\xe1\xcad\xde]aw\xa0\xdc\xb2\xb3{+\x85\x8d\x8b\xc5\rT\xcc\xd9X\xd5\x9b\r<\x99m\xb8b6s\xbfp\x0eo~\xe9&\xb2{\xbe\xee\x93\xd2N1\\\x94\x968IWO7\xcb\xb6e\x80\xf7\x9air\xb2~\x17\x1cF\x0f\x82T]RBX\xdex\x13\x85\xfa\xcd-\xce\xdc\xe4\xe5^\x99u\xb5\x01\xd0-\xc3C\xcd\xc4y6\xb7\x9d|L1\xe74\xf7\x8cH\xe9\xa9\xfav\n\xec;\xf2\xa2w\xfb\x13_b\r)z!\xa3\xc8\xa8\xc2\xd2\x10\x00\x11\x11\r\xb2&\xfb\x04&\x84">x6l[\x06n>\xa0\xbe\x9c`\xa7\x9e\xe0\xfb\x85\x91\xc4,\xcf\xac\xe11@a\xed3@\xfd}\x8e\xfaTp\xcb7\xe7\xbf\xd4\xe0~b\xd9\xe0<\xba\x81\xd4"e\xfc\x939|j#0H\x86\xf8\x0b\x03\xd2\xe8\xf5\xe55\xdc\xc8\x06\\\xb7)\xcc\x9b\'\xf12'

'''

其实题目变量名没设置好

1
encrypted = AES.new(key=key, iv=iv, mode=AES.MODE_CBC).encrypt(b"".join([pad(i.encode(), 16) for i in flag]))

这是关键点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
from Crypto.Cipher import AES

from Crypto.Util.Padding import unpad

key = b'\x8fj\x94\x98-\x1fd\xd5\x89\xbe\xa9*Tu\x90\xb7'

encrypted = b'\x9fT@\xbc\x82\x8esQ\x1e\xd8\x1d\xdb\x9b\xb4\xf8rU\xc8\xa0\xcb\xaf H\xa9.\x04\x1e\xd2\x92\x1f\x0fBja-\x965x\xa8@\xc9x\xf9\xaf\x87\xd1\xa5}\xfc\x1b\xe0#\xc3m\xc9\x8973\x1c\x1f\x13\x8f\xb2a\xae\xa9]\xb9\xc2\xe8\x83A\x80\x13g\xc9a\x1c<\x8a\x9c&\xd9\xbd\x06\xef\xba9\xb0\x03\x9f\x022\xc9\x13\x9a\xffXPG\xc6o\xc0\xeaV7)XG9L\x84N7U\xe3Wn0G\x8e\xd3\x04(\n\x08\xb9\x17\xe6\xf1\xaa\xb7\x8a@$\x16\x13\x06A\x00\xc9Z\xdf\x7fQ\xc9\x08\xb4\xf3P\xfcpe\xe2\xeb\x96\x0e(-\xde\x17\xd1\x01\x1c_\x82\x8b\x9fw\xc8\x86\xfbw\xb5\xf7\xd0\xc8\x1784\xe3?\x00\x0b.)\xb7\xbc\x8e{\xe0\xae\x8d$\x0f\x19\'\xb6\xee@d\x00\xd9\x84\x8c\x0e\xa3,\xc6a\xa3\xba*1\xfd<\xfd\x18\xd6\x9e\x8c4\x8e#\xfd\xbd&0R\xeddE,\xed\xb6\x1e\x00\x11\xa6K\xd3\x1dT\x8c5\x8e\x00\xea\x10\xe9\'u"B#\xa1#\xd8\xe3\xf5j\xbc\x94M\xda\xe3\xcb*\xf0W1\xa0\x80\x1d\xfc\xbfo\x01?(da\r\xb6\x86\xd0\x90\x88Z\xa1`B\x89\x89\x89\xb3v\xa5\xf0\xe0\x0c\x8e\xcc+P\xfc\xfd#\x83\xe9\x93\x96\n\xf2\xa5\xfb\xc3\xc5\xaa\x9e\x89\x93\xb6\xf5\xea\x8c%NY\xc3\x0eR\xfas\xa1\x13\xf2/*\xce\x8b_:_r\xeb\xbe\x0b\x8a\x8c\x97\x7f|m}\xae\xa9I\x95\xcc\xe7\x80\xa5yC4\x1f5\xa4P\xc5\xbf.\xf9V\xe8|\xbb\xc3\xcb\x98&\'JB\x99\x94\xc0\r$\x0b\xbe48u\xeb\xca\xa1\xfbb\xd8_R\x97\x8e\xaeI\xfc\xc2\xb2\xd2#@\xec\x16\xf1\xd7eCQ\x1cO\x13\xca\xb5\xd3\x1a\xb1\xf1_D\x80\x06\xa5\xbe\xbev\xbd\xd6\xbb\x9a\xc9x\x9cf:\xcb>\xa2\xe1\xcad\xde]aw\xa0\xdc\xb2\xb3{+\x85\x8d\x8b\xc5\rT\xcc\xd9X\xd5\x9b\r<\x99m\xb8b6s\xbfp\x0eo~\xe9&\xb2{\xbe\xee\x93\xd2N1\\\x94\x968IWO7\xcb\xb6e\x80\xf7\x9air\xb2~\x17\x1cF\x0f\x82T]RBX\xdex\x13\x85\xfa\xcd-\xce\xdc\xe4\xe5^\x99u\xb5\x01\xd0-\xc3C\xcd\xc4y6\xb7\x9d|L1\xe74\xf7\x8cH\xe9\xa9\xfav\n\xec;\xf2\xa2w\xfb\x13_b\r)z!\xa3\xc8\xa8\xc2\xd2\x10\x00\x11\x11\r\xb2&\xfb\x04&\x84">x6l[\x06n>\xa0\xbe\x9c`\xa7\x9e\xe0\xfb\x85\x91\xc4,\xcf\xac\xe11@a\xed3@\xfd}\x8e\xfaTp\xcb7\xe7\xbf\xd4\xe0~b\xd9\xe0<\xba\x81\xd4"e\xfc\x939|j#0H\x86\xf8\x0b\x03\xd2\xe8\xf5\xe55\xdc\xc8\x06\\\xb7)\xcc\x9b\'\xf12'

iv = encrypted[:16]

ciphertext = encrypted[16:]

cipher = AES.new(key, AES.MODE_CBC, iv)

decrypted = unpad(cipher.decrypt(ciphertext), 16)

print("Decrypted flag:", decrypted.decode())

Happy*

比赛的时候没解出来

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
\#!/usr/bin/env python

\# Simplify the problem by happy4321

import os, utils

from secret import flag

assert flag.startswith(b'flag{') and flag.endswith(b'}')

seed = int(os.urandom(16).hex(), 16)

gen = utils.Gen(seed)

msg = b'Happy4321: ' + flag

enc = bytes(m ^ next(gen) for m in msg).hex()

print(enc)

\# cd1dd7c7a9cfe3c0067ff64694e64c38aa759c81d1c8f48cf6f7ee1df2d1e58584da52644ea56bd24dadca6bd5a6899a92b118f57de2529670264d48
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
class Gen:

  def __init__(self, state):

    self.nbits = 128

    self.state = state & ((1 << self.nbits) - 1)

    self.mask = 109908700282042807039366676242995409413

  def func0(self, steps=1):

    for _ in range(steps):

      res = self.state & self.mask

      bit = sum([(res >> i) & 1 for i in range(self.nbits)]) & 1

      self.state = ((self.state << 1) ^ bit) & ((1 << self.nbits) - 1)

    return bit

  def __next__(self):

    out = 0

    for _ in range(8):

      bit = self.func0(2023)

      out = (out << 1) ^ bit

    return out

轩辕杯2025

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

from gmpy2 import *

from random import choice

flag = b"flag{****************************}"

m = bytes_to_long(flag)

p = getPrime(256)

q = getPrime(256)

n = p*q

d = getPrime(130)

phi = (p-1)*(q-1)

e = invert(d, phi)

c = pow(m, e, n)

print(f'n = {n}')

print(f'c = {c}')

\# print(f'e = {e}')

def gen(bits):

  while True:

    p = 2

    while p.bit_length() < bits:

      p *= choice(sieve_base)

    if isPrime(p - 1):

      return p - 1

p1 = gen(256)

q1 = gen(256)

n1 = p1 * q1

c1 = p1 + e

print(f'n1 = {n1}')

print(f'c1 = {c1}')

'''

n = 10037257627154486608196774801095855162090578704439233219876490744017222686494761706171113312036056644757212254824459536550416291797454693336043852190135363

c = 6723803125309437675713195914771839852631361554645954138639198200804046718848872479140347495288135138109762940384847808522874831433140182790750890982139835

n1 = 151767047787614712083974720416865469041528766980347881592164779139223941980832935534609228636599644744364450753148219193621511377088383418096756216139022880709

c1 = 6701513605196718137208327145211106525052740242222174201768345944717813148931922063338128366155730924516887607710111701686062781667128443135522927486682574

'''


这里观察到d是只有130bit的符合boneh-durfee，现在还需要求出e

1
c1 = p1 + e

我们知道c1，现在只需要求出p1即可求出e

很明显我们可以用Williams的p+1算法分解

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
from Cryptodome.Util.number import *
from gmpy2 import *
from itertools import count

n = 151767047787614712083974720416865469041528766980347881592164779139223941980832935534609228636599644744364450753148219193621511377088383418096756216139022880709
e = 65537
c = 26971181342240802276810747395669930355754928952080329914687241779532014305320191048439959934699795162709365987652696472998140484810728817991804469778237933925

def mlucas(v, a, n):
  v1, v2 = v, (v ** 2 - 2) % n
  for bit in bin(a)[3:]: v1, v2 = ((v1 ** 2 - 2) % n, (v1 * v2 - v) % n) if bit == "0"else (
    (v1 * v2 - v) % n, (v2 ** 2 - 2) % n)
  return v1

def primegen():
  yield2
  yield3
  yield5
  yield7
  yield11
  yield13
  ps = primegen()  *# yay recursion*
  p = ps.__next__() and ps.__next__()
  q, sieve, n = p ** 2, {}, 13
  whileTrue:
    if n notin sieve:
      if n < q:
        yield n
      else:
        next, step = q + 2 * p, 2 * p
        while next in sieve:
          next += step
        sieve[next] = step
        p = ps.__next__()
        q = p ** 2
    else:
      step = sieve.pop(n)
      next = n + step
      while next in sieve:
        next += step
      sieve[next] = step
    n += 2

def ilog(x, b):*# greatest integer l such that b**l <= x.*
  l = 0
  while x >= b:
    x /= b
    l += 1
  return l

def attack(n):
  for v in count(1):
    for p in primegen():
      e = ilog(isqrt(n), p)
      if e == 0:
        break
      for _ in range(e):
        v = mlucas(v, p, n)
      g = gcd(v - 2, n)
      if1 < g < n:
        return int(g), int(n // g)  *# g|n*
      if g == n:
        break

p1, q1 = attack(n)
print(p1)
print(q1)

求出e后直接打就好

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
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
from __future__ import print_function
import time
from Crypto.Util.number import long_to_bytes
from Crypto.PublicKey import RSA

############################################

# Config

##########################################

"""
Setting debug to true will display more informations
about the lattice, the bounds, the vectors...
"""
debug = False

"""
Setting strict to true will stop the algorithm (and
return (-1, -1)) if we don't have a correct
upperbound on the determinant. Note that this
doesn't necesseraly mean that no solutions
will be found since the theoretical upperbound is
usualy far away from actual results. That is why
you should probably use `strict = False`
"""
strict = False

"""
This is experimental, but has provided remarkable results
so far. It tries to reduce the lattice as much as it can
while keeping its efficiency. I see no reason not to use
this option, but if things don't work, you should try
disabling it
"""
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

# display matrix picture with 0 and X

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)

# tries to remove unhelpful vectors

# we start at current = n-1 (last vector)

def remove_unhelpful(BB, monomials, bound, current):

    # end of our recursive function

​    if current == -1 or BB.dimensions()[0] <= dimension_min:
​        return BB

    # we start by checking from the end

​    for ii in range(current, -1, -1):

        # if it is unhelpful:

​        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 another vector is affected:

                # we increase the count

​                if BB[jj, ii] != 0:
​                    affected_vectors += 1
​                    affected_vector_index = jj
​    

            # level:0

            # if no other vectors end up affected

            # we remove it

​            if affected_vectors == 0:
​                BB = BB.delete_columns([ii])
​                BB = BB.delete_rows([ii])
​                monomials.pop(ii)
​                BB = remove_unhelpful(BB, monomials, bound, ii-1)
​                return BB
​    

            # level:1

            # if just one was affected we check

            # if it is affecting someone else

​            elif affected_vectors == 1:
​                affected_deeper = True
​                for kk in range(affected_vector_index + 1, BB.dimensions()[0]):

                    # if it is affecting even one vector

                    # we give up on this one

​                    if BB[kk, affected_vector_index] != 0:
​                        affected_deeper = False

                # remove both it if no other vector was affected and

                # this helpful vector is not helpful enough

                # compared to our unhelpful one

​                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

    # nothing happened

​    return BB

""" 
Returns:

* 0,0   if it fails

* -1,-1 if `strict=true`, and determinant doesn't bound

* x0,y0 the solutions of `pol`
  """
  def boneh_durfee(pol, modulus, mm, tt, XX, YY):
    """
    Boneh and Durfee revisited by Herrmann and May

    finds a solution if:

    * d < N^delta
    * |x| < e^delta
    * |y| < e^0.5
      whenever delta < 1 - sqrt(2)/2 ~ 0.292
        """

    # substitution (Herrman and May)

    PR.<u, x, y> = PolynomialRing(ZZ)
    Q = PR.quotient(x*y + 1 - u) # u = xy + 1
    polZ = Q(pol).lift()

    UU = XX*YY + 1

    # x-shifts

    gg = []
    for kk in range(mm + 1):
        for ii in range(mm - kk + 1):
            xshift = x^ii * modulus^(mm - kk) * polZ(u, x, y)^kk
            gg.append(xshift)
    gg.sort()

    # x-shifts list of monomials

    monomials = []
    for polynomial in gg:
        for monomial in polynomial.monomials():
            if monomial not in monomials:
                monomials.append(monomial)
    monomials.sort()

    # y-shifts (selected by Herrman and May)

    for jj in range(1, tt + 1):
        for kk in range(floor(mm/tt) * jj, mm + 1):
            yshift = y^jj * polZ(u, x, y)^kk * modulus^(mm - kk)
            yshift = Q(yshift).lift()
            gg.append(yshift) # substitution

    # y-shifts list of monomials

    for jj in range(1, tt + 1):
        for kk in range(floor(mm/tt) * jj, mm + 1):
            monomials.append(u^kk * y^jj)

    # construct lattice B

    nn = len(monomials)
    BB = Matrix(ZZ, nn)
    for ii in range(nn):
        BB[ii, 0] = gg[ii](0, 0, 0)
        for jj in range(1, ii + 1):
            if monomials[jj] in gg[ii].monomials():
                BB[ii, jj] = gg[ii].monomial_coefficient(monomials[jj]) * monomials[jj](UU,XX,YY)

    # Prototype to reduce the lattice

    if helpful_only:

        # automatically remove

  ​      BB = remove_unhelpful(BB, monomials, modulus^mm, nn-1)

        # reset dimension

  ​      nn = BB.dimensions()[0]
  ​      if nn == 0:
  ​          print("failure")
  ​          return 0,0

    # check if vectors are helpful

    if debug:
        helpful_vectors(BB, modulus^mm)

    # check if determinant is correctly bounded

    det = BB.det()
    bound = modulus^(mm*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

    # display the lattice basis

    if debug:
        matrix_overview(BB, modulus^mm)

    # LLL

    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!")

    # transform vector i & j -> polynomials 1 & 2

    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):

            # for i and j, create the two polynomials

  ​          PR.<w,z> = PolynomialRing(ZZ)
  ​          pol1 = pol2 = 0
  ​          for jj in range(nn):
  ​              pol1 += monomials[jj](w*z+1,w,z) * BB[pol1_idx, jj] / monomials[jj](UU,XX,YY)
  ​              pol2 += monomials[jj](w*z+1,w,z) * BB[pol2_idx, jj] / monomials[jj](UU,XX,YY)

            # resultant

  ​          PR.<q> = PolynomialRing(ZZ)
  ​          rr = pol1.resultant(pol2)
  ​    

            # are these good polynomials?

  ​          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 example():
    ############################################

    # How To Use This Script

​    ##########################################

​    #

    # The problem to solve (edit the following values)

​    #
​    

    # the modulus

​    N=10037257627154486608196774801095855162090578704439233219876490744017222686494761706171113312036056644757212254824459536550416291797454693336043852190135363;
​    e=6701513605196718137208327145211106525052740242222174201768345944717813148931274437740087428165253744741547590314279846187850432858954606153257994418035341;
​    c=6723803125309437675713195914771839852631361554645954138639198200804046718848872479140347495288135138109762940384847808522874831433140182790750890982139835;
​    

    # the hypothesis on the private exponent (the theoretical maximum is 0.292)

​    delta = .278 # this means that d < N^delta
​    
​    #

    # Lattice (tweak those values)

​    #
​    

    # you should tweak this (after a first run), (e.g. increment it until a solution is found)

​    m = 11 # size of the lattice (bigger the better/slower)
​    

    # you need to be a lattice master to tweak these

​    t = int((1-2*delta) * m)  # optimization from Herrmann and May
​    X = 2*floor(N^delta)  # this _might_ be too much
​    Y = floor(N^(1/2))    # correct if p, q are ~ same size
​    
​    #

    # Don't touch anything below

​    #
​    

    # Problem put in equation

​    P.<x,y> = PolynomialRing(ZZ)
​    A = int((N+1)/2)
​    pol = 1 + x * (A + y)
​    
​    #

    # Find the solutions!

​    #
​    

    # Checking bounds

​    if debug:
​        print("=== checking values ===")
​        print("* delta:", delta)
​        print("* delta < 0.292", delta < 0.292)
​        print("* size of e:", int(log(e)/log(2)))
​        print("* size of N:", int(log(N)/log(2)))
​        print("* m:", m, ", t:", t)
​    

    # boneh_durfee

​    if debug:
​        print("=== running algorithm ===")
​        start_time = time.time()
​    
​    solx, soly = boneh_durfee(pol, e, m, t, X, Y)
​    

    # found a solution?

​    if solx > 0:
​        d = int(pol(solx, soly) / e)
​        pplusq = int(soly*2)
​        import gmpy2
​        pminusq = gmpy2.iroot(pplusq^2-4*N,2)[0]
​        p = (pplusq + pminusq) // 2
​        q = N // p
​    
​        print("d =", d)
​        print("p =",p)
​        print("q =",q)
​        assert p*q == N
​        m = pow(c,d,N)
​        print(long_to_bytes(int(m))[::-1])
​        ##
​    else:
​        print("=== no solution was found ===")
​    
​    if debug:
​        print(("=== %s seconds ===" % (time.time() - start_time)))

if __name__ == "__main__":
    example()

easy_rsa

1
2
3
e = 65537
n = 1000000000000000000000000000156000000000000000000000000005643
c = 418535905348643941073541505434424306523376401168593325605206

直接分解n解RSA

简单编码

1
ABBAABB ABBABAB ABABAAA ABABAAB ABBBBAA ABBAABA ABABBAA ABBAAAA ABBAAAB ABBABAB ABBBAAA ABAABBB ABABBAA ABABABB ABABBAA ABBABBB ABBABAA ABABABA ABAABAB ABBBAAA ABBBABA ABABBAB ABBBBAA ABABBAB ABBBAAA ABBABAB ABBAABA ABABAAA ABABABA AABBAB ABBBABB ABBAABA ABBABAB AABABA ABBBBAA ABBBAAB ABBAABA AABBAB ABABBAA ABBAAAB ABBBAAA ABBABAB ABBABAA ABABABB ABBBABA ABABABB ABBAABB ABBABAA ABBABAB ABBABAB ABABAAA ABBBABA AABABB ABABBAB AABBAB ABABAAA ABBAAAB ABBBBAB ABBBAAA ABABABA ABBAAAA ABABAAB ABABABB ABBABBA ABBABAB AABABA ABBABAA ABBBABA ABBBABA AABBAA ABBBBAA ABBAAAA ABABBBB ABBABAB ABABABB ABAABBB ABBAAAA ABABAAA ABABABB ABBABAA ABBABBA ABABABA ABAABAB ABABABA AABABB ABABBAB ABBBBAA ABBBBAB ABBBAAA ABABAAB ABBABBB ABABAAB ABBAAAA ABAABAB ABBBABB ABBABAA ABBABAB ABABABA ABAABAB ABBBABA ABBAABA AABBAB ABABBAA ABAABAB ABBBAAA ABBABAB ABBBABA ABAABBB ABABBBA ABABABB ABABBAA ABBABBB ABBABAA ABAABAB ABABABA ABBBAAB ABABBAA ABBAABA ABABBAA ABAABAB ABBBAAA ABBABAB ABBABBB ABBBABB ABBBABA ABABBAA ABBABAB ABABABA ABBAABA ABAABAB ABBAABA ABBABBB ABBBAAA ABBAABA ABBBBAA ABBAAAA ABBABAA ABABBAB ABBABAA ABAABBB ABABABA ABABABB ABABABB AABBAB ABBAAAB ABBBBAB ABABABA ABBBABA AABBAB ABABABA ABBABAB ABBBAAB ABBBAAA ABBAAAB ABBBBAA ABBBBAA ABBABAA ABBAABA AABBAB ABBBABA

先考虑把A换成1，B换成0

1
2
3
4
5
6
7
8
9
10
11
c="ABBAABB ABBABAB ABABAAA ABABAAB ABBBBAA ABBAABA ABABBAA ABBAAAA ABBAAAB ABBABAB ABBBAAA ABAABBB ABABBAA ABABABB ABABBAA ABBABBB ABBABAA ABABABA ABAABAB ABBBAAA ABBBABA ABABBAB ABBBBAA ABABBAB ABBBAAA ABBABAB ABBAABA ABABAAA ABABABA AABBAB ABBBABB ABBAABA ABBABAB AABABA ABBBBAA ABBBAAB ABBAABA AABBAB ABABBAA ABBAAAB ABBBAAA ABBABAB ABBABAA ABABABB ABBBABA ABABABB ABBAABB ABBABAA ABBABAB ABBABAB ABABAAA ABBBABA AABABB ABABBAB AABBAB ABABAAA ABBAAAB ABBBBAB ABBBAAA ABABABA ABBAAAA ABABAAB ABABABB ABBABBA ABBABAB AABABA ABBABAA ABBBABA ABBBABA AABBAA ABBBBAA ABBAAAA ABABBBB ABBABAB ABABABB ABAABBB ABBAAAA ABABAAA ABABABB ABBABAA ABBABBA ABABABA ABAABAB ABABABA AABABB ABABBAB ABBBBAA ABBBBAB ABBBAAA ABABAAB ABBABBB ABABAAB ABBAAAA ABAABAB ABBBABB ABBABAA ABBABAB ABABABA ABAABAB ABBBABA ABBAABA AABBAB ABABBAA ABAABAB ABBBAAA ABBABAB ABBBABA ABAABBB ABABBBA ABABABB ABABBAA ABBABBB ABBABAA ABAABAB ABABABA ABBBAAB ABABBAA ABBAABA ABABBAA ABAABAB ABBBAAA ABBABAB ABBABBB ABBBABB ABBBABA ABABBAA ABBABAB ABABABA ABBAABA ABAABAB ABBAABA ABBABBB ABBBAAA ABBAABA ABBBBAA ABBAAAA ABBABAA ABABBAB ABBABAA ABAABBB ABABABA ABABABB ABABABB AABBAB ABBAAAB ABBBBAB ABABABA ABBBABA AABBAB ABABABA ABBABAB ABBBAAB ABBBAAA ABBAAAB ABBBBAA ABBBBAA ABBABAA ABBAABA AABBAB ABBBABA"


c=c.replace("A","1")
c=c.replace("B","0")
bl=c.split()
bits = []
for b in bl:
  bits.append(int(b, 2))
encoded=bytes(bits).decode()
print(encoded)

然后到厨子上解base32

image-20250525130454927

然后再解base64

image-20250525130523024

这里看到类似flag的东西

最后栅栏一下

image-20250525130646586

Diladila’s Cipher

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
def rol(val, r_bits, max_bits=16):

  return ((val << r_bits) & (2**max_bits - 1)) | (val >> (max_bits - r_bits))

def ror(val, r_bits, max_bits=16):

  return (val >> r_bits) | ((val << (max_bits - r_bits)) & (2**max_bits - 1))

def speck_round(x, y, k):

  x = (ror(x, 7) + y) & 0xFFFF

  x ^= k

  y = rol(y, 2) ^ x

  return x, y

def encrypt_block(x, y, keys):

  for k in keys:

​    x, y = speck_round(x, y, k)

  return x, y

def str_to_blocks(s):

  b = s.encode('utf-8')

  if len(b) % 4 != 0:

​    b += b'\x00' * (4 - len(b) % 4)

  blocks = []

  for i in range(0, len(b), 4):

​    x = int.from_bytes(b[i:i+2], 'little')

​    y = int.from_bytes(b[i+2:i+4], 'little')

​    blocks.append((x, y))

  return blocks

\# 这里写明文变量时用占位符，实际加密时请自行替换

plaintext = "***********"

keys = [0x1234, 0x5678, 0x9abc, 0xdef0]

\# 组织分组

blocks = str_to_blocks(plaintext)

ciphertext = []

for x, y in blocks:

  cx, cy = encrypt_block(x, y, keys)

  ciphertext.append((cx, cy))

\# 打印密文，供题目发布用

print("加密后的密文:")

for c in ciphertext:

  print(c)

最搞笑的一集，因为出题人的失误导致前面的一天根本无法解

speck_round()直接逆回去就行了，因为是对称加密

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
def rol(val, r_bits, max_bits=16):
  return ((val << r_bits) & (2 ** max_bits - 1)) | (val >> (max_bits - r_bits))


def ror(val, r_bits, max_bits=16):
  return (val >> r_bits) | ((val << (max_bits - r_bits)) & (2 ** max_bits - 1))



def speck_decrypt_round(x_prime, y_prime, k):
 
  x_xor_k = x_prime ^ k
  y_prev = ror((y_prime ^ x_prime), 2) 
  x_prev = rol((x_xor_k - y_prev) & 0xFFFF, 7) 
  return x_prev, y_prev

def decrypt_block(x, y, keys):
  for k in reversed(keys): *
    x, y = speck_decrypt_round(x, y, k)
  return x, y

def blocks_to_str(blocks):
  byte_arr = bytearray()
  for x, y in blocks:
    byte_arr.extend(x.to_bytes(2, 'little'))
    byte_arr.extend(y.to_bytes(2, 'little'))

  padding_len = 0
  for i in reversed(range(len(byte_arr))):
    if byte_arr[i] == 0:
      padding_len += 1
    else:
      break
  if padding_len > 0:
    byte_arr = byte_arr[:-padding_len]

  return byte_arr.decode('utf-8', errors='ignore')


keys = [0x1234, 0x5678, 0x9abc, 0xdef0]

cipher_blocks = [(57912, 19067), (38342, 34089), (16842, 41652), (30292, 50979), (9137, 57458), (29822, 64285), (33379, 14140), (16514, 4653)]
decrypted_blocks = []
for x, y in cipher_blocks:
  dx, dy = decrypt_block(x, y, keys)
  decrypted_blocks.append((dx, dy))



flag = blocks_to_str(decrypted_blocks)
print(flag)

dp

1
2
3
4
n = 110231451148882079381796143358970452100202953702391108796134950841737642949460527878714265898036116331356438846901198470479054762675790266666921561175879745335346704648242558094026330525194100460497557690574823790674495407503937159099381516207615786485815588440939371996099127648410831094531405905724333332751 
dp = 3086447084488829312768217706085402222803155373133262724515307236287352098952292947424429554074367555883852997440538764377662477589192987750154075762783925 
c = 59325046548488308883386075244531371583402390744927996480498220618691766045737849650329706821216622090853171635701444247741920578127703036446381752396125610456124290112692914728856924559989383692987222821742728733347723840032917282464481629726528696226995176072605314263644914703785378425284460609365608120126 
e = 65537

dp的泄露，随便找个板子打就好，本来是一血的，后面题目被删了，一血没了(╥﹏╥)

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

n = 110231451148882079381796143358970452100202953702391108796134950841737642949460527878714265898036116331356438846901198470479054762675790266666921561175879745335346704648242558094026330525194100460497557690574823790674495407503937159099381516207615786485815588440939371996099127648410831094531405905724333332751
dp = 3086447084488829312768217706085402222803155373133262724515307236287352098952292947424429554074367555883852997440538764377662477589192987750154075762783925
c = 59325046548488308883386075244531371583402390744927996480498220618691766045737849650329706821216622090853171635701444247741920578127703036446381752396125610456124290112692914728856924559989383692987222821742728733347723840032917282464481629726528696226995176072605314263644914703785378425284460609365608120126
e = 65537

for x in range(1,e):  *#遍历X*
  if (dp*e - 1) % x == 0:
    p = (dp*e - 1)// x + 1
    if n % p == 0:
      q = n // p  *#得到q*
      phi = (p - 1) * (q - 1)  *#欧拉函数*
      d = gmpy2.invert(e,phi)  *#求逆元*
      m = pow(c,d,n) *#幂取模，m=c^d mod n*
      flag = long_to_bytes(m)
      print(flag)
      break

古典密码*

没做出来

告白*

看其他师傅说是摩尔斯电码里的爱情故事

帕鲁杯2025

RSA_Quartic_Quandary

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 getPrime, bytes_to_long
import math

FLAG = b'**************'


def generate_parameters(bit_length=512):
    p = getPrime(bit_length)
    q = getPrime(bit_length)
    n = p * q
    e = 65537
    phi = (p - 1) * (q - 1)
    d = pow(e, -1, phi)
    s = p ** 4 + q ** 4
    return n, e, d, s, p, q


def main():
    n, e, d, s, p, q = generate_parameters()
    c = pow(bytes_to_long(FLAG), e, n)

    with open('output.txt', 'w') as f:
        f.write(f"n = {n}\n")
        f.write(f"e = {e}\n")
        f.write(f"c = {c}\n")
        f.write(f"s = {s}\n")
    
    print("[+] Parameters saved to output.txt")

if __name__ == "__main__":
    main()

直接解方程即可，题目给出了 s = p4 + q4

n = p * q

两个未知数，两个方程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
n = 125997816345753096048865891139073286898143461169514858050232837657906289840897974068391106608902082960171083817785532702158298589600947834699494234633846206712414663927142998976208173208829799860130354978308649020815886262453865196867390105038666506017720712272359417586671917060323891124382072599746305448903
e = 65537
c = 16076213508704830809521504161524867240789661063230251272973700316524961511842110066547743812160813341691286895800830395413052502516451815705610447484880112548934311914559776633140762863945819054432492392315491109745915225117227073045171062365772401296382778452901831550773993089344837645958797206220200272941
s = 35935569267272146368441512592153486419244649035623643902985220815940198358146024590300394059909370115858091217597774010493938674472746828352595432824315405933241792789402041405932624651226442192749572918686958461029988244396875361295785103356745756304497466567342796329331150560777052588294638069488836419744297241409127729615544668547101580333420563318486256358906310909703237944327684178950282413703357020770127158209107658407007489563388980582632159120621869165333921661377997970334407786581024278698231418756106787058054355713472306409772260619117725561889350862414726861327985706773512963177174611689685575805282
from Crypto.Util.number import *
import math
from sympy import *
f1, f2 = symbols("f1, f2")
f_solve = solve([f1 * f2 - n, f1 ** 4 + f2 ** 4 - s], [f1, f2])

print(f_solve)
p = 9886283652121924227364367891763650443585646023924602862402832944457976031272516261452668401020850156092802805016302198750132659632249261237412357024908843
q = 12744709820126371501672538820972733986675228838744099116170499394098621931788837908787562175058998307224041741444921422195431949471972242197577242845982421

phi = (p-1)*(q-1)
d = inverse(e,phi)
m = pow(c,d,n)
print(long_to_bytes(m))

# palu{This_is_a_fake_flag_change_it_for_real_use}

欧几里得

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
import random
import os
from Crypto.Util.number import *
from gmpy2 import lcm, gcd
def exgcd(a, b):
    if b == 0: return 1, 0
    x, y = exgcd(b, a%b)
    return y, x - a//b*y


def get_k():
    while True:
        p = getPrime(512)
        q = getPrime(512)
        phi = (p - 1) * (q - 1)
        if gcd(p * q, phi) == 1:
            break
    n = p * q
    while True:
        g = random.randint(1, n * n)
        if gcd((g - 1) // n, n) == 1:
            break
    return (n, g), (p, q)


def Paillier_encode(m, g, n):
    while True:
        r = random.randint(1, n - 1)
        if gcd(r, n) == 1:
            break
    return (pow(g, m, n * n) * pow(r, n, n * n)) % (n * n)


def Paillier_decode(c, p, q, g, n):
    lam = lcm(p - 1, q - 1)
    mi = exgcd((pow(g, lam, n * n) - 1) // n, n)[0] % n
    return (pow(c, lam, n * n) - 1) // n * mi % n


pk, sk = get_k()
n, g = pk
p, q = sk
m1 = bytes_to_long(flag)
m2 = bytes_to_long(os.urandom(2) * 35)
c1 = Paillier_encode(m1, g, n)
c2 = Paillier_encode(m2, g, n)
print(f'c = {Paillier_decode(c1 * c2, p, q, g, n)}')

# c = 1426774899479339414711783875769670405758108494041927642533743607154735397076811133205075799614352194241060726689487117802867974494099614371033282640015883625484033889861

Piallier加密具有加法同态性也就是密文相乘等于明文相加

这篇博客里有介绍

那么c = m1 + m2

再看到这里的m2

1
m2 = bytes_to_long(os.urandom(2) * 35)

用等比数列求和公式来表示 S = （1 + 2562 + 2564 + ... + 25668）

m1 = c = k * S

这里爆破k即可

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

c = 1426774899479339414711783875769670405758108494041927642533743607154735397076811133205075799614352194241060726689487117802867974494099614371033282640015883625484033889861



geom_factor = (pow(256, 70) - 1) // (pow(256, 2) - 1)



found = False

for s in range(65536):

  m2 = s * geom_factor

  if m2 > c:  

    continue

  m1 = c - m2

  try:

    flag = long_to_bytes(m1)
    
    
    
    if flag.isascii() and len(flag) < 100:  
    
      print(f"Trying s = {s}: {flag}")
    
      if b'flag{' in flag:  
    
        print(f"Found flag: {flag.decode()}")
    
        found = True
    
        break

  except ValueError:

    continue

if not found:

  print("Flag not found. Try adjusting the search conditions.")

易如反掌

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

primes = [(getPrime(1024), getPrime(1024)) for _ in range(4)]
N = [p * q for p, q in primes]
PHI = [(p**2 - 1) * (q**2 - 1) for p, q in primes]
d = getPrime(800)
flag = "palu{" + hashlib.md5(str(d)[].encode()).hexdigest() + "}"
E = [int(gmpy2.invert(d, PHI[i])) for i in range(4)]
print(N)
print(E)

# [23796646026878116589547283793150995927866567938335548416869023482791889761195291718895745055959853934513618760888513821480917766191633897946306199721200583177442944168533218236080466338723721813833112934172813408785753690869328477108925253250272864647989241887047368829689684698870160049332949549671046125158024445929082758264311584669347802324514633164611600348485747482925940752960745308927584754759033237553398957651216385369140164712159020014009858771182426893515016507774993840721603911101735647966838456333878426803669855790758035721418868768618171692143354466457771363078719423863861881209003100274869680348729, 19552522218179875003847447592795537408210008360038264050591506858077823059915495579150792312404199675077331435544143983146080988327453540449160493126531689234464110427289951139790715136775261122038034076109559997394039408007831367922647325571759843192843854522333120187643778356206039403073606561618190519937691323868253954852564110558105862497499849080112804340364976236598384571278659796189204447521325485338769935361453819608921520780103184296098278610439625935404967972315908808657494638735904210709873823527111315139018387713381604550946445856087746716671838144925662314348628830687634437271225081272705532826343, 20588310030910623387356293638800302031856407530120841616298227518984893505166480372963166394317326422544430837759332223527939420321960057410073228508230111170414845403161052128790464277007579491219950440477721075788978767309211469555824310913593208232853272958011299985202799390532181335087622499894389777412111445377637396650710486263652440053717323053536700098339137819966260269752816515681602936416736576044630343136577023173210517247609888936337876211461528203642347119434700140264859102502126842250671976238033270367185358966766106988830596616311824691409766437473419074865115209866730272194297815209976737570183, 18468380817178794606027384089796802449939260582378979728469492439450780893746976934315768186829245395964644992296264093276556001477514083927556578752836255491334765496791841945178275793885002188397918857222419803612711637177559554489679414049308077300718317502586411333302434329130562745942681716547306138457088216901181646333860559988117376012816579422902808478175975263110581667936249474308868051767856694498210084853797453949193117835061402537058150493808371384063278793041752943930928932275052745657700368980150842377283198946138726219378646040515809994704174471793592322237777371900834531014326150160506449286179]

# [229904181453273080302209653709086531153804577507365859149808244958841045687064628362978517491609413507875726243121473678430010600891588643092042173698830147997497783886459583186019270582236955524620567373560535686287255124958954671737097645556109314142383275516997850786599322033792080045303427363366927030304214333894247469120513426641296678531965795930756543043851154646310114366477311633838078242963665452936523438928643273392454483600446242320078010627755587492056369779661382734170244060951095344418599686788550312205964136120979823565225768814898285224838691541122088693411388097496320157113230752327025862802020421665288007529320920942060329299409362236414929126050037144149017275031336018100081931062647888329912802477032857776085190828105602067426203163344931483638271679183910241511044338001446584634203146294743522375846913845041274967653508735863706778364499099286484552570083394223973734909997825522191349543295855925973354640349809770822075226834555111927586299176453943116511915434890643239957459427390624136283086434711471863737451011157026905191204496081860277138227247744470804087252965368757930797560277881668806206419629425126031049566579233056222579590529869798537893505779097868221221068867624660759084762471141, 374749619911728044650812367560174497001343067563440477135516664935394734686391543012901514676044211541958613458868769659861216149364768233000844624035620893309356372294598009760824255187442531508754966566917198975934706398309982525100772311586501118200858124845012643495006029930202324305874402291277845166060497038915773767003006049720519011634861166208163030159519901867416488082395270295488885724507937683469910251316231210838654273986152493722244271430422693265608430755620420680629979226285393465423870727975987787149515374769359243334743541460110042872587610309611770320600248289328406805995688596910226273861759369388105641549933915686192055533242723330981192183310876306968103333706140401422550917946410378174896274789619184565321544130428008804628699594759946577979319393247067750024729672029363433673084437510430506410293512293930056667971242862448029841846596288648691077795207341975907335202945548990662460491169957175452745622341245617265849042542964819126377775749222973138584978725470886059043251544634105653274564085280013340679259157119014619894553239015777411757887293044706448625760604242512494466386343040583010961386979963779928616733980046763291988848903515836247301007113187121999960487508948748354549628160741, 111738429639840672983162926852338651562094139707285850255632987705635459657893186493838711733560515475806567653354737245246745810892238414756414117557971683747269900627524702653772058841085258035513296218047505149691384287812041721130367506731427022265277885965948486359682023555050085264531256406043361391744086539522028829421284667293339869140564699750714145488199268791908205712660933607330454849730499840287271163350865799682565216636393526339218836244889719975150503253630419647851422620890082315396457329065508602521784001607236788620811397449483104884860551374031790663030220424841642241965983726516537123807061999084476076850833658360594525986997125319941689903869138176347916707622148840226672408554102717625456819726220575710494929111642866840516339713870850732638906870325693572445316904688582043485093120585767903009745325497085286577015692005747499504730575062998090846463157669448943725039951120963375521054164657547731579771203443617489609201617736584055562887243883898406182052632245189418568410854530995044542628531851356363297989653392057214167031332353949367816700838296651167799441279086074308299608106786918676697564002641234952760724731325383088682051108589283162705846714876543662335188222683115878319143239781, 185935167438248768027713217055147583431480103445262049361952417166499278728434926508937684304985810617277398880507451351333771783039360671467147075085417403764439214700549777320094501151755362122677245586884124615115132430034242191429064710012407308619977881929109092467325180864745257810774684549914888829203014922855369708286801194645263982661023515570231007900615244109762444081806466412714045462184361892356485713147687194230341085490571821445962465385514845915484336766973332384198790601633964078447446832581798146300515184339036127604597014458389481920870330726947546808739829589808006774479656385317205167932706748974482578749055876192429032258189528408353619365693624106394913101463023497175917598944803733849984703912670992613579847331081015979121834040110652608301633876167262248103403520536210279949844194696898862249482809107840303473964914083996538912970715834110371196970613332286296427286356036576876121010776933023901744994067564045429384172315640135483480089769992730928266885675143187679290648773060781987273082229827156531141515679114580622348238382074084270808291251400949744720804368426414308355267344210055608246286737478682527960260877955900464059404976906697164610891962198768354924180929300959036213841843941]

可以根据论文来实现攻击

这里要构造的格是 $$ L = \begin{pmatrix} M^2 & e_0 & e_1 & e_2 & e_3 \\ 0 & -n_0^2 & 0 & 0 & 0 \\ 0 & 0 & -n_1^2 & 0 & 0 \\ 0 & 0 & 0 & -n_2^2 & 0 \\ 0 & 0 & 0 & 0 & -n_3^2 \\ \end{pmatrix} $$ 这里我是用另一种办法写的

我们这里需要求出的是d ed ≡ 1 mod  (p2 − 1)(q2 − 1)

ed = 1 + k(p2 − 1)(q2 − 1)

因为这里的p，q都很大，所以 p2 − 1 ≈ p2

q2 − 1 ≈ q2

同除d * n3 $$ \frac{e}{n^{2}} =\frac{k}{d}+\frac{1}{d*n^{2}} $$ $$ \frac{e}{n^{2}} \approx \frac{k}{d} $$ 然后连分数展开求（p2 − 1）(q2 − 1)

联立n=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
import hashlib

from tqdm import *

N=[23796646026878116589547283793150995927866567938335548416869023482791889761195291718895745055959853934513618760888513821480917766191633897946306199721200583177442944168533218236080466338723721813833112934172813408785753690869328477108925253250272864647989241887047368829689684698870160049332949549671046125158024445929082758264311584669347802324514633164611600348485747482925940752960745308927584754759033237553398957651216385369140164712159020014009858771182426893515016507774993840721603911101735647966838456333878426803669855790758035721418868768618171692143354466457771363078719423863861881209003100274869680348729, 19552522218179875003847447592795537408210008360038264050591506858077823059915495579150792312404199675077331435544143983146080988327453540449160493126531689234464110427289951139790715136775261122038034076109559997394039408007831367922647325571759843192843854522333120187643778356206039403073606561618190519937691323868253954852564110558105862497499849080112804340364976236598384571278659796189204447521325485338769935361453819608921520780103184296098278610439625935404967972315908808657494638735904210709873823527111315139018387713381604550946445856087746716671838144925662314348628830687634437271225081272705532826343, 20588310030910623387356293638800302031856407530120841616298227518984893505166480372963166394317326422544430837759332223527939420321960057410073228508230111170414845403161052128790464277007579491219950440477721075788978767309211469555824310913593208232853272958011299985202799390532181335087622499894389777412111445377637396650710486263652440053717323053536700098339137819966260269752816515681602936416736576044630343136577023173210517247609888936337876211461528203642347119434700140264859102502126842250671976238033270367185358966766106988830596616311824691409766437473419074865115209866730272194297815209976737570183, 18468380817178794606027384089796802449939260582378979728469492439450780893746976934315768186829245395964644992296264093276556001477514083927556578752836255491334765496791841945178275793885002188397918857222419803612711637177559554489679414049308077300718317502586411333302434329130562745942681716547306138457088216901181646333860559988117376012816579422902808478175975263110581667936249474308868051767856694498210084853797453949193117835061402537058150493808371384063278793041752943930928932275052745657700368980150842377283198946138726219378646040515809994704174471793592322237777371900834531014326150160506449286179]

E=[229904181453273080302209653709086531153804577507365859149808244958841045687064628362978517491609413507875726243121473678430010600891588643092042173698830147997497783886459583186019270582236955524620567373560535686287255124958954671737097645556109314142383275516997850786599322033792080045303427363366927030304214333894247469120513426641296678531965795930756543043851154646310114366477311633838078242963665452936523438928643273392454483600446242320078010627755587492056369779661382734170244060951095344418599686788550312205964136120979823565225768814898285224838691541122088693411388097496320157113230752327025862802020421665288007529320920942060329299409362236414929126050037144149017275031336018100081931062647888329912802477032857776085190828105602067426203163344931483638271679183910241511044338001446584634203146294743522375846913845041274967653508735863706778364499099286484552570083394223973734909997825522191349543295855925973354640349809770822075226834555111927586299176453943116511915434890643239957459427390624136283086434711471863737451011157026905191204496081860277138227247744470804087252965368757930797560277881668806206419629425126031049566579233056222579590529869798537893505779097868221221068867624660759084762471141, 374749619911728044650812367560174497001343067563440477135516664935394734686391543012901514676044211541958613458868769659861216149364768233000844624035620893309356372294598009760824255187442531508754966566917198975934706398309982525100772311586501118200858124845012643495006029930202324305874402291277845166060497038915773767003006049720519011634861166208163030159519901867416488082395270295488885724507937683469910251316231210838654273986152493722244271430422693265608430755620420680629979226285393465423870727975987787149515374769359243334743541460110042872587610309611770320600248289328406805995688596910226273861759369388105641549933915686192055533242723330981192183310876306968103333706140401422550917946410378174896274789619184565321544130428008804628699594759946577979319393247067750024729672029363433673084437510430506410293512293930056667971242862448029841846596288648691077795207341975907335202945548990662460491169957175452745622341245617265849042542964819126377775749222973138584978725470886059043251544634105653274564085280013340679259157119014619894553239015777411757887293044706448625760604242512494466386343040583010961386979963779928616733980046763291988848903515836247301007113187121999960487508948748354549628160741, 111738429639840672983162926852338651562094139707285850255632987705635459657893186493838711733560515475806567653354737245246745810892238414756414117557971683747269900627524702653772058841085258035513296218047505149691384287812041721130367506731427022265277885965948486359682023555050085264531256406043361391744086539522028829421284667293339869140564699750714145488199268791908205712660933607330454849730499840287271163350865799682565216636393526339218836244889719975150503253630419647851422620890082315396457329065508602521784001607236788620811397449483104884860551374031790663030220424841642241965983726516537123807061999084476076850833658360594525986997125319941689903869138176347916707622148840226672408554102717625456819726220575710494929111642866840516339713870850732638906870325693572445316904688582043485093120585767903009745325497085286577015692005747499504730575062998090846463157669448943725039951120963375521054164657547731579771203443617489609201617736584055562887243883898406182052632245189418568410854530995044542628531851356363297989653392057214167031332353949367816700838296651167799441279086074308299608106786918676697564002641234952760724731325383088682051108589283162705846714876543662335188222683115878319143239781, 185935167438248768027713217055147583431480103445262049361952417166499278728434926508937684304985810617277398880507451351333771783039360671467147075085417403764439214700549777320094501151755362122677245586884124615115132430034242191429064710012407308619977881929109092467325180864745257810774684549914888829203014922855369708286801194645263982661023515570231007900615244109762444081806466412714045462184361892356485713147687194230341085490571821445962465385514845915484336766973332384198790601633964078447446832581798146300515184339036127604597014458389481920870330726947546808739829589808006774479656385317205167932706748974482578749055876192429032258189528408353619365693624106394913101463023497175917598944803733849984703912670992613579847331081015979121834040110652608301633876167262248103403520536210279949844194696898862249482809107840303473964914083996538912970715834110371196970613332286296427286356036576876121010776933023901744994067564045429384172315640135483480089769992730928266885675143187679290648773060781987273082229827156531141515679114580622348238382074084270808291251400949744720804368426414308355267344210055608246286737478682527960260877955900464059404976906697164610891962198768354924180929300959036213841843941]

n =N[0] 

e = E[0]

cf = continued_fraction(Integer(e) / Integer(n^2))

for i in trange(2,2000):

   k = int(cf.numerator(i))    #取连分数的分子

   d = int(cf.denominator(i))

   if (e*d - 1)%k == 0:

 print(f"k = {k}")

 print(f"d = {d}")


最后md5加密d即可

循环锁链

拿到数据直接异或就好

1
2
3
4
5
6
7
8
9
cipher = bytes.fromhex("110D190E122A7442312B2500070C163927210300280D2720262C19000C3B0439221952440D")

plain = [0x70]  # 'p'

for i in range(len(cipher)):

  plain.append(cipher[i] ^ plain[i])

print(bytes(plain).decode())

轮回密码

轮回密文: y¦_›6>X¬y–!,!n¡mSaÜñüë—9¼6™

后面放hint给了加密脚本和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
import base64

def samsara_decrypt(cipher_text, key_word=b""):

    

    if not key_word:
        phase3 = cipher_text.encode('latin-1')  
    else:
        cipher_bytes = cipher_text.encode('latin-1')
        phase3 = bytes([cipher_bytes[i] ^ key_word[i % len(key_word)] for i in range(len(cipher_bytes))])

    cycle_step = len(key_word) % 6 + 1 if key_word else 1  

    

    phase2 = bytes([((c << cycle_step) | (c >> (8 - cycle_step))) & 0xFF for c in phase3])

    # Base85 解码

    try:
        phase1 = base64.b85decode(phase2)
    except Exception as e:
        print("Base85 解码失败:", e)
        return None

  

    original = bytes([((c << cycle_step) | (c >> (8 - cycle_step))) & 0xFF for c in phase1])

    return original

if __name__ == "__main__":
    cipher_text = "y¦_›6>X¬y–!,!n¡mSaÜñüë—9¼6™"
    key = b"Bore"  
    
    decrypted = samsara_decrypt(cipher_text, key)
    print("解密结果:", decrypted)

星际广播站*

文件查看器*