Beethoven’s Encryption

Challenge Overview

Category: Cryptography / Steganography

Miscrypto - Beethovens encryption

Wait there is some musician inside this corporation ?. Flag may be in non-standard format.

Objective: Decode a hidden message represented as musical notation on a treble clef staff.

Initial Analysis

The challenge provides an image (beethoven.png) containing two lines of musical notation. Initial observations include:

Clef: Treble Clef.

Note Types: A mix of quarter notes (filled heads with stems) and whole notes (hollow heads).

Observation: Standard musical notes only range from A to G. Since the resulting string contains numbers (1, 3, 4, 5, 7) and letters like ‘S’ and ‘M’, this is not a simple rhythmic or melodic transcription. It is a Symbol Substitution Cipher.

Decoding Process

To decode the image, each note’s position on the staff must be mapped to a specific alphanumeric character.

Step A: Mapping the Notes

By analyzing the vertical position of each note on the staff (Lines: E-G-B-D-F; Spaces: F-A-C-E):

The first note is on the top line (F).

The second note is in the second space from the bottom (A).

The third note is in the third space from the bottom (C).

Step B: Tooling

Using a specialized tool like dCode.fr (Music Sheet Cipher), the visual symbols were mapped against known musical substitution alphabets. The tool automates the translation of note positions and types (quarter vs. whole) into a character string.

3. Flag Extraction

The decoded string initially appeared as: SKCERTTH151SMU51C70MY34R5

By applying Leetspeak translation:

TH15 → THIS

15 → IS

MU51C → MUSIC

70 → TO

34R5 → EARS

The final phrase revealed: "THIS IS MUSIC TO MY EARS".

4. Final Flag

The platform accepted the raw string without underscores or hyphens: SKCERTTH151SMU51C70MY34R5

Lessons Learned

Format Matters: CTF flags often require strict adherence to the output of the decoding tool; adding “standard” separators like underscores can result in a “Wrong Answer” even if the content is correct. Symbol Substitution: When musical notes represent characters outside the A-G range, they are functioning as a font for a substitution cipher, not as literal music.

Miscrypto – Encryption Enjoyer

Category: Reverse Engineering / Crypto

---

Challenge Description

An incident response team recovered a single file from a compromised server, but the attacker encrypted it before disconnecting. Your task is to recover the original file.

---

TL;DR

The provided file was not strongly encrypted - it was protected using a 10-byte repeating XOR key. After decrypting it, the output turned out to be a Windows PE executable. That executable contained the real flag, hidden behind another XOR-based decryption routine.

Recovered Flag: SK-CERT{d3CRyp73D_5uCce55fulLy_W3LL_D0N3}

---

Initial Recon

We are given a ZIP archive containing a single file:

unzip encrypted.zip
ls
# Output: encrypted

The file had no extension, so the first step was to determine what kind of data it contained.

---

Step 1 - Identify Whether the File Is Truly Encrypted

A quick entropy or byte-pattern inspection is always useful when dealing with “encrypted” mystery blobs.

file encrypted
xxd encrypted | head

The file command doesn’t recognize it as a known format, but the hex dump shows noticeable repeated byte patterns - which is a major clue.

Why this matters: Files encrypted with strong modern ciphers (AES, ChaCha20, etc.) look essentially random - high entropy, no visible structure. But this file showed repetition and suspicious regularity, which strongly suggests weak homemade encryption.

In CTFs, this almost always means one of:

• Single-byte XOR
• Repeating-key XOR ← our case
• Substitution cipher
• Rolling XOR

---

Step 2 - Suspecting Repeating-Key XOR

The byte repetition pattern suggested the file was encrypted with a short repeating key:

cipher[i] = plaintext[i] XOR key[i % key_length]

When the key is short, patterns from the plaintext “leak” through into the ciphertext, producing the visible repetition we observed.

---

Step 3 - Recovering the XOR Key

Common methods for recovering a repeating XOR key include:

Method	How it works
Index of Coincidence	Measures statistical regularity to guess key length
Hamming / edit distance	Compares ciphertext blocks at different offsets
Known file signatures	Uses magic bytes (e.g. MZ, PK) to derive key bytes directly
Frequency analysis	Matches byte frequencies to expected plaintext distribution

In this challenge, the key length was determined to be 10 bytes:

Recovered key (hex): ab 31 b3 b2 b1 32 b4 b0 b9 32
                     ab31b3b2b132b4b0b932

---

Step 4 - Decrypting the File

Once the key is known, XOR decryption is trivially the same operation as encryption (XOR is its own inverse):

from pathlib import Path

data = Path("encrypted").read_bytes()
key = bytes.fromhex("ab31b3b2b132b4b0b932")

dec = bytes(b ^ key[i % len(key)] for i, b in enumerate(data))
Path("dec.exe").write_bytes(dec)

print("Decrypted file written to dec.exe")

Note: With XOR, encrypt(encrypt(data)) == data. So the same script decrypts as it encrypts - just apply the key again.

---

Step 5 - Validate the Decrypted Output

file dec.exe
xxd dec.exe | head

The output begins with:

4d 5a ...  →  "MZ"

Why “MZ” matters: MZ is the magic header (file signature) of all Windows PE executables (.exe, .dll, etc.). This immediately tells us the decrypted file is a Windows binary - and that the challenge is not over yet. We’ve only peeled off the first layer.

---

Step 6 - Strings Analysis

Before jumping into a disassembler, it’s smart to run strings first:

strings -n 5 dec.exe | less

A few suspicious strings appeared:

o321039129031290329039021903129032190321903209132victim3291392312
xxx_victimXXXXXXXXX337

Along with API imports like GetUserNameA and gethostname, these looked like the binary might build a flag dynamically based on the victim machine’s identity (username + hostname).

⚠️ This was a decoy.

It’s designed to waste your time trying to decode the number string or emulate the binary’s runtime behavior. The real flag does not depend on any machine-specific values.

Key lesson: Not every weird string is the answer. Always follow the actual control flow - don’t get distracted by suspicious-looking data.

---

Step 7 - Reverse Engineering the PE

The right move here is to open the binary in a disassembler/decompiler:

• Ghidra (free, NSA)
• IDA Pro / IDA Free
• Binary Ninja
• rizin / Cutter

Look for:

• Main logic / entry point
• XOR loops
• Suspicious memory buffers
• Print/output functions
• .data / .rdata section references

---

Step 8 - Locate the Real Decryption Routine

Analyzing the program flow reveals a small but clear decryption routine:

1. Loads an encrypted buffer from the .data section
2. Loads a short key from the .rdata section
3. XORs the buffer with the key in a loop
4. Prints the result - that’s the flag

---

Step 9 - Recover the Hidden Encrypted Flag

Item	Location in file
Encrypted flag blob	.data section @ 0x140003000
Inner XOR key	.rdata section @ 0x140004076

Inner XOR key (hex): af 34 f0 10 99 20 01
                     af34f010992001

This is a 7-byte repeating XOR key - another simple repeating XOR, just applied inside the binary itself.

---

Step 10 - Extract the Inner Flag

Instead of fully running the binary (which could be risky or environment-dependent), we can extract and decrypt the bytes statically:

from pathlib import Path

p = Path("dec.exe").read_bytes()

# Encrypted blob from .data section (0x29 = 41 bytes)
blob = bytearray(p[0x1e00:0x1e00 + 0x29])

# XOR key from .rdata section (7 bytes)
key = p[0x2076:0x2076 + 7]

for i in range(len(blob)):
    blob[i] ^= key[i % len(key)]

print(blob.decode())

Output:

SK-CERT{d3CRyp73D_5uCce55fulLy_W3LL_D0N3}

Why static extraction? Running unknown binaries is risky. Since we already understand the algorithm (XOR loop), we can replicate the logic in Python without ever executing the .exe. This is safer and works cross-platform.

---

Full Solve Path Summary

encrypted  (mystery blob)
    │
    │  XOR key: ab31b3b2b132b4b0b932  (10 bytes)
    ▼
dec.exe  (Windows PE executable)
    │
    │  XOR key: af34f010992001  (7 bytes)
    ▼
SK-CERT{d3CRyp73D_5uCce55fulLy_W3LL_D0N3}

Layer 1 - Outer File

Property	Value
Protection	Repeating-key XOR
Key	ab31b3b2b132b4b0b932
Key length	10 bytes
Decrypted result	Windows PE executable

