SkillAgentSearch skills...

rsa-attack-techniques

RSA attack playbook for CTF and real-world cryptanalysis

Install / Use

npx skills add yaklang/hack-skills --skill rsa-attack-techniques

Installs into whichever agent you are using.

About this skill
📄

SKILL.md

Installable skill definition

Quality Score

86/100

Category

Security

Supported Platforms

Zed

Our assessment of rsa-attack-techniques

rsa-attack-techniques scores 86/100 on our quality scale, 744th of 1,111 Security skills we index.

Its SKILL.md is 11 KB long, well organised into 38 sections with 16 code examples: a thorough specification that gives an agent plenty to work with.

With 2,288 GitHub stars, it is one of the more widely adopted skills in the catalogue.

Substance
29/30
Structure
20/20
Description
8/15
Adoption
14/20
Freshness
15/15

Maintenance, license and trust

  • The repository was last updated about 2 months ago, so rsa-attack-techniques is actively maintained.
  • Our last check on 2026-11-03 found the source still online.
  • It is released under the MIT license, a permissive license that allows use, modification and commercial use with attribution.
  • Its trust signals score 100/100, with no cautions. These come from repository metadata, not a code audit — read the skill file before letting an agent act on it.

Safety scan

No issues found

Our scan of the whole file found no instruction hijacking, hidden characters, credential access, data exfiltration or destructive commands. An AI review of the same text found nothing harmful.

AI review by kimi-k2.7-code on 2026-10-01. Automated pattern scan on 2026-10-01. It catches known dangerous patterns, not every risk — read a skill before letting an agent act on it.

rsa-attack-techniques compared with similar skills

All 4 of these similar skills score higher than rsa-attack-techniques; compare them before choosing.

SkillScoreStarsUpdatedFormat
rsa-attack-techniques (this skill)by yaklang862.3k2mo agoSKILL.md
x402by browser-use100121.0k3d agoSKILL.md
algorithmic-artby anthropics100177.9k55d agoSKILL.md
pptxby anthropics100177.9k55d agoSKILL.md
designby nextlevelbuilder100149.0k6d agoSKILL.md

Frequently asked questions

How do I install rsa-attack-techniques?
Run npx skills add yaklang/hack-skills --skill rsa-attack-techniques. The install tabs above show the steps for each supported agent.
Which AI agents does rsa-attack-techniques work with?
It is written for Zed, as a SKILL.md file. Other agents that read the same format can often use it too.
Is rsa-attack-techniques safe to use?
Our scan of the whole file found no instruction hijacking, hidden characters, credential access, data exfiltration or destructive commands. An AI review of the same text found nothing harmful. It is MIT-licensed and scores 100/100 on trust signals. Skills are instructions an agent will follow, so read the file before installing it and do not approve commands you do not understand.
Is rsa-attack-techniques still maintained?
The repository was last updated about 2 months ago, so rsa-attack-techniques is actively maintained.

name: rsa-attack-techniques description: >- RSA attack playbook for CTF and real-world cryptanalysis. Use when given RSA parameters (n, e, c) and need to recover plaintext by exploiting weak keys, small exponents, shared factors, or padding oracles.

SKILL: RSA Attack Techniques — Expert Cryptanalysis Playbook

AI LOAD INSTRUCTION: Expert RSA attack techniques for CTF and authorized security assessments. Covers factorization attacks, small exponent exploits, lattice-based approaches (Wiener/Boneh-Durfee/Coppersmith), broadcast attacks, common modulus, padding oracles, and fault attacks. Base models often suggest attacks that don't match the given parameters or miss the correct attack selection based on what's known.

0. RELATED ROUTING

Advanced Reference

Also load RSA_ATTACK_CATALOG.md when you need:

  • Detailed SageMath/Python implementation for each attack
  • Step-by-step mathematical derivation
  • Edge cases and failure conditions per attack

Quick attack selection

