前言

国城杯 2024 WriteUP，和Yolo打的，只解出一道逆向。复现Crypto全解，Reverse没做FunMz。

比赛时间：2024-12-07

完整 WriteUp

参考：国城杯 MXGA Writeup

Reverse

Round | Redo

复现的时候，发现这题WP当时写的有点冗杂了，所以重写一份。

程序接受用户名和密码，用户名的Base64编码（其实不是）为 c9m1bRmfY5Wk 。

分析这里的base64可以读源码，像我之前写的：

image-20250330222755309

实际上可以聪明点，把代码复制过来，加密试试，就会发现2、3位交换了，这样就能解密用户名了 round_and 。

前段时间做crypto学了一手剪枝，这比原来的代码好看多了。

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
class Round:
    def __init__(self):
        super().__init__()

    def shl(self, p0, p1):
        p0 = (p0 >> 3) % 1024
        return Round.Result(p0, ((p1 + p0) % 1024))

    def shr(self, p0, p1):
        p0 = (p0 << 3) % 1024
        return Round.Result(p0, ((p1 + p0) % 1024))

    def add(self, p0, p1, p2):
        p1 = (p1 + p0[p2]) % 1024
        return Round.Result(p1, (p2 + p1) % 1024)

    def sub(self, p0, p1, p2):
        p1 = (((p1 - p0[p2]) % 1024) + 1024) % 1024
        return Round.Result(p1, (p2 + p1) % 1024)

    def xor(self, p0, p1, p2):
        i = (p0[p2] ^ p1) % 1024
        return Round.Result(i, (p2 + i) % 1024)

    def round(self, p0, p1):
        assert len(p1) == 12
        result = None
        ointArray = [0] * 12
        i2 = 33
        for i in range(12):
            c = ord(p1[i])
            for _ in range(32):
                match (p0[i2] ^ c) % 5:
                    case 0:
                        result = self.add(p0, c, i2)
                    case 1:
                        result = self.sub(p0, c, i2)
                    case 2:
                        result = self.xor(p0, c, i2)
                    case 3:
                        result = self.shl(c, i2)
                    case 4:
                        result = self.shr(c, i2)
                    case _:
                        Round.Result(c, i2)
                c = result.getNum()
                i2 = result.getRip()
            ointArray[i] = c
        return ointArray

    class Result:
        def __init__(self, num, rip):
            self.num = num
            self.rip = rip

        def getNum(self):
            return self.num

        def getRip(self):
            return self.rip


def Makebox(p0):
    ointArray = [0] * 1024
    for i in range(1024):
        i2 = 1023 - i
        ointArray[i2] = i
    for i in range(1024):
        ointArray[i] ^= ord(p0[i % len(p0)])
    return ointArray


passwords = []
encoded_box = Makebox("c9m1bRmfY5Wk")


def dfs(password, i):
    ointArray1 = [352, 646, 752, 882, ord("A"), 0, ord("z"), 0, 0, 7, 350, 360]
    if i == 12:
        passwords.append(password)
        return

    for p in "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz_":
        password += p
        result = Round().round(encoded_box, password + "0" * (11 - i))
        if result[i] == ointArray1[i]:
            dfs(password, i + 1)
        password = password[:-1]
    return False


dfs("", 0)
print(passwords)
for password in passwords:
    print(f"D0g3xGC{{round_and{password}}}")
# ['_rounD_we_go']
# D0g3xGC{round_and_rounD_we_go}

crush’s_secret3 | Review

艹，我下载的附件运行不了，缺少ucrtbased.dll，VCRUNTIME140D.dll无法运行。

不过题还是很简单的，SMC段，下断点动态调试，是XXTEA，脚本：

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
#include <stdio.h>
#define _DWORD unsigned int

#include <stdio.h>
#include <stdlib.h>
#define delta 0x9e3779b9

void enc(unsigned int *v, unsigned int *key, int n)
{
    unsigned int sum = 0;
    unsigned int y, z, p, rounds, e;

    rounds = 6 + 52 / n;
    y = v[0];
    sum = rounds * delta;

    do
    {
        e = sum >> 2 & 3;
        for (p = n - 1; p > 0; p--)
        {
            z = v[p - 1];
            v[p] -= ((((z >> 5) ^ (y << 2)) + ((y >> 3) ^ (z << 4))) ^ ((key[(p & 3) ^ e] ^ z) + (y ^ sum)));
            y = v[p];
        }
        z = v[n - 1];
        v[0] -= (((key[(p ^ e) & 3] ^ z) + (y ^ sum)) ^ (((y << 2) ^ (z >> 5)) + ((z << 4) ^ (y >> 3))));
        y = v[0];
        sum = sum - delta;
    } while (--rounds);
}

