LA CTF 2026 - six seven
Challenge
Category: Crypto | Author: AVDestroyer
When bro uses RSA encryption to talk crap behind my back but I lowkey genuinely just factor his public key because I know he picked [67]* as his primes
nc chall.lac.tf 31180
chall.py
#!/usr/local/bin/python3
import secrets
from Crypto.Util.number import isPrime, bytes_to_long
def generate_67_prime(length: int) -> int:
while True:
digits = [secrets.choice("67") for _ in range(length - 1)]
digits.append("7")
test = int("".join(digits))
if isPrime(test, false_positive_prob=1e-12):
return test
p = generate_67_prime(256)
q = generate_67_prime(256)
n = p * q
e = 65537
FLAG = open("flag.txt", "rb").read()
m = bytes_to_long(FLAG)
c = pow(m, e, n)
print(f"n={n}")
print(f"c={c}")
Solution Summary
Digit-by-digit search: Starting from the lowest digits of n, progressively determine each digit of p and q, pruning based on the property that the low digits of a product depend only on the low digits of the factors.
Process
01 Reading the Problem
Looking at chall.py, I found it's RSA, but with a very special prime generation:
def generate_67_prime(length: int) -> int:
while True:
digits = [secrets.choice("67") for _ in range(length - 1)]
digits.append("7")
test = int("".join(digits))
if isPrime(test):
return test
Each digit can only be 6 or 7, with the last digit fixed as 7. These are 256-digit decimal primes.
02 Initial Analysis
My first thought: with only 6 and 7, this is essentially a binary choice. Treating 6 as 0 and 7 as 1, the search space is 2^255 (since the last digit is fixed).
2^255 is still too large for brute force. But this constraint must weaken something...
03 Attempted Approaches (Dead Ends)
Approach 1: Decompose p as 6R + B
p = 6×(111...1) + B = 6R + B
Where R = (10^256 - 1)/9, and B is a "binary coefficient" number.
Computed n mod R = BB' mod R, which gave some information, but I couldn't figure out how to use it directly.
Approach 2: Try to compute φ(n) directly
Expanding φ(n) = (p-1)(q-1), I tried to find the value of S = B + B', but the error margins were too large to be reliable.
Approach 3: Lattice attack?
I considered using Coppersmith's method, but B isn't "small" enough to satisfy the conditions.
04 Back to Basics: Digit-by-Digit Search
I had previously observed: the low digits of a product depend only on the low digits of the factors.
For example, the last digit of n = (last digit of p) × (last digit of q) mod 10.
Since each digit has only 2 choices (6 or 7), we can start from the low digits and progressively determine each digit of p and q.
Concern: Each step might branch into multiple candidates. After 256 steps, will this explode?
05 Actual Attempt
I wrote a simple search:
def search(n):
candidates = [(7, 7)] # Last digit is always 7
for k in range(2, 257):
mod = 10 ** k
n_low = n % mod
new_candidates = []
for p_low, q_low in candidates:
for p_digit in [6, 7]:
for q_digit in [6, 7]:
new_p = p_digit * (10 ** (k-1)) + p_low
new_q = q_digit * (10 ** (k-1)) + q_low
if (new_p * new_q) % mod == n_low:
new_candidates.append((new_p, new_q))
candidates = new_candidates
return candidates
Result: The number of candidates stays at 2-4 throughout!
k=50: 4 candidates
k=100: 2 candidates
k=150: 2 candidates
k=200: 2 candidates
k=250: 2 candidates
Final: 2 candidates
06 Why No Exponential Explosion?
I was worried each step would branch and lead to 2^256 candidates, but in practice:
- Not every step branches: Of the 4 combinations, usually only 1-2 satisfy the constraint
- Symmetry merges candidates: (p, q) and (q, p) are the same factorization
- Constraints compound: The mod 10^k constraint becomes increasingly restrictive
Analogy to solving Sudoku: Although each cell has multiple possibilities, the constraints mutually restrict each other, leading to a unique solution.
07 Getting the Flag
After finding p and q, standard RSA decryption:
phi = (p - 1) * (q - 1)
d = pow(e, -1, phi)
m = pow(c, d, n)
flag = long_to_bytes(m)
lactf{wh4t_67s_15_blud_f4ct0r1ng_15_blud_31nst31n}