The Strongest Exponent I Thought 2

Attachment:

from Crypto.Util.number import getPrime

flag = "TSGCTF{************REDACTED*************}"
assert len(flag) == 41

p = getPrime(1024)
q = getPrime(1024)
n = p * q
phi = (p - 1) * (q - 1)
# e = (p ** q) % phi
e = pow(p, q, phi)

m = int.from_bytes(flag.encode(), 'big')

c = pow(m, e, n)

print(f"n = {n}")
print(f"e = {e}")
print(f"c = {c}")
n = 12304937106495019948935823747896177539282746445389847240573471819615183350782871344655736641424538327646203132786364331680803172672565881147275872891374004325125755563779284122723272535648080869675254890421953184730207640610391499587131846028642837930573002266641165653436488988851379423113634977604789919048336354635258936662005400938712244679354370283198939324907588785304516972967767660681327553320071078132881601695691855892384395407410833039284741805467662060074582416349864492118156987242250334988709485218902717356401467908841000040063209207292376700158480563758869353523722467860892726428807123723391659759129
e = 4671508298202473062908098501122739212494104135822769469172957660169210197809353803016143135118329312461442335945081361046400708303845794518393283847717962634490620864727105047957787663674174103273199546275870204405433321074872048541293929182467813762150496313476918071127459153748615896909138251615692934309061780761262625941584853051868040264550530943071064965322169702801685784672354619433050569448706427815793570967672380706998764482936197619503081883603989897593357214325915544887558829367659538199805711114070709896237126163581049975456559860839042551241198296925972794823104585546475842981577962176035100657125
c = 734159268912236870326906291519339441060443190729549798304173425093568801503632263909956754998145543587462956329598121470425917551153360082681204702617948060192715494367013944150441511630518697760762122142274058030831598925419796406992806841961744715847324329596313556581670687011807097996415174407805818109493635886581027682687266023134960157243158377876713374560244314688652713790833693878860837389203062889825767981000866786402777089465218863064978825889452354777968576215646119739501361612158664806323278269221278619558106196445546507144889290265009352562267920470295408931325837487026801823417636759968187821134

Solved by AI:

TSGCTF 2025: The Strongest Exponent I Thought 2 - Writeup

Category: Cryptography
Points: (Not specified)
Author: (Not specified)
Solved by: (Your name/team)

Challenge Description

But this time, it's for real! The actual strongest character EVER!

We're given a custom RSA-like cryptosystem with a special exponent construction. The challenge provides:

  • problem.py - The encryption script
  • output.txt - The encrypted output containing n, e, and c

Files

  • problem.py - Encryption script
  • output.txt - Contains n, e, and c values

Encryption Script Analysis

from Crypto.Util.number import getPrime

flag = "TSGCTF{************REDACTED*************}"
assert len(flag) == 41

p = getPrime(1024)
q = getPrime(1024)
n = p * q
phi = (p - 1) * (q - 1)
# e = (p ** q) % phi
e = pow(p, q, phi)

m = int.from_bytes(flag.encode(), 'big')

c = pow(m, e, n)

print(f"n = {n}")
print(f"e = {e}")
print(f"c = {c}")

The key difference from standard RSA is the exponent: - Standard RSA: e is typically small (like 65537) and coprime with phi - This challenge: e = p^q mod phi

Given Values

n = 12304937106495019948935823747896177539282746445389847240573471819615183350782871344655736641424538327646203132786364331680803172672565881147275872891374004325125755563779284122723272535648080869675254890421953184730207640610391499587131846028642837930573002266641165653436488988851379423113634977604789919048336354635258936662005400938712244679354370283198939324907588785304516972967767660681327553320071078132881601695691855892384395407410833039284741805467662060074582416349864492118156987242250334988709485218902717356401467908841000040063209207292376700158480563758869353523722467860892726428807123723391659759129
e = 4671508298202473062908098501122739212494104135822769469172957660169210197809353803016143135118329312461442335945081361046400708303845794518393283847717962634490620864727105047957787663674174103273199546275870204405433321074872048541293929182467813762150496313476918071127459153748615896909138251615692934309061780761262625941584853051868040264550530943071064965322169702801685784672354619433050569448706427815793570967672380706998764482936197619503081883603989897593357214325915544887558829367659538199805711114070709896237126163581049975456559860839042551241198296925972794823104585546475842981577962176035100657125
c = 734159268912236870326906291519339441060443190729549798304173425093568801503632263909956754998145543587462956329598121470425917551153360082681204702617948060192715494367013944150441511630518697760762122142274058030831598925419796406992806841961744715847324329596313556581670687011807097996415174407805818109493635886581027682687266023134960157243158377876713374560244314688652713790833693878860837389203062889825767981000866786402777089465218863064978825889452354777968576215646119739501361612158664806323278269221278619558106196445546507144889290265009352562267920470295408931325837487026801823417636759968187821134

Mathematical Analysis

Key Insight

Given e = p^q mod phi where phi = (p-1)*(q-1):

  1. e ≡ p^q (mod phi)
  2. Since phi = (p-1)*(q-1), we have e ≡ p^q (mod (p-1)) (when a = b (mod c * d), you known that a = b (mod c))
  3. Because p ≡ 1 (mod (p-1)), we get p^q ≡ 1^q ≡ 1 (mod (p-1))
  4. Therefore: e ≡ 1 (mod (p-1))

This means p-1 divides e-1.

