For this challenge are provided with:
- an RSA public key $(n, e)$
- the ciphered flag $c_1 = m_1^e mod n$
- a blackbox function $hom\_sum: (c_1, c_2) -> ENC(DEC(c_1)+DEC(c_2))$
- a blackbox function $hom\_prod: (c_1, c_2) -> ENC(DEC(c_1).DEC(c_2))$ (notice that this function is not necessary: $ENC(DEC(c_1).DEC(c_2)) = c_1 . c_2$).
We are in a related-message situation: we can generate the ciphertex of an (unknown) message whose relation to another (unknown) message (the flag) is known. The Franklin–Reiter attack allows us to retrieve the messages from their ciphertexts:
First we generate the ciphertext of a related message, for instance, $c_2 = (m_1 + 1)^e = hom\_sum(c_1, 1^e)$.
Then we generate two polynomials of $\mathbb{Z} / n \mathbb{Z} [X]$:
$$P = X^e - c_1$$ $$G = (X - 1)^e - c_2$$
Notice that $P(m_1) = G(m_1) = 0$.
This means that $(X - m_1)$ is a common factor of $P$ and $G$, and hence, a factor of $GCD(P, G)$. Because $GCD(P,G)$ is most likely of degree $1$, the GCD is equal to $X-m_1$, giving:
$$m_1 = -GCD(P, G)(0)$$
As a note: the GCDs of two polynomials are not unique, but they are all equal up to a multiplicative scalar constant. We can consider $GCD(P, Q)$ to be the unique monic polynomial (a polynomial with a leading factor of $1$) of maximum degree that divide both $P$ and $G$
The last issue is that (as of 2026) sagemath does not implement the $GCD$ computation for polynomials in $\mathbb{Z} / n \mathbb{Z} [X]$. The simplest solution is to implement Euler’s algorithm:
def gcd(a, b):
while b:
a, b = b, a % b
return a
Unfortunately this algorithm takes quite a lot of time when $e=65537$ (as it is the case here). We can let it run for an hour or two and take the opportunity to go outside and touch some grass, or implement a faster algorithm. The script bellow implements the Half-GCD algorithm described in the book “The Design and Analysis of Computer Algorithms” (ISNB 978-0-201-00029-0) and is notably faster.
####### Local implementation of the challenge #######
from Crypto.PublicKey import RSA
def hom_prod(k, c1, c2):
m1 = pow(c1, k.d, k.n)
m2 = pow(c2, k.d, k.n)
return pow(m1 * m2, k.e, k.n)
def hom_sum(k, c1, c2):
m1 = pow(c1, k.d, k.n)
m2 = pow(c2, k.d, k.n)
return pow(m1 + m2, k.e, k.n)
k = RSA.generate(1024)
flag = int.from_bytes(b"FLAG{TEST LOCAL FLAG}", "big")
assert flag < k.n
flag_enc = pow(flag, k.e, k.n)
####### End local implementation #######
from sage.all import *
####### Fast GCD implementation #######
# Fast GCD implementation because it is not implemented by sage in Z/nZ[X]
# Euler's algorithm works but takes a lot more time
def hgcd(a0, a1):
ring = a0.parent()
(x,) = ring._first_ngens(1)
if a1.degree() <= a0.degree() / 2:
return matrix(ring, 2, [1, 0, 0, 1])
m = a0.degree() // 2
# ai = bi x**m + ci
b0, c0 = a0.quo_rem(x**m)
b1, c1 = a1.quo_rem(x**m)
r = hgcd(b0, b1)
d, e = r * vector([a0, a1])
q, f = d.quo_rem(e)
mm = m // 2
g0, h0 = e.quo_rem(x ** (m // 2))
g1, h1 = f.quo_rem(x ** (m // 2))
s = hgcd(g0, g1)
return s * matrix(ring, 2, [0, 1, 1, -q]) * r
def fast_gcd(a0, a1):
"""
Half-GCD algorithm as described in The Design and Analysis
of Computer Algorithms (ISNB 978-0-201-00029-0).
"""
if a0.degree() < a1.degree():
a0, a1 = a1, a0
if a0.degree() == a1.degree():
a0, a1 = a1, a0 % a1
if a1.divides(a0):
return a1
r = hgcd(a0, a1)
b0, b1 = r * vector([a0, a1])
if b1.divides(b0):
return b1
c = b0 % b1
return fast_gcd(b1, c)
####### Actual solution #######
n = Integer(k.n)
e = Integer(k.e)
enc_flag = Integer(flag_enc)
c1 = enc_flag
enc_1 = pow(1, e, n) # = 1 :-)
# c1 = flag^e [n]
# c2 = (flag + 1)^e [n]
c2 = Integer(hom_sum(k, c1, enc_1))
ring = PolynomialRing(Zmod(n), names=("x",))
(x,) = ring._first_ngens(1)
g = x**e - c1
p = (x + 1) ** e - c2
# g(flag) = p(flag) = 0 => (X-flag) divides both g1 and g2
# => (X-flag) divides GCD(g1, g2)
# deg(GCD(g, p)) is probably 1
# => flag = -GCD(g1,g2).monic()(0) [n]
gcd_gp = fast_gcd(g, p).monic()
assert gcd_gp.degree() == 1
m = -gcd_gp(0)
print(m.to_bytes().strip(b"\0").decode())