SkillAgentSearch skills...

lattice-crypto-attacks

Lattice-based cryptanalysis playbook

Install / Use

npx skills add yaklang/hack-skills --skill lattice-crypto-attacks

Installs into whichever agent you are using.

About this skill
📄

SKILL.md

Installable skill definition

Quality Score

88/100

Supported Platforms

Universal

Tags

Our assessment of lattice-crypto-attacks

lattice-crypto-attacks scores 88/100 on our quality scale, 1907th of 4,698 Development & Engineering skills we index (top 41%).

Its SKILL.md is 14 KB long, well organised into 52 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
30/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 lattice-crypto-attacks is actively maintained.
  • Our last check on 2026-11-01 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-02. Automated pattern scan on 2026-10-02. It catches known dangerous patterns, not every risk — read a skill before letting an agent act on it.

lattice-crypto-attacks compared with similar skills

All 4 of these similar skills score higher than lattice-crypto-attacks; compare them before choosing.

SkillScoreStarsUpdatedFormat
lattice-crypto-attacks (this skill)by yaklang882.3k2mo agoSKILL.md
taste-skillby Leonxlnx100116.8k8d agoCLAUDE.md
ai-job-searchby ai-job-search-dev10072.1ktodayCLAUDE.md
claude-howtoby luongnv8910047.3k2d agoCLAUDE.md
lobehubby lobehub10085.6ktodayMCP Server

Frequently asked questions

How do I install lattice-crypto-attacks?
Run npx skills add yaklang/hack-skills --skill lattice-crypto-attacks. The install tabs above show the steps for each supported agent.
Which AI agents does lattice-crypto-attacks work with?
It is written for Universal, as a SKILL.md file. Other agents that read the same format can often use it too.
Is lattice-crypto-attacks 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 lattice-crypto-attacks still maintained?
The repository was last updated about 2 months ago, so lattice-crypto-attacks is actively maintained.

name: lattice-crypto-attacks description: >- Lattice-based cryptanalysis playbook. Use when attacking RSA via Coppersmith small roots, recovering DSA/ECDSA nonces from bias, solving knapsack problems, or applying LLL/BKZ reduction to cryptographic constructions.

SKILL: Lattice-Based Cryptanalysis — Expert Attack Playbook

AI LOAD INSTRUCTION: Expert lattice techniques for CTF and cryptanalysis. Covers LLL/BKZ reduction, Coppersmith's method (univariate and multivariate), Hidden Number Problem for DSA/ECDSA nonce recovery, knapsack attacks, and NTRU analysis. Base models often fail to construct the correct attack lattice (wrong dimensions, missing scaling factors) or misapply Coppersmith bounds.

0. RELATED ROUTING

Quick application guide

| Problem Type | Lattice Technique | Key Parameter | |---|---|---| | RSA small roots | Coppersmith (LLL on polynomial lattice) | Root bound X < N^(1/e) | | RSA small d | Boneh-Durfee (multivariate Coppersmith) | d < N^0.292 | | DSA/ECDSA nonce bias | Hidden Number Problem → CVP | Bias bits known | | Knapsack cipher | Low-density lattice attack | Density < 0.9408 | | LCG truncated output | CVP on recurrence lattice | Unknown bits per output | | Subset sum | LLL reduction on knapsack lattice | Element size vs count | | NTRU key recovery | Lattice reduction on NTRU lattice | Dimension and key size |


1. LATTICE FUNDAMENTALS

1.1 Definitions

A lattice L is the set of all integer linear combinations of basis vectors:

L = { a₁·b₁ + a₂·b₂ + ... + aₙ·bₙ | aᵢ ∈ ℤ }

where b₁, ..., bₙ are linearly independent vectors in ℝᵐ.

Key problems:

  • SVP (Shortest Vector Problem): Find the shortest non-zero vector in L
  • CVP (Closest Vector Problem): Given target t, find v ∈ L closest to t
  • SVP is NP-hard in general, but LLL finds an approximately short vector in polynomial time

