In this CTF challenge we are given the following encryption script:
#!/usr/bin/env python3
from Crypto.Util.number import *
from flag import flag
def man(n):
B = bin(n)[2:]
M = ''
for b in B:
if b == '0':
M += '01'
else:
M += '11'
return int(M, 2)
def keygen(nbit):
while True:
p = getPrime(nbit)
r = man(p)
B = bin(p)[2:] + '1' * nbit
q = int(B, 2)
if isPrime(q) and isPrime(r):
return q, r
nbit = 256
p, q = keygen(nbit)
m = bytes_to_long(flag)
assert m < n
e, n = 1234567891, p * q
c = pow(m, e, n)
print(f'n = {n}')
print(f'c = {c}')
as well as output.txt:
n = 147170819334030469053514652921356515888015711942553338463409772437981228515273287953989706666936875524451626901247038180594875568558137526484665015890594045767912340169965961750130156341999306808017498374501001042628249176543370525803456692022546235595791111819909503496986338431136130272043196908119165239297
c = 77151713996168344370880352082934801122524956107256445231326053049976568087412199358725058612262271922128984783428798480191211811217854076875727477848490840660333035334309193217618178091153472265093622822195960145852562781183839474868269109313543427082414220136748700364027714272845969723750108397300867408537
This is an RSA-like implementation with some funky key generation
The encryption script implements a Manchester encoding scheme in the function man(). The number passed to this function is converted to bits, and each bit is replaced with either 01 or 11. The resulting bitstream is converted back into an integer.
The key generation algorithm produces a 256-bit prime integer $p$, which is used to generate both RSA prime factors. One is generated by passing $p$ to man(), resulting in a 512-bit integer, while the other prime is generated by appending 256 bits to $p$’s bitstream. This tells us a lot about the structure of the prime factors.
r: ?1?1?1?1?1?1?1?1...?1?1?1?1?1?1?1?1
q: ????????????????...1111111111111111
Since half of the prime factor $q$ is known, recovering the prime using coppersmith is a promising idea. However, even with 50% consecutive bits, the approach failed. Another approach may be to use branch and prune, since 50% of both primes are known and are scattered in $r$, but this also did not work out, probably due to $q$ missing too many consecutive bits.
Instead, we take advantage of the prime factor’s unique structure and relationship with the modulus $n$. First, for clarity, I will refer to the prime factors $q$ and $r$ as $p$ and $q$ respectively, due to the way the encryption script reuses variable names and returns the factors from the keygen algorithm
p: ????????????????...1111111111111111
q: ?1?1?1?1?1?1?1?1...?1?1?1?1?1?1?1?1
We can represent $p$ as the following:
\[\large p = 2^{256}\cdot x + 2^{256}-1\]for some unknown $x$ (upper bits). Taking $p$ modulo $2^{256}$, we get:
\[\large p = -1 \mod 2^{256}\]Which means:
\[\large \begin{align} \nonumber n = p \cdot q \mod 2^{256} \\ \nonumber n = -1 \cdot q \mod 2^{256} \\ \nonumber n = -q \mod 2^{256} \\ \nonumber -n = q \mod 2^{256} \end{align}\]So by taking $-n \mod 2^{256}$, we are able to recover the bottom $256$ bits of $q$. Remember, $q$ (r) was generated using the Manchester encoding. The $256$ bottom bits of $q$ include the $128$ least significant bits of the random prime. Since $p$ and $q$ are generated using the same prime, this leaks another $128$ bits of $p$, for a total of $384$. With 75% of a prime factor’s bits, the primes are recovered from coppersmith in a trivial manner.
Recovering 75% of $p$’s bits can be done like so:
rlow = (-n) % 2^256
rbits = bin(rlow)[2:]
# Undoing manchester encoding
qlow = ""
for i in range(0,len(rbits),2):
qlow += rbits[i]
qlow += "1"*256
leak = int(qlow,2)
With the leaked value, the prime is instantly recovered using cuso:
T = var("x")
f = 2^384 * x + leak
roots = cuso.find_small_roots(
relations = [f],
bounds = {T: (0, 2^128)},
modulus = "p",
modulus_multiple = n,
modulus_lower_bound = 2^511,
)
assert roots, "CuSO found no root"
p = roots[0]["p"]
From here, its just regular RSA decryption
p = roots[0]["p"]
q = n // p
assert p*q == n
phi = (p-1)*(q-1)
d = pow(e, -1, phi)
m = pow(c, d, n)
print(long_to_bytes(m).decode())
# CCTF{M4nch3sReR_c0D!ng_wI7H_RSA}
import cuso
from Crypto.Util.number import long_to_bytes
n = 147170819334030469053514652921356515888015711942553338463409772437981228515273287953989706666936875524451626901247038180594875568558137526484665015890594045767912340169965961750130156341999306808017498374501001042628249176543370525803456692022546235595791111819909503496986338431136130272043196908119165239297
c = 77151713996168344370880352082934801122524956107256445231326053049976568087412199358725058612262271922128984783428798480191211811217854076875727477848490840660333035334309193217618178091153472265093622822195960145852562781183839474868269109313543427082414220136748700364027714272845969723750108397300867408537
e = 1234567891
M = 2^256
rlow = (-n)%M
rbits = bin(rlow)[2:]
qlow = ""
for i in range(0,len(rbits),2):
qlow += rbits[i]
qlow += "1"*256
leak = int(qlow,2)
T = var("x")
f = 2^384 * x + leak
roots = cuso.find_small_roots(
relations = [f],
bounds = {T: (0, 2^128)},
modulus = "p",
modulus_multiple = n,
modulus_lower_bound = 2^511,
)
assert roots, "CuSO found no root"
p = roots[0]["p"]
q = n // p
assert p*q == n
phi = (p-1)*(q-1)
d = pow(e, -1, phi)
m = pow(c, d, n)
print(long_to_bytes(m).decode())
# CCTF{M4nch3sReR_c0D!ng_wI7H_RSA}