int main()
{
    unsigned int v[12] = {0x5A764F8A, 0x05B0DF77, 0xF101DF69, 0xF9C14EF4, 0x27F03590, 0x7DF3324F, 0x2E322D74, 0x8F2A09BC, 0xABE2A0D7, 0x0C2A09FE, 0x35892BB2, 0x53ABBA12};
    unsigned int key[4] = {0x05201314, 0x52013140, 0x05201314, 0x52013140};
    int n = 2; // 轮数

    for (int j = 0; j < 12; j += 2)
    {
        enc(&v[j], key, n);
    }
    puts((char *)v);
    // The_wind_stops_at_autumn_water_and_I_stop_at_you

    return 0;
}

这出题人还挺文雅的，风止于秋水，我止于你。

ez_key | Review

sys逆向题，flag就在这些数字中。

image-20250330195955393

看出现的字符串可以猜出与键盘驱动相关

image-20250330205731582

键盘的键值，可能是统一的keycode、USB协议的HID键值、PS/2的键值。PS/2还分Set1、Set2、Set3，Make或Break。

HID码按键名称 HID码 PS/2 Set1 Make PS/2 Set1 Break PS/2 Set2 Make PS/2 Set2 Break PS/2 Set3 Make PS/2 Set3 Break
A \ a 0x04 1E 9E 1C F0 1C 1C F0 1C
B \ b 0x05 30 B0 32 F0 32 32 F0 32
C \ c 0x06 2E AE 21 F0 21 21 F0 21
D \ d 0x07 20 A0 23 F0 23 23 F0 23
E \ e 0x08 12 92 24 F0 24 24 F0 24
F \ f 0x09 21 A1 2B F0 2B 2B F0 2B
G \ g 0x0A 22 A2 34 F0 34 34 F0 34
H \ h 0x0B 23 A3 33 F0 33 33 F0 33
I \ i 0x0C 17 97 43 F0 43 43 F0 43
J \ j 0x0D 24 A4 3B F0 3B 3B F0 3B
K \ k 0x0E 25 A5 42 F0 42 42 F0 42
L \ l 0x0F 26 A6 4B F0 4B 4B F0 4B
M \ m 0x10 32 B2 3A F0 3A 3A F0 3A
N \ n 0x11 31 B1 31 F0 31 31 F0 31
O \ o 0x12 18 98 44 F0 44 44 F0 44
P \ p 0x13 19 99 4D F0 4D 4D F0 4D
Q \ q 0x14 10 90 15 F0 15 15 F0 15
R \ r 0x15 13 93 2D F0 2D 2D F0 2D
S \ s 0x16 1F 9F 1B F0 1B 1B F0 1B
T \ t 0x17 14 94 2C F0 2C 2C F0 2C
U \ u 0x18 16 96 3C F0 3C 3C F0 3C
V \ v 0x19 2F AF 2A F0 2A 2A F0 2A
W \ w 0x1A 11 91 1D F0 1D 1D F0 1D
X \ x 0x1B 2D AD 22 F0 22 22 F0 22
Y \ y 0x1C 15 95 35 F0 35 35 F0 35
Z \ z 0x1D 2C AC 1A F0 1A 1A F0 1A
Enter（回车） 0x28 1C 9C 5A F0 5A 5A F0 5A
Ese 0x29 01 81 76 F0 76 76 F0 76
Backspace 0x2A 0E 8E 66 F0 66 66 F0 66
Tab 0x2B 0F 8F 0D F0 0D 0D F0 0D
Spacebar（空格） 0x2C 39 B9 29 F0 29 29 F0 29
- \ _ 0x2D 0C 8C 4E F0 4E 4E F0 4E
+ \ = 0x2E 0D 8D 55 F0 55 55 F0 55
{ \ [ 0x2F 1A 9A 54 F0 54 54 F0 54
} \ ] 0x30 1B 9B 5B F0 5B 5B F0 5B
| \ | 0x31 2B AB 5D F0 5D 5D F0 5D
: \ ; 0x33 2C AC 5E F0 5E 5E F0 5E
" \ ’ 0x34 2D AD 5F F0 5F 5F F0 5F
~ \ ` 0x35 35 B5 63 F0 63 63 F0 63
< \ , 0x36 36 B6 60 F0 60 60 F0 60
> \ . 0x37 37 B7 61 F0 61 61 F0 61
? \ / 0x38 38 B8 62 F0 62 62 F0 62
Caps Lock(大写) 0x39 3A BA 46 F0 46 46 F0 46
F1 0x3A 3B BB 05 F0 05 05 F0 05
F2 0x3B 3C BC 06 F0 06 06 F0 06
F3 0x3C 3D BD 04 F0 04 04 F0 04
F4 0x3D 3E BE 0C F0 0C 0C F0 0C
F5 0x3E 3F BF 03 F0 03 03 F0 03
F6 0x3F 40 C0 0B F0 0B 0B F0 0B
F7 0x40 41 C1 83 F0 83 83 F0 83
F8 0x41 42 C2 0A F0 0A 0A F0 0A
F9 0x42 43 C3 01 F0 01 01 F0 01
F10 0x43 44 C4 09 F0 09 09 F0 09
F11 0x44 57 D7 78 F0 78 78 F0 78
F12 0x45 58 D8 07 F0 07 07 F0 07
PrintScreen 0x46 E0 37 E0 F0 37 E0 37 E0 F0 37 E0 37 E0 F0 37
Scroll Lock 0x47 E0 46 E0 C6 E0 46 E0 C6 E0 46 E0 C6
Pause 0x48 E1 14 77 E1 F0 14 F0 77 E1 14 77 E1 F0 14 F0 77 E1 14 77 E1 F0 14 F0 77
Insert 0x49 E0 70 E0 F0 70 E0 70 E0 F0 70 E0 70 E0 F0 70
Home 0x4A E0 6C E0 F0 6C E0 6C E0 F0 6C E0 6C E0 F0 6C
PageUp（上一页） 0x4B E0 6B E0 F0 6B E0 6B E0 F0 6B E0 6B E0 F0 6B
Delete 0x4C E0 71 E0 F0 71 E0 71 E0 F0 71 E0 71 E0 F0 71
End 0x4D E0 69 E0 F0 69 E0 69 E0 F0 69 E0 69 E0 F0 69
PageDown 0x4E E0 6A E0 F0 6A E0 6A E0 F0 6A E0 6A E0 F0 6A
RightArrow 0x4F E0 74 E0 F0 74 E0 74 E0 F0 74 E0 74 E0 F0 74
LeftArrow 0x50 E0 6B E0 F0 6B E0 6B E0 F0 6B E0 6B E0 F0 6B
DownArrow 0x51 E0 72 E0 F0 72 E0 72 E0 F0 72 E0 72 E0 F0 72
UpArrow 0x52 E0 71 E0 F0 71 E0 71 E0 F0 71 E0 71 E0 F0 71
Num Lock and Clear 0x53 E0 45 E0 C5 E0 45 E0 C5 E0 45 E0 C5
/ 0x54 E0 4A E0 CAA E0 4A E0 CAA E0 4A E0 CAA
* 0x55 37 B7 37 F0 37 37 F0 37
- 0x56 4A CAB 4A F0 4A 4A F0 4A
+ 0x57 4E CEB 4E F0 4E 4E F0 4E
Enter 0x58 9C F0 9C 5A F0 5A 5A F0 5A
1 \ End 0x59 E0 79 E0 F0 79 E0 79 E0 F0 79 E0 79 E0 F0 79
2 \ Down Arrow 0x5A E0 7A E0 F0 7A E0 7A E0 F0 7A E0 7A E0 F0 7A
3 \ Page Dn 0x5B E0 6C E0 F0 6C E0 6C E0 F0 6C E0 6C E0 F0 6C
4 \ Left Arrow 0x5C E0 71 E0 F0 71 E0 71 E0 F0 71 E0 71 E0 F0 71
5 0x5D E0 6D E0 F0 6D E0 6D E0 F0 6D E0 6D E0 F0 6D
6 \ Right Arrow 0x5E E0 72 E0 F0 72 E0 72 E0 F0 72 E0 72 E0 F0 72
7 \ Home 0x5F E0 6C E0 F0 6C E0 6C E0 F0 6C E0 6C E0 F0 6C
8 \ Up Arrow 0x60 E0 75 E0 F0 75 E0 75 E0 F0 75 E0 75 E0 F0 75
9 \ PageUp 0x61 E0 6A E0 F0 6A E0 6A E0 F0 6A E0 6A E0 F0 6A
0 \ Insert 0x62 E0 70 E0 F0 70 E0 70 E0 F0 70 E0 70 E0 F0 70
. \ Delete 0x63 E0 71 E0 F0 71 E0 71 E0 F0 71 E0 71 E0 F0 71
\ \ | （非美式） 0x64 E0 64 E0 C4 E0 64 E0 C4 E0 64 E0 C4
Application(应用) 0x65 E0 5D E0 F0 5D E0 5D E0 F0 5D E0 5D E0 F0 5D
Power(电源) 0x66 E0 5E E0 F0 5E E0 5E E0 F0 5E E0 5E E0 F0 5E
keypad =(小键盘) 0x67 E0 5A E0 F0 5A E0 5A E0 F0 5A E0 5A E0 F0 5A

这道题是PS/2 Set2 Make

1
2
3
4
5
6
7
8
ps2_key_map = { 0x01: "[ESC]", 0x02: "1", 0x03: "2", 0x04: "3", 0x05: "4", 0x06: "5", 0x07: "6", 0x08: "7", 0x09: "8", 0x0A: "9", 0x0B: "0", 0x0C: "-", 0x0D: "=", 0x0E: "[BACKSPACE]", 0x0F: "[TAB]", 0x10: "Q", 0x11: "W", 0x12: "E", 0x13: "R", 0x14: "T", 0x15: "Y", 0x16: "U", 0x17: "I", 0x18: "O", 0x19: "P", 0x1A: "[", 0x1B: "]", 0x1C: "[ENTER]", 0x1D: "[LEFT_CTRL]", 0x1E: "A", 0x1F: "S", 0x20: "D", 0x21: "F", 0x22: "G", 0x23: "H", 0x24: "J", 0x25: "K", 0x26: "L", 0x27: ";", 0x28: "'", 0x29: "`", 0x2A: "[LEFT_SHIFT]", 0x2B: "\\", 0x2C: "Z", 0x2D: "X", 0x2E: "C", 0x2F: "V", 0x30: "B", 0x31: "N", 0x32: "M", 0x33: ",", 0x34: ".", 0x35: "/", 0x36: "[RIGHT_SHIFT]", 0x37: "*", 0x38: "[LEFT_ALT]", 0x39: "[SPACE]", 0x3A: "[CAPS_LOCK]", 0x3B: "[F1]", 0x3C: "[F2]", 0x3D: "[F3]", 0x3E: "[F4]", 0x3F: "[F5]", 0x40: "[F6]", 0x41: "[F7]", 0x42: "[F8]", 0x43: "[F9]", 0x44: "[F10]", 0x45: "[NUM_LOCK]", 0x46: "[SCROLL_LOCK]", 0x47: "7", 0x48: "8", 0x49: "9", 0x4A: "-", 0x4B: "4", 0x4C: "5", 0x4D: "6", 0x4E: "+", 0x4F: "1", 0x50: "2", 0x51: "3", 0x52: "0", 0x53: ".", 0x57: "[F11]", 0x58: "[F12]", 0x81: "[ESC_RELEASE]", 0x82: "[1_RELEASE]", 0x83: "[2_RELEASE]", 0x84: "[3_RELEASE]", 0x85: "[4_RELEASE]", 0x86: "[5_RELEASE]", 0x87: "[6_RELEASE]", 0x88: "[7_RELEASE]", 0x89: "[8_RELEASE]", 0x8A: "[9_RELEASE]", 0x8B: "[0_RELEASE]", 0x8C: "[-_RELEASE]", 0x8D: "[=_RELEASE]", 0x8E: "[BACKSPACE_RELEASE]", 0x8F: "[TAB_RELEASE]", 0x90: "[Q_RELEASE]", 0x91: "[W_RELEASE]", 0x92: "[E_RELEASE]", 0x93: "[R_RELEASE]", 0x94: "[T_RELEASE]", 0x95: "[Y_RELEASE]", 0x96: "[U_RELEASE]", 0x97: "[I_RELEASE]", 0x98: "[O_RELEASE]", 0x99: "[P_RELEASE]", 0x9A: "[[_RELEASE]", 0x9B: "[]_RELEASE]", 0x9C: "[ENTER_RELEASE]", 0x9D: "[LEFT_CTRL_RELEASE]", 0x9E: "[A_RELEASE]", 0x9F: "[S_RELEASE]", 0xA0: "[D_RELEASE]", 0xA1: "[F_RELEASE]", 0xA2: "[G_RELEASE]", 0xA3: "[H_RELEASE]", 0xA4: "[J_RELEASE]", 0xA5: "[K_RELEASE]", 0xA6: "[L_RELEASE]", 0xA7: "[;_RELEASE]", 0xA8: "['_RELEASE]", 0xA9: "[`_RELEASE]", 0xAA: "[LEFT_SHIFT_RELEASE]", 0xAB: "[\\_RELEASE]", 0xAC: "[Z_RELEASE]", 0xAD: "[X_RELEASE]", 0xAE: "[C_RELEASE]", 0xAF: "[V_RELEASE]", 0xB0: "[B_RELEASE]", 0xB1: "[N_RELEASE]", 0xB2: "[M_RELEASE]", 0xB3: "[,_RELEASE]", 0xB4: "[._RELEASE]", 0xB5: "[/_RELEASE]", 0xB6: "[RIGHT_SHIFT_RELEASE]", 0xB7: "[*_RELEASE]", 0xB8: "[LEFT_ALT_RELEASE]", 0xB9: "[SPACE_RELEASE]", 0xBA: "[CAPS_LOCK_RELEASE]", 0xBB: "[F1_RELEASE]", 0xBC: "[F2_RELEASE]", 0xBD: "[F3_RELEASE]", 0xBE: "[F4_RELEASE]", 0xBF: "[F5_RELEASE]", 0xC0: "[F6_RELEASE]", 0xC1: "[F7_RELEASE]", 0xC2: "[F8_RELEASE]", 0xC3: "[F9_RELEASE]", 0xC4: "[F10_RELEASE]", 0xC5: "[NUM_LOCK_RELEASE]", 0xC6: "[SCROLL_LOCK_RELEASE]", 0xC7: "7_RELEASE", 0xC8: "8_RELEASE", 0xC9: "9_RELEASE", 0xCA: "-_RELEASE", 0xCB: "4_RELEASE", 0xCC: "5_RELEASE", 0xCD: "6_RELEASE", 0xCE: "+_RELEASE", 0xCF: "1_RELEASE", 0xD0: "2_RELEASE", 0xD1: "3_RELEASE", 0xD2: "0_RELEASE", 0xD3: "._RELEASE", 0xD7: "[F11_RELEASE]", 0xD8: "[F12_RELEASE]"}

keys = [ 32, 42, 11, 34, 4, 45, 34, 42, 46, 42, 26, 42, 30, 7, 7, 48, 3, 4, 5, 3, 12, 11, 5, 32, 5, 12, 5, 7, 9, 30, 12, 10, 10, 32, 4, 12, 8, 18, 32, 48, 30, 5, 46, 10, 11, 11, 2, 33, 27, 42]

print("".join([ps2_key_map.get(ps2_key, "Unknown Key") for ps2_key in keys]))
# D[LEFT_SHIFT]0G3XG[LEFT_SHIFT]C[LEFT_SHIFT][[LEFT_SHIFT]A66B2342-04D4-468A-99D3-7EDBA4C9001F][LEFT_SHIFT]
# D0g3xGC{a66b2342-04d4-468a-99d3-7edba4c9001f}

Crypto

Curve | Review

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

def add(P, Q):
    (x1, y1) = P
    (x2, y2) = Q

    x3 = (x1*y2 + y1*x2) * inverse(1 + d*x1*x2*y1*y2, p) % p
    y3 = (y1*y2 - a*x1*x2) * inverse(1 - d*x1*x2*y1*y2, p) % p
    return (x3, y3)

def mul(x, P):
    Q = (0, 1)
    while x > 0:
        if x % 2 == 1:
            Q = add(Q, P)
        P = add(P, P)
        x = x >> 1
    return Q

p = 64141017538026690847507665744072764126523219720088055136531450296140542176327
a = 362
d = 7
e=0x10001

gx=bytes_to_long(b'D0g3xGC{*****************}')

PR.<y>=PolynomialRing(Zmod(p))
f=(d*gx^2-1)*y^2+(1-a*gx^2)
gy=int(f.roots()[0][0])

assert (a*gx^2+gy^2)%p==(1+d*gx^2*gy^2)%p

G=(gx,gy)

eG = mul(e, G)
print(eG)

#eG = (34120664973166619886120801966861368419497948422807175421202190709822232354059, 11301243831592615312624457443883283529467532390028216735072818875052648928463)

题目给出了eG、e、椭圆曲线的参数，要求G的x坐标。

只需要算出e的逆即可求出G，要算e的逆则需要椭圆曲线的阶，而题目中的椭圆曲线是Twisted Edwards Curve，需要将其转化为sage可解的Weierstrass Curve形式即可。

下面是转换公式：

Montgomery -> Weierstrass：{A=3−J23K2B=2J3−9J27K3\begin{cases} A &= \frac{3 - J^2}{3K^2} \\ B &= \frac{2J^3 - 9J}{27K^3} \end{cases}

Twisted Edwards -> Montgomery：{J=2(a+d)a−dK=4a−d\begin{cases} J &= \frac{2(a + d)}{a - d} \\ K &= \frac{4}{a - d} \end{cases}

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 *

p = 64141017538026690847507665744072764126523219720088055136531450296140542176327
a = 362
d = 7
e = 0x10001


def add(P, Q):
    (x1, y1) = P
    (x2, y2) = Q

    x3 = (x1 * y2 + y1 * x2) * inverse(1 + d * x1 * x2 * y1 * y2, p) % p
    y3 = (y1 * y2 - a * x1 * x2) * inverse(1 - d * x1 * x2 * y1 * y2, p) % p
    return (x3, y3)


def mul(x, P):
    Q = (0, 1)
    while x > 0:
        if x % 2 == 1:
            Q = add(Q, P)
        P = add(P, P)
        x = x >> 1
    return Q


eG = (
    34120664973166619886120801966861368419497948422807175421202190709822232354059,
    11301243831592615312624457443883283529467532390028216735072818875052648928463,
)

# T -> M
J = 2 * (a + d) / (a - d)
K = 4 / (a - d)

# M -> W
A = (3 - J**2) / (3 * K**2)
B = (2 * J**3 - 9 * J) / (27 * K**3)

E = EllipticCurve(Zmod(p), [0, 0, 0, A, B])
od = E.order()
e_inv = int(pow(e, -1, od))
G = mul(e_inv, eG)

print(long_to_bytes(G[0]))  # b'D0g3xGC{SOlvE_The_Edcurv3}'

Ez_sign | Review

题目

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

flag = b"D0g3xGA{***************}"
msg = b"e = ?"


def sign(pub, pri, k):
    (p, q, g, y) = pub
    x = pri
    r = int(powmod(g, k, p) % q)
    H = bytes_to_long(sha1(os.urandom(20)).digest())
    s = int((H + r * x) * invert(k, q) % q)
    return (H, r, s)


k1 = getPrime(64)
k2 = k1**2
pri = bytes_to_long(msg)
a = 149328490045436942604988875802116489621328828898285420947715311349436861817490291824444921097051302371708542907256342876547658101870212721747647670430302669064864905380294108258544172347364992433926644937979367545128905469215614628012983692577094048505556341118385280805187867314256525730071844236934151633203
b = 829396411171540475587755762866203184101195238207
g = 87036604306839610565326489540582721363203007549199721259441400754982765368067012246281187432501490614633302696667034188357108387643921907247964850741525797183732941221335215366182266284004953589251764575162228404140768536534167491117433689878845912406615227673100755350290475167413701005196853054828541680397
y = 97644672217092534422903769459190836176879315123054001151977789291649564201120414036287557280431608390741595834467632108397663276781265601024889217654490419259208919898180195586714790127650244788782155032615116944102113736041131315531765220891253274685646444667344472175149252120261958868249193192444916098238

pub = (a, b, g, y)

H1, r1, s1 = sign(pub, pri, k1)

H2, r2, s2 = sign(pub, pri, k2)

p = getPrime(128)
q = getPrime(128)
n = p * q
c = powmod(bytes_to_long(flag), e, n)

C = p**2 + q**2

print(f"(H1, r1, s1) = {H1}, {r1}, {s1}")
print(f"(H2, r2, s2) = {H2}, {r2}, {s2}")
print(c)
print(C)

"""
(H1, r1, s1) = 659787401883545685817457221852854226644541324571, 334878452864978819061930997065061937449464345411, 282119793273156214497433603026823910474682900640
(H2, r2, s2) = 156467414524100313878421798396433081456201599833, 584114556699509111695337565541829205336940360354, 827371522240921066790477048569787834877112159142
c = 18947793008364154366082991046877977562448549186943043756326365751169362247521
C = 179093209181929149953346613617854206675976823277412565868079070299728290913658
"""

两个部分，第一部分通过两个签名解出msg（e = ?），第二部分解一个二平方问题，来算RSA。

因为两个签名的k具有平方关系，利用这点消元，会得出一元二次同余方程，读者可自行计算。

然后用sage解一下即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def solve_e(sign1, sign2, q):
    H1, r1, s1 = sign1
    H2, r2, s2 = sign2

    s1_inv = inverse(s1, q)
    s2_inv = inverse(s2, q)

    A = r1 * r1 * s1_inv * s1_inv
    B = 2 * H1 * r1 * s1_inv * s1_inv - r2 * s2_inv
    C = H1 * H1 * s1_inv * s1_inv - H2 * s2_inv

    P = PolynomialRing(Zmod(q), "x")
    x = P.gen()
    eq = A * x ^ 2 + B * x + C

    print(eq.roots())
    # [(91973915966463187834053272623425597244095846333, 1), (1865444199836044046649, 1)]

    print(long_to_bytes(91973915966463187834053272623425597244095846333))
    print(long_to_bytes(1865444199836044046649))  # b'e = 44519'

第二部分借用了脚本https://ask.sagemath.org/question/76636/sum-of-2-squares/

原理是将N在复数域分解因子，其中存在 N=p2+q2=(p+qi)(p−qi)N = p^2+q^2 = (p+qi)(p-qi)

本例中N的因子有768个，完全可以在合理的时间内求解。

1
2
3
4
def all_two_squares(n):
    return [
        (abs(d[0]), abs(d[1])) for d in divisors(GaussianIntegers()(n)) if norm(d) == 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
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
from Crypto.Util.number import *


def all_two_squares(n):
    return [
        (abs(d[0]), abs(d[1])) for d in divisors(GaussianIntegers()(n)) if norm(d) == n
    ]


def solve_e(sign1, sign2, q):
    H1, r1, s1 = sign1
    H2, r2, s2 = sign2

    s1_inv = inverse(s1, q)
    s2_inv = inverse(s2, q)

    A = r1 * r1 * s1_inv * s1_inv
    B = 2 * H1 * r1 * s1_inv * s1_inv - r2 * s2_inv
    C = H1 * H1 * s1_inv * s1_inv - H2 * s2_inv

    P = PolynomialRing(Zmod(q), "x")
    x = P.gen()
    eq = A * x ^ 2 + B * x + C

    print(eq.roots())
    # [(91973915966463187834053272623425597244095846333, 1), (1865444199836044046649, 1)]

    print(long_to_bytes(91973915966463187834053272623425597244095846333))
    print(long_to_bytes(1865444199836044046649))  # b'e = 44519'


p = 149328490045436942604988875802116489621328828898285420947715311349436861817490291824444921097051302371708542907256342876547658101870212721747647670430302669064864905380294108258544172347364992433926644937979367545128905469215614628012983692577094048505556341118385280805187867314256525730071844236934151633203
q = 829396411171540475587755762866203184101195238207
g = 87036604306839610565326489540582721363203007549199721259441400754982765368067012246281187432501490614633302696667034188357108387643921907247964850741525797183732941221335215366182266284004953589251764575162228404140768536534167491117433689878845912406615227673100755350290475167413701005196853054828541680397
y = 97644672217092534422903769459190836176879315123054001151977789291649564201120414036287557280431608390741595834467632108397663276781265601024889217654490419259208919898180195586714790127650244788782155032615116944102113736041131315531765220891253274685646444667344472175149252120261958868249193192444916098238

H1, r1, s1 = (
    659787401883545685817457221852854226644541324571,
    334878452864978819061930997065061937449464345411,
    282119793273156214497433603026823910474682900640,
)
H2, r2, s2 = (
    156467414524100313878421798396433081456201599833,
    584114556699509111695337565541829205336940360354,
    827371522240921066790477048569787834877112159142,
)
c = 18947793008364154366082991046877977562448549186943043756326365751169362247521
C = 179093209181929149953346613617854206675976823277412565868079070299728290913658

# solve_e((H1, r1, s1), (H2, r2, s2), q)
# ans = all_two_squares(C)
# print(ans)

e = 44519
ans = [
    (411800265284112683889770914584779351243, 97538457512222161659361018727247943103),
    (385935421767853150067085999079428269993, 173629085716646134993835981317457288147),
    (347432454257893250496407965506777649463, 241627603783727624224706687817893681267),
    (302951519846417861008714825074296492447, 295488723650623654106370451762393175957),
    (295488723650623654106370451762393175957, 302951519846417861008714825074296492447),
    (173629085716646134993835981317457288147, 385935421767853150067085999079428269993),
    (139154793241392602890445837550424516283, 399661297475592982293435778542228355087),
    (16944416637726545286802875167254662553, 422854698361903371427733980562270024707),
    (63300355510251304584114633515453587403, 418433117922332896279236283423489909057),
    (97538457512222161659361018727247943103, 411800265284112683889770914584779351243),
    (212200170463729600479653952183489384503, 366147916608975462877987617004979518093),
    (241627603783727624224706687817893681267, 347432454257893250496407965506777649463),
    (366147916608975462877987617004979518093, 212200170463729600479653952183489384503),
    (399661297475592982293435778542228355087, 139154793241392602890445837550424516283),
    (418433117922332896279236283423489909057, 63300355510251304584114633515453587403),
    (422854698361903371427733980562270024707, 16944416637726545286802875167254662553),
]


for p, q in ans:
    N = p * q
    phi = (p - 1) * (q - 1)
    d = inverse(e, phi)
    m = pow(c, d, N)

    try:
        print(long_to_bytes(int(m)).decode())
    except:
        pass
        
# D0g3xGC{EZ_DSA_@nd_C0mplex_QAQ}

BabyRSA | Review

题目

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

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


def gen_key(p, q):
    public_key = p * p * q
    e = public_key
    n = p * q
    phi_n = (p - 1) * (q - 1)
    private_key = inverse(e, phi_n)
    return public_key, private_key, e


p = getPrime(512)
q = getPrime(512)

N, d, e = gen_key(p, q)

c = gmpy2.powmod(bytes_to_long(flag), e, N)

print(N)
print(d)
print(c)

"""
n = 539403894871945779827202174061302970341082455928364137444962844359039924160163196863639732747261316352083923762760392277536591121706270680734175544093484423564223679628430671167864783270170316881238613070741410367403388936640139281272357761773388084534717028640788227350254140821128908338938211038299089224967666902522698905762169859839320277939509727532793553875254243396522340305880944219886874086251872580220405893975158782585205038779055706441633392356197489
d = 58169755386408729394668831947856757060407423126014928705447058468355548861569452522734305188388017764321018770435192767746145932739423507387500606563617116764196418533748380893094448060562081543927295828007016873588530479985728135015510171217414380395169021607415979109815455365309760152218352878885075237009
c = 82363935080688828403687816407414245190197520763274791336321809938555352729292372511750720874636733170318783864904860402219217916275532026726988967173244517058861515301795651235356589935260088896862597321759820481288634232602161279508285376396160040216717452399727353343286840178630019331762024227868572613111538565515895048015318352044475799556833174329418774012639769680007774968870455333386419199820213165698948819857171366903857477182306178673924861370469175
"""

已知 N=e=p2qN=e=p^2q ，$ c \equiv m^e \pmod{N}$ ，d=e−1(mod(p−1)(q−1))d = e^{-1} \pmod{(p-1)(q-1)}，还原明文。

显然有 med≡m(modpq)m^{ed} \equiv m \pmod{pq}，所以有 med−m=kpqm^{ed} - m = kpq ，观察发现这里m替换成其他数依然成立

令 m=2m=2 代入，即可求出 pq=gcd⁡(kpq,p2q)pq=\gcd(kpq,p^2q)

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


N = 539403894871945779827202174061302970341082455928364137444962844359039924160163196863639732747261316352083923762760392277536591121706270680734175544093484423564223679628430671167864783270170316881238613070741410367403388936640139281272357761773388084534717028640788227350254140821128908338938211038299089224967666902522698905762169859839320277939509727532793553875254243396522340305880944219886874086251872580220405893975158782585205038779055706441633392356197489
d = 58169755386408729394668831947856757060407423126014928705447058468355548861569452522734305188388017764321018770435192767746145932739423507387500606563617116764196418533748380893094448060562081543927295828007016873588530479985728135015510171217414380395169021607415979109815455365309760152218352878885075237009
c = 82363935080688828403687816407414245190197520763274791336321809938555352729292372511750720874636733170318783864904860402219217916275532026726988967173244517058861515301795651235356589935260088896862597321759820481288634232602161279508285376396160040216717452399727353343286840178630019331762024227868572613111538565515895048015318352044475799556833174329418774012639769680007774968870455333386419199820213165698948819857171366903857477182306178673924861370469175

pq = GCD(pow(2, N * d, N) - 2, N)
m = pow(c, d, pq)
m = long_to_bytes(m)
print(m)  # b'D0g3xGC{W1sh_Y0u_Go0d_L@ucK-111}'