国城杯2024 WriteUP

摘要

国城杯2024的WriteUP，Crypto全解，Reverse没做FunMz，一方面给的exe要求VS2022的环境，我偏爱VS Code，另一方面题目太复杂了，实在做不动。

前言

这次是2024年12月上旬的比赛，两人组队打的，我就做出来一道逆向，密码爆零了。我们校队的密码师傅直接ak了，我还得练啊。。

比赛WP：国城杯2024 WriteUP

Reverse

Round | Redo

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

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

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

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

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

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

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

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

#include 
#define _DWORD unsigned int

#include 
#include 
#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

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

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

键盘的键值，可能是统一的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

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

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

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

下面是转换公式：

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

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

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

Ez_sign

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

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

然后用sage解一下即可

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 = p^2+q^2 = (p+qi)(p-qi)$

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

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

完整代码：

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

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

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

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

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)