Description
I heard someone has been sneakily installing backdoors in open-source implementations of Diffie-Hellman... I wonder who it could be... ;)
- gen.py
- output.txt
Solution
First, let's open gen.py. Various functions are written in this file, but the variable c is the most noteworthy part.
#!/usr/bin/python
from binascii import hexlify
from gmpy2 import *
import math
import os
import sys
if sys.version_info < (3, 9):
math.gcd = gcd
math.lcm = lcm
_DEBUG = False
FLAG = open('flag.txt').read().strip()
FLAG = mpz(hexlify(FLAG.encode()), 16)
SEED = mpz(hexlify(os.urandom(32)).decode(), 16)
STATE = random_state(SEED)
def get_prime(state, bits):
return next_prime(mpz_urandomb(state, bits) | (1 << (bits - 1)))
def get_smooth_prime(state, bits, smoothness=16):
p = mpz(2)
p_factors = [p]
while p.bit_length() < bits - 2 * smoothness:
factor = get_prime(state, smoothness)
p_factors.append(factor)
p *= factor
bitcnt = (bits - p.bit_length()) // 2
while True:
prime1 = get_prime(state, bitcnt)
prime2 = get_prime(state, bitcnt)
tmpp = p * prime1 * prime2
if tmpp.bit_length() < bits:
bitcnt += 1
continue
if tmpp.bit_length() > bits:
bitcnt -= 1
continue
if is_prime(tmpp + 1):
p_factors.append(prime1)
p_factors.append(prime2)
p = tmpp + 1
break
p_factors.sort()
return (p, p_factors)
e = 0x10001
while True:
p, p_factors = get_smooth_prime(STATE, 1024, 16)
if len(p_factors) != len(set(p_factors)):
continue
# Smoothness should be different or some might encounter issues.
q, q_factors = get_smooth_prime(STATE, 1024, 17)
if len(q_factors) != len(set(q_factors)):
continue
factors = p_factors + q_factors
if e not in factors:
break
if _DEBUG:
import sys
sys.stderr.write(f'p = {p.digits(16)}\n\n')
sys.stderr.write(f'p_factors = [\n')
for factor in p_factors:
sys.stderr.write(f' {factor.digits(16)},\n')
sys.stderr.write(f']\n\n')
sys.stderr.write(f'q = {q.digits(16)}\n\n')
sys.stderr.write(f'q_factors = [\n')
for factor in q_factors:
sys.stderr.write(f' {factor.digits(16)},\n')
sys.stderr.write(f']\n\n')
n = p * q
m = math.lcm(p - 1, q - 1)
d = pow(e, -1, m)
c = pow(FLAG, e, n)
print(f'n = {n.digits(16)}')
print(f'c = {c.digits(16)}')
Looking at the code, we can see that it is very similar to the VerySmooth problem, with the numbers p and q all being SmoothInteger.
It seems that the Pollard'sp-1method can be used to prime factorize (Factorize) the composite number n.
However, we can also confirm that singularly this challenge did not use the RSA technique to generate the ciphertext, but rather the Diffie-Hellman algorithm, as shown in the problem description.
It seems that we can get the flag by solving this discrete logarithm problem.
First, let's look at the contents of output.txt. The contents are given n and c.
→ cat output.txt
n = 5837ab2dd26ff8ab827a4885c72229e2e908af1de303c35e1190659fb120acd3b256cd71d91cc25a96ed4261259c8928720217b1fb8fcc1002375f779ff64fc4f181715d882f304678bed6f376cb0497cb599d88dc4bb4563e33709bd8b8c8e41da4b61ab01eb50d188f532690520a6b69b6c4790d2076eebc32e01d59945b5c3d8af79d0b7eb271527f8c6eb6cf70bdd141a5278d6f9f557513ec56b94da27d7cb85117074d318154967e645f42b4b42231ad8e29f0a3ccd2596444f6cc1de903ec3cb27c28792e9437b6bc1cd57a61f15b96f1690027119cb87c07d96760230afff7f8c9287d0573c34830359694918a721d87213d0baba7ee2f519d839581
c = 40c4c7f7a326558762ac0f64a8abb6f6496851c45a2763791132ecc4c8e029cc0a8c9d6ddb62dbdedf1e4f2f8ba8cb8a965aa9eb8c88cd582274b6ba9402fa84e63a6847c925b3fc34c6d5e9b925f03c656b2a6c2691a15196e4a246c5e3cb46b41f5090bf588911fbd8459ca9da19c1a8f3cd61af905790dd049d16544a2c4fd38f99af62d8080d49b5760c86a0cdb94ddadc785415e4e3e5ddf413a0a10e919c3ddda9c571f26498312718b4da3063a294394dc01fbb2f2c514d2b70dd999980cf5743ecf843450d71a613d74a3ab5d201bf864a617c3a25fecb9191e0ebe9bf678abed2384deb5ce91f753e9f20036fe61edfada631a4876a5cca790bc46
Unfortunately, I couldn't figure out anything from this information alone. So I looked at the hints.
Look for Mr. Wong's whitepaper... His work has helped so many cats!
This is a paper presented at DEFCON24. I am not an expert in cryptography, so I don't understand everything, but this gives me a hint to solve the problem.
This figure shows that the difficult problem of finding x from the above equation can be decomposed into a simple problem of finding x from mod p and mod q instead of n.
Finally we can derive the answer to the original question using the Chinese Reminder Theorem (CRT).
In summary, we can get the flags by the following steps:
As in the VerySmooth problem, both the small numbers p and q are SmoothInteger, so the first step is to find out the prime numbers p and q by prime factorizing n in a reasonable amount of time. (Pollard's p-1 method)
Having found out the prime numbers p and q, the discrete logarithm problem (DLP) of the DP-Hellman algorithm is divided into smaller problems for each prime number p and q, and FLAG_p and FLAG_q are obtained in a reasonable time. (Pohlig-Hellman Algorithm)
Find the final FLAG using ChineseRemainderTheorem(CRT).
import math
from sage import *
N = 0x5bf9961e4bcfc88017e1a9a40958af5eae3b3ee3dcf25bce02e5d04858ba1754e13e86b78a098ea0025222336df6b692e14533dad7f478005b421d3287676843f9f49ffd7ebec1e8e43b96cde7cd28bd6fdf5747a4a075b5afa7da7a4e9a2ccb26342799965f3fb6e65e0bb9557c6f3a67568ccbfaaa7e3d6c5cb79dd2f9928111c3183bf58bd91412a0742bbfb3c5cebfb0b82825da0875c5ee3df208ce563f896d67287c8b9aad9943dd76e5eae1fc8abd473ec9f9e4f2b49b7897954ca77b8f00ed51949c7e4f1f09bd54b830058bd7f4da04e5228250ba062ec0e1d19fb48a05333aada60ecdfc8c62c15773ed7e077edba71621f6a6c10302cc9ed26ec9
B = 100000
primes = []
for i in range(2, B + 1):
flag = True
for j in primes:
if j * j > i:
break
if i % j == 0:
flag = False
break
if flag:
primes.append(i)
a = 2
for p in primes:
wow = pow(p, math.floor(math.log(B, p)))
a = pow(a, wow, N)
print(math.gcd(a - 1, N))
p = 112702077491326624035437448311528244416633038267184436467539953783623022543629307291975209668348933325006075339780165463077524233511267597550006727923822554354936896793276829740193900248027487979522143806746878229772394053610558597354876381637035909859704552979985236170415302488615161107293296362528480525723
q = N // p
assert p*q == N
g = 3
ct = 0x2475123653f5a4b842e7ac76829e896450126f7175520929a35b6a4302788ceff1a605ed30f4d01c19226e09fc95d005c61320d3bbd55cfebbc775332067ac6056c1969282091856eaa44ccaf5738ac6409e865bbd1186d69f718abd2b3a1dd3dc933a07ca687f0af9385406fd9ee4fa5f701ad46f0852bf4370264c21f775f1e15283444b3bf45af29b84bb429ed5a17adc9af78aee8c5351434491d5daf9dd3ce3cf0cd44b307eb403f0e9f482dd001b25ed284c4e6c1ba2864e5a2c4b1afe4161426cc67203f30553c88d7132aef1337eca00622b47cb7a28195f0e3a2ab934e6163b2941a4631412e13b1a72fe34e6480fada9af4dae14f2608805d61ee
flag = 38251710328773353864596243890570950490237
flag = bytes.fromhex(format(flag, 'x'))
print(flag)
# b'picoCTF{cf****b8}'
Top comments (0)