Flash CTF – Duality of Key

Challenge Objective

The goal of this challenge is to leverage the fact that d₁ and d₂ are close in value. We can factor N and decrypt the flag. The attack is based on techniques from this paper (https://eprint.iacr.org/2015/399.pdf), though one can derive the necessary equations independently.

What is Coppersmith’s method?

In simple terms, Coppersmith’s method can be used to solve polynomials f(x) = 0 mod N (where N = p × q). An extension of the Coppersmith algorithm allows us to solve for small roots modulo a factor of N.

Proof of Concept (PoC)

Working through the equations:

From the source file, we can observe that d₁ – d₂ is small.

Using RSA knowledge:

• e₁ × d₁ ≡ 1 mod φ (Equation 1)
• e₂ × d₂ ≡ 1 mod φ (Equation 2)

Multiplying Equation 1 by e₂ and Equation 2 by e₁ gives:

• (e₁ × d₁) × e₂ ≡ 1 × e₂ mod φ 
• (e₂ × d₂) × e₁ ≡ 1 × e₁ mod φ

Now subtract the two equations:

• e₁ × e₂ × (d₂ – d₁) ≡ (e₁ – e₂) mod φ

Multiplying both sides by inverse(e₁ × e₂) yields:

• d₂ – d₁ ≡ (e₁ × e₂)⁻¹ × (e₁ – e₂) mod φ

Since φ in this case is p(p – 1)q, we can reduce the modulus:

• d₂ – d₁ ≡ (e₁ × e₂)⁻¹ × (e₁ – e₂) mod p

Let a be the constant (e₁ × e₂)⁻¹ × (e₁ – e₂), and let x represent d₂ – d₁. Thus, the final equation becomes:

• (r – x) mod p = 0

Since x is small, we can use Coppersmith’s method to solve for it.

The following is the sage solve script:

from Crypto.Util.number import * 
from sage.all import *

half1 = 78651793350576640257900270619795917529285047644781765616581951057657331607131680336334150941043270280956949519156262933098001212767520262811961846436456656232341708272687902930721771428435673461029160550713916008786765253837510226768726267021261591817547516595574853876261700889652868486451202805313650219035
half2 = 30521573044014797629905067010977428736108369836323048856638167547126098265619057810389376407142161783807725860136412967017301160328902290246130326937605121934755173596117979252594236685871178336014678635615730794208623869595900231140992001089801097773670072560758257753786495727148635061494576282052813437443
e1 = 48041843429846995439836089780466518990169717666500777185155099979742475823401831891726475465268908458890247473550715925911568215099863398806220424601608634294086687496014534365765293677751551370125683019404227658935319070779153770341163005699949953408333148903106238404181636497469874910954910839321212097377
e2 = 81321083568988906930621381366281884594209208525141702431451133589494246818051381307156037678664472921898900352239167226199151581081491752218518268840312768099135951875491714805539024406839288835828740432643135907728846419267437850846744605160826081609587285016495347365304540108695192262127687343324790311323
N = 85331786094363726303676262519644108650742699682084288027986403245313360478382722639360576783920875212775769669608267562536548019296066688463786544707608059141596098797246525476204652518715852830744533620825938766057674429338584968831567070056099772240180671323983938508942001779310674405066276411305766485357

a = (e2 - e1) * inverse(e1 * e2, N)
P = PolynomialRing(Zmod(N), "x")
x = P.gen()
f = x - a

root = ZZ(f.monic().small_roots(X=2 ** 80, epsilon=0.8, beta=0.66)[0])
p = N // GCD(int(f(root)), N)
q = N // (p ** 2)
phi = p * (p - 1) * q
d1 = inverse(e1, phi)
d2 = inverse(e2, phi)

half1 = long_to_bytes(int(pow(half1, d1, p * p)))
half2 = long_to_bytes(int(pow(half2, d2, p * p)))

flag = half1 + half2

print(flag)

In this code, we compute the difference d₂ – d₁ as x, solve for it using Coppersmith’s method, and recover p. Once p is known, we calculate φ, derive d₁ and d₂, and finally decrypt the two halves of the flag.

Flag:

MetaCTF{R5A_V4r14nt5_4r3_U5u411ly_5u5_Th15_i5_4_Pap3r_ch4113ng3_h4d_to_tw3ak_1t_th0}