算法基础1

  • 前言

湾区杯的密码题虽然很像之前在楚惠杯遇到的题目，但是明显约束更少，而且z3工具虽然是专为线性约束诞生，但是不适合用来做多解。还是得学一下动态规划等等算法，希望以后不当脚本小子，TT

递归

  • 所有的编程课程都会给你将这个，个人有一些脚本小子，没怎么使用过这方面的。
    递归（英语：Recursion），又译为递回，在数学与计算机科学中，是指在函数的定义中使用函数自身的方法。递归一词还较常用于描述以自相似方法重复事物的过程。例如，当两面镜子相互之间近似平行时，镜中嵌套的图像是以无限递归的形式出现的。也可以理解为自我复制的过程。

  • 在最开始的时候我一般把递归理解称一种套娃。现在我也是这么想的，但是在长时间的学习会发现，如果只是对一个东西的大致概念有理解，看得懂也就是顶天了，想要实操，必须对其有一定的深入理解。

  • 示例

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    package main  

    import "fmt"  
      
    func rcn(n int) int {  
        if n == 0 || n == 1 {  
           return 1  
        } else {  
           a := n * rcn(n-1)  
           return a  
        }  
    }  
    func main() {  
        a := rcn(5)  
        fmt.Println(a)  
      
    }

    通过调试我们可以发现，递归是把函数先一次次的运算到底部界限，再一步步的倒退回去。具体可以参考一下堆的先进后出。
    ![[Pasted image 20250918002534.png]]
    在这里打两个断点，调试过程中你会发现，
    n….1变化之后再继续弹出a的，
    $f(n)=n*(n-1)(n-2)…1$
    $f(n)=n    f(n-1)$
    $f(n-1)=(n-1)f(n-2)$
    以此类推到，n-1。.可以发现这其实比较像小学二年级学过的数列。
    $f(3)=3    f(2)$ ……
    然后计算f(1)…,f(2),…f(n)
    接下来我们用经典的扩展欧几里得算法作为示例

  • 先推理出递归的大致结构

扩展欧几里得是基于，$gcd(a,b)=gcd(b,r)$ 其中 $r=a(mod~b)$
肯定有$ax+by=gcd(a,b)$ ，那么有
$bx_1+(a-qb)y_1=gcd(a,b)$
$ay_1+b(x_1-qy_1)$ =gcd(a,b)
所以$x=y_1,y=x_1-qy_1$
我们可以先一步步递归到最后一步，再倒回去得到x,y。

1
2
3
4
5
6
7
8
9
func extend_gcd(a, b int) (int, int, int) {  
    if b == 0 {  
       return a, 1, 0  
    }  
    gcd, x1, y1 := extend_gcd(b, a%b)  
    x := y1  
    y := x1 - (a/b)*y1  
    return gcd, x, y  
}

DFS(深度搜索)

来自wiki的介绍。

DFS全称Depth First Search ,中文名是深度优先搜索，是一种用于遍历或搜索属或图的算法。所谓深度优先，就是说每次都尝试向更深的节点走。
当然还有一个东西叫广度优先(BFS),没有遇到过挖个坑

过程解析

DFS的特在是建立在栈之上的，DFS本身可以通过栈的先进后出的特性来实现的，这里我们利用递归栈的特性来实现。这个是基于数据结构的图论的，福克斯这方面比较菜，理解的话是用调试对这理解的。
tips:当你看不懂一个代码的时候使用调试功能。
我们还是利用一个栗子

示例题目

给定一个整数n,将数字1~n排成一排，将会有很多排列方法。
现在请你按照字典序将所有的排列方法输出
我们利用递归的结构。一步一步的得到结果之后达到底部后再回溯。

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
package main  
  
import (  
    "fmt"  
    "strings")  
  
const N = 10  
  
var (  
    ans     [N]int  // 暂存一个排列  
    mark    [N]bool // 标记用过的数  
    n       int  
    results []string //  
)  
  
func dfs(u int) {  
    // 到达末尾，保存一个排列  
    if u == n {  
       var b strings.Builder  
       for i := 0; i < n; i++ {  
          fmt.Fprintf(&b, "%d ", ans[i])  #将数组写入字符串b
       }  
       results = append(results, b.String())  
       return  
    }  
  
    for i := 1; i <= n; i++ {  
       if !mark[i] {  
          mark[i] = true  
          ans[u] = i  
          dfs(u + 1)  
          // 复原  
          mark[i] = false  
          ans[u] = 0  
       }  
    }  
}  
  
func main() {  
    fmt.Scan(&n)  
    dfs(0)  #(初始化长度为0)
  
    // 统一输出  
    for _, line := range results {  
       fmt.Println(line)  
    }  
}

利用递归的特性实现深度搜索，当u=n开始退回，退回有合适的条件继续搜索。

湾区杯-PRNG

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
from Crypto.Util.number import *
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from hashlib import md5
from secret import flag
import random

