elliptic-shiho/solve.sage

## solve.sage
"""
Google CTF 2024 Quals: mceliece

References:

1. V. M. Sidelinkov and S. O. Shestakov. 1992. "On insecurity of cryptosystems based on generalized Reed-Solomon codes".
2. C. Wischebrink. 2009. "Cryptanalysis of the Niederreiter Public Key Scheme Based on GRS Subcodes".
3. A. Couvreur, P. Gaborit, V. Gauthier-Umaña, A. Otmani, and Jean-Pierre Tillich. 2013 (revised at 2014). "Distinguisher-Based Attacks on Public-Key Cryptosystems Using Reed-Solomon Codes".
4. A. Otmani and H. T. Kalachi. 2015. "Square Code Attack on a Modified Sidelnikov Cryptosystem".
"""

from sage.all import *
from Crypto.Util.number import long_to_bytes
from functools import reduce
from tqdm import tqdm
import itertools


def compute_squared_dimension(C):
    comp = []
    for v1, v2 in itertools.combinations(C.basis(), r=2):
        if v1.is_zero():
            continue
        if v2.is_zero():
            continue
        v = vector([e1 * e2 for e1, e2 in zip(v1, v2)])  # component-wise product
        if v.is_zero():
            continue
        comp.append(v)
    if len(comp) == 0:
        return 0
    return span(comp).dimension()


