The probabilistic problem, improved and strong!
Files given:
def gen_params(nbit):
p, q = [getPrime(nbit) for _ in range(2)]
n, f, g = p * q, lcm(p-1, q-1), p + q
e = pow(g, f, n**2)
u = divmod(e-1, n)[0]
v = inverse(u, n)
params = int(n), int(f), int(v)
return params
def improved(m, params):
n, f, v = params
if 1 < m < n**2 - 1:
e = pow(m, f, n**2)
u = divmod(e-1, n)[0]
L = divmod(u*v, n)[1]
H = hashlib.sha1(str(L).encode('utf-8')).hexdigest()
return H
The goal of this challenge is to create a collision given improved as the hash function given \(n,f,v\). As it is unlikely that we find a sha1 collision, we aim to find a collision in L. We first express L mathematically:
\[n=pq\quad f=\lambda(n)=\lcm(p-1,q-1)\] \[L(m)=\frac{m^f-1}{n}v\pmod n\]
and note that \(x^f=1\pmod n\) whenever \((x,n)=1\).
Lets suppose we want \(L(m_1)=L(m_2+kn)\), then expanding this out, we get
\[\frac{m_1^f-1}{n}=\frac{(m_2+kn)^f-1}{n}\pmod n\] \[m_1^f=m_2^f+fm_2^{f-1}kn\pmod{n^2}\] \[\frac{m_1^f-m_2^f}{fm_2^{f-1}n}=k\pmod n\] \[\frac{m_1^f-m_2^f}{n}\frac{m_2}{f}=k\pmod n\]
which can easily be computed since we know \(n,f\)! Hence getting collisions is simple.
Solution at solve.py
Flag:
CCTF{Phillip_N0W_4_pr0b4b1liStiC__aSymM3Tr1C__AlGOrithM!!}