assert flag.startswith(b"flag{")


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

    def next(self):
        self.seed = (self.seed**2 * self.a + self.b) % self.m
        return self.seed


p = 2**512
a = getPrime(512)
b = getPrime(512)
seed = getRandomRange(1, p)
cipher = AES.new(key=md5(long_to_bytes(seed)).digest(), mode=AES.MODE_CTR)
L = LCG(seed, a, b, p)

def replace_with_question_marks(input_str, probability):
    if not input_str:
        return input_str
    length = len(input_str)
    indices = set()
    while len(indices) < int(length * probability):
        indices.add(random.randint(0, length - 1))

    output_str = list(input_str)
    for index in indices:
        output_str[index] = "?"

    return "".join(output_str)


def replace_some_content():
    bin_a = bin(a)[2:].zfill(512)
    bin_b = bin(b)[2:].zfill(512)
    bin_first_next = bin(L.next())[2:].zfill(512)
    bin_second_next = bin(L.next())[2:].zfill(512)

    bin_a_replaced = replace_with_question_marks(bin_a, 0.19)
    bin_b_replaced = replace_with_question_marks(bin_b, 0.19)
    bin_first_next_replaced = replace_with_question_marks(bin_first_next, 0.19)
    bin_second_next_replaced = replace_with_question_marks(bin_second_next, 0.19)

    print(bin_a_replaced)
    print(bin_b_replaced)
    print(bin_first_next_replaced)
    print(bin_second_next_replaced)
    print(cipher.encrypt(pad(flag, 16)))
    print(cipher.nonce)


replace_some_content()


# a = "1100001101001?101111100?01110001010011?1???11???01000011100101010100101??011?01?00?0?000110000?01?01010?10101?1101010100010011?101010010000?10110??10100?000?1?11?10???0?1111?1000100100?1110111010?0?01?00?11?0011?0101101?100000?1??0101010?1?101?1001?0011110??0000000?00100?1010011100001111111001?10?001??0110001111?100110000110011011?111101?1??1010101101?01?0000011?1111001?000111??1??00010?10011001?000110000??10?10100000100?10?1101111?101?001??00?01111???01??1?10100??0101?011?1000?011101?110???0110111011?101?1"
# b = "1000?11?0111000?1001??11?1100?001?0?0111011011100?0?110?11111?1?0?111100?0111???01?001100?000?001??0110??0?001000000110?0100?01100?001000011?01001000011010100?01110000001??0000111???101101?0100?011??010011?0?100?0?111100?00110000111?10???0?01?100?1100?0111001?11?1110?011?100101101?10?0??00010011?101?111?110001100?0??0?10?11100100111?100100001?0?00000??1101001?010?110000110?0001101000010011001100?010?100000100001?10100101110010000?0111?0001??1?001100000010000?011000??0?10?1001000100???1100111?11?11011010100?"
# c1 = "1100101001100???1??101100?00101111?000001011?0??0?0?1??11?0001?1?01111?0?1100011101?01011??110011100001100100???000101?1011010100111110?11?010111101?0?0110?0100001?000?1011?111111111000001?100000001011?0110111?11010010100?10011110000?0101??1?00001111010110?00110001111011001?0010110101100011111?01?0000?0?0011?0?101??1111100?11?11100010???1?0?1?11?1100?1100010?1111111011?100100111?11?11?1101?1?1100111?01?01111?11?0??1111?001000?0000?1?010?100111101?01011?1?1?111?01???01?1111?01?????0?001011000111010010?111101"
# c2 = "00000000011?1000110011?001???10011010?0?01?11010011010??10010111?1111?1000?1??11?1111??111?1010001001111?10?0111001??101?10000000101111110111??11111?0?0??10?0101?111001101000101?00010?111?1100111?0?1110?1111?0110?11010110001100000111101?010010??0??101?1001000?010101?01110?01001010001?0?01?00?0110100100??10?00??1010111010010??1?100110?????01001?001110101111?1?00?0?00101?101?0?101?110011?1?00111100??1?1?00?1110?010?110?00?010011010001101?00110101?1??0010?101111000?11011101011?0010010110000000110110101??1?011?"
# enc = b'\xcb\xe0wY\xe3\\\xf7\xc8\x89/\x1c\xdb^P\xc09\xca\xcf\xe7\xa7\xa4\xb5\xaeQ\xc8K\xabg_\x8e\xfa?\xdc\xce9\xd7\x0en"?\xc0\n\xe0hT+\xc0\x81'
# nonce = b'n\x13\xd1\xdf\xb6]\xb5\xf7'

