Codegate CTF 2022 Quals - Prime Generator (crypto)
Published on 27 Feb 2022
Writeups
In this challenge, the server generates a random 296-bit number $U$.
In the first stage, the server generates a random 512-bit prime $p$ of the shape $(U||L)$ and tells us the 216-bit value $L$. We can repeat this as many times as we want. From such $p$, we can learn some information about $U$: since $p$ is prime, it must not be divisible by any small prime. We learn that $L \not\equiv 2^{216} U \pmod{d}$ for any small odd prime $d$. After enough queries (about $d\ln{d}$), we can learn $U \mod d$. Note that these queries do not depend on d itself, so we can reuse the same pool for each $d$. That is, we choose to use primes $d=3,5,...,229$ and we need about $229\ln{229} \approx 1244$ queries to recover $U$ modulo each of these primes. Using the CRT, we can recover $U$ completely, since the product of all these primes is larger than 296 bits.
In the second stage, a new prime $p$ of the same shape $(U||L)$ is generated, as a part of an RSA semiprime $pq$ with a fully random 512-bit $q$. The flag is encrypted using this modulus. We can solve it by exploiting the partial leak of $p$ (we know the 296 bits $U$), using the Coppersmith's small roots method.
In [1]:
ps = list(primes(3, 230))
math.log(prod(ps), 2), ps[-1]
Out [1]:
(302.22738675455395, 229)
In [2]:
from sock import Sock
f = Sock("15.164.247.87 9001")
f.send("2\n")
f.read_until("n : ")
n = int(f.read_line())
f.read_until("c : ")
c = int(f.read_line())
print(n)
print(c)
49753641656174528750613579887335344462630218624131102579147028972295514810799439249011518827865402250366318719813207443463545435156983520911826206585750995269340692798825327077413735231288244844136901373354664850283746375557952430654290226592050130604660939433666817238766467346251278153045027078084589706461 32628734791401281262789821643456889579081977769379545196297676610561699825026936116281468926422604514383679407207174896425623126141469122496976829566170281678436413605740823462190158568473834354936454488327368109658536389224073924525306894648125624415868720460266243168794121538238437169799776951320791223282
In [3]:
nums = []
cands = {p: set(range(p)) for p in ps}
t = 130
f.send("1\n10\n" * t)
for i in tqdm(range(t)):
f.read_until("many?")
f.read_line()
f.read_until("> ")
for j in range(10):
nums.append(int(f.read_line()))
lo = nums[-1]
for p, cs in cands.items():
cs.discard((-lo) % p)
if i % 10 == 0:
print([len(cs) for cs in cands.values()])
len(nums)
1%|█▌ | 1/130 [00:01<02:54, 1.35s/it]
[1, 1, 3, 3, 7, 9, 10, 14, 20, 22, 29, 32, 34, 37, 43, 52, 51, 57, 61, 64, 69, 73, 79, 88, 93, 93, 97, 99, 103, 117, 122, 127, 130, 139, 141, 148, 153, 158, 164, 170, 171, 181, 183, 187, 189, 201, 214, 217, 219]
8%|████████████████▉ | 11/130 [00:09<01:49, 1.09it/s]
[1, 1, 1, 1, 1, 1, 1, 2, 2, 3, 4, 2, 5, 5, 13, 7, 12, 12, 15, 20, 16, 24, 27, 30, 36, 35, 42, 38, 41, 53, 59, 54, 65, 72, 78, 72, 83, 94, 88, 96, 98, 105, 110, 118, 122, 127, 134, 145, 138]
16%|████████████████████████████████▎ | 21/130 [00:18<01:42, 1.07it/s]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 1, 4, 5, 5, 6, 5, 8, 10, 10, 13, 13, 15, 21, 20, 26, 30, 25, 30, 41, 39, 40, 44, 56, 50, 55, 56, 61, 69, 74, 72, 74, 85, 100, 94]
24%|███████████████████████████████████████████████▋ | 31/130 [00:29<01:40, 1.01s/it]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 2, 2, 2, 4, 3, 3, 5, 3, 5, 11, 8, 13, 14, 10, 15, 26, 22, 17, 25, 30, 23, 30, 36, 29, 44, 43, 48, 46, 52, 67, 65]
32%|███████████████████████████████████████████████████████████████ | 41/130 [00:40<01:39, 1.11s/it]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 2, 2, 3, 1, 2, 4, 2, 5, 8, 4, 10, 13, 13, 11, 17, 18, 12, 17, 21, 19, 29, 30, 32, 32, 34, 47, 41]
39%|██████████████████████████████████████████████████████████████████████████████▍ | 51/130 [00:48<01:08, 1.16it/s]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 2, 1, 2, 2, 2, 3, 4, 1, 7, 5, 9, 6, 12, 9, 8, 8, 14, 11, 17, 19, 19, 17, 24, 27, 25]
47%|█████████████████████████████████████████████████████████████████████████████████████████████▊ | 61/130 [01:00<01:17, 1.12s/it]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 1, 1, 3, 1, 4, 3, 6, 2, 6, 4, 4, 3, 9, 7, 12, 10, 13, 12, 16, 18, 15]
55%|█████████████████████████████████████████████████████████████████████████████████████████████████████████████▏ | 71/130 [01:10<01:01, 1.03s/it]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 1, 4, 2, 4, 1, 3, 4, 3, 2, 7, 2, 7, 5, 6, 6, 7, 14, 9]
62%|████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████▌ | 81/130 [01:19<00:45, 1.07it/s]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 4, 1, 3, 3, 2, 2, 7, 1, 6, 3, 4, 5, 5, 8, 5]
70%|████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████ | 91/130 [01:29<00:33, 1.15it/s]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 3, 2, 1, 4, 1, 6, 2, 2, 5, 5, 5, 3]
78%|██████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████▌ | 101/130 [01:38<00:29, 1.03s/it]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 2, 1, 3, 2, 2, 3, 3, 4, 2]
85%|█████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████▉ | 111/130 [01:48<00:20, 1.09s/it]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 2, 1, 2, 2, 1, 2, 3, 4, 2]
93%|█████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████▏ | 121/130 [01:59<00:08, 1.01it/s]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 1, 1, 1, 3, 2, 1]
100%|███████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████| 130/130 [02:08<00:00, 1.01it/s]
Out [3]:
1300
In [4]:
prod([len(cs) for cs in cands.values()])
Out [4]:
24
In [5]:
from binteger import Bin
R, x = Zmod(n)['x'].objgen()
for rems in product(*[cands[p] for p in ps]):
rems = [r * inverse_mod(2**216, p) % p for r, p in zip(rems, ps)]
u = crt(list(rems), ps)
if u > 2**296:
continue
print("try", u, ZZ(u).nbits())
u = int(u) << 216
poly = x + u
rs = poly.small_roots(X=2**216, beta=0.49)
if rs:
print(rs)
for r in rs:
p = int(u + r)
p = gcd(p, n)
print("gcd", p)
if 1 < p < n:
q = n // int(p)
p = int(p)
d = inverse_mod(0x10001, n - p - q + 1)
msg = pow(c, d, n)
print(Bin(msg).bytes)
try 67743400979862310367407785711104791917060925830205436173036558827514270522687377520100747 296
[81170000847848927277947127436419116175015541987733346290640471767]
gcd 7134212802611282345790495331615815725308810976513460997271020501002880374627794804009183029052209525909305205441979249571870845363822471884355749414291159
b'codegate2022{ef9fdfaae10f7afe84bea52307966a9e}\x00\x92\xa6\xe5\xa2f\x96\x99\x98\xd4\xf9I\x0br\xa5.{!\x16\x82\xc2iC\x0b\x0cK\x8a\xa6]I\xed\xfc\x1c\xff\x17d\x12\xfc\x0cK \xce\xa8\xde~\xbd\xd5\x89\xccnm5pB\xd7\xb1\x85\x06\xa6t\x9f]\xbf\xaf7\x87\x97\x02G\\[c\x1eO\x8f.r\xa4\xae\x86\xbf'