1.2 Lattice Quality Metrics

Determinant: det(L) = |det(B)| where B is the basis matrix
Gaussian heuristic: shortest vector ≈ √(n/(2πe)) · det(L)^(1/n)

2. LLL ALGORITHM

2.1 What LLL Does

Takes a lattice basis B and produces a reduced basis B' where:

  • Vectors are nearly orthogonal
  • First vector is approximately short (within 2^((n-1)/2) factor of SVP)
  • Runs in polynomial time: O(n^5 · d · log³ B) where d = dimension, B = max entry size

2.2 SageMath Usage

# SageMath
M = matrix(ZZ, [
    [1, 0, 0, large_value_1],
    [0, 1, 0, large_value_2],
    [0, 0, 1, large_value_3],
    [0, 0, 0, modulus],
])

L = M.LLL()
# Short vectors in L reveal the solution
short_vector = L[0]  # first row is typically shortest

2.3 Python (fpylll)

from fpylll import IntegerMatrix, LLL

n = 4
A = IntegerMatrix(n, n)
# Fill matrix A...
A[0] = (1, 0, 0, large_value_1)
A[1] = (0, 1, 0, large_value_2)
A[2] = (0, 0, 1, large_value_3)
A[3] = (0, 0, 0, modulus)

LLL.reduction(A)
print(A[0])  # shortest vector

3. BKZ (BLOCK KORKINE-ZOLOTAREV)

3.1 Comparison with LLL

| Property | LLL | BKZ-β | |---|---|---| | Quality | 2^((n-1)/2) approximation | 2^(n/(β-1)) approximation | | Speed | Polynomial | Exponential in β | | Block size | Fixed (2) | Configurable β | | Best for | Quick reduction | High-quality reduction |

3.2 Usage

# SageMath
M = matrix(ZZ, [...])
L = M.BKZ(block_size=20)  # β = 20

# fpylll
from fpylll import BKZ
BKZ.reduction(A, BKZ.Param(block_size=20))

Rule of thumb: start with LLL, increase to BKZ if needed. BKZ block size 20-40 is usually sufficient for CTF.


4. COPPERSMITH'S METHOD

4.1 Univariate Case

Given f(x) ≡ 0 (mod N) with small root |x₀| < X, find x₀.

Bound: X < N^(1/d) where d = degree of f.

# SageMath — built-in small_roots
N = ...
R.<x> = PolynomialRing(Zmod(N))
f = x^3 + a*x^2 + b*x + c  # known polynomial
roots = f.small_roots(X=2^100, beta=1.0, epsilon=1/30)

Parameters:

  • X: upper bound on the root
  • beta: N = p^beta (beta=1.0 for modular root of N itself; beta=0.5 for root mod unknown factor p ≈ √N)
  • epsilon: smaller = better results but slower (try 1/30 to 1/100)

4.2 Stereotyped Message Attack (RSA)

# SageMath
n, e, c = ...  # RSA parameters
known_msb = ...  # known upper portion of message

R.<x> = PolynomialRing(Zmod(n))
f = (known_msb + x)^e - c

# x represents the unknown lower bits
X = 2^(unknown_bit_count)
roots = f.small_roots(X=X, beta=1.0)
if roots:
    m = known_msb + int(roots[0])

4.3 Partial Key Exposure (Factor p)

Known MSBs of p: p = p_known + x where x is small.

# SageMath
n = ...
p_known = ...  # known upper bits of p

R.<x> = PolynomialRing(Zmod(n))
f = p_known + x
roots = f.small_roots(X=2^unknown_bits, beta=0.5)
# beta=0.5 because p ≈ √n
if roots:
    p = p_known + int(roots[0])
    q = n // p

4.4 Multivariate Coppersmith (Howgrave-Graham)

For f(x, y) ≡ 0 (mod N):

  • No polynomial-time algorithm guaranteed
  • Heuristic methods work in practice
  • Used in Boneh-Durfee for RSA small d
