python
# Let's implement the CRC16 and CRC8 exactly as in the PHP code and then
# build a solver for last 3 bytes to make both CRC16 and CRC8 be zero.

def compute_crc16_py(data: bytes) -> int:
    checksum = 0xFFFF
    for b in data:
        checksum ^= b
        for _ in range(8):
            if checksum & 1:
                checksum = ((checksum >> 1) ^ 0xA001)
            else:
                checksum >>= 1
    return checksum & 0xFFFF

crc8_table = [
    0x00, 0x07, 0x0E, 0x09, 0x1C, 0x1B, 0x12, 0x15,
    0x38, 0x3F, 0x36, 0x31, 0x24, 0x23, 0x2A, 0x2D,
    0x70, 0x77, 0x7E, 0x79, 0x6C, 0x6B, 0x62, 0x65,
    0x48, 0x4F, 0x46, 0x41, 0x54, 0x53, 0x5A, 0x5D,
    0xE0, 0xE7, 0xEE, 0xE9, 0xFC, 0xFB, 0xF2, 0xF5,
    0xD8, 0xDF, 0xD6, 0xD1, 0xC4, 0xC3, 0xCA, 0xCD,
    0x90, 0x97, 0x9E, 0x99, 0x8C, 0x8B, 0x82, 0x85,
    0xA8, 0xAF, 0xA6, 0xA1, 0xB4, 0xB3, 0xBA, 0xBD,
    0xC7, 0xC0, 0xC9, 0xCE, 0xDB, 0xDC, 0xD5, 0xD2,
    0xFF, 0xF8, 0xF1, 0xF6, 0xE3, 0xE4, 0xED, 0xEA,
    0xB7, 0xB0, 0xB9, 0xBE, 0xAB, 0xAC, 0xA5, 0xA2,
    0x8F, 0x88, 0x81, 0x86, 0x93, 0x94, 0x9D, 0x9A,
    0x27, 0x20, 0x29, 0x2E, 0x3B, 0x3C, 0x35, 0x32,
    0x1F, 0x18, 0x11, 0x16, 0x03, 0x04, 0x0D, 0x0A,
    0x57, 0x50, 0x59, 0x5E, 0x4B, 0x4C, 0x45, 0x42,
    0x6F, 0x68, 0x61, 0x66, 0x73, 0x74, 0x7D, 0x7A,
    0x89, 0x8E, 0x87, 0x80, 0x95, 0x92, 0x9B, 0x9C,
    0xB1, 0xB6, 0xBF, 0xB8, 0xAD, 0xAA, 0xA3, 0xA4,
    0xF9, 0xFE, 0xF7, 0xF0, 0xE5, 0xE2, 0xEB, 0xEC,
    0xC1, 0xC6, 0xCF, 0xC8, 0xDD, 0xDA, 0xD3, 0xD4,
    0x69, 0x6E, 0x67, 0x60, 0x75, 0x72, 0x7B, 0x7C,
    0x51, 0x56, 0x5F, 0x58, 0x4D, 0x4A, 0x43, 0x44,
    0x19, 0x1E, 0x17, 0x10, 0x05, 0x02, 0x0B, 0x0C,
    0x21, 0x26, 0x2F, 0x28, 0x3D, 0x3A, 0x33, 0x34,
    0x4E, 0x49, 0x40, 0x47, 0x52, 0x55, 0x5C, 0x5B,
    0x76, 0x71, 0x78, 0x7F, 0x6A, 0x6D, 0x64, 0x63,
    0x3E, 0x39, 0x30, 0x37, 0x22, 0x25, 0x2C, 0x2B,
    0x06, 0x01, 0x08, 0x0F, 0x1A, 0x1D, 0x14, 0x13,
    0xAE, 0xA9, 0xA0, 0xA7, 0xB2, 0xB5, 0xBC, 0xBB,
    0x96, 0x91, 0x98, 0x9F, 0x8A, 0x8D, 0x84, 0x83,
    0xDE, 0xD9, 0xD0, 0xD7, 0xC2, 0xC5, 0xCC, 0xCB,
    0xE6, 0xE1, 0xE8, 0xEF, 0xFA, 0xFD, 0xF4, 0xF3
]

