LA CTF 2025: big e

Problem

Solution

Let’s start by taking a look at chall.py:

from Crypto.Util.number import bytes_to_long, getPrime  
  
flag = REDACTED  
  
pt = bytes_to_long(flag)  
  
p = getPrime(1024)  
q = getPrime(1024)  
n = p*q  
  
e_1 = getPrime(16)  
e_2 = getPrime(16)  
  
ct_1 = pow(pt, e_1, n)  
ct_2 = pow(pt, e_2, n)  
print("ct_1 = ", ct_1)  
print("ct_2 = ", ct_2)  
  
print("e_1 = ", e_1)  
print("e_2 = ", e_2)  
  
print("n = ", n)  
  
# ct_1 = 7003427993343973209633604223157797389179484683813683779456722118278438552981580821629201099609635249903171901413187274301782131604125932440261436398792561279923201353644665062240232628983398769617870021735462687213315384230009597811708620803976743966567909514341685037497925118142192131350408768935124431331080433697691313467918865993755818981120044023483948250730200785386337033076398494691789842346973681951019033860698847693411061368646250415931744527789768875833220281187219666909459057523372182679170829387933194504283746668835390769531217602348382915358689492117524129757929202594190396696326156951763154356777  
# ct_2 = 2995334251818636287120912468673386461522795145344535560487265325864722413686091982727438605788851631192187299910519824438553287094479216297828199976116043039048528458879462591368580247044838727287694258607151549844079706204392479194688578102781851646467977751150658542264776551648799517340378173131694653270749425410071080383488918100565955153958793977478719703463115004497213753735577027928062856483316183232075922059366731900291340025009516177568909257605255717594938087543899066756942042664781424833498278544829618874970165660669400140113047048269742309745649848573501494088032718459018143817236079173978684104782  
# e_1 = 49043  
# e_2 = 60737  
# n = 9162219874876832806204248523866163938680921861751582550947065673035037752546476053774362284605943422397285024205866696280912237827227700515353007344062472274717294484810421409217463791112287997964358655519896402380272695026012981743782564008035342746214988154836484419372449523768063368280069515180570625408254410932129769708259508451185553774810385066789146531683973766796965747310893648672657945403825359068647151094841570404979930542270681833162424933411724266687320976217446032292107871449464575533610369244978941764470549091443086646932177141081314452355708815370388814214178980532690792441231698974328523197187

Notice that pt (i.e. the flag) is encrypted twice, each time with a different public exponent (i.e. big e), but both times using the same modulus (i.e. n). Those big e’s won’t do much to defend against a common modulus attack!

Background

For a message $m$, public exponent $e$, and modulus $n$, the ciphertext $c$ of $m$ using RSA is $c=m^e\mathrm{mod}n$.

Given two ciphertexts $c_1,c_2$ such that $c_1=m^{e_1}\mathrm{mod}n$ and $c_2=m^{e_2}\mathrm{mod}n$ (i.e. same $m$, same $n$, different $e$), $m$ can be recovered from public information (i.e. $c_1,c_2,e_1,e_2,n$) if $gcd(e_1,e_2)=1$ and $gcd(c_2,n)=1$.

If $gcd(e_1,e_2)=1$, there exist integers $x$ and $y$ such that $e_1\times x+e_2\times y=1$ by Bézout’s identity. To find $x$ and $y$, use the Extended Euclidean algorithm. That is,

• Solve for $x$: Ignore $y$ and invert $e_1$ under $\mathrm{mod}{e}_2$
  1. Let $y=1$
  2. Then $e_1\times x+e_2\times y=e_1\times x+e_2=1$
  3. $x=e_1^{-1}\mathrm{mod}{e}_2$ since $gcd(e_1,e_2)=1$ (i.e. $e_1$ is invertible under $e_2$)
• Solve for $y$: Since $e_1$, $e_2$, and $x$ are known, reorder
  1. $e_1\times x+e_2\times y=1$
  2. $e_2\times y=1-e_1\times x$
  3. $y=\frac{1-e_1\times x}{e_2}$

With $x$ and $y$, $m$ is recovered like so:

$c_1^x\times c_2^y\mathrm{mod}n=(m^{e_1}{)}^x\times (m^{e_2}{)}^y=m^{e_{1}x}\times m^{e_{2}y}\mathrm{mod}n=m^{e_{1}x+e_{2}y}\mathrm{mod}n=m^1\mathrm{mod}n=m\mathrm{mod}n$

But $y$ will be negative (since $e_1\times x>1$), in which case we need $c_2^{-1}\mathrm{mod}n$. $c_2$ is invertible if $gcd(c_2,n)=1$, hence the second condition.

To recover $m$, therefore, we must now compute $c_1^x\times (c_2^{-1}{)}^y\mathrm{mod}n$.

Script

ct_1 = 7003427993343973209633604223157797389179484683813683779456722118278438552981580821629201099609635249903171901413187274301782131604125932440261436398792561279923201353644665062240232628983398769617870021735462687213315384230009597811708620803976743966567909514341685037497925118142192131350408768935124431331080433697691313467918865993755818981120044023483948250730200785386337033076398494691789842346973681951019033860698847693411061368646250415931744527789768875833220281187219666909459057523372182679170829387933194504283746668835390769531217602348382915358689492117524129757929202594190396696326156951763154356777  
ct_2 = 2995334251818636287120912468673386461522795145344535560487265325864722413686091982727438605788851631192187299910519824438553287094479216297828199976116043039048528458879462591368580247044838727287694258607151549844079706204392479194688578102781851646467977751150658542264776551648799517340378173131694653270749425410071080383488918100565955153958793977478719703463115004497213753735577027928062856483316183232075922059366731900291340025009516177568909257605255717594938087543899066756942042664781424833498278544829618874970165660669400140113047048269742309745649848573501494088032718459018143817236079173978684104782  
e_1 = 49043  
e_2 = 60737  
n = 9162219874876832806204248523866163938680921861751582550947065673035037752546476053774362284605943422397285024205866696280912237827227700515353007344062472274717294484810421409217463791112287997964358655519896402380272695026012981743782564008035342746214988154836484419372449523768063368280069515180570625408254410932129769708259508451185553774810385066789146531683973766796965747310893648672657945403825359068647151094841570404979930542270681833162424933411724266687320976217446032292107871449464575533610369244978941764470549091443086646932177141081314452355708815370388814214178980532690792441231698974328523197187
 
from gmpy2 import gcd, invert
 
if (gcd(e_1, e_2) == 1 and gcd(ct_2, n) == 1):  
	x = invert(e_1, e_2)  
	y = int((1-(x*e_1))/e_2)  
	
	mx = pow(ct_1, x, n)  
	my = pow(invert(ct_2, n), -y, n)  
	
	m_int = (mx * my) % n  
	m_bytes = bytes.fromhex(hex(m_int)[2:])  
	m_str = m_bytes.decode("utf-8")  
	
	print(m_str)