def find_random_position(pk, k, r, n):
    # An implementation of [3]
    rows, columns = pk.dimensions()
    LC = LinearCode(pk)
    a = min(LC.length() // 2, k - 1)
    print(f"[+] {a = }")
    assert a < k
    assert 2 * k - 1 + r - n < a
    rand = []

    odd_code = LC.shortened([x * 2 + 1 for x in range(a)])
    odd_dim = compute_squared_dimension(odd_code)
    even_code = LC.shortened([x * 2 for x in range(a)])
    even_dim = compute_squared_dimension(even_code)

    for i in tqdm(range(columns), ascii=True, ncols=64):
        C = odd_code if i % 2 == 0 else even_code
        d = odd_dim if i % 2 == 0 else even_dim
        dim = compute_squared_dimension(C.punctured([i // 2]))
        if d - dim == 1:
            rand.append(i)
            print(rand)

    if len(rand) != r:
        print("[-] length mismatch")
        print(f"Expected: {r}, Actual: {len(rand)}")
    return rand


def sidelinkov_shestakov_attack(pubkey, ciphertext):
    # An implementation of [1], but I also referenced [2]
    k, n = pubkey.dimensions()
    M = pubkey.echelon_form()
    F = M.base_ring()
    # we need to guess c := c_{b1} / c_{b2} \in F
    for c in tqdm(F.list(), ascii=True, ncols=64):
        a = [0 for _ in range(n)]
        # we can assume a[0] = 0 and a[1] = 1
        a[0] = 0
        a[1] = 1

        # find a[k], ..., a[n - 1] using a property of echelon form
        failed = False
        for j in range(k, n):
            # M[0, j] / M[1, j] = c * (a[j] - 1) / a[j]
            # <=> a[j] = c / (c - M[0, j] / M[1, j])
            x = M[0, j] / M[1, j]
            if x == c:
                failed = True
                break
            a[j] = c / (c - x)

        if failed:
            continue

        # find a[2], ..., a[k - 1]
        for i in range(2, k):
            for j1 in range(k, n - 1):
                j2 = j1 + 1
                """
                A[j] := M[0, j] / M[i, j] * a[j]
                There exists `t` which satisfies A[j] = t * (a[j] - a[i])
                t is an independent value to `i` so it holds

                A[j1] - A[j2] = t * (a[j1] - a[j2])
                <=> (A[j1] - A[j2]) / (a[j1] - a[j2]) = t.
                """

                Aj1 = M[0, j1] / M[i, j1] * a[j1]
                Aj2 = M[0, j2] / M[i, j2] * a[j2]
                if a[j1] == a[j2]:
                    continue

                t = (Aj1 - Aj2) / (a[j1] - a[j2])
                if t == 0:
                    continue

                # If we have `t`, we can compute a[i] directly
                a[i] = -Aj1 / t + a[j1]
                break
            else:
                failed = True
                break
        if failed:
            continue

        try:
            C = codes.GeneralizedReedSolomonCode(a, k)
            return C.decode_to_code(vector(ciphertext))
        except:
            # If we can't guess `c` correctly, `a[i]` is not valid
            pass


def solve():
    p, n, k, r = load("params.sobj")
    ciphertext = load("flag_enc.sobj")
    pubkey = load("pubkey.sobj")

    print("[+] Find random column positions")
    assert 2 * k - 1 + r > n
    random_positions = find_random_position(pubkey, k, r, n)

    print(f"Guessed positions = {random_positions}")

    ciphertext = ciphertext.delete_columns(random_positions)
    pubkey = pubkey.delete_columns(random_positions)

    print("[+] Sidelinkov & Shestakov Attack")

    decoded = sidelinkov_shestakov_attack(pubkey, ciphertext)

    print(f"{decoded = }")
    m = pubkey.solve_left(decoded)
    print(f"{m = }")
    unpadded_message = long_to_bytes(
        reduce(lambda x, y: ZZ(x) * p + ZZ(y), m[: -ZZ(m[-1])][::-1], 0)
    )
    print(f"{unpadded_message = }")


if __name__ == "__main__":
    solve()


"""
Mon Jun 24 17:41:01 JST 2024 ~/Downloads/mceliece
> sage solve.sage
[+] Find random column positions
[+] a = 147
  0%|                                   | 0/295 [00:00<?, ?it/s][0]
  3%|8                          | 9/295 [00:00<00:10, 26.58it/s][0, 9]
  5%|#3                        | 15/295 [00:00<00:10, 26.59it/s][0, 9, 17]
  8%|##1                       | 24/295 [00:00<00:10, 26.24it/s][0, 9, 17, 25]
  9%|##3                       | 27/295 [00:01<00:10, 26.29it/s][0, 9, 17, 25, 28]
 13%|###4                      | 39/295 [00:01<00:09, 26.45it/s][0, 9, 17, 25, 28, 39]
 15%|###9                      | 45/295 [00:01<00:09, 26.29it/s][0, 9, 17, 25, 28, 39, 46]
 17%|####4                     | 51/295 [00:01<00:09, 26.35it/s][0, 9, 17, 25, 28, 39, 46, 53]
 21%|#####5                    | 63/295 [00:02<00:08, 26.40it/s][0, 9, 17, 25, 28, 39, 46, 53, 65]
 23%|######                    | 69/295 [00:02<00:08, 26.28it/s][0, 9, 17, 25, 28, 39, 46, 53, 65, 70]
 29%|#######6                  | 87/295 [00:03<00:07, 26.22it/s][0, 9, 17, 25, 28, 39, 46, 53, 65, 70, 87]
[0, 9, 17, 25, 28, 39, 46, 53, 65, 70, 87, 89]
 32%|########1                 | 93/295 [00:03<00:08, 24.71it/s][0, 9, 17, 25, 28, 39, 46, 53, 65, 70, 87, 89, 93]
[0, 9, 17, 25, 28, 39, 46, 53, 65, 70, 87, 89, 93, 95]
 39%|#########6               | 114/295 [00:04<00:06, 26.01it/s][0, 9, 17, 25, 28, 39, 46, 53, 65, 70, 87, 89, 93, 95, 114]
 43%|##########6              | 126/295 [00:04<00:06, 26.02it/s][0, 9, 17, 25, 28, 39, 46, 53, 65, 70, 87, 89, 93, 95, 114, 126]
 46%|###########4             | 135/295 [00:05<00:06, 26.16it/s][0, 9, 17, 25, 28, 39, 46, 53, 65, 70, 87, 89, 93, 95, 114, 126, 137]
 47%|###########6             | 138/295 [00:05<00:05, 26.20it/s][0, 9, 17, 25, 28, 39, 46, 53, 65, 70, 87, 89, 93, 95, 114, 126, 137, 140]
 50%|############4            | 147/295 [00:05<00:05, 26.23it/s][0, 9, 17, 25, 28, 39, 46, 53, 65, 70, 87, 89, 93, 95, 114, 126, 137, 140, 148]
 51%|############7            | 150/295 [00:05<00:05, 26.27it/s][0, 9, 17, 25, 28, 39, 46, 53, 65, 70, 87, 89, 93, 95, 114, 126, 137, 140, 148, 151]
 52%|############9            | 153/295 [00:05<00:05, 26.17it/s][0, 9, 17, 25, 28, 39, 46, 53, 65, 70, 87, 89, 93, 95, 114, 126, 137, 140, 148, 151, 154]
 53%|#############2           | 156/295 [00:05<00:05, 26.02it/s][0, 9, 17, 25, 28, 39, 46, 53, 65, 70, 87, 89, 93, 95, 114, 126, 137, 140, 148, 151, 154, 157]
[0, 9, 17, 25, 28, 39, 46, 53, 65, 70, 87, 89, 93, 95, 114, 126, 137, 140, 148, 151, 154, 157, 158]
 54%|#############4           | 159/295 [00:06<00:05, 26.09it/s][0, 9, 17, 25, 28, 39, 46, 53, 65, 70, 87, 89, 93, 95, 114, 126, 137, 140, 148, 151, 154, 157, 158, 161]
 55%|#############7           | 162/295 [00:06<00:05, 26.13it/s][0, 9, 17, 25, 28, 39, 46, 53, 65, 70, 87, 89, 93, 95, 114, 126, 137, 140, 148, 151, 154, 157, 158, 161, 162]
 56%|#############9           | 165/295 [00:06<00:04, 26.12it/s][0, 9, 17, 25, 28, 39, 46, 53, 65, 70, 87, 89, 93, 95, 114, 126, 137, 140, 148, 151, 154, 157, 158, 161, 162, 165]
 58%|##############4          | 171/295 [00:06<00:04, 26.04it/s][0, 9, 17, 25, 28, 39, 46, 53, 65, 70, 87, 89, 93, 95, 114, 126, 137, 140, 148, 151, 154, 157, 158, 161, 162, 165, 171]
[0, 9, 17, 25, 28, 39, 46, 53, 65, 70, 87, 89, 93, 95, 114, 126, 137, 140, 148, 151, 154, 157, 158, 161, 162, 165, 171, 173]
 61%|###############2         | 180/295 [00:06<00:04, 25.84it/s][0, 9, 17, 25, 28, 39, 46, 53, 65, 70, 87, 89, 93, 95, 114, 126, 137, 140, 148, 151, 154, 157, 158, 161, 162, 165, 171, 173, 180]
 63%|###############7         | 186/295 [00:07<00:04, 26.01it/s][0, 9, 17, 25, 28, 39, 46, 53, 65, 70, 87, 89, 93, 95, 114, 126, 137, 140, 148, 151, 154, 157, 158, 161, 162, 165, 171, 173, 180, 187]
 73%|##################3      | 216/295 [00:08<00:03, 26.19it/s][0, 9, 17, 25, 28, 39, 46, 53, 65, 70, 87, 89, 93, 95, 114, 126, 137, 140, 148, 151, 154, 157, 158, 161, 162, 165, 171, 173, 180, 187, 217]
[0, 9, 17, 25, 28, 39, 46, 53, 65, 70, 87, 89, 93, 95, 114, 126, 137, 140, 148, 151, 154, 157, 158, 161, 162, 165, 171, 173, 180, 187, 217, 218]
 76%|###################      | 225/295 [00:08<00:02, 25.94it/s][0, 9, 17, 25, 28, 39, 46, 53, 65, 70, 87, 89, 93, 95, 114, 126, 137, 140, 148, 151, 154, 157, 158, 161, 162, 165, 171, 173, 180, 187, 217, 218, 225]
 83%|####################8    | 246/295 [00:09<00:01, 26.16it/s][0, 9, 17, 25, 28, 39, 46, 53, 65, 70, 87, 89, 93, 95, 114, 126, 137, 140, 148, 151, 154, 157, 158, 161, 162, 165, 171, 173, 180, 187, 217, 218, 225, 246]
 87%|#####################8   | 258/295 [00:09<00:01, 26.12it/s][0, 9, 17, 25, 28, 39, 46, 53, 65, 70, 87, 89, 93, 95, 114, 126, 137, 140, 148, 151, 154, 157, 158, 161, 162, 165, 171, 173, 180, 187, 217, 218, 225, 246, 259]
[0, 9, 17, 25, 28, 39, 46, 53, 65, 70, 87, 89, 93, 95, 114, 126, 137, 140, 148, 151, 154, 157, 158, 161, 162, 165, 171, 173, 180, 187, 217, 218, 225, 246, 259, 260]
 88%|######################1  | 261/295 [00:09<00:01, 26.14it/s][0, 9, 17, 25, 28, 39, 46, 53, 65, 70, 87, 89, 93, 95, 114, 126, 137, 140, 148, 151, 154, 157, 158, 161, 162, 165, 171, 173, 180, 187, 217, 218, 225, 246, 259, 260, 261]
 93%|#######################1 | 273/295 [00:10<00:00, 26.03it/s][0, 9, 17, 25, 28, 39, 46, 53, 65, 70, 87, 89, 93, 95, 114, 126, 137, 140, 148, 151, 154, 157, 158, 161, 162, 165, 171, 173, 180, 187, 217, 218, 225, 246, 259, 260, 261, 275]
100%|########################9| 294/295 [00:11<00:00, 26.00it/s][0, 9, 17, 25, 28, 39, 46, 53, 65, 70, 87, 89, 93, 95, 114, 126, 137, 140, 148, 151, 154, 157, 158, 161, 162, 165, 171, 173, 180, 187, 217, 218, 225, 246, 259, 260, 261, 275, 294]
100%|#########################| 295/295 [00:11<00:00, 26.12it/s]
Guessed positions = [0, 9, 17, 25, 28, 39, 46, 53, 65, 70, 87, 89, 93, 95, 114, 126, 137, 140, 148, 151, 154, 157, 158, 161, 162, 165, 171, 173, 180, 187, 217, 218, 225, 246, 259, 260, 261, 275, 294]
[+] Sidelinkov & Shestakov Attack
 60%|##############9          | 312/521 [00:07<00:04, 42.31it/s]
decoded = (94, 351, 127, 78, 419, 48, 405, 278, 256, 334, 495, 26, 61, 70, 486, 37, 439, 479, 399, 88, 201, 345, 73, 369, 247, 388, 383, 120, 348, 69, 512, 62, 77, 150, 190, 184, 157, 94, 423, 72, 452, 383, 285, 384, 166, 220, 7, 256, 81, 6, 104, 147, 228, 171, 434, 323, 204, 60, 169, 301, 294, 21, 441, 264, 367, 152, 180, 45, 189, 299, 207, 351, 351, 409, 159, 305, 229, 110, 345, 423, 508, 392, 359, 261, 88, 425, 310, 14, 38, 475, 489, 42, 82, 173, 116, 171, 157, 153, 144, 442, 272, 4, 222, 96, 140, 197, 296, 286, 349, 387, 23, 509, 32, 414, 57, 188, 414, 256, 154, 454, 283, 288, 222, 14, 141, 119, 464, 421, 440, 78, 15, 395, 167, 201, 221, 329, 62, 440, 397, 516, 95, 308, 449, 232, 270, 164, 469, 341, 443, 231, 78, 464, 410, 8, 349, 24, 47, 348, 481, 473, 209, 19, 351, 499, 459, 323, 427, 106, 219, 214, 105, 216, 100, 451, 288, 331, 293, 231, 188, 423, 379, 459, 341, 18, 50, 121, 317, 299, 459, 472, 509, 122, 154, 31, 224, 281, 217, 496, 7, 517, 299, 355, 293, 280, 515, 186, 420, 65, 300, 102, 147, 206, 255, 502, 484, 490, 413, 421, 315, 16, 95, 148, 133, 438, 384, 225, 22, 131, 432, 473, 408, 342, 161, 294, 354, 496, 401, 304, 209, 431, 272, 442, 369, 100, 84, 30, 262, 11, 197, 520, 105, 501, 397, 516, 223, 184)
m = (415, 292, 340, 123, 291, 53, 146, 417, 338, 476, 466, 517, 446, 220, 33, 433, 72, 212, 125, 480, 191, 224, 84, 140, 435, 362, 121, 366, 118, 518, 98, 440, 153, 273, 198, 76, 236, 102, 477, 339, 510, 166, 477, 19, 226, 323, 319, 108, 386, 2, 260, 271, 165, 57, 427, 509, 412, 57, 501, 390, 375, 363, 457, 350, 334, 110, 482, 46, 339, 74, 73, 323, 492, 10, 403, 132, 412, 140, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91)
unpadded_message = b'CTF{1f_0nly_th3r3_w45_50m3_c0d3_1nd1st1ngu15h4bl3_fr0m_r4nd0mn355_70c2decd2dd58446e825}\n'
"""
	"""
	Google CTF 2024 Quals: mceliece

	References:

	1. V. M. Sidelinkov and S. O. Shestakov. 1992. "On insecurity of cryptosystems based on generalized Reed-Solomon codes".
	2. C. Wischebrink. 2009. "Cryptanalysis of the Niederreiter Public Key Scheme Based on GRS Subcodes".
	3. A. Couvreur, P. Gaborit, V. Gauthier-Umaña, A. Otmani, and Jean-Pierre Tillich. 2013 (revised at 2014). "Distinguisher-Based Attacks on Public-Key Cryptosystems Using Reed-Solomon Codes".
	4. A. Otmani and H. T. Kalachi. 2015. "Square Code Attack on a Modified Sidelnikov Cryptosystem".
	"""

	from sage.all import *
	from Crypto.Util.number import long_to_bytes
	from functools import reduce
	from tqdm import tqdm
	import itertools


	def compute_squared_dimension(C):
	comp = []
	for v1, v2 in itertools.combinations(C.basis(), r=2):
	if v1.is_zero():
	continue
	if v2.is_zero():
	continue
	v = vector([e1 * e2 for e1, e2 in zip(v1, v2)]) # component-wise product
	if v.is_zero():
	continue
	comp.append(v)
	if len(comp) == 0:
	return 0
	return span(comp).dimension()


	def find_random_position(pk, k, r, n):
	# An implementation of [3]
	rows, columns = pk.dimensions()
	LC = LinearCode(pk)
	a = min(LC.length() // 2, k - 1)
	print(f"[+] {a = }")
	assert a < k
	assert 2 * k - 1 + r - n < a
	rand = []

	odd_code = LC.shortened([x * 2 + 1 for x in range(a)])
	odd_dim = compute_squared_dimension(odd_code)
	even_code = LC.shortened([x * 2 for x in range(a)])
	even_dim = compute_squared_dimension(even_code)

	for i in tqdm(range(columns), ascii=True, ncols=64):
	C = odd_code if i % 2 == 0 else even_code
	d = odd_dim if i % 2 == 0 else even_dim
	dim = compute_squared_dimension(C.punctured([i // 2]))
	if d - dim == 1:
	rand.append(i)
	print(rand)

	if len(rand) != r:
	print("[-] length mismatch")
	print(f"Expected: {r}, Actual: {len(rand)}")
	return rand


	def sidelinkov_shestakov_attack(pubkey, ciphertext):
	# An implementation of [1], but I also referenced [2]
	k, n = pubkey.dimensions()
	M = pubkey.echelon_form()
	F = M.base_ring()
	# we need to guess c := c_{b1} / c_{b2} \in F
	for c in tqdm(F.list(), ascii=True, ncols=64):
	a = [0 for _ in range(n)]
	# we can assume a[0] = 0 and a[1] = 1
	a[0] = 0
	a[1] = 1

	# find a[k], ..., a[n - 1] using a property of echelon form
	failed = False
	for j in range(k, n):
	# M[0, j] / M[1, j] = c * (a[j] - 1) / a[j]
	# <=> a[j] = c / (c - M[0, j] / M[1, j])
	x = M[0, j] / M[1, j]
	if x == c:
	failed = True
	break
	a[j] = c / (c - x)

	if failed:
	continue

	# find a[2], ..., a[k - 1]
	for i in range(2, k):
	for j1 in range(k, n - 1):
	j2 = j1 + 1
	"""
	A[j] := M[0, j] / M[i, j] * a[j]
	There exists `t` which satisfies A[j] = t * (a[j] - a[i])
	t is an independent value to `i` so it holds

	A[j1] - A[j2] = t * (a[j1] - a[j2])
	<=> (A[j1] - A[j2]) / (a[j1] - a[j2]) = t.
	"""

	Aj1 = M[0, j1] / M[i, j1] * a[j1]
	Aj2 = M[0, j2] / M[i, j2] * a[j2]
	if a[j1] == a[j2]:
	continue

	t = (Aj1 - Aj2) / (a[j1] - a[j2])
	if t == 0:
	continue

	# If we have `t`, we can compute a[i] directly
	a[i] = -Aj1 / t + a[j1]
	break
	else:
	failed = True
	break
	if failed:
	continue

	try:
	C = codes.GeneralizedReedSolomonCode(a, k)
	return C.decode_to_code(vector(ciphertext))
	except:
	# If we can't guess `c` correctly, `a[i]` is not valid
	pass


	def solve():
	p, n, k, r = load("params.sobj")
	ciphertext = load("flag_enc.sobj")
	pubkey = load("pubkey.sobj")

	print("[+] Find random column positions")
	assert 2 * k - 1 + r > n
	random_positions = find_random_position(pubkey, k, r, n)

	print(f"Guessed positions = {random_positions}")

	ciphertext = ciphertext.delete_columns(random_positions)
	pubkey = pubkey.delete_columns(random_positions)

	print("[+] Sidelinkov & Shestakov Attack")

	decoded = sidelinkov_shestakov_attack(pubkey, ciphertext)

	print(f"{decoded = }")
	m = pubkey.solve_left(decoded)
	print(f"{m = }")
	unpadded_message = long_to_bytes(
	reduce(lambda x, y: ZZ(x) * p + ZZ(y), m[: -ZZ(m[-1])][::-1], 0)
	)
	print(f"{unpadded_message = }")


	if __name__ == "__main__":
	solve()


	"""
	Mon Jun 24 17:41:01 JST 2024 ~/Downloads/mceliece
	> sage solve.sage
	[+] Find random column positions
	[+] a = 147
	0%\| \| 0/295 [00:00<?, ?it/s][0]
	3%\|8 \| 9/295 [00:00<00:10, 26.58it/s][0, 9]
	5%\|#3 \| 15/295 [00:00<00:10, 26.59it/s][0, 9, 17]
	8%\|##1 \| 24/295 [00:00<00:10, 26.24it/s][0, 9, 17, 25]
	9%\|##3 \| 27/295 [00:01<00:10, 26.29it/s][0, 9, 17, 25, 28]
	13%\|###4 \| 39/295 [00:01<00:09, 26.45it/s][0, 9, 17, 25, 28, 39]
	15%\|###9 \| 45/295 [00:01<00:09, 26.29it/s][0, 9, 17, 25, 28, 39, 46]
	17%\|####4 \| 51/295 [00:01<00:09, 26.35it/s][0, 9, 17, 25, 28, 39, 46, 53]
	21%\|#####5 \| 63/295 [00:02<00:08, 26.40it/s][0, 9, 17, 25, 28, 39, 46, 53, 65]
	23%\|###### \| 69/295 [00:02<00:08, 26.28it/s][0, 9, 17, 25, 28, 39, 46, 53, 65, 70]
	29%\|#######6 \| 87/295 [00:03<00:07, 26.22it/s][0, 9, 17, 25, 28, 39, 46, 53, 65, 70, 87]
	[0, 9, 17, 25, 28, 39, 46, 53, 65, 70, 87, 89]
	32%\|########1 \| 93/295 [00:03<00:08, 24.71it/s][0, 9, 17, 25, 28, 39, 46, 53, 65, 70, 87, 89, 93]
	[0, 9, 17, 25, 28, 39, 46, 53, 65, 70, 87, 89, 93, 95]
	39%\|#########6 \| 114/295 [00:04<00:06, 26.01it/s][0, 9, 17, 25, 28, 39, 46, 53, 65, 70, 87, 89, 93, 95, 114]
	43%\|##########6 \| 126/295 [00:04<00:06, 26.02it/s][0, 9, 17, 25, 28, 39, 46, 53, 65, 70, 87, 89, 93, 95, 114, 126]
	46%\|###########4 \| 135/295 [00:05<00:06, 26.16it/s][0, 9, 17, 25, 28, 39, 46, 53, 65, 70, 87, 89, 93, 95, 114, 126, 137]
	47%\|###########6 \| 138/295 [00:05<00:05, 26.20it/s][0, 9, 17, 25, 28, 39, 46, 53, 65, 70, 87, 89, 93, 95, 114, 126, 137, 140]
	50%\|############4 \| 147/295 [00:05<00:05, 26.23it/s][0, 9, 17, 25, 28, 39, 46, 53, 65, 70, 87, 89, 93, 95, 114, 126, 137, 140, 148]
	51%\|############7 \| 150/295 [00:05<00:05, 26.27it/s][0, 9, 17, 25, 28, 39, 46, 53, 65, 70, 87, 89, 93, 95, 114, 126, 137, 140, 148, 151]
	52%\|############9 \| 153/295 [00:05<00:05, 26.17it/s][0, 9, 17, 25, 28, 39, 46, 53, 65, 70, 87, 89, 93, 95, 114, 126, 137, 140, 148, 151, 154]
	53%\|#############2 \| 156/295 [00:05<00:05, 26.02it/s][0, 9, 17, 25, 28, 39, 46, 53, 65, 70, 87, 89, 93, 95, 114, 126, 137, 140, 148, 151, 154, 157]
	[0, 9, 17, 25, 28, 39, 46, 53, 65, 70, 87, 89, 93, 95, 114, 126, 137, 140, 148, 151, 154, 157, 158]
	54%\|#############4 \| 159/295 [00:06<00:05, 26.09it/s][0, 9, 17, 25, 28, 39, 46, 53, 65, 70, 87, 89, 93, 95, 114, 126, 137, 140, 148, 151, 154, 157, 158, 161]
	55%\|#############7 \| 162/295 [00:06<00:05, 26.13it/s][0, 9, 17, 25, 28, 39, 46, 53, 65, 70, 87, 89, 93, 95, 114, 126, 137, 140, 148, 151, 154, 157, 158, 161, 162]
	56%\|#############9 \| 165/295 [00:06<00:04, 26.12it/s][0, 9, 17, 25, 28, 39, 46, 53, 65, 70, 87, 89, 93, 95, 114, 126, 137, 140, 148, 151, 154, 157, 158, 161, 162, 165]
	58%\|##############4 \| 171/295 [00:06<00:04, 26.04it/s][0, 9, 17, 25, 28, 39, 46, 53, 65, 70, 87, 89, 93, 95, 114, 126, 137, 140, 148, 151, 154, 157, 158, 161, 162, 165, 171]
	[0, 9, 17, 25, 28, 39, 46, 53, 65, 70, 87, 89, 93, 95, 114, 126, 137, 140, 148, 151, 154, 157, 158, 161, 162, 165, 171, 173]
	61%\|###############2 \| 180/295 [00:06<00:04, 25.84it/s][0, 9, 17, 25, 28, 39, 46, 53, 65, 70, 87, 89, 93, 95, 114, 126, 137, 140, 148, 151, 154, 157, 158, 161, 162, 165, 171, 173, 180]
	63%\|###############7 \| 186/295 [00:07<00:04, 26.01it/s][0, 9, 17, 25, 28, 39, 46, 53, 65, 70, 87, 89, 93, 95, 114, 126, 137, 140, 148, 151, 154, 157, 158, 161, 162, 165, 171, 173, 180, 187]
	73%\|##################3 \| 216/295 [00:08<00:03, 26.19it/s][0, 9, 17, 25, 28, 39, 46, 53, 65, 70, 87, 89, 93, 95, 114, 126, 137, 140, 148, 151, 154, 157, 158, 161, 162, 165, 171, 173, 180, 187, 217]
	[0, 9, 17, 25, 28, 39, 46, 53, 65, 70, 87, 89, 93, 95, 114, 126, 137, 140, 148, 151, 154, 157, 158, 161, 162, 165, 171, 173, 180, 187, 217, 218]
	76%\|################### \| 225/295 [00:08<00:02, 25.94it/s][0, 9, 17, 25, 28, 39, 46, 53, 65, 70, 87, 89, 93, 95, 114, 126, 137, 140, 148, 151, 154, 157, 158, 161, 162, 165, 171, 173, 180, 187, 217, 218, 225]
	83%\|####################8 \| 246/295 [00:09<00:01, 26.16it/s][0, 9, 17, 25, 28, 39, 46, 53, 65, 70, 87, 89, 93, 95, 114, 126, 137, 140, 148, 151, 154, 157, 158, 161, 162, 165, 171, 173, 180, 187, 217, 218, 225, 246]
	87%\|#####################8 \| 258/295 [00:09<00:01, 26.12it/s][0, 9, 17, 25, 28, 39, 46, 53, 65, 70, 87, 89, 93, 95, 114, 126, 137, 140, 148, 151, 154, 157, 158, 161, 162, 165, 171, 173, 180, 187, 217, 218, 225, 246, 259]
	[0, 9, 17, 25, 28, 39, 46, 53, 65, 70, 87, 89, 93, 95, 114, 126, 137, 140, 148, 151, 154, 157, 158, 161, 162, 165, 171, 173, 180, 187, 217, 218, 225, 246, 259, 260]
	88%\|######################1 \| 261/295 [00:09<00:01, 26.14it/s][0, 9, 17, 25, 28, 39, 46, 53, 65, 70, 87, 89, 93, 95, 114, 126, 137, 140, 148, 151, 154, 157, 158, 161, 162, 165, 171, 173, 180, 187, 217, 218, 225, 246, 259, 260, 261]
	93%\|#######################1 \| 273/295 [00:10<00:00, 26.03it/s][0, 9, 17, 25, 28, 39, 46, 53, 65, 70, 87, 89, 93, 95, 114, 126, 137, 140, 148, 151, 154, 157, 158, 161, 162, 165, 171, 173, 180, 187, 217, 218, 225, 246, 259, 260, 261, 275]
	100%\|########################9\| 294/295 [00:11<00:00, 26.00it/s][0, 9, 17, 25, 28, 39, 46, 53, 65, 70, 87, 89, 93, 95, 114, 126, 137, 140, 148, 151, 154, 157, 158, 161, 162, 165, 171, 173, 180, 187, 217, 218, 225, 246, 259, 260, 261, 275, 294]
	100%\|#########################\| 295/295 [00:11<00:00, 26.12it/s]
	Guessed positions = [0, 9, 17, 25, 28, 39, 46, 53, 65, 70, 87, 89, 93, 95, 114, 126, 137, 140, 148, 151, 154, 157, 158, 161, 162, 165, 171, 173, 180, 187, 217, 218, 225, 246, 259, 260, 261, 275, 294]
	[+] Sidelinkov & Shestakov Attack
	60%\|##############9 \| 312/521 [00:07<00:04, 42.31it/s]
	decoded = (94, 351, 127, 78, 419, 48, 405, 278, 256, 334, 495, 26, 61, 70, 486, 37, 439, 479, 399, 88, 201, 345, 73, 369, 247, 388, 383, 120, 348, 69, 512, 62, 77, 150, 190, 184, 157, 94, 423, 72, 452, 383, 285, 384, 166, 220, 7, 256, 81, 6, 104, 147, 228, 171, 434, 323, 204, 60, 169, 301, 294, 21, 441, 264, 367, 152, 180, 45, 189, 299, 207, 351, 351, 409, 159, 305, 229, 110, 345, 423, 508, 392, 359, 261, 88, 425, 310, 14, 38, 475, 489, 42, 82, 173, 116, 171, 157, 153, 144, 442, 272, 4, 222, 96, 140, 197, 296, 286, 349, 387, 23, 509, 32, 414, 57, 188, 414, 256, 154, 454, 283, 288, 222, 14, 141, 119, 464, 421, 440, 78, 15, 395, 167, 201, 221, 329, 62, 440, 397, 516, 95, 308, 449, 232, 270, 164, 469, 341, 443, 231, 78, 464, 410, 8, 349, 24, 47, 348, 481, 473, 209, 19, 351, 499, 459, 323, 427, 106, 219, 214, 105, 216, 100, 451, 288, 331, 293, 231, 188, 423, 379, 459, 341, 18, 50, 121, 317, 299, 459, 472, 509, 122, 154, 31, 224, 281, 217, 496, 7, 517, 299, 355, 293, 280, 515, 186, 420, 65, 300, 102, 147, 206, 255, 502, 484, 490, 413, 421, 315, 16, 95, 148, 133, 438, 384, 225, 22, 131, 432, 473, 408, 342, 161, 294, 354, 496, 401, 304, 209, 431, 272, 442, 369, 100, 84, 30, 262, 11, 197, 520, 105, 501, 397, 516, 223, 184)
	m = (415, 292, 340, 123, 291, 53, 146, 417, 338, 476, 466, 517, 446, 220, 33, 433, 72, 212, 125, 480, 191, 224, 84, 140, 435, 362, 121, 366, 118, 518, 98, 440, 153, 273, 198, 76, 236, 102, 477, 339, 510, 166, 477, 19, 226, 323, 319, 108, 386, 2, 260, 271, 165, 57, 427, 509, 412, 57, 501, 390, 375, 363, 457, 350, 334, 110, 482, 46, 339, 74, 73, 323, 492, 10, 403, 132, 412, 140, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91)
	unpadded_message = b'CTF{1f_0nly_th3r3_w45_50m3_c0d3_1nd1st1ngu15h4bl3_fr0m_r4nd0mn355_70c2decd2dd58446e825}\n'
	"""