def crc8_py(data: bytes) -> int:
    crc = 0
    for b in data:
        crc = crc8_table[(crc ^ b) & 0xff]
    return crc & 0xff

secret = b"Enj0yNSSCTF4th!"
len(secret), secret


(15, b'Enj0yNSSCTF4th!')

python
from typing import List, Tuple

def combined_crc(data: bytes) -> int:
    """Return combined 24-bit value: lower 16 bits = crc16, upper 8 bits = crc8 (or reversed)."""
    c16 = compute_crc16_py(data)
    c8 = crc8_py(data)
    return (c8 << 16) | c16

secret = b"Enj0yNSSCTF4th!"
len(secret), combined_crc(secret), compute_crc16_py(secret), crc8_py(secret)


(15, 10699630, 17262, 163)

python
hex(compute_crc16_py(secret)), hex(crc8_py(secret)), hex(combined_crc(secret))


('0x436e', '0xa3', '0xa3436e')

python
def solve_linear_mod2(A_cols: List[int], b: int, n: int = 24) -> Tuple[bool, int]:
    """
    Solve A x = b over GF(2), where A is 24x24 with columns given in A_cols (each a 24-bit int).
    Returns (ok, x) where x is 24-bit int of solution bits, if ok.
    """
    # Build augmented matrix with columns; but easier: perform elimination on rows with columns representation.
    # We'll pivot per row using columns like bitset of columns.
    # Convert to row-based matrix: For i in 0..23, row i is [A_ij] across j and RHS b_i.
    # We'll maintain a list of column bitmasks and vector b bits.
    cols = A_cols[:]  # copy
    # Keep track of which column is pivot for each row
    pivot_col_for_row = [-1] * n
    row_mask = [1 << i for i in range(n)]  # bit masks for rows
    # We'll maintain transformation matrices to solve; Instead implement algorithm to find x by constructing inverse.
    # Simpler: Form 24x24 matrix and perform Gauss-Jordan to get inverse, then x = inv * b.
    # But computing inverse from column form is tricky. Alternative: Do elimination on columns while applying same operations to an identity matrix to produce inverse "R" such that R*A = I; Then x = R*b.
    # We'll operate on columns: We want to transform A to Identity by row operations (XOR of rows), which correspond to left-multiplying by some matrix R, and apply R to b.
    # Row operations correspond to XORing row i into row j; In column representation, XOR row i into row j means in each column, toggle bit j if bit i was 1? Hmm.
    # Actually XORing row i into row j: For each column c, if bit i of c is 1, we toggle bit j of that column.
    # But implementing row ops via columns requires iterating all columns repeatedly.
    # Simpler: Convert to row-wise matrix as integers of 24 bits across columns. But our columns are bits for rows; To build rows, we can, for each row r, assemble a 24-bit row_i where bit j is 1 if A_cols[j] has bit r set.
    ncols = n
    rows = [0] * n
    for r in range(n):
        row = 0
        for j in range(ncols):
            if (cols[j] >> r) & 1:
                row |= (1 << j)
        rows[r] = row
    # Now rows is list of 24 rows, each 24-bit row across columns; bbits is 24-bit vector b.
    bbits = b
    # Perform Gauss-Jordan elimination to reduce rows to identity, applying same ops to bbits.
    # We'll pivot col by col.
    pivot_row_for_col = [-1] * n
    r = 0
    for c in range(n):
        # find a row >= r with bit c set
        pivot = None
        for rr in range(r, n):
            if (rows[rr] >> c) & 1:
                pivot = rr
                break
        if pivot is None:
            # singular
            return (False, 0)
        # swap rows r and pivot
        if pivot != r:
            rows[r], rows[pivot] = rows[pivot], rows[r]
            # swap b bits r and pivot
            br = (bbits >> r) & 1
            bp = (bbits >> pivot) & 1
            if br != bp:
                bbits ^= (1 << r) | (1 << pivot)
        # eliminate other rows in column c
        for rr in range(n):
            if rr != r and ((rows[rr] >> c) & 1):
                rows[rr] ^= rows[r]
                # also apply to bbits: toggle bit rr by bit r
                if ((bbits >> r) & 1):
                    bbits ^= (1 << rr)
        pivot_row_for_col[c] = r
        r += 1
        if r == n:
            break
    # Now rows should be identity and bbits is the solution vector x across columns.
    x = 0
    # we need to reconstruct x_j = bbit at row equal to pivot_row_for_col[c] for column c?
    # After elimination to identity, rows[ri] has 1 at column ri. bbits bit ri holds solution variable for that column.
    # So x's bit c equals bbits at row index equal to pivot_row_for_col[c]?
    # Verify: Identity row i corresponds to equation x_i = bbit_i.
    # Yes, columns aligned with variables.
    x = 0
    for c in range(n):
        row_index = pivot_row_for_col[c]
        if row_index == -1:
            return (False, 0)
        bit = (bbits >> row_index) & 1
        if bit:
            x |= (1 << c)
    return (True, x)

