# six seven (crypto)

## Challenge summary

The server prints an RSA modulus n and ciphertext c. The primes p and q are
generated by `generate_67_prime(256)`, which builds a 256-digit decimal number
whose digits are only 6 or 7, with the last digit fixed to 7. Both p and q
follow this pattern, so n = p*q. The task is to factor n and decrypt c.

## Key observation

Write the digits in base-10, least significant first:

- p = sum p_i * 10^i, q = sum q_i * 10^i
- each p_i, q_i is in {6, 7}, and p_0 = q_0 = 7

Let n_k be the k-th base-10 digit of n (LSB = k=0). For the k-th digit of the
product, only digits with indices adding to k contribute:

sum_{i=0..k} p_i * q_{k-i}.

For k >= 1, split the sum:

- p_0 * q_k + p_k * q_0 = 7 * (p_k + q_k)
- the remaining cross terms are
  U_k = sum_{i=1..k-1} p_i * q_{k-i}

So the digit recurrence is:

S_k = 7 * (p_k + q_k) + U_k
total_k = S_k + carry_{k-1}
n_k = total_k mod 10
carry_k = total_k // 10

At k=0, 7*7 = 49, so n_0 = 9 and carry_0 = 4.

Because each p_k and q_k is only 6 or 7, there are only 4 choices per digit.
Most choices are immediately ruled out by n_k, so a DFS over digits is tiny.

## Algorithm

1) Parse n and c.
2) Let L = number of digits of p (256 in this challenge).
3) DFS over k = 1..L-1 to reconstruct p_k and q_k:
   - compute U_k from already chosen digits
   - try each (p_k, q_k) in {(6,6),(6,7),(7,6),(7,7)}
   - keep only choices matching n_k with the carry
4) After k = L, verify p*q == n.
5) Compute phi = (p-1)*(q-1), d = e^{-1} mod phi, then m = c^d mod n.
6) Convert m to bytes to recover the flag.

The search is effectively linear in L because each digit is almost forced by
the n_k constraint.

## Reference solver (core idea)

This is the core DFS logic (not including PoW or networking):

```python
digits = list(map(int, str(n)[::-1]))
if len(digits) < 2*L:
    digits += [0]*(2*L - len(digits))

p_digits = [None]*L
q_digits = [None]*L
p_digits[0] = 7
q_digits[0] = 7

def dfs(k, carry):
    if k == L:
        p = sum(d * 10**i for i, d in enumerate(p_digits))
        q = sum(d * 10**i for i, d in enumerate(q_digits))
        return (p, q) if p*q == n else None

    U = sum(p_digits[i] * q_digits[k-i] for i in range(1, k))
    for pk in (6, 7):
        for qk in (6, 7):
            total = 7*(pk + qk) + U + carry
            if total % 10 != digits[k]:
                continue
            p_digits[k] = pk
            q_digits[k] = qk
            res = dfs(k+1, total // 10)
            if res:
                return res
    return None

assert digits[0] == 9
p, q = dfs(1, 4)
```

## Result

Decryption yields the flag:

`lactf{wh4t_67s_15_blud_f4ct0r1ng_15_blud_31nst31n}`