# SageMath — Boneh-Durfee
# e*d ≡ 1 (mod phi) where phi = (p-1)(q-1)
# Rewrite: e*d = 1 + k*((n+1) - (p+q))
# Let x = k, y = (p+q), both small relative to n

R.<x, y> = PolynomialRing(ZZ)
A = (n + 1) // 2
f = 1 + x * (A + y)  # mod e

# Build shift polynomials and construct lattice
# Apply LLL to find small (x₀, y₀)

5. HIDDEN NUMBER PROBLEM (HNP) — DSA/ECDSA NONCE RECOVERY

5.1 Problem Statement

Given: signatures (rᵢ, sᵢ) where nonces kᵢ have known bias (leaked MSBs or LSBs).

DSA equation: s = k⁻¹(H(m) + xr) mod q

Rearranged: k = s⁻¹(H(m) + xr) mod q

If partial bits of k are known: reduces to CVP on a lattice.

5.2 Attack Setup

# SageMath
def ecdsa_nonce_attack(signatures, q, known_bits, bit_position='msb'):
    """
    signatures: list of (r, s, hash, known_nonce_bits)
    q: curve order
    known_bits: number of known bits per nonce
    """
    n = len(signatures)

    # Build lattice
    B = 2^(q.nbits() - known_bits)  # bound on unknown part
    M = matrix(QQ, n + 2, n + 2)

    for i in range(n):
        r_i, s_i, h_i, a_i = signatures[i]
        t_i = Integer(inverse_mod(s_i, q) * r_i % q)
        u_i = Integer(inverse_mod(s_i, q) * h_i % q)

        M[i, i] = q
        M[n, i] = t_i
        M[n+1, i] = u_i - a_i  # a_i = known nonce bits

    M[n, n] = B / q
    M[n+1, n+1] = B

    # LLL reduction
    L = M.LLL()

    # Find row containing the private key x
    for row in L:
        x_candidate = Integer(row[n] * q / B) % q
        # Verify x_candidate against one signature
        if verify_private_key(x_candidate, signatures[0], q):
            return x_candidate

    return None

5.3 Practical Nonce Bias Sources

| Source | Leaked Bits | Required Signatures | |---|---|---| | MSB bias (always 0) | 1 bit | ~100 signatures | | k generated with wrong length | Variable | ~50 signatures | | Timing side channel | 1-4 bits | 20-100 signatures | | Insecure PRNG | Many | Few | | Reused nonce (k₁ = k₂) | All | 2 signatures |

For reused nonce (simplest case):

def ecdsa_reused_nonce(r, s1, s2, h1, h2, q):
    """Recover private key when nonce k is reused."""
    # s1 - s2 = k⁻¹(h1 - h2) mod q  (since r is same)
    k = ((h1 - h2) * inverse_mod(s1 - s2, q)) % q
    x = ((s1 * k - h1) * inverse_mod(r, q)) % q
    return x, k

6. KNAPSACK / SUBSET SUM ATTACKS

6.1 Low-Density Attack

Knapsack: given weights a₁,...,aₙ and target S, find x₁,...,xₙ ∈ {0,1} such that Σxᵢaᵢ = S.

Density d = n / max(log₂ aᵢ). If d < 0.9408, lattice attack works.

# SageMath
def knapsack_lattice(weights, target):
    """Solve subset sum via LLL lattice attack."""
    n = len(weights)

    # Build lattice (Lagarias-Odlyzko style)
    N = ceil(sqrt(n) / 2)  # scaling factor
    M = matrix(ZZ, n + 1, n + 1)

    for i in range(n):
        M[i, i] = 1
        M[i, n] = N * weights[i]
    M[n, n] = N * target

    # Alternative: CJLOSS embedding
    M2 = matrix(ZZ, n + 1, n + 2)
    for i in range(n):
        M2[i, i] = 1
        M2[i, n + 1] = N * weights[i]
    M2[n, n] = 1
    M2[n, n + 1] = N * (-target)

    L = M2.LLL()

    # Look for short vector with entries in {0, 1, -1}
    for row in L:
        if all(v in (0, 1) for v in row[:n]):
            solution = list(row[:n])
            if sum(solution[i] * weights[i] for i in range(n)) == target:
                return solution

    return None