def build_A_and_b(prefix: bytes, target_crc: int) -> Tuple[List[int], int, int]:
    # prefix is first 12 bytes (for 15 length). We will set last 3 bytes initially zero.
    assert len(prefix) == 12
    base = prefix + b'\x00\x00\x00'
    base_crc = combined_crc(base)
    bvec = base_crc ^ target_crc  # A*x should equal this
    # build columns: for each bit j of last 3 bytes (0..23), compute delta crc when toggled
    cols = []
    for bit_index in range(24):
        # Construct delta with that single bit set
        last3 = bytearray(3)
        # Map bit_index to byte position and bit within byte
        byte_pos = bit_index // 8  # 0..2
        bit_in_byte = bit_index % 8
        last3[byte_pos] ^= (1 << bit_in_byte)
        test = prefix + bytes(last3)
        delta_col = combined_crc(test) ^ base_crc
        # Represent delta_col as 24-bit int: bits 0..15 for crc16, bits 16..23 for crc8
        cols.append(delta_col & ((1<<24)-1))
    return cols, bvec, base_crc

target = combined_crc(secret)
prefix = b"A"*12
Acols, bvec, base_crc = build_A_and_b(prefix, target)
ok, x = solve_linear_mod2(Acols, bvec, 24)
ok, hex(x), hex(base_crc), hex(target)


(False, '0x0', '0x81d60d', '0xa3436e')

python
from itertools import combinations

def build_A_for_positions(prefix_bytes: bytes, var_positions: Tuple[int,int,int], target_crc: int):
    # length n = 15; prefix_bytes is length 15 with all bytes initial; We'll set variables set to zero initially
    n = 15
    base = bytearray(prefix_bytes)
    for pos in var_positions:
        base[pos] = 0  # ensure zero initial (we will vary bits relative to zero)
    base = bytes(base)
    base_crc = combined_crc(base)
    bvec = base_crc ^ target_crc
    cols = []
    for pos in var_positions:
        for bit in range(8):
            arr = bytearray(base)
            arr[pos] ^= (1 << bit)
            delta = combined_crc(bytes(arr)) ^ base_crc
            cols.append(delta & ((1<<24)-1))
    return cols, bvec, base

# Let's search for positions.
n = 15
# choose base message as 15 'A's
base_msg = bytearray(b"A"*15)
# We'll vary 3 positions anywhere in 0..14
full_rank_triplets = []
for pos_triplet in combinations(range(n), 3):
    Acols, bvec, base = build_A_for_positions(base_msg, pos_triplet, target)
    ok, x = solve_linear_mod2(Acols, bvec, 24)
    if ok:
        full_rank_triplets.append((pos_triplet, x, bvec))
        break

len(full_rank_triplets), full_rank_triplets[:1]


(0, [])