利用深搜加剪枝优化求解。
这里参考了一下小绿草密码ye的算法将，自己手搓了一遍。不过用z3也能做我试了一下但是效率会慢一些，不过我做的时候忘记給求二次剩余加上all_roots=True了。绷不住了。但是z3确实不适合做这种求全解爆破的。

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
import itertools  
import random  
from Crypto.Cipher import AES  
from Crypto.Util.number import *  
from hashlib import md5  
from sympy import sqrt_mod  
a = "1100001101001?101111100?01110001010011?1???11???01000011100101010100101??011?01?00?0?000110000?01?01010?10101?1101010100010011?101010010000?10110??10100?000?1?11?10???0?1111?1000100100?1110111010?0?01?00?11?0011?0101101?100000?1??0101010?1?101?1001?0011110??0000000?00100?1010011100001111111001?10?001??0110001111?100110000110011011?111101?1??1010101101?01?0000011?1111001?000111??1??00010?10011001?000110000??10?10100000100?10?1101111?101?001??00?01111???01??1?10100??0101?011?1000?011101?110???0110111011?101?1"  
b = "1000?11?0111000?1001??11?1100?001?0?0111011011100?0?110?11111?1?0?111100?0111???01?001100?000?001??0110??0?001000000110?0100?01100?001000011?01001000011010100?01110000001??0000111???101101?0100?011??010011?0?100?0?111100?00110000111?10???0?01?100?1100?0111001?11?1110?011?100101101?10?0??00010011?101?111?110001100?0??0?10?11100100111?100100001?0?00000??1101001?010?110000110?0001101000010011001100?010?100000100001?10100101110010000?0111?0001??1?001100000010000?011000??0?10?1001000100???1100111?11?11011010100?"  
c1 = "1100101001100???1??101100?00101111?000001011?0??0?0?1??11?0001?1?01111?0?1100011101?01011??110011100001100100???000101?1011010100111110?11?010111101?0?0110?0100001?000?1011?111111111000001?100000001011?0110111?11010010100?10011110000?0101??1?00001111010110?00110001111011001?0010110101100011111?01?0000?0?0011?0?101??1111100?11?11100010???1?0?1?11?1100?1100010?1111111011?100100111?11?11?1101?1?1100111?01?01111?11?0??1111?001000?0000?1?010?100111101?01011?1?1?111?01???01?1111?01?????0?001011000111010010?111101"  
c2 = "00000000011?1000110011?001???10011010?0?01?11010011010??10010111?1111?1000?1??11?1111??111?1010001001111?10?0111001??101?10000000101111110111??11111?0?0??10?0101?111001101000101?00010?111?1100111?0?1110?1111?0110?11010110001100000111101?010010??0??101?1001000?010101?01110?01001010001?0?01?00?0110100100??10?00??1010111010010??1?100110?????01001?001110101111?1?00?0?00101?101?0?101?110011?1?00111100??1?1?00?1110?010?110?00?010011010001101?00110101?1??0010?101111000?11011101011?0010010110000000110110101??1?011?"  
enc = b'\xcb\xe0wY\xe3\\\xf7\xc8\x89/\x1c\xdb^P\xc09\xca\xcf\xe7\xa7\xa4\xb5\xaeQ\xc8K\xabg_\x8e\xfa?\xdc\xce9\xd7\x0en"?\xc0\n\xe0hT+\xc0\x81'  
nonce = b'n\x13\xd1\xdf\xb6]\xb5\xf7'  
import itertools  
  
p = 2 ** 512  
A = [a, b, c1, c2]  
b = b[:-1] + '1'  
LL=[]  
  
def dfs(bbbb):  
    i = len(bbbb[0]) + 1  
    if len(bbbb[0]) == 512:  
        LL.append(bbbb)  
    else:  
        tmp=[]  
        for c in A:  
            if (c[-i]=='?'):  
                tmp.append(['0','1'])  
            else:  
                tmp.append([None])  
        for G in itertools.product(*tmp):  
            L = []  
            for j,k in enumerate(G):  
                if k is None:  
                    L.append(A[j][-i]+bbbb[j])  
                else:  
                    L.append(k+bbbb[j])  
            func=lambda x: int(x, 2)  
            a, b, c1, c2 = map(func, L)  
            if (a * c1**2 + b) % 2**i == c2:  
                dfs(L)  
  
  
  
dfs(["", "", "", ""])  
for a,b,c1,c2 in LL:  
    a = int(a, 2)  
    b = int(b, 2)  
    c1 = int(c1, 2)  
    c2 = int(c2, 2)  
    ss = (c1 - b) * pow(a, -1, 2 ** 512) % 2 ** 512  
    s=sqrt_mod(ss,2**512,all_roots=True)  
    for seed in s:  
        cipher = AES.new(key=md5(long_to_bytes(seed)).digest(), mode=AES.MODE_CTR, nonce=nonce)  
        res = cipher.decrypt(enc)  
        if b"flag" in res:  
            print(res)
crypto > 算法
#crypto #io
算法基础1
http://example.com/2025/09/23/算法1/
Author
fox
Posted on
September 23, 2025
Licensed under