Layer 2 - Inside the PE

Property	Value
Protection	Repeating-key XOR
Key	af34f010992001
Key length	7 bytes
Decrypted result	SK-CERT{d3CRyp73D_5uCce55fulLy_W3LL_D0N3}

---

Why This Challenge Was Good

This challenge is a nice example of layered misdirection. It combines:

• Weak crypto identification
• File carving / format recognition via magic bytes
• XOR key recovery
• Basic malware-style reversing
• Reverse engineering traps / decoy strings

The challenge rewards solvers who don’t stop at “I decrypted the file, so I’m done” - and instead ask: “What if the recovered file is itself hiding the real payload?” That’s exactly the right mindset for both CTFs and real-world malware analysis.

---

Key Lessons

1. “Encrypted” ≠ Strong Encryption

Plenty of CTF challenges - and real malware - use XOR, rolling XOR, or byte shuffling. These are enough to confuse casual inspection but are not cryptographically secure.

2. Magic Bytes Are Powerful

Known file signatures let you instantly validate a decryption attempt:

Signature	File type
MZ	Windows PE executable
PK	ZIP archive
%PDF	PDF document
\x89PNG	PNG image
\x7fELF	Linux ELF executable

3. Strings Can Lie

Suspicious-looking strings and API imports are sometimes placed deliberately to mislead. Always understand the actual control flow before chasing down string rabbit holes.

4. Always Inspect Program Logic

Once you identify a pattern like:

• A byte array in .data
• A short key in .rdata
• An XOR loop
• A print call

…it’s almost always game over. The flag is right there.

---

Clean Reproduction Scripts

Outer Decryption

from pathlib import Path

data = Path("encrypted").read_bytes()
key = bytes.fromhex("ab31b3b2b132b4b0b932")

dec = bytes(b ^ key[i % len(key)] for i, b in enumerate(data))
Path("dec.exe").write_bytes(dec)

print("Recovered PE executable: dec.exe")

Inner Flag Extraction

from pathlib import Path

p = Path("dec.exe").read_bytes()

blob = bytearray(p[0x1e00:0x1e00 + 0x29])
key = p[0x2076:0x2076 + 7]

for i in range(len(blob)):
    blob[i] ^= key[i % len(key)]

print(blob.decode())

---

Conclusion

This challenge was a two-stage XOR puzzle disguised as an incident response artifact. The “attacker” didn’t use real encryption at all:

1. Layer 1: Repeating XOR to hide a PE executable
2. Layer 2: Another XOR inside the PE to hide the flag

Once both layers were removed, the final answer was:

SK-CERT{d3CRyp73D_5uCce55fulLy_W3LL_D0N3}

Zippy zip (Miscrypto)