python
def solve_rectangular(Acols: List[int], bvec: int) -> Tuple[bool, int, List[int]]:
    """
    Solve A x = b over GF(2), where A is 24 x m with columns in Acols (each 24-bit int).
    Returns (ok, x_bits, pivot_cols). x_bits is m-bit vector giving one solution with free vars 0.
    """
    m = len(Acols)
    # Build rows
    rows = [0]*24
    for r in range(24):
        row = 0
        for j in range(m):
            if (Acols[j] >> r) & 1:
                row |= (1 << j)
        rows[r] = row
    bbits = bvec
    pivot_col_for_row = [-1]*24
    r = 0
    for c in range(m):
        # find a row >= r with bit c set
        pivot = None
        for rr in range(r,24):
            if (rows[rr] >> c) & 1:
                pivot = rr; break
        if pivot is None:
            continue
        # swap rows r and pivot
        if pivot != r:
            rows[r], rows[pivot] = rows[pivot], rows[r]
            br = (bbits >> r) & 1
            bp = (bbits >> pivot) & 1
            if br != bp:
                bbits ^= (1<<r) | (1<<pivot)
        # eliminate other rows in column c
        for rr in range(24):
            if rr != r and ((rows[rr] >> c) & 1):
                rows[rr] ^= rows[r]
                if ((bbits >> r) & 1):
                    bbits ^= (1 << rr)
        pivot_col_for_row[r] = c
        r += 1
        if r == 24:
            break
    if r < 24:
        # Not full rank -> system may have no solution or infinite, but we need to ensure consistency: rows with all-zero row must have bbit zero too
        # Check consistency
        for rr in range(r,24):
            if rows[rr] == 0 and ((bbits >> rr) & 1):
                return (False, 0, [])
        # We cannot solve uniquely; but we can set some variables arbitrarily. For simplicity, try to use additional columns by reordering? Already considered.
        # We'll attempt to pick free vars as zero and determine pivot vars by back substitution using rows[0..r-1].
    # Back-substitute to get solution with free vars zero:
    x = 0
    # Work from last pivot row to first
    for i in range(r-1, -1, -1):
        c = pivot_col_for_row[i]
        # sum of A[i, j]*x_j for j>c
        sum_bit = 0
        rowmask = rows[i]
        # Bits set in rowmask excluding pivot column
        mask_ex_pivot = rowmask & ~(1 << c)
        # compute dot product with x
        tmp = mask_ex_pivot & x
        # parity of tmp bits
        sum_bit = bin(tmp).count("1") & 1
        bi = (bbits >> i) & 1
        xi = bi ^ sum_bit
        if xi:
            x |= (1 << c)
    pivot_cols = [pivot_col_for_row[i] for i in range(r) if pivot_col_for_row[i] != -1]
    return (True, x, pivot_cols)

# Test with m=120
n=15
# base message all zeros; columns for all bits across 15 bytes
Acols_all = []
base_msg = bytes([0]*n)
base_crc = combined_crc(base_msg)
target = combined_crc(secret)
bvec = base_crc ^ target  # which equals target since base_crc=CRC(zeros)
for pos in range(n):
    for bit in range(8):
        arr = bytearray(base_msg)
        arr[pos] ^= (1 << bit)
        delta = combined_crc(bytes(arr)) ^ base_crc
        Acols_all.append(delta)
ok, x, pivots = solve_rectangular(Acols_all, bvec)
ok, len(pivots), "solution nonzero bits:", bin(x).count("1") if ok else None


(True, 23, 'solution nonzero bits:', 12)

python
def rank_of_positions(var_positions):
    # Return rank (number of pivots) of A for these positions, independent of bvec
    base_msg = bytes([0]*15)
    Acols = []
    base_crc = combined_crc(base_msg)
    for pos in var_positions:
        for bit in range(8):
            arr = bytearray(base_msg)
            arr[pos] ^= (1 << bit)
            delta = combined_crc(bytes(arr)) ^ base_crc
            Acols.append(delta)
    ok, x, piv = solve_rectangular(Acols, 0)  # solving with zero b is always consistent; pivots count equals rank
    return len(piv)

# Search for any 3 positions whose rank == 23
triples_rank = []
for pos_triplet in combinations(range(15), 3):
    r = rank_of_positions(pos_triplet)
    if r >= 23:
        triples_rank.append((pos_triplet, r))
len(triples_rank)


246

python
def try_find_solution_with_k(k=3):
    base_msg = bytes([0]*15)  # zeros base; We'll set variables to unknown; Others remain zero
    target = combined_crc(secret)
    base_crc = combined_crc(base_msg)
    bvec = base_crc ^ target
    for pos_tuple in combinations(range(15), k):
        # build Acols for these positions
        Acols = []
        for pos in pos_tuple:
            for bit in range(8):
                arr = bytearray(base_msg)
                arr[pos] ^= (1 << bit)
                delta = combined_crc(bytes(arr)) ^ base_crc
                Acols.append(delta)
        ok, x, piv = solve_rectangular(Acols, bvec)
        if ok:
            return pos_tuple, x
    return None, None

