Zenn
💭

[crypto 172pts] twin-d - TokyoWesterns CTF 6th 2020

2020/10/05に公開
#
CTF
#
writeup
tech

challenge

task.rb

require 'json'
require 'openssl'

p = OpenSSL::BN::generate_prime(1024).to_i
q = OpenSSL::BN::generate_prime(1024).to_i

while true
    d = OpenSSL::BN::generate_prime(1024).to_i
    break if ((p - 1) * (q - 1)).gcd(d) == 1 && ((p - 1) * (q - 1)).gcd(d + 2) == 1
end

e1 = OpenSSL::BN.new(d).mod_inverse(OpenSSL::BN.new((p - 1) * (q - 1))).to_i
e2 = OpenSSL::BN.new(d + 2).mod_inverse(OpenSSL::BN.new((p - 1) * (q - 1))).to_i

flag = File.read('flag.txt')
msg = OpenSSL::BN.new(flag.unpack1("H*").to_i(16))
n = OpenSSL::BN.new(p * q)
enc = msg.mod_exp(OpenSSL::BN.new(e1), n)

puts ({ n: (p*q).to_s, e1: e1.to_s, e2: e2.to_s, enc: enc.to_s }).to_json

output(n, e1, e2, enc)が与えられる。

数式に表すと以下の通り。

n = p * q \\ e_1d \equiv 1 \bmod{\varphi(n)} \\ e_2(d+2) \equiv 1 \bmod{\varphi(n)} \\ enc \equiv flag ^{e_1} \bmod{n}

solution

式変形をうまくしてやる。

e_2(d+2) \equiv 1 \bmod{\varphi(n)} \\ e_2d + 2e_2 \equiv 1 \bmod{\varphi(n)} \\

ここで、両辺にe_1を掛ける。

e_1e_2d + 2e_1e_2 \equiv e_1 \bmod{\varphi(n)} \\

e_1d \equiv 1 \bmod{\varphi(n)}より

e_2 + 2e_1e_2 -e_1 \equiv 0 \bmod{\varphi(n)}\\ e_2 + 2e_1e_2 - e_1 = k \varphi(n)

ここでk \in \mathbb{Z}とする。
e_2 + 2e_1e_2 - e_1を計算することで、k\varphi(n)を得ることができる。
よって、

d \equiv e_1 \bmod{k\varphi(n)}

を計算することで、dを求めることができる。

solverどーん

from Crypto.Util.number import long_to_bytes, inverse
import json

with open("./../challenge/twin-d/output") as f:
    data = json.loads(f.read().strip())
n = int(data["n"])
e1 = int(data["e1"])
e2 = int(data["e2"])
c = int(data["enc"])

kphi = e2 + 2*e1*e2 - e1
d = inverse(e1, kphi)
m = pow(c, d, n)
print(long_to_bytes(m))

$ python3 solver.py 
b'TWCTF{even_if_it_is_f4+e}\n'

解法が他にもいろいろあった。

references

Discussion