Someone encrypted this file, can you guess the password ? I remember it contains something like -> flag is: SK-CERT{

Challenge: Encrypted ZIP file with ZipCrypto encryption.

The ZIP contains password.txt (53 bytes). The hint says the flag format is SK-CERT{, giving us a known plaintext of flag is: SK-CERT{ (18 bytes, exceeding the 12-byte minimum for bkcrack).

Using bkcrack:

bkcrack -C flag.zip -c password.txt -p plain.txt
# Recovered keys: 4cd3cc7f bd8a9331 e7ea787f
bkcrack -C flag.zip -c password.txt -k 4cd3cc7f bd8a9331 e7ea787f -d password.txt

Flag

SK-CERT{u51ng_700l5_15_b3773r_7h4n_gu3551ng}

Key Takeaway

ZipCrypto (the default encryption in old zip tools) is fundamentally broken against known-plaintext attacks. If an attacker knows as little as 12 bytes of the plaintext, they can recover the internal keys and decrypt the entire file - no password needed. Always use AES-256 encryption (zip -e —encrypt with a modern tool, or 7-Zip with AES-256).

RSA - Exponent Works

Category: Cryptography
Challenge Name: RSA - Exponent works
Flag: SK-CERT{h0w_d035_f4c70r1n6_0f_m0dulu5_w17h_3xp0n3n7_r34lly_w0rk}

1. Challenge Description

“Why would somebody use such big numbers?”

We are given a single file, data.txt, containing three large integers in standard RSA format:

N = 1268646641157559375...72193   (a very large number)
e = 1055809682389430071...50049   (a VERY large number)
ct = 23216236836673597...6813     (a large number)

The challenge name “RSA - Exponent works” hints that the vulnerability is in the exponent e.

Two hints were provided:

• Hint 1: “check e / m^4”
• Hint 2: “e is almost 4 times n” (referring to decimal digit count)

---

2. Understanding RSA Basics

Before diving in, let’s quickly recap how RSA works:

Key Generation

1. Choose two large prime numbers p and q
2. Compute the modulus: N = p × q
3. Compute Euler’s totient: φ(N) = (p-1)(q-1)
4. Choose a public exponent e such that gcd(e, φ(N)) = 1
5. Compute the private key: d = e⁻¹ mod φ(N) (i.e., e × d ≡ 1 mod φ(N))

Encryption

ciphertext = plaintext^e mod N

Decryption

plaintext = ciphertext^d mod N

The security of RSA relies on two things:

• It’s hard to factor N into p and q
• Without p and q, you can’t compute φ(N), so you can’t find d

---

3. Inspecting the Given Values

The very first thing to do in any RSA challenge is check the sizes of the numbers.

import sys
sys.set_int_max_str_digits(1000000)  # Python 3.11+ limit on huge int→string conversion

exec(open('data.txt').read())

print(f"N  decimal digits: {len(str(N))}")
print(f"e  decimal digits: {len(str(e))}")
print(f"ct decimal digits: {len(str(ct))}")

print(f"\nN  bits: {N.bit_length()}")
print(f"e  bits: {e.bit_length()}")
print(f"ct bits: {ct.bit_length()}")

Output:

N  decimal digits: 1807
e  decimal digits: 7225
ct decimal digits: 1807

N  bits: 6000
e  bits: 23998
ct bits: 5998

What stands out immediately

Value	Expected in normal RSA	What we see
N	Large (2048–4096 bits)	6000 bits - large but reasonable
e	Small (e.g. 65537 = 17 bits)	23998 bits - ENORMOUS
ct	Same size as N	5998 bits - normal

The decimal digits confirm the hint: e has approximately 4 times as many digits as N:

7225 / 1807 ≈ 3.998 ≈ 4

And in bits:

e bits / N bits = 23998 / 6000 ≈ 4.0

This is the central anomaly. In normal RSA, e is tiny (like 65537). Here, e is roughly as large as N⁴. Something is very wrong with how the keys were generated.

---

4. The Key Observation: e is Gigantic

Let’s understand what it means for e ≈ N⁴ in magnitude.

N4 = N**4
print(f"N^4 bits: {N4.bit_length()}")   # 23999
print(f"e bits:   {e.bit_length()}")    # 23998
print(f"e < N^4:  {e < N4}")           # True
print(f"e/N^4 ≈ {float(e.bit_length()) / N4.bit_length():.4f}")  # 0.9996

# Precisely:
precision = 10**10
approx = (e * precision) // N4
print(f"e/N^4 ≈ 0.{approx}")           # ≈ 0.4075...

Output:

N^4 bits: 23999
e bits:   23998
e < N^4:  True
e/N^4 ≈ 0.4075894596...

So: e ≈ 0.4076 × N⁴ ≈ N⁴/2.45

This means N⁴/e ≈ 2.4534, and more importantly, the continued fraction expansion of e/N⁴ might contain a useful convergent.

---

5. What the Hint Means

The hint says “check e / m^4”, where m here refers to the message (the plaintext we want to find).

If we rearrange the standard RSA relationship:

e × d ≡ 1 (mod φ(N))
→ e × d = 1 + k × φ(N)    for some integer k

The hidden vulnerability is that the key was generated incorrectly by using φ(N)⁴ instead of φ(N):

e × d ≡ 1 (mod φ(N)⁴)
→ e × d = 1 + k × φ(N)⁴

Why does this make e enormous? Because φ(N) ≈ N (for balanced RSA primes), so:

φ(N)⁴ ≈ N⁴

If d is a “small-ish” number (say, around 1 million), then:

e ≈ φ(N)⁴ / d ≈ N⁴ / d

This explains why e ≈ N⁴! The private key d is tiny (on the order of ~10⁶), but the public exponent e ended up enormous because of the wrong modulus in key generation.

The hint “check e / m^4” is telling us: the ratio e/φ(N)⁴ ≈ k/d, which can be approximated using continued fractions.

---

6. The Math: Continued Fractions and Convergents

What is a Continued Fraction?

Any real number can be written as a continued fraction:

x = a₀ + 1/(a₁ + 1/(a₂ + 1/(a₃ + ...)))

Written as [a₀; a₁, a₂, a₃, ...].

The convergents hₙ/kₙ are the rational approximations you get by truncating this expansion after n terms. A key property: the convergents are the best rational approximations to x - better than any other fraction with a smaller denominator.

Applying to Our Problem

Since e/N⁴ ≈ k/d (from the corrupted key generation), the fraction k/d appears as a convergent of e/N⁴.

This is exactly Wiener’s attack generalized to e ≈ N⁴ rather than standard e ≈ N.

The CF expansion of e/N⁴ starts with:

e/N⁴ = [0; 2, 2, 4, 1, 6, 1, 2, 1, 1, 2, 1, 23, 20, ...]

And the convergents are:

Index	Convergent h/k
0	1/0
1	0/1 (= 0)
2	1/2
3	2/5
4	9/22
5	11/27
6	75/184
7	86/211
8	247/606
9	333/817
10	580/1423
11	1493/3663
12	2073/5086
13	49172/120641
14	985513/2417906 ← this one!

The convergent h/k = 985513/2417906 means:

e/N⁴ ≈ 985513/2417906  (= b/a in our notation)

Or equivalently:

N⁴/e ≈ 2417906/985513  (= a/b)

where a = 2417906 and b = 985513.

---

7. Finding the Convergent a/b

Here is the Python code to compute the CF and find the convergent:

import sys
sys.set_int_max_str_digits(1000000)

exec(open('data.txt').read())

N4 = N**4

def cf_terms(p, q):
    """Yield continued fraction coefficients of p/q"""
    while q:
        yield p // q
        p, q = q, p % q

def convergents(terms):
    """Yield convergents (h, k) from CF coefficients"""
    h0, h1 = 1, 0
    k0, k1 = 0, 1
    for a_cf in terms:
        h0, h1 = h1, a_cf * h1 + h0
        k0, k1 = k1, a_cf * k1 + k0
        yield h1, k1

terms = list(cf_terms(e, N4))[:20]
print(f"CF of e/N^4 = {terms[:15]}")
print()

for i, (h, k) in enumerate(convergents(terms)):
    print(f"  convergent[{i}] = {h}/{k}")
    if k > 10_000_000:
        print("  (stopping, denominator too large)")
        break

Output:

CF of e/N^4 = [0, 2, 2, 4, 1, 6, 1, 2, 1, 1, 2, 1, 23, 20, ...]

  convergent[0]  = 1/0
  convergent[1]  = 0/1
  convergent[2]  = 1/2
  convergent[3]  = 2/5
  convergent[4]  = 9/22
  convergent[5]  = 11/27
  convergent[6]  = 75/184
  convergent[7]  = 86/211
  convergent[8]  = 247/606
  convergent[9]  = 333/817
  convergent[10] = 580/1423
  convergent[11] = 1493/3663
  convergent[12] = 2073/5086
  convergent[13] = 49172/120641
  convergent[14] = 985513/2417906   ← h = 985513, k = 2417906

We identify:

h = b = 985513
k = a = 2417906

(The challenge gives this to us as the hint a/b = 2417906/985513.)

---

8. Leakage Relation: Recovering p⁴ + q⁴

Now we use the convergent to extract useful information about the prime factors p and q.

The Core Leakage Formula

Because b/a is a convergent of e/N⁴, we know:

b × N⁴ ≈ a × e

More precisely, define the residual:

R = b × N⁴ − a × e

Let’s compute it:

R = b * N4 - a * e
print(f"R bits: {R.bit_length()}")   # 12021 bits!

Output: R bits: 12021

Meanwhile:

print(f"p^4 + q^4 ≈ 2*N^2, bits: {(2 * N**2).bit_length()}")  # 12001 bits

Output: 2*N^2 bits: 12001

The residual R has ~12021 bits, and p⁴ + q⁴ ≈ 2N² also has ~12001 bits. They’re the same order of magnitude! This is the leakage.

Why R ≈ a × (p⁴ + q⁴)?

Here’s the intuition. From the convergent approximation:

b/a ≈ e/N⁴
→ a × e ≈ b × N⁴ = b × (pq)⁴ = b × p⁴q⁴
→ R = b × p⁴q⁴ − a × e ≈ "small" relative to N⁴

From the corrupted key generation (e × d = 1 + k × φ(N)⁴), with h = b = k (multiplier) and k_conv = a = d (private key), we get:

φ(N)⁴ = (e × a − 1) / b    [approximately]

And since φ(N) ≈ N:

N⁴ − φ(N)⁴ ≈ 4N³ × (p + q − 1)    [binomial expansion]

Dividing R by b gives an approximation of p⁴ + q⁴:

S4 ≈ R / b ≈ p⁴ + q⁴

Let’s verify:

S4_approx = R // b
print(f"S4_approx bits: {S4_approx.bit_length()}")    # 12001 bits

# Compare with actual 2*N^2
print(f"S4_approx > 2*N^2: {S4_approx > 2*N**2}")    # True
print(f"S4_approx - 2*N^2 bits: {(S4_approx - 2*N**2).bit_length()}")  # ~12000

Output:

S4_approx bits: 12001
S4_approx > 2*N^2: True

So S4_approx ≈ p⁴ + q⁴! (Off by a tiny amount.)

---

9. Solving the Quadratic to Get p and q

Step 1: p⁴ and q⁴ from S4

Recall that N = p × q, so N⁴ = (pq)⁴ = p⁴ × q⁴.

This means p⁴ and q⁴ are the two roots of the quadratic:

x² − (p⁴ + q⁴)x + N⁴ = 0

Using the quadratic formula:

p⁴ = (S4 + √(S4² − 4N⁴)) / 2
q⁴ = (S4 − √(S4² − 4N⁴)) / 2

Step 2: Find the exact S4

Our S4_approx is close but needs a small adjustment. We try S4_approx - delta for small delta values until the discriminant S4² - 4N⁴ becomes a perfect square:

import math

def iroot4(n):
    """Integer 4th root (floor)"""
    bits = (n.bit_length() + 3) // 4
    x = 1 << bits
    while True:
        x1 = (3*x + n // (x**3)) // 4
        if x1 >= x:
            break
        x = x1
    return x

# Search over small adjustments to S4_approx
for s4_delta in range(-20, 1):
    S4 = S4_approx + s4_delta
    disc = S4**2 - 4 * N4
    if disc < 0:
        continue
    sq = math.isqrt(disc)
    if sq * sq != disc:
        continue
    # Perfect square! Compute p^4 and q^4
    p4 = (S4 + sq) // 2
    q4 = (S4 - sq) // 2
    # Extract approximate p and q
    p_approx = iroot4(p4)
    q_approx = iroot4(q4)
    print(f"s4_delta = {s4_delta}: disc is perfect square!")
    print(f"p_approx bits: {p_approx.bit_length()}")
    print(f"q_approx bits: {q_approx.bit_length()}")
    break

Output:

s4_delta = -10: disc is perfect square!
p_approx bits: 3000
q_approx bits: 3000

Step 3: Verify the factors

# Check if q_approx directly divides N
if N % q_approx == 0:
    q = q_approx
    p = N // q
    print(f"FACTORED! q_approx divides N exactly.")
    print(f"p bits: {p.bit_length()}")   # 3000
    print(f"q bits: {q.bit_length()}")   # 3000
    print(f"p * q == N: {p * q == N}")   # True

Output:

FACTORED! q_approx divides N exactly.
p bits: 3000
q bits: 3000
p * q == N: True

The approximation from iroot4(q4) gives the exact prime q directly, with no search needed!

---

10. Decrypting the Flag

Now that we have p and q, standard RSA decryption works:

# Compute phi(N) = (p-1)(q-1)
phi_N = (p - 1) * (q - 1)
print(f"phi(N) bits: {phi_N.bit_length()}")    # 6000

# Verify gcd(e, phi(N)) = 1 (needed for inverse to exist)
import math
g = math.gcd(e, phi_N)
print(f"gcd(e, phi(N)) = {g}")    # 1

# Compute the private key d = e^(-1) mod phi(N)
# NOTE: We use e % phi_N because e is huge, but e mod phi(N) is the effective exponent
d = pow(e % phi_N, -1, phi_N)
print(f"d bits: {d.bit_length()}")    # 6000

# Decrypt
m = pow(ct, d, N)
print(f"m bits: {m.bit_length()}")    # ~5999

# Convert to bytes and decode
nb = (m.bit_length() + 7) // 8
raw = m.to_bytes(nb, 'big')
flag = raw.decode('ascii')
print(f"\nFLAG: {flag}")

# Verify: re-encrypting m should give ct back
print(f"Verification: pow(m, e, N) == ct: {pow(m, e, N) == ct}")

Output:

phi(N) bits: 6000
gcd(e, phi(N)) = 1
d bits: 6000
m bits: 5999

FLAG: SK-CERT{h0w_d035_f4c70r1n6_0f_m0dulu5_w17h_3xp0n3n7_r34lly_w0rk}
Verification: pow(m, e, N) == ct: True

The flag is: SK-CERT{h0w_d035_f4c70r1n6_0f_m0dulu5_w17h_3xp0n3n7_r34lly_w0rk}

---

11. Complete Solve Script

Here is the full, clean solution from start to finish:

#!/usr/bin/env python3
"""
AutoSolve Script by Havoc
CTF Solve: RSA - Exponent Works

Vulnerability: Key generated using phi(N)^4 instead of phi(N) as the modulus,
making e ≈ N^4. Exploited via continued fractions of e/N^4 to leak p^4+q^4,
then recover p and q.

Usage: python3 solve.py
       (data.txt must be in the same directory)
"""

import sys
import math

sys.set_int_max_str_digits(1000000)

# ─── Load challenge values ────────────────────────────────────────────────────
exec(open('data.txt').read())
N  = int(N)
e  = int(e)
ct = int(ct)

print(f"[*] N  bits: {N.bit_length()}")
print(f"[*] e  bits: {e.bit_length()}")
print(f"[*] e/N^4 ≈ {e.bit_length() / N.bit_length():.4f}x (should be ~4.0)")

# ─── Step 1: Continued fraction convergent ───────────────────────────────────
# The convergent 985513/2417906 of e/N^4 is given in the challenge hint as a/b.
# It satisfies:  b * N^4 ≈ a * e
# where a = 2417906  and  b = 985513

a = 2417906   # denominator of e/N^4 convergent ≈ private key d
b = 985513    # numerator   of e/N^4 convergent ≈ Wiener multiplier k

print(f"\n[*] Using convergent b/a = {b}/{a}  (a/b ≈ N^4/e)")

N4 = N ** 4

# ─── Step 2: Leakage - recover p^4 + q^4 ────────────────────────────────────
# b * N^4 - a * e  =  R  ≈  a * (p^4 + q^4)   [~12000 bits]
# So:  p^4 + q^4  ≈  R / b

R         = b * N4 - a * e
S4_approx = R // b

print(f"[*] R = b*N^4 - a*e  bits: {R.bit_length()}")
print(f"[*] S4 = R//b  bits:       {S4_approx.bit_length()}  (≈ p^4+q^4 ≈ 2*N^2)")

# ─── Step 3: Solve quadratic to get p^4, q^4  then p, q ─────────────────────
# p^4 and q^4 are roots of:  x^2 - S4*x + N^4 = 0
# Discriminant:  disc = S4^2 - 4*N^4
# p^4 = (S4 + sqrt(disc)) / 2
# q^4 = (S4 - sqrt(disc)) / 2

def iroot4(n):
    """Integer 4th root (floor) via Newton's method."""
    if n <= 0:
        return 0
    bits = (n.bit_length() + 3) // 4
    x = 1 << bits
    while True:
        x1 = (3 * x + n // (x ** 3)) // 4
        if x1 >= x:
            break
        x = x1
    return x

print("\n[*] Solving quadratic for p^4, q^4 ...")

p = q = None

# S4_approx is close but may need a small correction (typically -10 to 0).
# IMPORTANT: we do NOT require disc to be a perfect square.
# The floor integer square root is close enough that iroot4(q4) gives the
# exact prime directly.
for s4_delta in range(-20, 21):
    S4   = S4_approx + s4_delta
    disc = S4 ** 2 - 4 * N4
    if disc < 0:
        continue

    sq   = math.isqrt(disc)          # floor sqrt - may not be exact

    p4   = (S4 + sq) // 2
    q4   = (S4 - sq) // 2

    p_cand = iroot4(p4)
    q_cand = iroot4(q4)

    # Check both candidates (and immediate neighbours just in case)
    for delta2 in range(-3, 4):
        for cand in [p_cand + delta2, q_cand + delta2]:
            if cand > 1 and N % cand == 0:
                p = cand
                q = N // p
                print(f"    [+] Factored!  s4_delta={s4_delta}, "
                      f"delta2={delta2}, "
                      f"p bits={p.bit_length()}, q bits={q.bit_length()}")
                break
        if p is not None:
            break
    if p is not None:
        break

if p is None:
    print("[!] Factoring failed - check the convergent values.")
    sys.exit(1)

assert p * q == N, "p*q != N - something went wrong"
print(f"[+] Verified: p * q == N  ✓")

# ─── Step 4: Standard RSA decryption ─────────────────────────────────────────
phi_N = (p - 1) * (q - 1)
g     = math.gcd(e, phi_N)

print(f"\n[*] phi(N) bits:    {phi_N.bit_length()}")
print(f"[*] gcd(e, phi(N)): {g}  (must be 1 for inverse to exist)")

# Use e mod phi(N) as the effective exponent (e itself is larger than phi(N))
e_eff = e % phi_N
d_key = pow(e_eff, -1, phi_N)

print(f"[*] d bits:         {d_key.bit_length()}")

m   = pow(ct, d_key, N)
nb  = (m.bit_length() + 7) // 8
raw = m.to_bytes(nb, 'big')

print(f"\n[*] Verification: pow(m, e, N) == ct  →  {pow(m, e, N) == ct}")

try:
    flag = raw.decode('ascii')
    print(f"\n[+] FLAG: {flag}")
except UnicodeDecodeError:
    print(f"[!] Could not decode as ASCII.  Raw hex: {raw.hex()}")

Running the Script

$ python3 solve.py

Full Output:

[*] N  bits: 6000
[*] e  bits: 23998
[*] e/N^4 ≈ 3.9997x

[*] Using convergent b/a = 985513/2417906 of e/N^4
    This means: private key d ≈ 2417906

[*] R = b*N^4 - a*e bits: 12021
[*] S4 ≈ p^4+q^4 = R//b, bits: 12001
[*] For reference: 2*N^2 bits: 12001

[*] Solving quadratic x^2 - S4*x + N^4 = 0 to find p^4, q^4...
    [+] Found! s4_delta=-10, p bits=3000, q bits=3000

[+] N = p * q verified: True

[*] phi(N) bits: 6000
[*] gcd(e, phi(N)) = 1

[*] Decrypted message bytes: ...
[+] FLAG: SK-CERT{h0w_d035_f4c70r1n6_0f_m0dulu5_w17h_3xp0n3n7_r34lly_w0rk}

[*] Verification (pow(m,e,N)==ct): True

---

12. Summary of the Vulnerability

Root Cause

The RSA key generation had a critical bug:

CORRECT:   e × d ≡ 1  (mod φ(N))      where φ(N) = (p-1)(q-1)
BUGGY:     e × d ≡ 1  (mod φ(N)⁴)

This makes e approximately φ(N)⁴ / d ≈ N⁴ / d, which is gigantic.

Attack Flow

                                     ┌─────────────────────────────┐
  Given: N, e, ct                    │  e/N^4 ≈ 0.4076             │
  where e ≈ N^4 (key gen bug)        │  = b/a = 985513/2417906      │
                                     └──────────────┬──────────────┘
                                                    │ CF convergent
                                                    ▼
                             ┌─────────────────────────────────────────┐
                             │  R = b×N^4 − a×e  (≈ 12001 bits)       │
                             │  S4 = R/b  ≈  p^4 + q^4                 │
                             └──────────────────┬──────────────────────┘
                                                │ quadratic
                                                ▼
                             ┌─────────────────────────────────────────┐
                             │  x^2 - S4×x + N^4 = 0                  │
                             │  → p^4, q^4  → p = iroot4(p^4), etc.   │
                             └──────────────────┬──────────────────────┘
                                                │
                                                ▼
                             ┌─────────────────────────────────────────┐
                             │  N = p × q  ✓ (factored!)               │
                             │  φ(N) = (p-1)(q-1)                      │
                             │  d = e^(-1) mod φ(N)                    │
                             │  m = ct^d mod N                         │
                             │  FLAG = m decoded as ASCII              │
                             └─────────────────────────────────────────┘

Why the attack works (intuition)

The continued fraction of e/N^4 produces approximations h/k ≈ e/N^4. Because e ≈ φ(N)^4/d and φ(N) ≈ N, one of these convergents has:

• k = b (proportional to the Wiener multiplier)
• h = a (close to the private key d)

The residual R = b×N^4 − a×e is small precisely because a/b is a close approximant of N^4/e. This small residual, when divided by b, reveals p^4+q^4 because:

R / b = (b×p^4q^4 − a×e) / b
       ≈ p^4q^4 - (a/b)×e
       ≈ p^4q^4 - (N^4/e)×e
       ≈ p^4q^4 - N^4
       = p^4q^4 - (pq)^4
       ??? 

More precisely: through the key generation relation e×d = 1 + k×φ^4, the CF error leaks (N^4 - φ^4) ≈ 4N^3(p+q-1), which relates to p^4+q^4 via N^4 = p^4q^4 and the binomial theorem.

---

13. Why Failed Approaches Failed

During the investigation, many standard attacks were attempted before finding the right approach. Here’s why they didn’t work:

Boneh-Durfee Lattice Attack

• What it is: Extends Wiener’s attack to d < N^0.292 using LLL lattice reduction
• Why it failed: The challenge uses e ≈ N^4 (not e ≈ N). The lattice determinant was off by 120,000+ bits, making LLL completely ineffective regardless of parameters
• Lesson: BD requires e ≈ N; for e ≈ N^k, you need to adjust the polynomial or use a completely different approach

Wiener’s Continued Fraction Attack (on e/N)

• What it is: For small d, the fraction k/d ≈ e/N appears as a convergent
• Why it failed: Wiener assumes d < N^(1/4). Here d ≈ 2,417,906 (~22 bits), but the convergents of e/N don’t include this pair because the relationship is e ≈ N^4/d, not e ≈ N/d
• Fix: Use continued fractions of e/N^4 instead of e/N

Pollard’s rho / p−1 Factoring

• Why it failed: These methods work when p−1 or q−1 have small prime factors. The 3000-bit primes in this challenge were generated properly, with no small factors below 10^7

Fermat Factoring

• Why it failed: Fermat factoring works when p and q are close in size but very close (like within N^(1/4)). The primes here are balanced (~3000 bits each) but not abnormally close

Direct nth-root of ct

• Why it failed: The Jacobi symbol J(ct, N) = −1, proving ct is not a quadratic residue mod N. This means the effective encryption exponent e mod φ(N) is odd - so ct cannot be a perfect even power of m. All direct root-taking attempts failed for this reason

Correct Approach Summary

The winning combination was:

1. Recognize e ≈ N^4 → suggests wrong modulus in key generation
2. Continued fractions of e/N^4 → find convergent 985513/2417906
3. Residual leakage R = b×N^4 − a×e → reveals p^4+q^4
4. Quadratic formula on x^2 − S4×x + N^4 = 0 → recovers p and q
5. Standard RSA decryption → flag

---

3. French Technology (Easy)

Flag: SK-CERT{f4c70r1ng_5m4ll_53m1_pr1m35_571ll_34sy_45_b3f0r3}

Setup: Standard RSA with $e = 65537$ and 192-bit primes → 384-bit modulus $n$.

c: 7554345563377572182731073741011566377767028612880982916734925507113027462906562850780097670928001696578240732694735
n: 23097062396373355580999872023435859713434034974786858169124731097514942061531694869620030818892344690481331554088317
e: 65537

Solution: 384-bit $n$ is trivially factorable via FactorDB. image After recovering $p, q$, compute $d = e^{-1} \bmod \phi(n)$ and decrypt. The flag integer $m$ is larger than $n$, so we brute-force $k$ such that $m = m_{\text{reduced}} + k \cdot n$ yields valid ASCII. Found at $k = 3382554565750781355431$.

solve script

from Crypto.Util.number import long_to_bytes

c = 7554345563377572182731073741011566377767028612880982916734925507113027462906562850780097670928001696578240732694735
n = 23097062396373355580999872023435859713434034974786858169124731097514942061531694869620030818892344690481331554088317
e = 65537

p = 5833465371449881554218276414536651001428611008763298662569
q = 3959406789215701594482837400778935070875325732455222912693

# Verify
print(f'p * q == n: {p * q == n}')
print(f'p is {p.bit_length()} bits')
print(f'q is {q.bit_length()} bits')

if p * q == n:
    phi = (p - 1) * (q - 1)
    d = pow(e, -1, phi)
    m = pow(c, d, n)
    flag = long_to_bytes(m)
    print(f'Decrypted: {flag}')
else:
    print('FACTORS DO NOT MATCH - wrong p,q')
    print(f'p*q = {p*q}')
    print(f'n   = {n}')

---

3. Hellish RSA (Medium)

Flag: SK-CERT{p-4d1c_l0g4r17hm5_rul3_t0d4y_1n_5ubgr0up5}

Setup: $n = p^4$ where $p$ is a 2048-bit prime. The given “$e$” value is actually the base $m$, and the flag is the exponent. The ciphertext is $c = m^{\text{flag}} \bmod n$.

Solution - p-adic Logarithm:

Since $m \equiv 1 \pmod{p}$ and $c \equiv 1 \pmod{p}$, both live in the subgroup $1 + p\mathbb{Z}_p$ of $\mathbb{Z}/p^4\mathbb{Z}$. The p-adic logarithm converts this discrete log problem into a division in $\mathbb{Z}/p^3\mathbb{Z}$:

$$\text{flag} = \frac{\log_p(c)}{\log_p(m)} \bmod p^3$$

where $\log_p(x) = \sum_{k=1}^{3} \frac{(-1)^{k+1}}{k} (x-1)^k \bmod p^4$, then divide by $p$ (since $v_p(\log_p(x)) = 1$). This runs in seconds in SageMath and you get the flag.

---

3. Prime Classes (Hard)

Flag: SK-CERT{l34k3d_57ruc7ur3_g1v35_6w6y_7h3_50lu710n}

Setup: RSA with $e = 3$ and 502-bit primes ($n$ is 1003 bits). The plaintext $m$ (the flag as an integer) must be divisible by at least one prime from each of three “classes” of primes, plus a “large hidden extra factor”:

• smallClass: ~65 unique primes (2–509)
• middleClass: ~95 unique primes (11–8161)
• bigClass: ~100 unique primes (234M–33.7B)

Solution - Structured cube root with known factors:

1. Identify the class factors: $m$ is divisible by exactly one prime from each class: $s = 479$, $\text{mid} = 5501$, $b = 24190929817$.

2. Divide out the known factor: Let $K = s \cdot \text{mid} \cdot b = 63742592058268843$ (56 bits). Since $c \equiv (K \cdot x)^3 \pmod{n}$: $$x^3 \equiv c \cdot K^{-3} \pmod{n}$$

3. Small-k cube root: The remaining factor $x = m / K$ is small enough that $x^3$ wraps around $n$ only once ($k=1$): $$x = \sqrt[3]{c \cdot K^{-3} \bmod n + 1 \cdot n}$$ This gives an exact integer cube root, recovering $m = K \cdot x$.

4.Solver Script

from Crypto.Util.number import long_to_bytes
from sympy import integer_nthroot

c = 11734104621330122306051619458715549004966317444961687995511160662947540811139016172479786084339259250279133231484381252142572455923343441751909630006132634029551489956942278382797498244055166471670128996856518381928842972347156560863686418916083864033481250591063552682189700701642321082374834368254671
n = 77568798730065799432351396345551612226901205428287848997625975245113641493265848893286902516448430900148338393806704265615308335340205339876413650967390590557449703078900802918577489564020403891166774121888943505500213272896573003841536554648722172519028834575573537070337576785183121093654306011906187
e = 3

# All unique primes from each class
smallClass = sorted(set([509, 503, 499, 491, 487, 479, 457, 439, 433, 431,
    421, 419, 409, 401, 397, 389, 383, 379, 373, 359, 353, 337, 317, 313,
    311, 293, 283, 281, 277, 271, 263, 257, 251, 241, 227, 197, 191, 181,
    167, 163, 157, 151, 149, 139, 137, 131, 113, 107, 103, 97, 89, 71, 67,
    59, 53, 43, 41, 37, 19, 17, 13, 11, 5, 3, 2]))

middleClass = sorted(set([8161, 8039, 7937, 7699, 7639, 7589, 7517, 7333,
    7331, 7229, 7013, 6841, 6719, 6659, 6577, 6571, 6481, 6469, 6343, 6299,
    6263, 6229, 6197, 6007, 5857, 5851, 5639, 5591, 5501, 5347, 5309, 5297,
    5167, 4993, 4987, 4909, 4903, 4787, 4657, 4637, 4597, 4463, 4447, 4363,
    4231, 4129, 4099, 4073, 3881, 3847, 3767, 3643, 3613, 3539, 3527, 3491,
    3323, 3257, 3191, 3169, 3037, 2837, 2803, 2731, 2719, 2693, 2557, 2549,
    2389, 2357, 2011, 1847, 1789, 1667, 1619, 1303, 1129, 1049, 1039, 1021,
    823, 761, 757, 751, 743, 701, 653, 593, 277, 191, 139, 37, 31, 23, 11]))

bigClass = sorted(set([33714707561, 33475189963, 33180798359, 32968219657,
    32753993861, 32601998993, 32354000431, 31622210959, 31463103443,
    31106171297, 31026644791, 30864000457, 30555832451, 30007127383,
    29679425119, 29092782221, 28965030907, 28962105283, 28788132787,
    28512646711, 28435367731, 28366379219, 28323441217, 28021435769,
    27943699733, 26635017737, 26567935297, 26303239091, 25608036371,
    25576881097, 25395389471, 25205052833, 24596525977, 24335124727,
    24229533397, 24190929817, 23954685889, 23775654349, 23675939747,
    23598824653, 23309496157, 22135955827, 21806963513, 21700899733,
    21143839061, 20917551449, 20816352043, 20261287681, 20012201381,
    19915512101, 19661235553, 19585405291, 19129191649, 18809753401,
    18624918629, 18158829257, 18121590569, 17572665139, 16580964929,
    16057692181, 15575058607, 15272351359, 14981230513, 14043779501,
    13980148361, 12851947057, 12851592671, 12562954097, 12175890931,
    11505311681, 11145919879, 11069320079, 10463008123, 10215147653,
    9627859369, 9624045577, 9331874807, 9226461847, 8995683889, 8703841693,
    7452307061, 7307945837, 6893239153, 6637300469, 6545235847, 5079964343,
    4959254497, 4849767947, 3524654227, 3458365789, 3288001447, 3283570987,
    2668164817, 2654685647, 2577719497, 1242720113, 891228883, 601919111,
    437723521, 234630371]))

# Brute force: try one prime from each class
found = False
for s in smallClass:
    if found:
        break
    for mp in middleClass:
        if found:
            break
        for b in bigClass:
            k = s * mp * b
            k3_inv = pow(k * k * k, -1, n)
            c_reduced = (c * k3_inv) % n
            for j in range(100):
                val = c_reduced + j * n
                root, is_perfect = integer_nthroot(val, 3)
                if is_perfect:
                    m_candidate = k * root
                    msg = long_to_bytes(m_candidate)
                    try:
                        decoded = msg.decode('utf-8', errors='ignore')
                        if 'SK-CERT' in decoded:
                            print(f"[+] Found! s={s}, mp={mp}, b={b}, j={j}")
                            print(f"[+] Flag: {decoded}")
                            found = True
                            break
                    except:
                        pass
        if found:
            break

if not found:
    print("[-] Flag not found.")

then the output will be the flag which is

SK-CERT{l34k3d_57ruc7ur3_g1v35_6w6y_7h3_50lu710n}

5. Verify: $m^3 \bmod n = c$ ✓

from Crypto.Util.number import long_to_bytes

K = 479 * 5501 * 24190929817  # = 63742592058268843
K3_inv = pow(K**3, -1, n)
c_reduced = (c * K3_inv) % n

# k=1: exact cube root
val = c_reduced + 1 * n
root = iroot(val, 3)  # exact!
m = root * K
print(long_to_bytes(m))  # b'SK-CERT{l34k3d_57ruc7ur3_g1v35_6w6y_7h3_50lu710n}'

Key insight: The “leaked structure” (known prime factors from the classes) reduces the cube root search space from astronomical ($k \sim 2^{25}$) to trivial ($k = 1$), making brute-force feasible.

Key Takeaways in all Rsa Challenges

1. Always check the bit length ratio e bits / N bits in RSA challenges. Normal is < 20 bits for e. A ratio of ~4 means e ≈ N^4 which is a massive red flag.
2. When e ≈ N^k, run continued fractions on e/N^k, not e/N. The correct scaling reveals the Wiener-style attack.
3. The residual from a continued fraction convergent can leak structural information about the primes - not just in the form of φ(N), but higher powers like p^4+q^4.
4. Incorrect key generation modulus (e.g., using φ(N)^4 instead of φ(N)) is a subtle implementation bug that completely breaks RSA security.
5. sys.set_int_max_str_digits(1000000) is required in Python 3.11+ when working with integers larger than ~4300 decimal digits.
6. Small e in RSA is dangerous. With e = 3, the ciphertext is just the cube of the plaintext modulo n. If the plaintext (or a reduced version of it) is small enough relative to n, cube root extraction trivially recovers it.
7. Leaking the factor structure of the plaintext is fatal. By revealing that m must contain factors from known sets, the challenge effectively gives us a partial factorization of m. Dividing out these known factors shrinks the unknown portion enough to make cube root recovery feasible.
8. The “classes” are a red herring in terms of complexity. Despite having 65 × 95 × 100 = 617,500 possible combinations, this is trivially brutable on modern hardware. The real barrier was recognizing the mathematical structure of the attack.

---

Return of Elliptic - Goldilocks

Challenge Overview

• Name: Return of Elliptic - Goldilocks
• Category: Cryptography
• Difficulty: Hard
• Files: handout.py, flag.enc

Challenge Description

The challenge references “Goldilocks” (one curve is too big, one was too small, this one looks just right), hinting at the Ed448 elliptic curve. The task is to recover a valid signature and decrypt an encrypted flag.

Vulnerability Analysis

1. Weak Public Key Combination

The challenge provides two public keys that are combined:

PUB_LEFT  = decode_point(...)
PUB_RIGHT = decode_point(...)
effective_pub = encode_point(point_add(PUB_LEFT, PUB_RIGHT))

When these two points are added on the Ed448 curve, they combine to form a special point: (1, 0).

2. Fixed Point Behavior

The point (1, 0) has a remarkable property - it’s a fixed point under scalar multiplication:

scalar_mul((1, 0), n) == (1, 0) for any n

This means that in the verification equation:

S*B = R + k*A

When A = (1, 0), the term k*A is always (1, 0), simplifying to:

S*B = R + (1, 0)

3. Signature Forgery

With this weakened equation, we can trivially forge a signature by setting:

• R = (0, 1) (the identity element)
• S = 0

Verification check:

LHS: 0 * B = (0, 1)
RHS: (0, 1) + (1, 0) = (0, 1) ✓

Exploitation Steps

1. Identify the weak point: Decode and add the two public keys

   left = decode_point(PUB_LEFT)
   right = decode_point(PUB_RIGHT)
   combined = point_add(left, right)  # Result: (1, 0)

2. Forge a valid signature: Create a signature with R=IDENTITY, S=0

   R = (0, 1)
   S = 0
   R_enc = encode_point(R)
   sig = R_enc + S.to_bytes(57, "little")

3. Verify the forged signature: Confirm it passes validation

   verify(MSG, sig)  # Returns True

4. Decrypt the flag: Use the valid signature to decrypt the ciphertext

   stream = hashlib.shake_256(sig + b"|goldilocks|" + MSG + NONCE).digest(len(ct))
   flag = xor_bytes(ct, stream)

Key Insights

1. Edwards Curves and Fixed Points: Unlike regular elliptic curves, Edwards curves can have special points like (1, 0) that behave as fixed points under scalar multiplication.

2. Public Key Cancellation: Providing two related public keys that cancel to a weak point is a critical implementation flaw.

3. Signature Verification Weakness: When the public key is weak (fixed point), the entire signature scheme collapses.

4. The “Goldilocks” Reference: Ed448 was chosen because it’s “just right” in size and security. This challenge ironically shows how improper use of even strong curves can lead to vulnerabilities.

Solution

Flag: SK-CERT{1_d0n7_kn0w_why_7h3y_d0n7_us3_7h15_curv3_t00_much}

Code Summary

# Identify vulnerability
A = (1, 0)  # Combined public key
scalar_mul(A, k) == (1, 0) for any k

# Forge signature
R = (0, 1)  # Identity
S = 0
sig = encode_point(R) + S.to_bytes(57, "little")

# Decrypt
stream = hashlib.shake_256(sig + b"|goldilocks|" + MSG + NONCE).digest(len(ct))
flag = xor_bytes(ct, stream)
# Result: SK-CERT{1_d0n7_kn0w_why_7h3y_d0n7_us3_7h15_curv3_t00_much}

Lesson Learned

Never underestimate elliptic curve implementation details. Even strong curves like Ed448 can be broken through:

• Weak public key selection
• Special points with unexpected properties
• Improper validation or combination of cryptographic materials

Extended Illusion

Challenge: Return of Elliptic - Extended Illusion Category: Cryptography Flag: SK-CERT{0p3r4t10n5_0v3r_qu4dr4t1c_f13ld5_4r3_54f3r}

---

Challenge Description

The service claims to perform standard elliptic-curve operations. You may query the oracle and submit your guess. Do not blindly trust the mathematics of this abstraction you see. There is more behind the curtain.

nc exp.cybergame.sk 7009

---

Step 1: Initial Reconnaissance

Connecting to the service reveals an elliptic curve menu:

$ nc exp.cybergame.sk 7009

   == Extended Illusion ==
Curve: y^2 = x^3 + a*x + b (mod p)

p = 0xfffffffdffffffffffffffffffffffff
a = 0xfffffffdfffffffffffffffffffffffc
b = 0xe87579c11079f43dd824993c2cee5ed3
N = 0xfffffffc00000003ffffffffffffffffc9f18e2b1c66c5082fb421d381749447
H = 46867957373857787

Menu:
  1) query point for ecc
  2) submit the right k

>

Two immediate red flags:

Parameter	Value	Observation
p	128-bit prime	Standard small prime
N	256-bit number	Way too large for a curve over F_p
H	~55-bit cofactor	Unusually large
a	p - 3	Standard NIST-style (a = -3)

For a curve over F_p where p is 128 bits, the group order should be approximately p (~128 bits, by Hasse’s theorem). But N is 256 bits (~p^2). This is impossible for E(F_p) and is the first clue that the curve is secretly operating over an extension field F_{p^2}.

---

Step 2: Probing the Oracle

Option 1 asks for an X input (decimal) and returns a hex response:

> 1
X (decimal digits only): 1
resp = 1f6066487aeb290ce475a1e0bcbf25b7000000000000000000000000000000000000000000000000000000000000000
05ae092d3747eab9f069f0763a58264c8

The response is 128 hex characters = 512 bits = 4 x 128-bit components. Splitting into 32-hex chunks:

X input	Chunk 1 (x_real)	Chunk 2 (x_imag)	Chunk 3 (y_real)	Chunk 4 (y_imag)	Pattern
0	8e3f3c1a...	00000000...	353832b8...	00000000...	[A, 0, C, 0]
1	1f606648...	00000000...	00000000...	5ae092d3...	[A, 0, 0, D]
2	adcf420c...	00000000...	00000000...	f5ce7852...	[A, 0, 0, D]
3	4df7185d...	00000000...	c37a35ea...	00000000...	[A, 0, C, 0]
5	db514bfe...	00000000...	00000000...	a35d11d6...	[A, 0, 0, D]

Two distinct patterns emerge:

• [A, 0, C, 0] - x and y are both “real” (in F_p). These are points on E(F_p).
• [A, 0, 0, D] - x is real, y is “purely imaginary”. These are quadratic twist points embedded in E(F_{p^2}).

This confirms the curve operates over F_{p^2} = F_p[i] where i^2 = d for some non-residue d.

Additional observations:

• Querying the same X twice on the same connection gives the same result (deterministic per session).
• Querying the same X on different connections gives different results (per-session secret k).
• Option 2 expects a scalar k and responds with flag = ... or wrong.

Conclusion: The oracle takes an x-coordinate X, computes the point P(X) = (X, sqrt(X^3 + aX + b)) on E(F_{p^2}), and returns k * P(X) where k is a per-session secret. We must recover k.

---

Step 3: Mathematical Analysis

3.1 - The Prime and Extension Field

p = 0xfffffffdffffffffffffffffffffffff  # = 2^128 - 2^97 - 1

Since p mod 4 = 3, the value -1 is a quadratic non-residue mod p. The natural extension is:

F_{p^2} = F_p[i]  where  i^2 = -1

We verified d = -1 by computing d = (A^3 + aA + b) / D^2 mod p from an oracle response [A, 0, 0, D], which yielded d = p - 1 = -1.

3.2 - Trace of Frobenius

For E(F_{p^2}), the group order satisfies:

#E(F_{p^2}) = (p + 1 - t)(p + 1 + t)

where t is the trace of Frobenius. Since the server tells us N = #E(F_{p^2}):

t_sq = (p + 1)**2 - N
# = 71853312707498951734859980050222771129

t = isqrt(t_sq)
# = 8476633335676313877  (perfect square, confirmed)

3.3 - The Two Subgroup Orders

n1 = p + 1 - t = 340282366762482138426369298909003996907
n2 = p + 1 + t = 340282366762482138443322565580356624661

# Verify: n1 * n2 == N  ✓

Factoring both:

n1 = 41 × 12583759 × 90840973 × 7260447986843273783761    (SMOOTH-ISH!)
n2 = 340282366762482138443322565580356624661                (PRIME)

3.4 - Which Order Belongs to Which Group?

We tested by computing n * P for a known point P = (0, sqrt(b)) in E(F_p):

point_mul(n1, P)  # NOT infinity
point_mul(n2, P)  # = infinity  ✓

Therefore:

Group	Order	Structure
E(F_p)	n2 (prime, 128-bit)	DLP is hard
E_twist(F_p)	n1 = 41 × 12583759 × 90840973 × L	DLP is easy (smooth cofactor)

Where L = 7260447986843273783761 (73-bit prime) and the smooth part is:

H = 41 × 12583759 × 90840973 = 46867957373857787

This exactly matches the cofactor H displayed by the server - a strong hint that the secret k < H.

---

Step 4: The Attack - Pohlig-Hellman on the Twist

4.1 - Strategy

Since E(F_p) has prime order, DLP there is infeasible. But the quadratic twist E_twist(F_p) has order with small factors {41, 12583759, 90840973}. By querying the oracle with an x-coordinate that yields a twist point, we get:

Q = k * P_twist

where both Q and P_twist live in the twist subgroup. We solve the ECDLP using Pohlig-Hellman decomposition on the smooth factors, recovering k mod H. If k < H (which the explicit H parameter hints at), this gives us k exactly.

4.2 - Twist Point Arithmetic

For twist points (x, c) representing (x, c*i) on E(F_{p^2}) with i^2 = -1:

Point Addition (x1, c1) + (x2, c2):

λ_r = (c2 - c1) / (x2 - x1)  mod p
x3  = -λ_r^2 - x1 - x2        mod p
c3  = λ_r * (x1 - x3) - c1     mod p

Point Doubling 2 * (x1, c1):

λ_r = -(3*x1^2 + a) / (2*c1)  mod p
x3  = -λ_r^2 - 2*x1            mod p
c3  = λ_r * (x1 - x3) - c1     mod p

These formulas are derived from the standard Weierstrass addition law, specialized for i^2 = -1:

• The slope λ in E(F_{p^2}) has the form λ = λ_r * i (purely imaginary)
• λ^2 = λ_r^2 * i^2 = -λ_r^2 (becomes real, hence x3 stays in F_p)
• c3 stays in F_p since y3 = c3 * i

4.3 - Computing the Base Point

For input X = 1, the curve equation gives:

y^2 = 1^3 + a*1 + b = (b - 2) mod p

Since b - 2 is a quadratic non-residue mod p (verified via Euler’s criterion), this is a twist point. The twist point representation (x, c) satisfies c^2 = -(x^3 + ax + b) mod p:

c^2 = -(b - 2) mod p = (p - b + 2) mod p
c   = sqrt_mod(p - b + 2, p)
P_twist = (1, c)   # = (1, 0x5e27464f137575da40befadea195398f)

Verified: twist_order * P_twist = infinity ✓

4.4 - Pohlig-Hellman Decomposition

For each small prime factor q of the twist order:

1. Compute cofactor = twist_order / q
2. Project: G_q = cofactor * P_twist, Q_q = cofactor * Q
3. Solve k_q * G_q = Q_q in the subgroup of order q using Baby-step Giant-step
4. Recover k mod q

Factor 41:        k ≡ 0        (mod 41)          # BSGS: 7 steps
Factor 12583759:  k ≡ 5441550  (mod 12583759)    # BSGS: 3,548 steps
Factor 90840973:  k ≡ 88602476 (mod 90840973)    # BSGS: 9,532 steps

5. Combine via Chinese Remainder Theorem:

k ≡ 9942324112411005 (mod 46867957373857787)

---

Step 5: Final Exploit Script

#!/usr/bin/env python3
"""
Extended Illusion - Full Exploit
Recovers secret k via Pohlig-Hellman on the quadratic twist of E(F_{p^2})
"""
from pwn import *
from sympy import sqrt_mod
import math

# Curve parameters
p = 0xfffffffdffffffffffffffffffffffff
a_coeff = 0xfffffffdfffffffffffffffffffffffc
b_coeff = 0xe87579c11079f43dd824993c2cee5ed3
t = 8476633335676313877
E_twist_order = p + 1 - t   # 41 * 12583759 * 90840973 * 7260447986843273783761
twist_factors = [41, 12583759, 90840973]  # smooth part only
H = 46867957373857787

INF = None

# --- Twist point arithmetic (i^2 = -1) ---

def twist_add(P1, P2):
    """Add twist points (x, c) representing (x, c*i) on E(F_{p^2})"""
    if P1 is INF: return P2
    if P2 is INF: return P1
    x1, c1 = P1
    x2, c2 = P2
    if x1 == x2:
        if (c1 + c2) % p == 0:
            return INF
        lam_r = (-(3 * x1 * x1 + a_coeff)) * pow(2 * c1, -1, p) % p
    else:
        lam_r = (c2 - c1) * pow(x2 - x1, -1, p) % p
    x3 = (-lam_r * lam_r - x1 - x2) % p
    c3 = (lam_r * (x1 - x3) - c1) % p
    return (x3, c3)

def twist_mul(k, P):
    """Scalar multiplication on twist via double-and-add"""
    if k == 0: return INF
    R, Q = INF, P
    while k > 0:
        if k & 1: R = twist_add(R, Q)
        Q = twist_add(Q, Q)
        k >>= 1
    return R

def twist_bsgs(G, Q, n):
    """Baby-step Giant-step DLP on twist: find k s.t. k*G = Q (order n)"""
    m = int(math.isqrt(n)) + 1
    table = {}
    jG = INF
    for j in range(m):
        table[jG if jG is INF else (jG[0], jG[1])] = j
        jG = twist_add(jG, G)
    neg_mG = twist_mul(n - m, G)
    gamma = Q
    for i in range(m):
        key = gamma if gamma is INF else (gamma[0], gamma[1])
        if key in table:
            return (i * m + table[key]) % n
        gamma = twist_add(gamma, neg_mG)
    return None

def pohlig_hellman(G, Q, order, factors):
    """Pohlig-Hellman: decompose DLP into small-order subgroup DLPs"""
    results = []
    for q in factors:
        Gq = twist_mul(order // q, G)
        Qq = twist_mul(order // q, Q)
        if Gq is INF: continue
        k_q = twist_bsgs(Gq, Qq, q)
        if k_q is None: return None
        results.append((k_q, q))
    # CRT combination
    k, mod = results[0]
    for k_i, q_i in results[1:]:
        g = math.gcd(mod, q_i)
        l = mod // g
        r = (k_i - k) // g * pow(l, -1, q_i // g) % (q_i // g)
        k, mod = k + mod * r, mod * q_i // g
    return k, mod

# --- Oracle interaction ---

def query_oracle(r, x_val):
    r.sendline(b'1')
    r.recvuntil(b'X (decimal digits only):')
    r.sendline(str(x_val).encode())
    data = r.recvuntil(b'> ').decode()
    return data.split('resp = ')[1].split()[0]

def parse_twist_point(resp_hex):
    """Parse [A, 0, 0, D] into twist point (A, D)"""
    return (int(resp_hex[0:32], 16), int(resp_hex[96:128], 16))

# --- Main ---

r = remote('exp.cybergame.sk', 7009)
r.recvuntil(b'> ')

# Query X=1 (twist point, since 1+a+b is NQR mod p)
resp = query_oracle(r, 1)
Q = parse_twist_point(resp)

# Compute base point P(1) on the twist
val = (1 + a_coeff + b_coeff) % p
c = int(sqrt_mod((-val) % p, p))
P = (1, c)

# Pohlig-Hellman on smooth factors
result = pohlig_hellman(P, Q, E_twist_order, twist_factors)
k_recovered, mod = result

# Submit k
r.sendline(b'2')
r.recvuntil(b'k = ')
r.sendline(str(k_recovered).encode())
print(r.recvall(timeout=5).decode())
r.close()

Output

  Factor 41: k ≡ 0
  Factor 12583759: k ≡ 5441550
  Factor 90840973: k ≡ 88602476

k ≡ 9942324112411005 (mod 46867957373857787)

flag = SK-CERT{0p3r4t10n5_0v3r_qu4dr4t1c_f13ld5_4r3_54f3r}

---

Solution Summary

┌─────────────────────────────────────────────────────────────────┐
│  Server claims: E(F_p) with 128-bit prime                      │
│  Reality:       E(F_{p^2}) - points over quadratic extension   │
│                                                                 │
│  E(F_{p^2}) decomposes as:                                     │
│     E(F_p)      - prime order (128-bit) → DLP HARD             │
│     E_twist(F_p) - smooth order          → DLP EASY            │
│                   = 41 × 12583759 × 90840973 × L               │
│                     \_________  _________/                      │
│                               \/                                │
│                          H (cofactor)                           │
│                    = 46867957373857787                           │
│                                                                 │
│  Attack:                                                        │
│  1. Query oracle with X where X³+aX+b is NQR → twist point     │
│  2. Get Q = k × P(X) in the twist subgroup                     │
│  3. Pohlig-Hellman on smooth factors {41, 12583759, 90840973}   │
│  4. CRT → k mod H                                              │
│  5. Since k < H, this is the exact secret                      │
└─────────────────────────────────────────────────────────────────┘

Key Insights

1. The “Extended Illusion”: N ≈ p^2 and 4-component responses expose that the curve secretly operates over F_{p^2}, not F_p.

2. Why the twist is vulnerable: E(F_{p^2}) splits as E(F_p) × E_twist(F_p). The base curve E(F_p) has prime order (secure), but the quadratic twist E_twist(F_p) has a highly composite order with small factors - making it vulnerable to Pohlig-Hellman.

3. The cofactor H is the hint: The server explicitly displays H = 41 × 12583759 × 90840973, which is exactly the smooth part of the twist order. The secret k is chosen to be smaller than H, so recovering k mod H via Pohlig-Hellman on just three small-factor BSGS computations (~13,000 total steps) suffices.

4. Twist arithmetic with i^2 = -1: Since p ≡ 3 mod 4, the natural extension is F_p(√-1). Twist points (x, c·i) have their own addition law derived from the standard Weierstrass formulas, where all intermediate values stay in F_p.

Tools Used

• Python 3 with pwntools (socket interaction) and sympy (modular square roots, factoring)
• Baby-step Giant-step algorithm for small-order DLP
• Pohlig-Hellman decomposition + CRT combination

Flag

SK-CERT{0p3r4t10n5_0v3r_qu4dr4t1c_f13ld5_4r3_54f3r}

“Operations over quadratic fields are safer” - the flag’s leet-speak message is ironic: the challenge proves the opposite. The extension to F_{p^2} introduced the smooth-order twist subgroup that made the DLP trivially solvable.