pos3, x3 = try_find_solution_with_k(3)
pos4, x4 = try_find_solution_with_k(4)
pos3, pos4 is not None


((0, 1, 3), True)

python
pos3, x3


((0, 1, 3), 10188351)

python
def bytes_from_x(x, k=3):
    bs = []
    for i in range(k):
        bs.append((x >> (8*i)) & 0xFF)
    return bs
bs = bytes_from_x(x3, 3)
bs


[63, 118, 155]

python
pos4, x4


((0, 1, 2, 3), 35891783)

python
def build_message_from_positions(x_bits: int, positions: Tuple[int,...], base_msg=None) -> bytes:
    if base_msg is None:
        base_msg = bytearray([0]*15)
    else:
        base_msg = bytearray(base_msg)
    for i, pos in enumerate(positions):
        val = (x_bits >> (8*i)) & 0xFF
        base_msg[pos] = val
    return bytes(base_msg)

m4 = build_message_from_positions(x4, pos4)
list(m4), m4, len(m4), combined_crc(m4), combined_crc(secret)


([71, 170, 35, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 b'G\xaa#\x02\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00',
 15,
 10699630,
 10699630)

python
import itertools

def find_printable_solution():
    base_msg = bytes([0]*15)
    target = combined_crc(secret)
    base_crc = combined_crc(base_msg)
    bvec = base_crc ^ target
    printable = range(0x20, 0x7f)
    for k in range(3,6):
        for positions in combinations(range(15), k):
            # Solve for one solution
            Acols = []
            for pos in positions:
                for bit in range(8):
                    arr = bytearray(base_msg)
                    arr[pos] ^= (1 << bit)
                    delta = combined_crc(bytes(arr)) ^ base_crc
                    Acols.append(delta)
            ok, x_bits, piv = solve_rectangular(Acols, bvec)
            if not ok:
                continue
            # General solution: x = x_bits XOR y for any y in null space of A
            # Compute basis of null space by finding columns that are not pivot columns, express them in terms of pivot columns.
            m = len(Acols)
            # Recompute elimination to get rows state and bbits for nullspace; We'll use rows from solve_rectangular by slight modification to also get reduced rows and pivot list.
            # For simplicity, rebuild elimination to get pivot columns and row RREF:
            rows = [0]*24
            for r in range(24):
                row = 0
                for j in range(m):
                    if (Acols[j] >> r) & 1:
                        row |= (1 << j)
                rows[r] = row
            pivot_row = [-1]*m
            pivot_col_for_row = [-1]*24
            r = 0
            for c in range(m):
                pivot = None
                for rr in range(r,24):
                    if (rows[rr] >> c) & 1:
                        pivot = rr; break
                if pivot is None:
                    continue
                if pivot != r:
                    rows[r], rows[pivot] = rows[pivot], rows[r]
                # eliminate other rows
                for rr in range(24):
                    if rr != r and ((rows[rr] >> c) & 1):
                        rows[rr] ^= rows[r]
                pivot_col_for_row[r] = c
                pivot_row[c] = r
                r += 1
                if r == 24:
                    break
            pivot_cols = [c for c in range(m) if pivot_row[c] != -1]
            free_cols = [c for c in range(m) if pivot_row[c] == -1]
            # Build nullspace basis vectors 'nvecs' as m-bit integers; For each free col f, set x_f = 1, and x_pivot computed to keep A*x=0
            nvecs = []
            for f in free_cols:
                # Start with vector with bit f set
                v = 1 << f
                # For each pivot row i, compute x_p = sum of known bits in that row (which currently is bit f if row has 1 in column f).
                # For RREF, rows[i] has 1 at pivot col and some other 1s; So to enforce row dot x = 0, set pivot var accordingly.
                for i in range(r-1, -1, -1):
                    c = pivot_col_for_row[i]
                    rowmask = rows[i]
                    # compute sum of x bits in non-pivot columns present in rowmask
                    sum_bit = bin(v & (rowmask & ~(1 << c))).count("1") & 1
                    if sum_bit:
                        v ^= (1 << c)  # set pivot to 1 to cancel sum
                nvecs.append(v)
            # Now try combinations of nullspace adjustments to make bytes printable.
            # We'll try small combinations of up to, say, 10 iterations random or greedy; but we can iterate across combinations for small number free_cols.
            # free_cols = m - rank ≈ k*8 - 23. For k=3, free ~= 1; for k=4, free ~= 9; for k=5, free ~= 17.
            # Let's do a heuristic: iterate through some random combinations limited.
            from itertools import product
            free = len(nvecs)
            # Try limited combinations: first try zero adjustment; then single basis toggles; then pairs; etc.
            candidate_vs = [0]
            candidate_vs += [nvecs[i] for i in range(min(free, 12))]
            # add some pairs
            for i in range(min(free, 8)):
                for j in range(i+1, min(free, 8)):
                    candidate_vs.append(nvecs[i] ^ nvecs[j])
            seen = set()
            for add in candidate_vs:
                sol = x_bits ^ add
                # Build bytes for these positions
                vals = []
                okp = True
                for idx in range(k):
                    byteval = (sol >> (8*idx)) & 0xFF
                    vals.append(byteval)
                    if byteval not in printable:
                        okp = False
                        break
                if okp:
                    # Build final message
                    m = build_message_from_positions(sol, positions, base_msg)
                    if m != secret:
                        return positions, m, vals
    return None

res = find_printable_solution()
res


((0, 1, 4),
 b'Rm\x00\x00-\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00',
 [82, 109, 45])

python
import random

def find_fully_printable_solution_with_last4():
    printable = set(range(0x20, 0x7f))
    for attempt in range(200):
        # choose first 11 bytes randomly printable, and ensure message != secret
        prefix = bytes([random.choice(list(printable)) for _ in range(11)])
        # It's okay if some match secret; Not necessary to differ except entire string; we'll check at end.
        # Build A for last 4 positions: 11..14 indices
        positions = (11,12,13,14)
        base_msg = bytearray(prefix + b'\x00\x00\x00\x00')
        base_msg = bytes(base_msg)
        target = combined_crc(secret)
        base_crc = combined_crc(base_msg)
        bvec = base_crc ^ target
        # Build Acols for last 4 positions
        Acols = []
        for pos in positions:
            for bit in range(8):
                arr = bytearray(base_msg)
                arr[pos] ^= (1 << bit)
                delta = combined_crc(bytes(arr)) ^ base_crc
                Acols.append(delta)
        ok, x_bits, piv = solve_rectangular(Acols, bvec)
        if not ok:
            continue
        # Build nullspace basis for these 32 columns
        m = len(Acols)
        rows = [0]*24
        for r in range(24):
            row = 0
            for j in range(m):
                if (Acols[j] >> r) & 1:
                    row |= (1<<j)
            rows[r] = row
        pivot_row = [-1]*m
        pivot_col_for_row = [-1]*24
        rnk = 0
        for c in range(m):
            pivot = None
            for rr in range(rnk,24):
                if (rows[rr] >> c) & 1:
                    pivot = rr; break
            if pivot is None:
                continue
            if pivot != rnk:
                rows[rnk], rows[pivot] = rows[pivot], rows[rnk]
            for rr in range(24):
                if rr != rnk and ((rows[rr] >> c) & 1):
                    rows[rr] ^= rows[rnk]
            pivot_col_for_row[rnk] = c
            pivot_row[c] = rnk
            rnk += 1
            if rnk == 24:
                break
        free_cols = [c for c in range(m) if pivot_row[c] == -1]
        nvecs = []
        for f in free_cols:
            v = 1 << f
            for i in range(rnk-1, -1, -1):
                c = pivot_col_for_row[i]
                rowmask = rows[i]
                if bin(v & (rowmask & ~(1<<c))).count("1") & 1:
                    v ^= (1 << c)
            nvecs.append(v)
        # Try to adjust to make last 4 bytes printable
        vals = [(x_bits >> (8*i)) & 0xFF for i in range(4)]
        # Try greedy search via flipping basis vectors
        def bytes_from_solution(sol):
            return [(sol >> (8*i)) & 0xFF for i in range(4)]
        # Evaluate current bytes
        def printable_count(vs):
            return sum(1 for b in vs if b in printable)
        if all(b in printable for b in vals):
            sol = x_bits
        else:
            # Try toggling combinations up to depth 3
            best = (printable_count(vals), x_bits)
            sol = None
            basis_count = min(len(nvecs), 12)
            # Try single toggles
            for i in range(basis_count):
                s = x_bits ^ nvecs[i]
                vs = bytes_from_solution(s)
                sc = printable_count(vs)
                if sc == 4:
                    sol = s; break
                if sc > best[0]:
                    best = (sc, s)
            if sol is None:
                # try pairs
                for i in range(basis_count):
                    for j in range(i+1, basis_count):
                        s = x_bits ^ nvecs[i] ^ nvecs[j]
                        vs = bytes_from_solution(s)
                        sc = printable_count(vs)
                        if sc == 4:
                            sol = s; break
                    if sol is not None: break
            if sol is None:
                # try triples
                for i in range(basis_count):
                    for j in range(i+1, basis_count):
                        for k in range(j+1, basis_count):
                            s = x_bits ^ nvecs[i] ^ nvecs[j] ^ nvecs[k]
                            vs = bytes_from_solution(s)
                            sc = printable_count(vs)
                            if sc == 4:
                                sol = s; break
                        if sol is not None: break
                    if sol is not None: break
            if sol is None:
                sol = best[1]
        vals = bytes_from_solution(sol)
        m_final = bytearray(base_msg)
        for i, pos in enumerate(positions):
            m_final[pos] = vals[i]
        m_final = bytes(m_final)
        if all(32 <= b <= 126 for b in m_final) and m_final != secret:
            return m_final, vals, prefix
    return None

res = find_fully_printable_solution_with_last4()
res[:2] if res else None


(b'cDXM 4pujqY/-IC', [47, 45, 73, 67])

python
candidate = b'cDXM 4pujqY/-IC'
len(candidate), candidate != secret, hex(combined_crc(candidate)), hex(combined_crc(secret))


(15, True, '0xa3436e', '0xa3436e')

python
hex(compute_crc16_py(candidate)), hex(crc8_py(candidate))


('0x436e', '0xa3')

python
import math
e1 = 26675174225063019792412591801113799130868333007861486357720578798352030914999710926292644671603600643369845213171396954004158372043593223603274138224817810197939227716991483870437629436082594926630937775718564690554680519001757082557490487364436474044434348412437933432480883175650430050712391958500932343901
e2 = 43950877784211432364704383093702059665468498126670135130662770287054349774316943441695986309047768423965591753129960761705976613430837039441242214744782506036708881166308335886272786409715558332802625980679432726451306523481798238346507261619084743433957076290727858148266709423500224748925763767341340730807
math.gcd(e1, e2)

1

python
import math
e1 = 26675174225063019792412591801113799130868333007861486357720578798352030914999710926292644671603600643369845213171396954004158372043593223603274138224817810197939227716991483870437629436082594926630937775718564690554680519001757082557490487364436474044434348412437933432480883175650430050712391958500932343901
e2 = 43950877784211432364704383093702059665468498126670135130662770287054349774316943441695986309047768423965591753129960761705976613430837039441242214744782506036708881166308335886272786409715558332802625980679432726451306523481798238346507261619084743433957076290727858148266709423500224748925763767341340730807
math.gcd(e1-1, e2-1)

2

python
N = 153098639535230461427067981471925418840838598338005180035334795636906122233147195601425250354397215037964687813767036136951747775082105669481477681815877751367786247871862319200300034505895599830252899234816623479894529037827470533297869568936005422622937802442126007732338221711447957108942595934348420152967
N.bit_length()

1024

python
import math
N = 153098639535230461427067981471925418840838598338005180035334795636906122233147195601425250354397215037964687813767036136951747775082105669481477681815877751367786247871862319200300034505895599830252899234816623479894529037827470533297869568936005422622937802442126007732338221711447957108942595934348420152967
e1=26675174225063019792412591801113799130868333007861486357720578798352030914999710926292644671603600643369845213171396954004158372043593223603274138224817810197939227716991483870437629436082594926630937775718564690554680519001757082557490487364436474044434348412437933432480883175650430050712391958500932343901
e2=43950877784211432364704383093702059665468498126670135130662770287054349774316943441695986309047768423965591753129960761705976613430837039441242214744782506036708881166308335886272786409715558332802625980679432726451306523481798238346507261619084743433957076290727858148266709423500224748925763767341340730807
math.gcd(N, e1*e2 - 1)

1

python
import math
for val in (e1-1,e1+1,e2-1,e2+1, e1*e2+1):
    g = math.gcd(N, val)
    print(val.bit_length(), g)

python
from Crypto.Util.number import long_to_bytes
c = 93877717323267388927595086106164695425439307573037159369718380924127343418544815509333679743420188507149532789861080535086578879105173477672709484480809535461054572173818555600022970592546859742598747214025487041690467952494343056536435494716815059600034890617984024099540213482984895312025775728869974483561
len(long_to_bytes(c)), long_to_bytes(c)[:40]

(128,
 b'\x85\xaf\xb1\xd1\x0cECS0\xe2\xdb!\x8e\xa7\xdde\xc4\xb5\r\x91\xd4`\xb31\x19\xaf9\xc8\xc2\x82\xc9\xbd\x17\x92#\xe2\tH\x8b\xfa')

python
import math, sys
N = 153098639535230461427067981471925418840838598338005180035334795636906122233147195601425250354397215037964687813767036136951747775082105669481477681815877751367786247871862319200300034505895599830252899234816623479894529037827470533297869568936005422622937802442126007732338221711447957108942595934348420152967
e1=26675174225063019792412591801113799130868333007861486357720578798352030914999710926292644671603600643369845213171396954004158372043593223603274138224817810197939227716991483870437629436082594926630937775718564690554680519001757082557490487364436474044434348412437933432480883175650430050712391958500932343901
e2=43950877784211432364704383093702059665468498126670135130662770287054349774316943441695986309047768423965591753129960761705976613430837039441242214744782506036708881166308335886272786409715558332802625980679432726451306523481798238346507261619084743433957076290727858148266709423500224748925763767341340730807
c = 93877717323267388927595086106164695425439307573037159369718380924127343418544815509333679743420188507149532789861080535086578879105173477672709484480809535461054572173818555600022970592546859742598747214025487041690467952494343056536435494716815059600034890617984024099540213482984895312025775728869974483561
g1 = math.gcd(pow(c, e1-1, N) - 1, N)
g2 = math.gcd(pow(c, e2-1, N) - 1, N)
g1, g2

(1, 1)

python
import math
def test(exponent):
    return math.gcd(pow(c, exponent, N) - 1, N)
for exp in [e1+1, e2+1, (e1-1)//2, (e2-1)//2]:
    print(test(exp))

python
import math
def egcd(a,b):
    if b==0:
        return (1,0,a)
    x,y,g=egcd(b,a%b)
    return (y, x - (a//b)*y, g)

a,b,g=egcd(e1-1, e2-1)
a,b,g

(-681272191168245234644311052352831312523380402726483531525994414219555240446525444877807761264748386016281843810587694578141968160981937867254122381768952851595001493747966790073351136648925756135920280707888586891377962212690170983833354461314635175984465930288666564254269265025067167299388546590935025454,
 413485584595803605823260492324784302349912263197049939019825015613727021813341804633412569927180669886435699358899131904411696376616325826048235457423992722939503272618628443595006959408554175090984096217499888522551198629065849308113703755224247872852735117708163854533783494697672012191746972529924131167,
 2)

python
import math
r1 = pow(c, e1-1, N)
r2 = pow(c, e2-1, N)
math.gcd((r1 - r2) % N, N)

1

python
import math
t = (pow(c, e1, N) - pow(c, e2, N)) % N
math.gcd(t, N)

1

python
import math, time
N = 153098639535230461427067981471925418840838598338005180035334795636906122233147195601425250354397215037964687813767036136951747775082105669481477681815877751367786247871862319200300034505895599830252899234816623479894529037827470533297869568936005422622937802442126007732338221711447957108942595934348420152967
def fermat_factor(N, max_iter=5_000_000):
    a = math.isqrt(N)
    if a*a < N:
        a += 1
    for i in range(max_iter):
        b2 = a*a - N
        b = math.isqrt(b2)
        if b*b == b2:
            p = a-b
            q = a+b
            return p, q, i
        a += 1
    return None

start = time.time()
res = fermat_factor(N, max_iter=2_000_000)  # 2 million iterations
time.time() - start, res is not None

(3.535285234451294, False)

python
start = time.time()
res = fermat_factor(N, max_iter=20_000_000)
elapsed = time.time() - start
elapsed, res

(34.94282245635986, None)