kashiCTF 2026 - Efficient

Posted on Edited on In Views: Disqus:

Generating primes is expensive. I optimized my key generation to be twice as fast. The modulus is 4096 bits — perfectly secure.

Initial Analysis

The hint "optimized my key generation to be twice as fast" suggests that instead of generating two distinct large primes, the author might have reused the same prime (\(n = p^2\)) or chosen two primes that are extremely close to each other. This makes the modulus vulnerable to Fermat's Factorization Method or simply taking the square root.

Extraction & Decoding

Given a 4096-bit modulus \(n\), we can check if it's a perfect square or if its factors are close to \(\sqrt{n}\) by starting from \(\lfloor\sqrt{n}\rfloor\) and searching downwards. Once factored, we calculate \(\phi(n)\), derive the private key \(d\), and decrypt the AES key which was used to encrypt the flag.

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
import math
import base64
from Crypto.Util.number import long_to_bytes, bytes_to_long
from Crypto.Util.Padding import unpad
from Crypto.Cipher import AES

# Modulus and public exponent
n = 0x752a94a112ba0ce096f47934dac094d3d07b8c036613938142c0d4c15fc82692eee38d2457dd8d16472c4ddbe8cb5e2a6331e0ca0351094fc9516559768ebfe44509154d64116fa1fe1daf698413d37c9fe3406555f3190e29d99bee0cdd663d531c8e818f2686c7ad24338b4e93c6bfbd1b5a6dc5161316b2cb9ac1ae05a4ac43fdeb3b024b2e00dfcd87069ea1645996d9ad16ac3a9697414c17279112303a1d21136a99dc47628e15a3d6e18779de7aec310331dff1a81871b03e214de09f56c0f3de02f9f399be4ebc094f34b578d311a8b48e9c6cf2fa2f4e321f1dab0a99e5b9d99464c19452d9cc21544ac8e32fb9f13d1b2990758de0876de465cbd3632f846ef49fd7b97abee2ce529cfbc75a0d0792df6cc8091198134e9f646cf7d33c85c4ddd2c4b9a248c2c470d7369ebc7245bcec049455da2ceb742b26058514418398149d03cd1ad74a997375d0462a43e73aa62fc1f7e0dcc67e8f1559073074b9b8d3c37edfcfce67fd1822227933c5a14425d76119fc0a25da4c059761c86bc3077c4d096d9b9f6ae2faf728dbf24d48fa74d99c8c0d8780d2963ca9eccef0dd847ce22fc5b13793981257a9d4dd1af965e9baa5bd9fc4e3321cf8c6fd9871e342e5ae0dff19ab6e9fd8e14b5cc766b92df3306ef63af248b019528928644007c17e31918f9fdf10daeadc1eb8abeb6297bdc8f8e9b27c591f12159479
e = 65537

# Factor n
p = math.isqrt(n)
while n % p != 0:
    p -= 1
q = n // p

# Calculate phi
if p == q:
    phi = p * (p - 1)
else:
    phi = (p - 1) * (q - 1)

# Decrypt AES Key
d = pow(e, -1, phi)
ct_b64 = "MVoAMG4KRlXdSxEtVL/GpwXWyelWmAsJJhMnPaTzF2Hhjm/h/vkHJKQIyHSld2XuB6Q0sWq/TN1dkSePEB1oq6ugzMcgp5VQ9Xn0mOCn1GZ7fP3bKUVD6mG1bt3dkHxzlAT7v6c6xKaTtJJKTV3JXnB2u3duW4dCrFyassEjHM1PEML3CWqJBrgxnlTIYI4i9ydwg1MF1fTOBTm2KLlQ6rIGnBWcGwg4k+8I7e0mIbhod53w3FzIPXePv0ONVp+HBn4XsICwEHhJLXixmHcEz0jxwCgRdz9qr+Ur1pOaVuKN/26cwpYdVTlY5Fk7KapoV3Ews69353gCa+QYiJtzuwr1uFTBe74GfZZ8xzxFK51TnMbqB1M5cpzBK8/TK+ES/+yy1R4jsGkQ4i7Qz0oAsqBoNExSaLsNgwzZe4dYRE2BwDy2tW2QAYFUeU+SVjUb2BI67QtQYl2g+GB0kAMzbcRFr/kykIHqqb2N05BxgRrtsFjq2zWvpJJ71OFCrWVg8IzO7N+WUXFFyFv7ZfdnKOhC/iPNNmLbJXa3Gul89Fa6VyvCJw6lA/t7QCsjtcVG7ox51JAvoHhw5FLIpT+wmfq969iUujkXzLpjyXBVrfnEdjRt61zGEd3tmWIYst721GcKnbxKBehxwpseDBYR0hJRy+CIf5SnrP6/Blq55cQ="
ct_int = bytes_to_long(base64.b64decode(ct_b64))
aes_key = long_to_bytes(pow(ct_int, d, n))

# Decrypt Flag
iv = base64.b64decode("XSCnpZLyN1Oin7F67hOKWQ==")
flag_ct = base64.b64decode("n+H1n3ezKEm0ulyLMcp/ShxLZAddKX7y848o/Lf/56qDev/DPBz+IRcJ14yHWGOuodMaMwyLZi9er7slNa+QMw==")

cipher = AES.new(aes_key, AES.MODE_CBC, iv)
flag = unpad(bytes(cipher.decrypt(flag_ct)), AES.block_size).decode()

print(f"\n[+] FLAG: {flag}")

Flag

kashiCTF{wh3n_0n3_pr1m3_1s_n0t_3n0ugh_p_squared_1s_w0rs3}