7. NTRU CRYPTANALYSIS

7.1 NTRU Lattice

# SageMath
def ntru_lattice_attack(h, q, N):
    """
    Construct NTRU lattice for key recovery.
    h = public key polynomial (mod q)
    q = modulus
    N = dimension
    """
    # NTRU lattice:
    # | qI  0 |
    # | H   I |
    # where H is the circulant matrix of h

    H = matrix(ZZ, N, N)
    for i in range(N):
        for j in range(N):
            H[i, j] = h[(j - i) % N]

    M = block_matrix([
        [q * identity_matrix(N), zero_matrix(N)],
        [H, identity_matrix(N)]
    ])

    L = M.LLL()

    # Short vector in reduced basis = (f, g) private key
    for row in L:
        f = vector(row[:N])
        g = vector(row[N:])
        if f.norm() < q and g.norm() < q:
            return f, g

    return None

8. CONSTRUCTING ATTACK LATTICES — METHODOLOGY

8.1 General Recipe

1. Express the cryptographic problem as:
   "Find small x such that f(x) ≡ 0 (mod N)"
   or "Find x close to target t in some lattice L"

2. Choose lattice type:
   ├─ Polynomial lattice → Coppersmith-style
   ├─ Modular lattice → HNP-style CVP
   └─ Knapsack lattice → subset sum / CJLOSS

3. Determine dimensions:
   └─ More dimensions = better approximation but slower

4. Set scaling factors:
   └─ Balance the rows so short vector has roughly equal entries
   └─ Common: multiply by N/X where X is the root bound

5. Apply reduction:
   ├─ LLL first (fast, usually sufficient)
   └─ BKZ if LLL fails (increase block size: 20, 30, 40)

6. Extract solution:
   └─ Check reduced basis rows for valid solutions

8.2 Embedding Technique (CVP → SVP)

Transform CVP into SVP by embedding the target into the lattice:

# SageMath
def cvp_to_svp(basis_matrix, target, scale=1):
    """Convert CVP to SVP via Kannan's embedding."""
    n = basis_matrix.nrows()
    m = basis_matrix.ncols()

    # Augment matrix
    M = matrix(ZZ, n + 1, m + 1)
    for i in range(n):
        for j in range(m):
            M[i, j] = basis_matrix[i, j]
        M[i, m] = 0

    for j in range(m):
        M[n, j] = target[j]
    M[n, m] = scale  # scaling factor (try 1, then adjust)

    L = M.LLL()

    # Look for row with last entry = ±scale
    for row in L:
        if abs(row[m]) == scale:
            return vector(target) - vector(row[:m]) * (row[m] // abs(row[m]))

    return None

8.3 Dimension Selection Guide

| Problem | Typical Dimension | Notes | |---|---|---| | Coppersmith univariate (degree d) | d × m where m ≈ 1/ε | Larger m = smaller root bound | | HNP with n signatures | n + 2 | n ≥ known_bits_ratio × q_bits | | Knapsack with n weights | n + 1 or n + 2 | Depends on density | | LCG with n outputs | n + 1 | More outputs = easier | | Boneh-Durfee | (m+1)(m+2)/2 | m = parameter depth |


9. DECISION TREE

Lattice approach needed — which construction?
│
├─ RSA-related?
│  ├─ Small unknown part of message → Coppersmith univariate
│  │  └─ Check: unknown_bits < n_bits / e
│  ├─ Partial factor knowledge → Coppersmith mod p
│  │  └─ Use beta=0.5, X=2^unknown_bits
│  ├─ Small private exponent d → Boneh-Durfee
│  │  └─ Ch

Truncated for display — read the full file on GitHub.

Related Skills

View on GitHub
GitHub Stars2.3k
CategoryDevelopment
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