lattice-crypto-attacks

Name: lattice-crypto-attacks
Author: Prohao42

91stars8forks

How to install lattice-crypto-attacks?

prohao42/aimy-skill/lattice-crypto-attacks

$npx -y skills add Prohao42/aimy-skill --skill lattice-crypto-attacks

Installs into the current project.

Summary

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.

Files · 1

View on GitHub

SKILL.md

1	# SKILL: Lattice-Based Cryptanalysis — Expert Attack Playbook
2
3	> 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.
4
5	## 0. RELATED ROUTING
6
7	- [rsa-attack-techniques](../rsa-attack-techniques/SKILL.md) for RSA-specific attacks that use lattice methods (Coppersmith, Boneh-Durfee)
8	- [symmetric-cipher-attacks](../symmetric-cipher-attacks/SKILL.md) for LCG state recovery via lattice
9	- [classical-cipher-analysis](../classical-cipher-analysis/SKILL.md) when lattice methods apply to classical cipher analysis
10
11	### Quick application guide
12
13	\| Problem Type \| Lattice Technique \| Key Parameter \|
14	\|---\|---\|---\|
15	\| RSA small roots \| Coppersmith (LLL on polynomial lattice) \| Root bound X < N^(1/e) \|
16	\| RSA small d \| Boneh-Durfee (multivariate Coppersmith) \| d < N^0.292 \|
17	\| DSA/ECDSA nonce bias \| Hidden Number Problem → CVP \| Bias bits known \|
18	\| Knapsack cipher \| Low-density lattice attack \| Density < 0.9408 \|
19	\| LCG truncated output \| CVP on recurrence lattice \| Unknown bits per output \|
20	\| Subset sum \| LLL reduction on knapsack lattice \| Element size vs count \|
21	\| NTRU key recovery \| Lattice reduction on NTRU lattice \| Dimension and key size \|
22
23	---
24
25	## 1. LATTICE FUNDAMENTALS
26
27	### 1.1 Definitions
28
29	A lattice L is the set of all integer linear combinations of basis vectors:
30
31	```
32	L = { a₁·b₁ + a₂·b₂ + ... + aₙ·bₙ \| aᵢ ∈ ℤ }
33	```
34
35	where b₁, ..., bₙ are linearly independent vectors in ℝᵐ.
36
37	Key problems:
38	- SVP (Shortest Vector Problem): Find the shortest non-zero vector in L
39	- CVP (Closest Vector Problem): Given target t, find v ∈ L closest to t
40	- SVP is NP-hard in general, but LLL finds an approximately short vector in polynomial time
41
42	### 1.2 Lattice Quality Metrics
43
44	```
45	Determinant: det(L) = \|det(B)\| where B is the basis matrix
46	Gaussian heuristic: shortest vector ≈ √(n/(2πe)) · det(L)^(1/n)
47	```
48
49	---
50
51	## 2. LLL ALGORITHM
52
53	### 2.1 What LLL Does
54
55	Takes a lattice basis B and produces a reduced basis B' where:
56	- Vectors are nearly orthogonal
57	- First vector is approximately short (within 2^((n-1)/2) factor of SVP)
58	- Runs in polynomial time: O(n^5 · d · log³ B) where d = dimension, B = max entry size
59
60	### 2.2 SageMath Usage
61
62	```python
63	# SageMath
64	M = matrix(ZZ, [
65	[1, 0, 0, large_value_1],
66	[0, 1, 0, large_value_2],
67	[0, 0, 1, large_value_3],
68	[0, 0, 0, modulus],
69	])
70
71	L = M.LLL()
72	# Short vectors in L reveal the solution
73	short_vector = L[0] # first row is typically shortest
74	```
75
76	### 2.3 Python (fpylll)
77
78	```python
79	from fpylll import IntegerMatrix, LLL
80
81	n = 4
82	A = IntegerMatrix(n, n)
83	# Fill matrix A...
84	A[0] = (1, 0, 0, large_value_1)
85	A[1] = (0, 1, 0, large_value_2)
86	A[2] = (0, 0, 1, large_value_3)
87	A[3] = (0, 0, 0, modulus)
88
89	LLL.reduction(A)
90	print(A[0]) # shortest vector
91	```
92
93	---
94
95	## 3. BKZ (BLOCK KORKINE-ZOLOTAREV)
96
97	### 3.1 Comparison with LLL
98
99	\| Property \| LLL \| BKZ-β \|
100	\|---\|---\|---\|
101	\| Quality \| 2^((n-1)/2) approximation \| 2^(n/(β-1)) approximation \|
102	\| Speed \| Polynomial \| Exponential in β \|
103	\| Block size \| Fixed (2) \| Configurable β \|
104	\| Best for \| Quick reduction \| High-quality reduction \|
105
106	### 3.2 Usage
107
108	```python
109	# SageMath
110	M = matrix(ZZ, [...])
111	L = M.BKZ(block_size=20) # β = 20
112
113	# fpylll
114	from fpylll import BKZ
115	BKZ.reduction(A, BKZ.Param(block_size=20))
116	```
117
118	Rule of thumb: start with LLL, increase to BKZ if needed. BKZ block size 20-40 is usually sufficient for CTF.
119
120	---
121
122	## 4. COPPERSMITH'S METHOD
123
124	### 4.1 Univariate Case
125
126	Given f(x) ≡ 0 (mod N) with small root \|x₀\| < X, find x₀.
127
128	Bound: X < N^(1/d) where d = degree of f.
129
130	```python
131	# SageMath — built-in small_roots
132	N = ...
133	R.<x> = PolynomialRing(Zmod(N))
134	f = x^3 + ax^2 + bx + c # known polynomial
135	roots = f.small_roots(X=2^100, beta=1.0, epsilon=1/30)
136	```
137
138	Parameters:
139	- `X`: upper bound on the root
140	- `beta`: N = p^beta (beta=1.0 for modular root of N itself; beta=0.5 for root mod unknown factor p ≈ √N)
141	- `epsilon`: smaller = better results but slower (try 1/30 to 1/100)
142
143	### 4.2 Stereotyped Message Attack (RSA)
144
145	```python
146	# SageMath
147	n, e, c = ... # RSA parameters
148	known_msb = ... # known upper portion of message
149
150	R.<x> = PolynomialRing(Zmod(n))
151	f = (known_msb + x)^e - c
152
153	# x represents the unknown lower bits
154	X = 2^(unknown_bit_count)
155	roots = f.small_roots(X=X, beta=1.0)
156	if roots:
157	m = known_msb + int(roots[0])
158	```
159
160	### 4.3 Partial Key Exposure (Factor p)
161
162	Known MSBs of p: `p = p_known + x` where x is small.
163
164	```python
165	# SageMath
166	n = ...
167	p_k

People who liked this also viewed

6 picks

Type

lattice-crypto-attacks

91stars8forks

View on GitHub

How to install lattice-crypto-attacks?

prohao42/aimy-skill/lattice-crypto-attacks

$npx -y skills add Prohao42/aimy-skill --skill lattice-crypto-attacks

Installs into the current project.

Summary

Files · 1

View on GitHub

SKILL.md

1	# SKILL: Lattice-Based Cryptanalysis — Expert Attack Playbook
2
3	> 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.
4
5	## 0. RELATED ROUTING
6
7	- [rsa-attack-techniques](../rsa-attack-techniques/SKILL.md) for RSA-specific attacks that use lattice methods (Coppersmith, Boneh-Durfee)
8	- [symmetric-cipher-attacks](../symmetric-cipher-attacks/SKILL.md) for LCG state recovery via lattice
9	- [classical-cipher-analysis](../classical-cipher-analysis/SKILL.md) when lattice methods apply to classical cipher analysis
10
11	### Quick application guide
12
13	\| Problem Type \| Lattice Technique \| Key Parameter \|
14	\|---\|---\|---\|
15	\| RSA small roots \| Coppersmith (LLL on polynomial lattice) \| Root bound X < N^(1/e) \|
16	\| RSA small d \| Boneh-Durfee (multivariate Coppersmith) \| d < N^0.292 \|
17	\| DSA/ECDSA nonce bias \| Hidden Number Problem → CVP \| Bias bits known \|
18	\| Knapsack cipher \| Low-density lattice attack \| Density < 0.9408 \|
19	\| LCG truncated output \| CVP on recurrence lattice \| Unknown bits per output \|
20	\| Subset sum \| LLL reduction on knapsack lattice \| Element size vs count \|
21	\| NTRU key recovery \| Lattice reduction on NTRU lattice \| Dimension and key size \|
22
23	---
24
25	## 1. LATTICE FUNDAMENTALS
26
27	### 1.1 Definitions
28
29	A lattice L is the set of all integer linear combinations of basis vectors:
30
31	```
32	L = { a₁·b₁ + a₂·b₂ + ... + aₙ·bₙ \| aᵢ ∈ ℤ }
33	```
34
35	where b₁, ..., bₙ are linearly independent vectors in ℝᵐ.
36
37	Key problems:
38	- SVP (Shortest Vector Problem): Find the shortest non-zero vector in L
39	- CVP (Closest Vector Problem): Given target t, find v ∈ L closest to t
40	- SVP is NP-hard in general, but LLL finds an approximately short vector in polynomial time
41
42	### 1.2 Lattice Quality Metrics
43
44	```
45	Determinant: det(L) = \|det(B)\| where B is the basis matrix
46	Gaussian heuristic: shortest vector ≈ √(n/(2πe)) · det(L)^(1/n)
47	```
48
49	---
50
51	## 2. LLL ALGORITHM
52
53	### 2.1 What LLL Does
54
55	Takes a lattice basis B and produces a reduced basis B' where:
56	- Vectors are nearly orthogonal
57	- First vector is approximately short (within 2^((n-1)/2) factor of SVP)
58	- Runs in polynomial time: O(n^5 · d · log³ B) where d = dimension, B = max entry size
59
60	### 2.2 SageMath Usage
61
62	```python
63	# SageMath
64	M = matrix(ZZ, [
65	[1, 0, 0, large_value_1],
66	[0, 1, 0, large_value_2],
67	[0, 0, 1, large_value_3],
68	[0, 0, 0, modulus],
69	])
70
71	L = M.LLL()
72	# Short vectors in L reveal the solution
73	short_vector = L[0] # first row is typically shortest
74	```
75
76	### 2.3 Python (fpylll)
77
78	```python
79	from fpylll import IntegerMatrix, LLL
80
81	n = 4
82	A = IntegerMatrix(n, n)
83	# Fill matrix A...
84	A[0] = (1, 0, 0, large_value_1)
85	A[1] = (0, 1, 0, large_value_2)
86	A[2] = (0, 0, 1, large_value_3)
87	A[3] = (0, 0, 0, modulus)
88
89	LLL.reduction(A)
90	print(A[0]) # shortest vector
91	```
92
93	---
94
95	## 3. BKZ (BLOCK KORKINE-ZOLOTAREV)
96
97	### 3.1 Comparison with LLL
98
99	\| Property \| LLL \| BKZ-β \|
100	\|---\|---\|---\|
101	\| Quality \| 2^((n-1)/2) approximation \| 2^(n/(β-1)) approximation \|
102	\| Speed \| Polynomial \| Exponential in β \|
103	\| Block size \| Fixed (2) \| Configurable β \|
104	\| Best for \| Quick reduction \| High-quality reduction \|
105
106	### 3.2 Usage
107
108	```python
109	# SageMath
110	M = matrix(ZZ, [...])
111	L = M.BKZ(block_size=20) # β = 20
112
113	# fpylll
114	from fpylll import BKZ
115	BKZ.reduction(A, BKZ.Param(block_size=20))
116	```
117
118	Rule of thumb: start with LLL, increase to BKZ if needed. BKZ block size 20-40 is usually sufficient for CTF.
119
120	---
121
122	## 4. COPPERSMITH'S METHOD
123
124	### 4.1 Univariate Case
125
126	Given f(x) ≡ 0 (mod N) with small root \|x₀\| < X, find x₀.
127
128	Bound: X < N^(1/d) where d = degree of f.
129
130	```python
131	# SageMath — built-in small_roots
132	N = ...
133	R.<x> = PolynomialRing(Zmod(N))
134	f = x^3 + ax^2 + bx + c # known polynomial
135	roots = f.small_roots(X=2^100, beta=1.0, epsilon=1/30)
136	```
137
138	Parameters:
139	- `X`: upper bound on the root
140	- `beta`: N = p^beta (beta=1.0 for modular root of N itself; beta=0.5 for root mod unknown factor p ≈ √N)
141	- `epsilon`: smaller = better results but slower (try 1/30 to 1/100)
142
143	### 4.2 Stereotyped Message Attack (RSA)
144
145	```python
146	# SageMath
147	n, e, c = ... # RSA parameters
148	known_msb = ... # known upper portion of message
149
150	R.<x> = PolynomialRing(Zmod(n))
151	f = (known_msb + x)^e - c
152
153	# x represents the unknown lower bits
154	X = 2^(unknown_bit_count)
155	roots = f.small_roots(X=X, beta=1.0)
156	if roots:
157	m = known_msb + int(roots[0])
158	```
159
160	### 4.3 Partial Key Exposure (Factor p)
161
162	Known MSBs of p: `p = p_known + x` where x is small.
163
164	```python
165	# SageMath
166	n = ...
167	p_k

People who liked this also viewed

6 picks

Type