Do you wanna air my dirty laundry?
How to solve
Recovering PRNG
The challenge uses 256-bit LFSR PRNG, of which seed is the lower 256-bit of 1024-bit prime number.
Let’s see pailler_enc unction.
def paillier_enc(m, p, noise):
p = next_prime(p + noise)
q = getStrongPrime(512)
n = p * q
g = (1 + prng.rand() * n) % n**2
c = pow(g, m, n**2) * pow(prng.rand(), n, n**2) % n**2
return n, g, c
The value p is 1024-bit, so n should be 1536-bit. This means that g = (1 + prng.rand() * n) % n**2 is just same as g = 1 + prng.rand() * n, beacuse prng.rand() is only 256-bit.
So, you can get some prng.rand() values from gs, and then recover the PRNG by reversing the PRNG steps.
class PRNG256(object):
def __init__(self, seed):
self.mask = (1 << 256) - 1
self.seed = seed & self.mask
def _pick(self):
b = ((self.seed>>0)^(self.seed>>2)^(self.seed>>5)^(self.seed>>10)^1)&1
self.seed = ((self.seed>>1)|(b<<255)) & self.mask
return b
def _rev(self):
b = ((self.seed>>255)^(self.seed>>1)^(self.seed>>4)^(self.seed>>9)^1)&1
self.seed = ((self.seed<<1)|b) & self.mask
def rev(self):
for i in range(256):
self._rev()
def rand(self):
x = 0
for i in range(256):
x = (x << 1) | self._pick()
return x
with open('output.txt', 'r') as f:
ln = len("[+] pubkey: ")
lines = f.readlines()
pubkeys = eval(lines[1][ln:])
shares = eval(lines[2][ln:])
g1 = (pubkeys[0][1] - 1) // pubkeys[0][0]
g1_rev = int(format(g1, '0256b')[::-1], 2)
prng2 = PRNG256(g1_rev)
prng2.rev()
prng2.rev()
Recovering msg from ciphertexts
Now we know every prng.rand() values. Then, how can we recover m from c = pow(g, m, n**2) * pow(prng.rand(), n, n**2) % n**2?
First, we know pow(prng.rand(), n, n**2), so we can get pow(g, m, n**2).
About pow(g, m, n**2), let’s use the lemma:
$$(1+n)^x \equiv 1+nx (\textrm{mod}\ n^2)$$
and $L$ function from the Paillier cryptosystem. (Check out Background section of the wikipedia article.)
Let’s name the prng.rand() of g = 1 + prng.rand() * n as $noise$. Then,
$$g \equiv 1 + n \cdot noise \equiv (1 + n)^{noise} (\textrm{mod}\ n^2)$$
$$g^m \equiv (1 + n)^{noise \cdot m} \equiv 1 + n \cdot noise \cdot m (\textrm{mod}\ n^2)$$
Therefore, if the value of pow(g, m, n**2) is x, we can get m by:
$$L(x) \cdot noise^{-1}\ \textrm{mod}\ n$$
# ...
noises = [ [ prng2.rand() for j in range(3) ] for i in range(5) ]
assert all([ noises[i][1] == (pubkeys[i][1] - 1) // pubkeys[i][0] for i in range(5) ])
from Crypto.Util.number import inverse
msgs = []
for i in range(5):
n = pubkeys[i][0]
gm = shares[i][1] * pow(inverse(noises[i][2], n**2), n, n**2) % (n**2)
assert (gm - 1) % n == 0
m = ((gm - 1) // n) * inverse(noises[i][1], n) % n
# Actually the input m of paillier_enc is f(x) + noise.
# Removing noise here
m -= noises[i][0]
msgs.append(m)
Recovering PRIME and flag
Let’s see the make_shares funciton.
def make_shares(secret, k, shares, prime=PRIME):
PR, x = PolynomialRing(GF(prime), name='x').objgen()
f = PR([secret] + [ZZ.random_element(prime) for _ in range(k-1)])
xy = []
pubkey = []
for x in range(1, shares+1):
noise = prng.rand()
n, g, y = paillier_enc(f(x) + noise, prime, noise)
pubkey.append([n, g])
xy.append([x, y])
return pubkey, xy
We can write f = PR([secret] + [ZZ.random_element(prime) for _ in range(k-1)]) as $ax^2 + bx + secret$ with unknown $a, b$.
We know the values $f(1), f(2), f(3), f(4), f(5)$, but we still don’t know PRIME value.
To recover PRIME, follow these steps:
$$f(1) = a + b + secret (\textrm{mod}\ PRIME)$$ $$f(2) = 4a + 2b + secret (\textrm{mod}\ PRIME)$$ $$f(3) = 9a + 3b + secret (\textrm{mod}\ PRIME)$$ $$f(4) = 16a + 4b + secret (\textrm{mod}\ PRIME)$$ $$f(5) = 25a + 5b + secret (\textrm{mod}\ PRIME)$$
$$f(2) - f(1) = 3a + b (\textrm{mod}\ PRIME)$$ $$f(3) - f(2) = 5a + b (\textrm{mod}\ PRIME)$$ $$f(4) - f(3) = 7a + b (\textrm{mod}\ PRIME)$$ $$f(5) - f(4) = 9a + b (\textrm{mod}\ PRIME)$$
$$f(3) - 2f(2) + f(1) = 2a (\textrm{mod}\ PRIME)$$ $$f(4) - 2f(3) + f(2) = 2a (\textrm{mod}\ PRIME)$$ $$f(5) - 2f(4) + f(3) = 2a (\textrm{mod}\ PRIME)$$
Those three values should be same in mod PRIME. Let’s see the values.
# ...
diff1 = [msgs[i + 1] - msgs[i] for i in range(4)]
diff2 = [diff1[i + 1] - diff1[i] for i in range(3)]
print(diff2)
[15811421083594511222443737739252635264048880525922585588301936609228995378847100219077025996330637679748201495232713488175501419093889756582141854326794585932757033416010075789093873549925885865427721464977303837867972880212881542442858600772700056257381545416159374874599314719160184896130245018676138377339,
15811421083594511222443737739252635264048880525922585588301936609228995378847100219077025996330637679748201495232713488175501419093889756582141854326794585932757033416010075789093873549925885865427721464977303837867972880212881542442858600772700056257381545416159374874599314719160184896130245018676138377339,
-124774146038784351164660695638844469856057176985103369924500484527626445042767085680881218533371013137755309524956122804303169360720687143840617652657883917066736244248204558778941905728536041360624781514852127873619283658133441911094549580928196987208500641692108582717297358074519511405222407995323945125710]
The third value is different from the others. It means the difference between the third and the others is the multiple of PRIME, because it should be same in mod PRIME.
The difference is:
140585567122378862387104433378097105120106057511025955512802421136855440421614185899958244529701650817503511020188836292478670779814576900422759506984678502999493277664214634568035779278461927226052502979829431711487256538346323453537408181700897043465882187108267957591896672793679696301352653014000083503049
and it’s actually a prime number. Therefore, it must be PRIME.
Now we know the value of PRIME, we can decrypt the flag.
Here is the full solver.
from Crypto.Util.number import long_to_bytes, inverse
class PRNG256(object):
def __init__(self, seed):
self.mask = (1 << 256) - 1
self.seed = seed & self.mask
def _pick(self):
b = ((self.seed>>0)^(self.seed>>2)^(self.seed>>5)^(self.seed>>10)^1)&1
self.seed = ((self.seed>>1)|(b<<255)) & self.mask
return b
def _rev(self):
b = ((self.seed>>255)^(self.seed>>1)^(self.seed>>4)^(self.seed>>9)^1)&1
self.seed = ((self.seed<<1)|b) & self.mask
def rev(self):
for i in range(256):
self._rev()
def rand(self):
x = 0
for i in range(256):
x = (x << 1) | self._pick()
return x
with open('output.txt', 'r') as f:
ln = len("[+] pubkey: ")
lines = f.readlines()
pubkeys = eval(lines[1][ln:])
shares = eval(lines[2][ln:])
g1 = (pubkeys[0][1] - 1) // pubkeys[0][0]
g1_rev = int(format(g1, '0256b')[::-1], 2)
prng2 = PRNG256(g1_rev)
prng2.rev()
prng2.rev()
noises = [ [ prng2.rand() for j in range(3) ] for i in range(5) ]
assert all([ noises[i][1] == (pubkeys[i][1] - 1) // pubkeys[i][0] for i in range(5) ])
msgs = []
for i in range(5):
n = pubkeys[i][0]
gm = shares[i][1] * pow(inverse(noises[i][2], n**2), n, n**2) % (n**2)
assert (gm - 1) % n == 0
m = ((gm - 1) // n) * inverse(noises[i][1], n) % n
m -= noises[i][0]
msgs.append(m)
diff1 = [msgs[i + 1] - msgs[i] for i in range(4)]
diff2 = [diff1[i + 1] - diff1[i] for i in range(3)]
p = diff2[1] - diff2[2] # It is prime!
a = diff2[0] * inverse(2, p) % p
b = (diff1[0] - 3 * a) % p
secret = (msgs[0] - a - b) % p
print(long_to_bytes(secret))
The flag is zer0pts{excellent_w0rk!y0u_are_a_master_0f_crypt0!!!}.