## DEV Community 👩‍💻👨‍💻 is a community of 964,423 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

karapto

Posted on

# 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  = 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.

$c = 3^{\text{flag}} \mod n$

First, let's look at the contents of output.txt. The contents are given n and c.

→ cat output.txt


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.

$y = g^x \mod n(=pq)$

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:

1. 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)

2. 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)

3. Find the final FLAG using ChineseRemainderTheorem(CRT).

import math
from sage import *

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