Consequences

Since p-1 divides e-1, we can write e-1 = k*(p-1) for some integer k.

For any integer a coprime with n (like a=2): - By Fermat's little theorem: a^(p-1) ≡ 1 (mod p) - Therefore: a^(e-1) = a^(k*(p-1)) ≡ 1^k ≡ 1 (mod p)

Thus p divides a^(e-1) - 1.

Since p also divides n, we have: 

gcd(a^(e-1) - 1, n) = p

This allows us to factor n!

Attack Plan

  1. Compute gcd(2^(e-1) - 1, n) to obtain p
  2. Compute q = n // p
  3. Compute phi = (p-1)*(q-1)
  4. Compute d = e^(-1) mod phi (modular inverse)
  5. Decrypt: m = c^d mod n
  6. Convert m to bytes to get the flag

Exploit Implementation

#!/usr/bin/env python3
from Crypto.Util.number import long_to_bytes
import math

# Given values
n = 12304937106495019948935823747896177539282746445389847240573471819615183350782871344655736641424538327646203132786364331680803172672565881147275872891374004325125755563779284122723272535648080869675254890421953184730207640610391499587131846028642837930573002266641165653436488988851379423113634977604789919048336354635258936662005400938712244679354370283198939324907588785304516972967767660681327553320071078132881601695691855892384395407410833039284741805467662060074582416349864492118156987242250334988709485218902717356401467908841000040063209207292376700158480563758869353523722467860892726428807123723391659759129
e = 4671508298202473062908098501122739212494104135822769469172957660169210197809353803016143135118329312461442335945081361046400708303845794518393283847717962634490620864727105047957787663674174103273199546275870204405433321074872048541293929182467813762150496313476918071127459153748615896909138251615692934309061780761262625941584853051868040264550530943071064965322169702801685784672354619433050569448706427815793570967672380706998764482936197619503081883603989897593357214325915544887558829367659538199805711114070709896237126163581049975456559860839042551241198296925972794823104585546475842981577962176035100657125
c = 734159268912236870326906291519339441060443190729549798304173425093568801503632263909956754998145543587462956329598121470425917551153360082681204702617948060192715494367013944150441511630518697760762122142274058030831598925419796406992806841961744715847324329596313556581670687011807097996415174407805818109493635886581027682687266023134960157243158377876713374560244314688652713790833693878860837389203062889825767981000866786402777089465218863064978825889452354777968576215646119739501361612158664806323278269221278619558106196445546507144889290265009352562267920470295408931325837487026801823417636759968187821134

# Step 1: Factor n using the vulnerability
pow_result = pow(2, e-1, n)
p = math.gcd(pow_result - 1, n)
q = n // p

print(f"Found p: {p}")
print(f"Found q: {q}")
print(f"Verification: n == p*q? {n == p*q}")

# Step 2: Compute phi and decryption exponent
phi = (p-1)*(q-1)
d = pow(e, -1, phi)  # Modular inverse

# Step 3: Decrypt
m = pow(c, d, n)

# Step 4: Convert to flag
flag = long_to_bytes(m)
print(f"Flag: {flag.decode()}")

Running the Exploit

$ python3 exp.py
Found p: 105937009553883862577967493979820300930239452369039712050865514405472077146174715149934438264344045317716403466474742353074706323059068441839265251729695958013724754515351900282908744725502755279101079244363313515315674647685808381377886490847262229336888471590571794486450616598202909282796888725875837701253
Found q: 116153336386527217696396836098940101996561406780282082275084959504295159477378988046243098201524326207914965592350955440641219375853263533368698528142124545547342363268572615298653923480284789760821739772188389370773347340174102358172495894629846892502629301625010753345575197711382718272022098628309152764293
Verification: n == p*q? True
Flag: TSGCTF{My_power_is_too_dangerous_to_use!}

Flag

TSGCTF{My_power_is_too_dangerous_to_use!}

Why This Works

The vulnerability stems from the custom exponent construction e = p^q mod phi. While this might seem strong at first glance, it creates a mathematical relationship e ≡ 1 (mod (p-1)). This is essentially leaking a multiple of (p-1), which is enough to factor n using the GCD attack.

In standard RSA, we choose e to be a small, fixed number (like 65537) that's coprime with phi. This challenge demonstrates why deviating from well-established cryptographic constructions can introduce vulnerabilities.

Alternative Approaches

  1. Using different a values: The attack works with any a coprime to n, not just a=2. If gcd(2^(e-1) - 1, n) = 1 (which doesn't happen here), we could try a=3, a=5, etc.

  2. Pollard's p-1 algorithm: Since we know e-1 is a multiple of p-1, we could potentially use Pollard's p-1 algorithm with e-1 as the bound. However, the GCD attack is simpler and more efficient in this case.

Lessons Learned

  1. Don't roll your own crypto: Custom cryptographic constructions often have hidden vulnerabilities.
  2. Mathematical relationships matter: The relationship e ≡ 1 (mod (p-1)) seems innocuous but is fatal for RSA security.
  3. GCD attacks are powerful: Knowing a multiple of (p-1) or (q-1) can lead to factorization.
  4. Fermat's little theorem is useful: a^(p-1) ≡ 1 (mod p) is a fundamental tool in many cryptographic attacks.

References

  • RSA cryptosystem
  • Fermat's little theorem
  • GCD-based factorization attacks
  • Pollard's p-1 algorithm