Public-Key Crypto CTF Solver

A skill for solving public-key cryptography challenges in CTFs and security research. Focuses on RSA, ECC/ECDSA, and lattice-based attacks.

When to use this skill

Use this skill when:

• You have RSA parameters (n, e, c) and need to decrypt or factor
• You're analyzing ECDSA signatures for nonce reuse or bias
• You encounter lattice-based crypto problems
• You need to recover private keys from cryptographic artifacts
• You're working on CTF crypto challenges involving public-key algorithms

Recommended Tooling

• SageMath: For LLL/lattice attacks and modular arithmetic
• RsaCtfTool: Swiss-army knife for RSA attacks
• factordb.com: Quick factorization checks

RSA Attacks

Start here when you have

n, e, c

and additional hints.

Common Attack Patterns

1. Shared Modulus Attack: Same

   n

   used with different

   e

   values
2. Low Exponent Attack: Small

   e

   (e.g., e=3) with small messages
3. Partial Key Exposure: Some bits of

   d

   or

   p

   /

   q

   known
4. Related Messages: Same message encrypted with different padding
5. Small Factors:

   n

   has small prime factors (check factordb first)

Attack Workflow

1. Check factordb.com for

   n

   - instant factorization if available
2. Run RsaCtfTool for automated attack detection
3. Use SageMath for custom lattice attacks if needed

ECDSA Nonce Recovery

If two signatures reuse the same nonce

k

, the private key can be recovered.

Recovery Formulas

Given:

• Two messages

  m1, m2

  with signatures

  (r, s1)

  and

  (r, s2)

• Same

  r

  indicates nonce reuse
• Group order

  n

Recovery:

k = (h(m1) - h(m2)) * (s1 - s2)^{-1} mod n
d = (s1*k - h(m1)) * r^{-1} mod n

Where:

• h(m)

  = hash of message

• d

  = private key

• k

  = nonce

Nonce Bias/Leakage

Even if

k

isn't identical, bias or leakage of nonce bits across signatures can enable lattice recovery. This is a common CTF theme.

Invalid-Curve Attacks

If a protocol fails to validate that points are on the expected curve (or subgroup), an attacker may force operations in a weak group.

Defense Checklist

• Validate points are on-curve
• Validate points are in the correct subgroup
• Check for small subgroup attacks

Attack Pattern

Many CTF tasks model this as: "server multiplies attacker-chosen point by secret scalar and returns something."

Scripts

ECDSA Nonce Recovery

Use

scripts/ecdsa_nonce_recovery.py

when you have two signatures with the same

r

value.

RSA Factorization Helper

Use

scripts/rsa_factor_check.py

to quickly check factordb and run basic factorization.

SageMath Patterns

For lattice attacks, use SageMath with LLL:

from sage.all import *

# Example: Lattice basis construction
n = 2  # dimension
basis = Matrix(ZZ, [[n, 0], [0, n]])
reduced = basis.LLL()

Common CTF Patterns

1. Nonce reuse in ECDSA → Direct private key recovery
2. Small RSA factors → Check factordb first
3. Invalid curve points → Force weak group operations
4. Lattice problems → Use SageMath LLL
5. Partial key exposure → Coppersmith's method

Next Steps

After identifying the attack pattern:

1. Extract relevant parameters from the challenge
2. Run the appropriate script or SageMath code
3. Verify the recovered key works
4. Document the attack for writeup