# 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