lattice-crypto-attacks
Lattice-based cryptanalysis playbook
Install / Use
npx skills add yaklang/hack-skills --skill lattice-crypto-attacksInstalls into whichever agent you are using.
SKILL.md
Installable skill definition
Quality Score
Category
Development & EngineeringSupported Platforms
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.
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 foundOur 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.
| Skill | Score | Stars | Updated | Format |
|---|---|---|---|---|
| lattice-crypto-attacks (this skill)by yaklang | 88 | 2.3k | 2mo ago | SKILL.md |
| taste-skillby Leonxlnx | 100 | 116.8k | 8d ago | CLAUDE.md |
| ai-job-searchby ai-job-search-dev | 100 | 72.1k | today | CLAUDE.md |
| claude-howtoby luongnv89 | 100 | 47.3k | 2d ago | CLAUDE.md |
| lobehubby lobehub | 100 | 85.6k | today | MCP 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.
Skill content
View source on GitHubname: 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
- rsa-attack-techniques for RSA-specific attacks that use lattice methods (Coppersmith, Boneh-Durfee)
- symmetric-cipher-attacks for LCG state recovery via lattice
- classical-cipher-analysis when lattice methods apply to classical cipher analysis
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 rootbeta: 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
taste-skill
116.8kAgent skills that give coding agents taste: art direction, reference images and a browser check instead of generic AI pages
ai-job-search
72.1kThe job search that runs on your machine. AI job application framework built on Claude Code: evaluate postings, tailor CVs, write cover letters, prep interviews. Fork it and own it.
claude-howto
47.3kA visual, example-driven guide to Claude Code — from basic concepts to advanced agents, with copy-paste templates that bring immediate value.
lobehub
85.6k🤯 LobeHub - Super-Agents on Your Team. Add super-agents to the chats your team already uses.They take on work by themselves and get better every week.
Languages
Trust signals
From repository metadata: license, adoption, age and documentation. Not a code audit — see the Safety scan above for what the skill file itself contains.
