RSA could be hard, or easy?
Files given:
nbit = 64
while True:
p, q = getPrime(nbit), getPrime(nbit)
P = int(str(p) + str(q))
Q = int(str(q) + str(p))
PP = int(str(P) + str(Q))
QQ = int(str(Q) + str(P))
if isPrime(PP) and isPrime(QQ):
break
This challenge generates our primes with the above method. In order to understand what’s going on, we can rewrite \(PP\cdot QQ\) in terms of \(p,q\). Let \(\ell_p,\ell_q\) be the number of decimal digits of \(p,q\) respectively, then
\[P=p10^{\ell_q}+q\] \[Q=q10^{\ell_p}+p\] \[PP=P10^{\ell_p+\ell_q}+Q\] \[QQ=Q10^{\ell_p+\ell_q}+P\] \[PP\cdot QQ=pq10^{3(\ell_p+\ell_q)}+\left(p^210^{\ell_q}+q^210^{\ell_p}+pq\right)10^{2(\ell_p+\ell_q)}+\dots+p^210^{\ell_q}+q^210^{\ell_p}+pq\]
Looking closely at the expansion, it tells us that by taking the first and last \(\ell_p/\ell_q\)-ish digits of \(PP\cdot QQ\), we get a very good approximation of \(pq\). Since we know \(p,q<2^{64}\), we expect the length to be \(19/20\), hence we simply brute force a little by hand until yafu factorization finds only two prime factors of \(pq\)
PQ =
9802713296337413422\
272498467780536422550545430268877750619346836296911192794023888752291658602460169966140187114767462486843957741638712\
2924526713690754043
pq =
9802713296337413421\
2924526713690754043
Solution at solve.py
Flag:
CCTF{wH3Re_0Ur_Br41N_Iz_5uP3R_4CtIVe_bY_RSA!!}