| Given / Observable | Attack | Tool | |---|---|---| | Small n (< 512 bits) | Direct factorization | factordb, yafu, msieve | | e = 3, small message | Cube root | gmpy2.iroot | | Multiple (n, c) same small e | Hastad broadcast | CRT + iroot | | Very large e or very small d | Wiener / Boneh-Durfee | SageMath, RsaCtfTool | | Partial p knowledge | Coppersmith small roots | SageMath | | Same n, different e | Common modulus | Extended GCD | | Multiple n values | Batch GCD (shared factor) | Python/SageMath | | Padding error oracle | Bleichenbacher | Custom script | | LSB parity oracle | LSB oracle attack | Custom script | | Fault in CRT computation | RSA-CRT fault | Single faulty signature |


1. FACTORIZATION ATTACKS

1.1 Direct Factorization (Small n)

from sympy import factorint

n = 0x...  # small modulus
factors = factorint(n)
p, q = list(factors.keys())

When: n < ~512 bits, or known to be in factordb.

1.2 Fermat's Factorization

Works when p and q are close together: |p - q| is small.

from gmpy2 import isqrt, is_square

def fermat_factor(n):
    a = isqrt(n) + 1
    while True:
        b2 = a * a - n
        if is_square(b2):
            b = isqrt(b2)
            return (a + b, a - b)
        a += 1

1.3 Pollard's p-1

Works when p-1 has only small prime factors (B-smooth).

from gmpy2 import gcd

def pollard_p1(n, B=2**20):
    a = 2
    for j in range(2, B):
        a = pow(a, j, n)
    d = gcd(a - 1, n)
    if 1 < d < n:
        return d
    return None

1.4 Batch GCD (Multiple n share a factor)

from math import gcd
from functools import reduce

def batch_gcd(moduli):
    """Find shared factors among multiple RSA moduli."""
    product = reduce(lambda a, b: a * b, moduli)
    results = {}
    for i, n in enumerate(moduli):
        remainder = product // n
        g = gcd(n, remainder)
        if g != 1 and g != n:
            results[i] = (g, n // g)
    return results

2. SMALL EXPONENT ATTACKS

2.1 Cube Root Attack (e = 3, small m)

If m^e < n (no modular reduction occurred), simply take the e-th root.

from gmpy2 import iroot

c = 0x...  # ciphertext
e = 3
m, exact = iroot(c, e)
if exact:
    print(f"Plaintext: {bytes.fromhex(hex(m)[2:])}")

2.2 Hastad Broadcast Attack

Same message encrypted with same small e under different moduli (n₁, n₂, ..., nₑ).

from sympy.ntheory.modular import crt
from gmpy2 import iroot

# e = 3, three ciphertexts under three different n
n_list = [n1, n2, n3]
c_list = [c1, c2, c3]

# CRT: find x such that x ≡ ci (mod ni) for all i
r, M = crt(n_list, c_list)
m, exact = iroot(r, 3)
assert exact

2.3 Related Message Attack (Franklin-Reiter)

Two messages related by a known linear function: m₂ = a·m₁ + b. Same n and e.

# SageMath
def franklin_reiter(n, e, c1, c2, a, b):
    R.<x> = PolynomialRing(Zmod(n))
    f1 = x^e - c1
    f2 = (a*x + b)^e - c2
    return Integer(n - gcd(f1, f2).coefficients()[0])

3. LARGE e / SMALL d ATTACKS

3.1 Wiener's Attack (Continued Fractions)

When d < n^(1/4) / 3, the continued fraction expansion of e/n reveals d.

def wiener_attack(e, n):
    """Recover d when d is small via continued fractions."""
    cf = continued_fraction(e, n)
    convergents = get_convergents(cf)

    for k, d in convergents:
        if k == 0:
            continue
        phi_candidate = (e * d - 1) // k
        # phi(n) = n - p - q + 1 → p + q = n - phi + 1
        s = n - phi_candidate + 1
        # p, q are roots of x^2 - s*x + n = 0
        discriminant = s * s - 4 * n
        if discriminant >= 0:
            from gmpy2 import isqrt, is_square
            if is_square(discriminant):
                return d
    return None

def continued_fraction(a, b):
    cf = []
    while b:
        cf.append(a // b)
        a, b = b, a % b
    return cf

def get_convergents(cf):
    convergents = []
    h_prev, h_curr = 0, 1
    k_prev, k_curr = 1, 0
    for a in cf:
        h_prev, h_curr = h_curr, a * h_curr + h_prev
        k_prev, k_curr = k_curr, a * k_curr + k_prev
        convergents.append((h_curr, k_curr))
    return convergents

3.2 Boneh-Durfee Attack (Lattice-Based)

Extends Wiener: works when d < n^0.292. Uses lattice reduction (LLL/BKZ).

Use SageMath implementation — see lattice-crypto-attacks for theory.


4. COPPERSMITH'S METHOD

4.1 Stereotyped Message

Known portion of plaintext, unknown part is small.

# SageMath
n = ...
e = 3
c = ...
known_prefix = b"flag{" + b"\x00" * 27  # known prefix, unknown suffix
known_int = int.from_bytes(known_prefix, 'big')

R.<x> = PolynomialRing(Zmod(n))
f = (known_int + x)^e - c
roots = f.small_roots(X=2^(27*8), beta=1.0)
if roots:
    m = known_int + int(roots[0])
    print(bytes.fromhex(hex(m)[2:]))

4.2 Partial Key Exposure

Known MSB or LSB of p → recover full p via Coppersmith.

# SageMath — known MSB of p
p_msb = ...  # known upper bits of p
R.<x> = PolynomialRing(Zmod(n))
f = p_msb + x
roots = f.small_roots(X=2^unknown_bits, beta=0.5)
if roots:
    p = p_msb + int(roots[0])
    q = n // p

5. COMMON MODULUS ATTACK

Two ciphertexts of same message under same n but different e₁, e₂ where gcd(e₁, e₂) = 1.

from gmpy2 import gcd, invert

def common_modulus(n, e1, e2, c1, c2):
    """Recover m when same message encrypted with two different e under same n."""
    assert gcd(e1, e2) == 1
    _, s1, s2 = extended_gcd(e1, e2)  # s1*e1 + s2*e2 = 1

    if s1 < 0:
        c1 = invert(c1, n)
        s1 = -s1
    if s2 < 0:
        c2 = invert(c2, n)
        s2 = -s2

    m = (pow(c1, s1, n) * pow(c2, s2, n)) % n
    return m

def extended_gcd(a, b):
    if a == 0:
        return b, 0, 1
    g, x, y = extended_gcd(b % a, a)
    return g, y - (b // a) * x, x

6. ORACLE ATTACKS

6.1 LSB Oracle (Parity Oracle)

An oracle reveals whether decrypted message is even or odd.

from gmpy2 import mpz

def lsb_oracle_attack(n, e, c, oracle_func):
    """Decrypt using LSB (parity) oracle. oracle_func(c) returns m%2."""
    from fractions import Fraction
    lo, hi = Fraction(0), Fraction(n)

    for _ in range(n.bit_length()):
        c = (c * pow(2, e, n)) % n  # multiply plaintext by 2
        if oracle_func(c) == 0:
            hi = (lo + hi) / 2
        else:
            lo = (lo + hi) / 2

    return int(hi)

6.2 Bleichenbacher (PKCS#1 v1.5 Padding Oracle)

Given a padding validity oracle (valid/invalid PKCS#1 v1.5), iteratively narrow down the plaintext range.

Complexity: O(2^16) oracle queries per byte on average.

Target: TLS implementations returning different errors for valid/invalid padding.

6.3 Manger's Attack (PKCS#1 OAEP)

Similar to Bleichenbacher but for OAEP padding. Exploits oracle that distinguishes whether the first byte after unpadding is 0x00.


7. RSA-CRT FAULT ATTACK

If RSA-CRT signing produces a faulty signature (fault in one CRT half):

def rsa_crt_fault(n, e, correct_sig, faulty_sig, msg):
    """Factor n from one correct and one faulty CRT signature."""
    from math import gcd
    diff = pow(correct_sig, e, n) - pow(faulty_sig, e, n)
    p = gcd(diff % n, n)
    if 1 < p < n:
        q = n // p
        return p, q
    return None

# Even simpler: only faulty signature needed if message is known
def rsa_crt_fault_simple(n, e, faulty_sig, msg):
    p = gcd(pow(faulty_sig, e, n) - msg, n)
    if 1 < p < n:
        return p, n // p
    return None

8. DECISION TREE

RSA challenge — what information do you have?
│
├─ Have n and it's small (< 512 bits)?
│  └─ Factor directly: factordb.com → yafu → msieve
│
├─ Have multiple n values?
│  └─ Batch GCD — shared factors?
│     ├─ Yes → factor all that share factors
│     └─ No → analyze each n individually
│
├─ Know e?
│  ├─ e = 3 (or small)?
│  │  ├─ Single ciphertext, small message → cube root
│  │  ├─ Multiple ciphertexts, different n → Hastad broadcast
│  │  ├─ Two related messages → Franklin-Reiter
│  │  └─ Partial plaintext known → Coppersmith
│  │
│  ├─ e is very large?
│  │  └─ d is likely small → Wiener → Boneh-Durfee
│  │
│  └─ Same n, two different e values?
│     └─ Common modulus attack (Bezout coefficients)
│
├─ Know partial factorization info?
│  ├─ Know some bits of p → Coppersmith partial key
│  ├─ p-1 is B-smooth → Pollard p-1
│  └─ p ≈ q (close primes) → Fermat factorization
│
├─ Have an oracle?
│  ├─ Parity oracle (LSB) → LSB oracle attack
│  ├─ Padding validity oracle (PKCS#1 v1.5) → Bleichenbacher
│  └─ OAEP oracle → Manger's attack
│
├─ Have faulty signature?
│  └─ RSA-CRT fault → factor n from faulty sig
│
├─ Know e·d relationship?
│  └─ e·d ≡ 1 mod φ(n) → factor n from (e,d,n)
│
└─ None of the above?
   ├─ Check factordb for known factorization
   ├─ Try Pollard rho for medium-size n
   ├─ Look for implementation flaws (weak PRNG for key generation)
   └─ Consider side-channel if physical access available

9. TOOLS

| Tool | Purpose | Usage | |---|---|---| | RsaCtfTool | Automated RSA attack suite | python3 RsaCtfTool.py --publickey pub.pem --uncipherfile flag.enc | | SageMath | Mathematical computation | Coppersmith, lattice attacks, polynomial arithmetic | | factordb.com | Online factor database | Check if n is already factored | | yafu | Fast factorization (SIQS/GNFS) | yafu "factor(n)" | | msieve | GNFS factorization | Large n factorization | | gmpy2 | Fast Python integer library | iroot, invert, gcd | | pycryptodome | RSA primitives | Key construction from factors |

RsaCtfTool Quick Commands

# From public key
python3 RsaCtfTool.py --publickey pub.pem -n --private

# From parameters
python3 RsaCtfTool.py -n $N -e $E --uncipher $C

# Try all attacks
python3 RsaCtfTool.py --publickey pub.pem --uncipherfile flag.enc --attack all

Decrypt After Factoring

from Crypto.PublicKey import RSA
from gmpy2 import invert

p, q = ...  # factored
n = p * q
e = 65537
phi = (p - 1) * (q - 1)
d = int(invert(e, phi))

c = ...  # ciphertext as integer
m = pow(c, d, n)
plaintext = m.to_bytes((m.bit_length() + 7) // 8, 'big')
print(plaintext)

Related Skills

View on GitHub
GitHub Stars2.3k
CategorySecurity
Updated2mo ago
Forks303

Languages

CSS

Trust signals

100/100

From repository metadata: license, adoption, age and documentation. Not a code audit — see the Safety scan above for what the skill file itself contains.

No cautions