{ "cells": [ { "cell_type": "markdown", "id": "lll-000", "metadata": {}, "source": [ "# Chapter 49: LLL — A Step-by-Step Tutorial with Four Applications\n", "\n", "The **Lenstra–Lenstra–Lovász (LLL)** algorithm (1982) is the workhorse of\n", "applied lattice theory. In a single $O(n^4 \\log B)$-time procedure it converts\n", "an arbitrary basis of an integer lattice into a *reduced* basis whose first\n", "vector is provably no more than an exponential factor longer than the actual\n", "shortest lattice vector. That guarantee is, by the standards of NP-hard\n", "problems, almost laughably weak — and yet, applied carefully, LLL has broken\n", "or shaped almost every public-key cryptosystem from the late 1970s onwards:\n", "the Merkle–Hellman knapsack, Coppersmith's RSA-with-stereotyped-messages\n", "attack, the Boneh–Venkatesan attack on the Hidden Number Problem (and hence\n", "biased ECDSA), and most recently it sits underneath every lattice-based\n", "cryptanalytic estimator for ML-KEM and ML-DSA.\n", "\n", "This chapter is the **deep dive** behind W2 of the post-quantum course.\n", "We build LLL bottom-up:\n", "\n", "- **Part I — Mathematics.** Lattices, Gram–Schmidt orthogonalisation,\n", " and the *Hadamard ratio* — a single number that tells us how good a\n", " basis is.\n", "- **Part II — Building blocks.** The two pieces that compose LLL:\n", " size reduction and the Lovász swap condition.\n", "- **Part III — Full algorithm.** Pseudocode, decomposed Python, a worked\n", " 2D example, and the famous Hermite-factor bound.\n", "- **Part IV — Four applications.** Each is a complete, runnable\n", " end-to-end demo with the cryptanalytic punch line at the end.\n", "\n", "```{admonition} Where this fits in the course\n", ":class: tip\n", "Read this chapter alongside W2 (the LLL lecture). It complements the\n", "upstream cryptanalysis-course Chapter 40 (lattice problems) by going\n", "**deeper into the algorithm itself** and then turning around to show\n", "four direct applications. The W1 knapsack key you generated at the end\n", "of [Chapter 46](../w1_landscape/ch46_pqc_landscape.ipynb) is exactly\n", "the input to Application A below.\n", "```\n" ] }, { "cell_type": "markdown", "id": "lll-001", "metadata": {}, "source": [ "## Part I — Mathematical foundations\n", "\n", "### 49.1 Lattices and bases\n", "\n", "A **lattice** $\\mathcal L \\subset \\mathbb R^n$ is the set of all *integer*\n", "linear combinations of $n$ linearly independent vectors $b_1, \\ldots, b_n$:\n", "\n", "$$\n", "\\mathcal L \\;=\\; \\mathcal L(B) \\;=\\; \\Bigl\\{ \\sum_{i=1}^n c_i b_i \\;:\\; c_i \\in \\mathbb Z \\Bigr\\}\n", "$$\n", "\n", "The matrix $B \\in \\mathbb R^{n \\times n}$ whose **rows** are\n", "$b_1, \\ldots, b_n$ is a **basis** of $\\mathcal L$. A lattice has *infinitely\n", "many* bases — any $B' = U B$ with $U \\in \\mathrm{GL}_n(\\mathbb Z)$ (an\n", "integer matrix with $\\det U = \\pm 1$) generates the same lattice. So a\n", "lattice is an *equivalence class* of bases under unimodular row operations.\n", "\n", "The **determinant** (or *covolume*) of the lattice is\n", "\n", "$$\n", "\\det(\\mathcal L) \\;=\\; |\\det B|.\n", "$$\n", "\n", "It is invariant under change of basis: every basis of $\\mathcal L$ has the\n", "same absolute determinant. Geometrically, $\\det \\mathcal L$ is the volume\n", "of the *fundamental parallelepiped* spanned by any basis.\n" ] }, { "cell_type": "code", "execution_count": 1, "id": "lll-002", "metadata": { "execution": { "iopub.execute_input": "2026-05-12T08:45:43.100127Z", "iopub.status.busy": "2026-05-12T08:45:43.099992Z", "iopub.status.idle": "2026-05-12T08:45:43.185733Z", "shell.execute_reply": "2026-05-12T08:45:43.185286Z" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Bad basis B = [[201.0, 37.0], [1648.0, 297.0]]\n", " det L = 1279.0000000000073\n", " basis vector norms = [204.37710243566914, 1674.5485958908448]\n", " shortest non-zero vector found by enumeration: [40.0, 1.0] with norm 40.0125\n" ] } ], "source": [ "# Tiny lattice utilities, used throughout the tutorial.\n", "import numpy as np\n", "import math\n", "from fractions import Fraction\n", "\n", "\n", "def lattice_det(B):\n", " '''Absolute determinant (covolume) of a square integer/float basis.'''\n", " return abs(np.linalg.det(np.array(B, dtype=float)))\n", "\n", "\n", "def shortest_via_enumeration_2d(B, R=10):\n", " '''Find the shortest non-zero vector of a 2D lattice by enumeration.\n", "\n", " Brute-force over c1, c2 in [-R, R]. Only honest for tiny lattices.\n", " '''\n", " B = np.array(B, dtype=float)\n", " best = None\n", " best_norm = float('inf')\n", " for c1 in range(-R, R + 1):\n", " for c2 in range(-R, R + 1):\n", " if c1 == 0 and c2 == 0:\n", " continue\n", " v = c1 * B[0] + c2 * B[1]\n", " n = float(np.linalg.norm(v))\n", " if n < best_norm:\n", " best_norm = n; best = v\n", " return best, best_norm\n", "\n", "\n", "# Demo: a 2D lattice with a deliberately bad basis (almost parallel vectors).\n", "B_bad = [[201.0, 37.0], [1648.0, 297.0]]\n", "print('Bad basis B =', B_bad)\n", "print(' det L =', lattice_det(B_bad))\n", "print(' basis vector norms =',\n", " np.linalg.norm(B_bad, axis=1).tolist())\n", "v_short, n_short = shortest_via_enumeration_2d(B_bad, R=20)\n", "print(' shortest non-zero vector found by enumeration:',\n", " v_short.tolist(), 'with norm', round(n_short, 4))\n" ] }, { "cell_type": "markdown", "id": "lll-003", "metadata": {}, "source": [ "### 49.2 Gram–Schmidt orthogonalisation (GSO)\n", "\n", "LLL's central trick is to **measure** how far a basis is from being\n", "orthogonal, then *make* it more orthogonal one step at a time. The\n", "measurement is the Gram–Schmidt orthogonalisation.\n", "\n", "```{admonition} Definition — GSO of a basis\n", ":class: important\n", "Given $b_1, \\ldots, b_n$, define iteratively:\n", "\n", "$$\n", "\\mu_{i,j} \\;=\\; \\frac{\\langle b_i, b_j^* \\rangle}{\\langle b_j^*, b_j^* \\rangle}\n", "\\quad (j < i),\n", "\\qquad\n", "b_i^* \\;=\\; b_i - \\sum_{j = 0.0\n" ] } ], "source": [ "def gram_schmidt(B):\n", " '''Compute the Gram-Schmidt basis B* and the coefficient matrix mu.\n", "\n", " Inputs\n", " ------\n", " B : array-like (n, m)\n", " Rows are basis vectors (n basis vectors in R^m, with m >= n).\n", "\n", " Returns\n", " -------\n", " Bs : (n, m) ndarray\n", " Orthogonalised basis vectors b_1^*, ..., b_n^*.\n", " mu : (n, n) ndarray\n", " Lower-triangular matrix of GSO coefficients (mu[i, j] = mu_{i, j}).\n", " The diagonal is set to 1 and the upper triangle to 0 by convention.\n", " '''\n", " B = np.array(B, dtype=float)\n", " n = B.shape[0]\n", " Bs = np.zeros_like(B)\n", " mu = np.zeros((n, n)) # only the lower triangle is filled\n", " for i in range(n):\n", " Bs[i] = B[i].copy()\n", " for j in range(i):\n", " denom = float(Bs[j] @ Bs[j])\n", " mu[i, j] = float(B[i] @ Bs[j]) / denom if denom > 0 else 0.0\n", " Bs[i] = Bs[i] - mu[i, j] * Bs[j]\n", " return Bs, mu\n", "\n", "\n", "# Sanity check: B*[i] is orthogonal to B*[j] for j < i.\n", "B = [[2.0, 0.0], [3.0, 1.0]]\n", "Bs, mu = gram_schmidt(B)\n", "print('B =', B)\n", "print('B* =', Bs.tolist())\n", "print('mu =', mu.tolist())\n", "print('orthogonality check =', float(Bs[0] @ Bs[1]))\n" ] }, { "cell_type": "markdown", "id": "lll-005", "metadata": {}, "source": [ "### 49.3 The Hadamard ratio\n", "\n", "How orthogonal is a basis? The standard scalar measure is the **Hadamard\n", "ratio**:\n", "\n", "$$\n", "H(B) \\;=\\; \\left( \\frac{\\det(\\mathcal L)}{\\prod_{i=1}^n \\|b_i\\|} \\right)^{1/n}\n", "\\;\\in\\; (0, 1].\n", "$$\n", "\n", "It is $1$ when $B$ is perfectly orthogonal (Hadamard's inequality is\n", "tight) and tends to $0$ as $B$ becomes more parallel (skewed). LLL pushes\n", "$H(B)$ towards $1$.\n" ] }, { "cell_type": "code", "execution_count": 3, "id": "lll-006", "metadata": { "execution": { "iopub.execute_input": "2026-05-12T08:45:43.190807Z", "iopub.status.busy": "2026-05-12T08:45:43.190738Z", "iopub.status.idle": "2026-05-12T08:45:43.192873Z", "shell.execute_reply": "2026-05-12T08:45:43.192480Z" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Bad basis : H = 0.0611\n" ] } ], "source": [ "def hadamard_ratio(B):\n", " '''Return H(B) in (0, 1], a quality measure of the basis B.\n", "\n", " 1.0 = perfectly orthogonal; near 0 = very skewed.\n", " '''\n", " B = np.array(B, dtype=float)\n", " n = B.shape[0]\n", " det = abs(np.linalg.det(B))\n", " norms_prod = np.prod(np.linalg.norm(B, axis=1))\n", " if norms_prod == 0: return 0.0\n", " return (det / norms_prod) ** (1.0 / n)\n", "\n", "\n", "# Demo on the bad basis we built earlier.\n", "print('Bad basis : H =', round(hadamard_ratio(B_bad), 4))\n", "\n", "# A perfectly orthogonal basis of the same lattice would have H = 1.\n", "# Hint: the shortest vector found above plus another short independent vector\n", "# would be near-orthogonal. We will reach this end via LLL in §49.6.\n" ] }, { "cell_type": "markdown", "id": "lll-007", "metadata": {}, "source": [ "## Part II — The two LLL building blocks\n", "\n", "### 49.4 Size reduction\n", "\n", "Once we have the GSO, we can reduce the size of a basis vector $b_i$\n", "**without leaving the lattice** by subtracting integer multiples of\n", "earlier basis vectors. Concretely:\n", "\n", "```{admonition} Size-reduction step (single $i$, single $j < i$)\n", ":class: important\n", "If $|\\mu_{i,j}| > 1/2$, replace\n", "\n", "$$\n", "b_i \\;\\leftarrow\\; b_i - \\lfloor \\mu_{i,j} \\rceil \\, b_j,\n", "$$\n", "\n", "where $\\lfloor \\cdot \\rceil$ is rounding to the nearest integer. After\n", "this, the new $\\mu_{i,j}$ has $|\\mu_{i,j}| \\le 1/2$. The lattice is\n", "unchanged. The other GSO coefficients $\\mu_{i, k}$ for $k < j$ also\n", "update accordingly.\n", "```\n", "\n", "A basis is **size-reduced** when *every* $|\\mu_{i,j}| \\le 1/2$ for\n", "$j < i$. Geometrically, every basis vector lies inside the\n", "\"Voronoi-ish\" region around its earlier orthogonal projection, so no\n", "vector overshoots.\n" ] }, { "cell_type": "code", "execution_count": 4, "id": "lll-008", "metadata": { "execution": { "iopub.execute_input": "2026-05-12T08:45:43.193700Z", "iopub.status.busy": "2026-05-12T08:45:43.193646Z", "iopub.status.idle": "2026-05-12T08:45:43.195983Z", "shell.execute_reply": "2026-05-12T08:45:43.195708Z" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "before norms = [204.377, 1674.549] H = 0.061\n", "after norms = [204.377, 40.012] H = 0.395\n" ] } ], "source": [ "def size_reduce(B, mu):\n", " '''Apply size reduction in place. Mutates B and mu and returns them.\n", "\n", " Walks i from 1 to n-1; for each i, subtracts integer multiples of\n", " earlier basis vectors so that |mu_{i, j}| <= 1/2 for every j < i.\n", " The lattice is unchanged: only the choice of basis shifts.\n", " '''\n", " n = B.shape[0]\n", " for i in range(1, n):\n", " for j in range(i - 1, -1, -1):\n", " q = round(mu[i, j])\n", " if q != 0:\n", " B[i] = B[i] - q * B[j]\n", " # mu[j, j] is conventionally 0 in our representation, so the\n", " # vector update touches only positions strictly less than j;\n", " # the position-j entry decreases by exactly q (the +1 implicit\n", " # diagonal of b_j against itself).\n", " mu[i, :j] = mu[i, :j] - q * mu[j, :j]\n", " mu[i, j] = mu[i, j] - q\n", " return B, mu\n", "\n", "\n", "# Demo: take the bad basis, size-reduce, observe shorter b_2.\n", "B = np.array(B_bad, dtype=float)\n", "Bs, mu = gram_schmidt(B)\n", "print('before norms =', np.round(np.linalg.norm(B, axis=1), 3).tolist(),\n", " ' H =', round(hadamard_ratio(B), 3))\n", "B, mu = size_reduce(B, mu)\n", "print('after norms =', np.round(np.linalg.norm(B, axis=1), 3).tolist(),\n", " ' H =', round(hadamard_ratio(B), 3))\n" ] }, { "cell_type": "markdown", "id": "lll-009", "metadata": {}, "source": [ "### 49.5 The Lovász condition\n", "\n", "Size reduction alone is not enough — it cannot **swap** two vectors. To\n", "make any progress on the *length* of $b_1$, LLL also needs a *swap test*:\n", "\n", "```{admonition} Definition — Lovász condition (parameter $\\delta \\in (1/4, 1)$)\n", ":class: important\n", "The pair $(b_{k-1}, b_k)$ satisfies the **$\\delta$-Lovász condition** iff\n", "\n", "$$\n", "\\|b_k^*\\|^2 \\;\\ge\\; \\bigl(\\delta - \\mu_{k, k-1}^2\\bigr) \\, \\|b_{k-1}^*\\|^2.\n", "$$\n", "\n", "If the condition **fails**, swap $b_{k-1}$ and $b_k$ (and update the GSO\n", "on the fly). If it **holds**, leave them and move on.\n", "```\n", "\n", "The traditional textbook value is $\\delta = 3/4$, which gives the standard\n", "worst-case approximation factor $2^{(n-1)/2}$. Larger $\\delta$ ($\\to 1$)\n", "yields better-quality output at higher running cost.\n", "\n", "```{admonition} Why this is the right condition\n", ":class: tip\n", "After size reduction, $\\|b_k\\|^2 = \\|b_k^*\\|^2 + \\mu_{k,k-1}^2 \\|b_{k-1}^*\\|^2$.\n", "If we swap $b_{k-1}$ and $b_k$, the *new* $b_{k-1}^*$ becomes $b_k$\n", "itself (because nothing earlier than $k-1$ was orthogonalised against it).\n", "The Lovász condition is exactly the condition that **the new $\\|b_{k-1}^*\\|$\n", "is no more than $1/\\sqrt{\\delta}$ times the old one** — i.e. the swap\n", "*shrinks* the leading orthogonal vector by at least a constant factor.\n", "That gives the polynomial-time termination guarantee.\n", "```\n" ] }, { "cell_type": "markdown", "id": "lll-010", "metadata": {}, "source": [ "## Part III — The full algorithm\n", "\n", "### 49.6 Pseudocode\n", "\n", "```\n", "LLL(B, delta):\n", " n = number of basis vectors\n", " (B*, mu) = gram_schmidt(B)\n", " k = 1\n", " while k < n:\n", " size_reduce(B, mu) # only on row k, suffices\n", " if Lovasz(B*, mu, k, delta):\n", " k = k + 1\n", " else:\n", " swap(B[k-1], B[k])\n", " (B*, mu) = gram_schmidt(B) # refresh\n", " k = max(k - 1, 1)\n", " return B\n", "```\n", "\n", "We now translate this directly into Python.\n" ] }, { "cell_type": "code", "execution_count": 5, "id": "lll-011", "metadata": { "execution": { "iopub.execute_input": "2026-05-12T08:45:43.197083Z", "iopub.status.busy": "2026-05-12T08:45:43.197005Z", "iopub.status.idle": "2026-05-12T08:45:43.200920Z", "shell.execute_reply": "2026-05-12T08:45:43.200650Z" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ " swap, total swaps so far = 1\n", " swap, total swaps so far = 2\n", "Reduced basis: [[1, 32], [40, 1]]\n", " norms = [32.016, 40.012]\n", " H = 0.999\n", " swaps = 2\n" ] } ], "source": [ "def lll(B, delta=0.75, verbose=False):\n", " '''The Lenstra-Lenstra-Lovasz algorithm.\n", "\n", " Internally we keep B as a list-of-lists of **Python ints** (so it is\n", " exact even when entries exceed 2^53), and use Python floats only for\n", " the GSO scratch arrays. That is enough for exact size reduction and\n", " a reliable Lovasz-condition comparison out to ~64-bit basis entries.\n", " For very-large-entry lattices a Fraction-based mu would be required.\n", "\n", " Parameters\n", " ----------\n", " B : array-like (n, m)\n", " Initial basis with n basis vectors in R^m (rows).\n", " delta : float in (1/4, 1)\n", " Quality / runtime trade-off. 3/4 is the textbook value.\n", "\n", " Returns\n", " -------\n", " B_red : list of lists of int\n", " A delta-LLL-reduced basis of the SAME lattice.\n", " swaps : int\n", " Number of swap operations performed.\n", " '''\n", " # Keep B as ints; if input was float-array, round.\n", " B = [[int(round(x)) for x in row] for row in (\n", " B.tolist() if isinstance(B, np.ndarray) else B)]\n", " n_rows = len(B)\n", "\n", " def gso():\n", " '''Recompute GSO Bs (float) and mu (float) from the current int B.'''\n", " Bs = [[float(x) for x in row] for row in B]\n", " mu = [[0.0] * n_rows for _ in range(n_rows)]\n", " for i in range(n_rows):\n", " for j in range(i):\n", " denom = sum(s * s for s in Bs[j])\n", " if denom > 0:\n", " mu[i][j] = sum(B[i][c] * Bs[j][c] for c in range(len(B[i]))) / denom\n", " for c in range(len(Bs[i])):\n", " Bs[i][c] -= mu[i][j] * Bs[j][c]\n", " return Bs, mu\n", "\n", " Bs, mu = gso()\n", " k = 1\n", " swaps = 0\n", " while k < n_rows:\n", " # 1. Size-reduce row k against all earlier rows (exact integer ops on B).\n", " for j in range(k - 1, -1, -1):\n", " q = round(mu[k][j])\n", " if q != 0:\n", " for c in range(len(B[k])):\n", " B[k][c] -= q * B[j][c]\n", " for c in range(j):\n", " mu[k][c] -= q * mu[j][c]\n", " mu[k][j] -= q\n", "\n", " # 2. Lovasz condition.\n", " lhs = sum(s * s for s in Bs[k])\n", " rhs = (delta - mu[k][k-1] ** 2) * sum(s * s for s in Bs[k-1])\n", " if lhs >= rhs:\n", " k += 1\n", " else:\n", " B[k], B[k-1] = B[k-1], B[k]\n", " swaps += 1\n", " Bs, mu = gso()\n", " k = max(k - 1, 1)\n", " if verbose:\n", " print(f' swap, total swaps so far = {swaps}')\n", " return B, swaps\n", "\n", "\n", "# Sanity: run on the bad 2D lattice.\n", "B_red, swaps = lll(B_bad, delta=0.75, verbose=True)\n", "B_red_np = np.array(B_red, dtype=float)\n", "print('Reduced basis:', B_red)\n", "print(' norms =', np.round(np.linalg.norm(B_red_np, axis=1), 3).tolist())\n", "print(' H =', round(hadamard_ratio(B_red_np), 3))\n", "print(' swaps =', swaps)\n" ] }, { "cell_type": "markdown", "id": "lll-012", "metadata": {}, "source": [ "### 49.7 Worked example — a deliberately bad 2D lattice\n", "\n", "We picked the basis $b_1 = (201, 37)$, $b_2 = (1648, 297)$ to be\n", "*almost parallel*. The Hadamard ratio of the input basis was\n", "$\\approx 0.001$ — terrible. After LLL we expect (a) much shorter\n", "basis vectors, (b) Hadamard ratio close to 1, and (c) the first\n", "output vector to coincide (up to sign) with the actual shortest\n", "non-zero lattice vector.\n" ] }, { "cell_type": "code", "execution_count": 6, "id": "lll-013", "metadata": { "execution": { "iopub.execute_input": "2026-05-12T08:45:43.201840Z", "iopub.status.busy": "2026-05-12T08:45:43.201785Z", "iopub.status.idle": "2026-05-12T08:45:43.237071Z", "shell.execute_reply": "2026-05-12T08:45:43.236704Z" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ " basis 1 vector norm basis 2 vector norm H\n", " in: [201.0, 37.0] 204.38 [1648.0, 297.0] 1674.55 0.061\n", " out: [1, 32] 32.02 [40, 1] 40.01 0.999\n", "\n", "shortest non-zero vector by enumeration: [-1.0, -32.0] with norm 32.016\n", "LLL b_1 norm vs enumeration shortest: 32.016 vs 32.016 \n" ] } ], "source": [ "# Quantitative comparison.\n", "B_in = np.array(B_bad, dtype=float)\n", "B_red, _ = lll(B_in, delta=0.75)\n", "B_red_np = np.array(B_red, dtype=float)\n", "# Brute-force enumeration with a wide window so we definitely see the optimum.\n", "v_short, _ = shortest_via_enumeration_2d(B_in, R=60)\n", "\n", "print(' basis 1 vector norm basis 2 vector norm H')\n", "print(' in: ', B_in[0].tolist(), '%7.2f' % np.linalg.norm(B_in[0]),\n", " ' ', B_in[1].tolist(), '%7.2f' % np.linalg.norm(B_in[1]),\n", " ' %.3f' % hadamard_ratio(B_in))\n", "print(' out:', B_red[0], '%7.2f' % np.linalg.norm(B_red_np[0]),\n", " ' ', B_red[1], '%7.2f' % np.linalg.norm(B_red_np[1]),\n", " ' %.3f' % hadamard_ratio(B_red_np))\n", "print()\n", "print('shortest non-zero vector by enumeration:',\n", " v_short.tolist(), 'with norm', round(np.linalg.norm(v_short), 3))\n", "print('LLL b_1 norm vs enumeration shortest:',\n", " f'{np.linalg.norm(B_red_np[0]):.3f} vs {np.linalg.norm(v_short):.3f}',\n", " ' -> LLL beat enumeration!' if np.linalg.norm(B_red_np[0]) <\n", " np.linalg.norm(v_short) - 1e-3 else '')\n" ] }, { "cell_type": "markdown", "id": "lll-014", "metadata": {}, "source": [ "### 49.8 The Hermite-factor guarantee\n", "\n", "```{admonition} Theorem — LLL approximation factor\n", ":class: important\n", "Let $B$ be the output of LLL with parameter $\\delta = 3/4$. Then\n", "\n", "$$\n", "\\|b_1\\| \\;\\le\\; 2^{(n-1)/2} \\cdot \\lambda_1(\\mathcal L)\n", "$$\n", "\n", "where $\\lambda_1(\\mathcal L)$ is the actual shortest-vector length. The\n", "constant $2^{(n-1)/2}$ is the *worst-case* **Hermite factor**.\n", "```\n", "\n", "In *practice*, on random lattices, LLL outputs a first vector within a\n", "factor $\\delta_{LLL}^n$ of $\\lambda_1$ where $\\delta_{LLL} \\approx 1.0219$\n", "empirically. That's the **root-Hermite factor**. So for $n = 100$ LLL\n", "typically achieves a factor $\\approx 8$, not $2^{50}$ — much better than\n", "the worst case.\n", "\n", "The running time is $O(n^4 \\log B_{\\max})$ classical, where $B_{\\max}$\n", "is the largest input entry.\n" ] }, { "cell_type": "markdown", "id": "lll-015", "metadata": {}, "source": [ "## Part IV — Four direct applications\n", "\n", "We now turn LLL on four cryptanalytically interesting problems.\n", "Each application is **complete**: setup, lattice construction,\n", "Python, and verification.\n" ] }, { "cell_type": "markdown", "id": "lll-016", "metadata": {}, "source": [ "### Application A — Breaking the Merkle–Hellman knapsack\n", "\n", "This is the bridge from W1 to W2 of the course. Given a low-density\n", "Merkle–Hellman public key $a_1, \\ldots, a_n$ and a ciphertext $S$, we\n", "want to recover the plaintext bit-vector $\\mathbf x \\in \\{0, 1\\}^n$ such\n", "that $\\sum x_i a_i = S$.\n", "\n", "```{admonition} Lagarias–Odlyzko (1985) lattice\n", ":class: important\n", "Build the $(n+1) \\times (n+1)$ lattice with rows\n", "\n", "$$\n", "b_i \\;=\\; (\\underbrace{0, \\ldots, 0, 2}_{\\text{position } i}, 0, \\ldots, 0,\\; 2 a_i)\n", "\\quad (i = 1, \\ldots, n),\n", "\\qquad\n", "b_{n+1} \\;=\\; (1, 1, \\ldots, 1,\\; 2 S).\n", "$$\n", "\n", "Any $\\mathbf c \\in \\{0, 1\\}^n$ with $\\sum c_i a_i = S$ corresponds to a\n", "short lattice vector $v = -\\sum c_i b_i + b_{n+1}$ whose first $n$\n", "coordinates are $\\pm 1$ and last coordinate is $0$. LLL finds it for\n", "densities $d \\lesssim 0.94$ (Coster–Joux–LaMacchia–Odlyzko–Schnorr–Stern\n", "1992).\n", "```\n" ] }, { "cell_type": "code", "execution_count": 7, "id": "lll-017", "metadata": { "execution": { "iopub.execute_input": "2026-05-12T08:45:43.238157Z", "iopub.status.busy": "2026-05-12T08:45:43.238086Z", "iopub.status.idle": "2026-05-12T08:45:43.246782Z", "shell.execute_reply": "2026-05-12T08:45:43.246484Z" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "n = 10, plaintext = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]\n", "density d = n / log2(max a) = 0.250\n", "ciphertext S = 5587552117795\n", "\n", "LLL on the 11-dim LO lattice (53 swaps)\n", "recovered = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]\n", "truth = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]\n", " -> Lagarias-Odlyzko via LLL succeeded.\n" ] } ], "source": [ "# A. Build a low-density Merkle-Hellman keypair, encrypt, then break with LLL.\n", "import random as _r\n", "\n", "def merkle_hellman_keygen(n=10, target_bits=40, seed=0):\n", " rng = _r.Random(seed)\n", " w = [rng.randrange(2, 10)]\n", " for _ in range(n - 1):\n", " w.append(sum(w) + rng.randrange(1, 10))\n", " m = max(sum(w) + rng.randrange(1, 100), 1 << target_bits)\n", " while True:\n", " r = rng.randrange(2, m)\n", " if math.gcd(r, m) == 1: break\n", " a = [(r * wi) % m for wi in w]\n", " return a, w, m, r\n", "\n", "def encrypt(a, bits):\n", " return sum(b * ai for b, ai in zip(bits, a))\n", "\n", "def lo_lattice(a, S):\n", " '''The (n+1)x(n+1) Lagarias-Odlyzko lattice for the knapsack (a, S).'''\n", " n = len(a)\n", " L = [[0] * (n + 1) for _ in range(n + 1)]\n", " for i in range(n):\n", " L[i][i] = 2\n", " L[i][n] = 2 * a[i]\n", " for j in range(n):\n", " L[n][j] = 1\n", " L[n][n] = 2 * S\n", " return L\n", "\n", "def bits_from_short_vec(v, n):\n", " '''Recover (0/1)-bits from the +/-1 entries of a short LO-lattice vector.'''\n", " out = []\n", " for x in v[:n]:\n", " xi = int(round(x))\n", " if xi == 1: out.append(0)\n", " elif xi == -1: out.append(1)\n", " else: return None\n", " return out\n", "\n", "\n", "# Demo.\n", "n = 10\n", "a, w_secret, m_secret, r_secret = merkle_hellman_keygen(n=n, target_bits=40, seed=42)\n", "plain = [_r.Random(7).randrange(2) for _ in range(n)]\n", "S = encrypt(a, plain)\n", "print(f'n = {n}, plaintext = {plain}')\n", "print(f'density d = n / log2(max a) = {n / max(a).bit_length():.3f}')\n", "print(f'ciphertext S = {S}')\n", "\n", "L = np.array(lo_lattice(a, S), dtype=float)\n", "L_red, swaps = lll(L, delta=0.75)\n", "print(f'\\nLLL on the {n+1}-dim LO lattice ({swaps} swaps)')\n", "\n", "recovered = None\n", "for row in L_red:\n", " if abs(row[-1]) > 1e-6: continue # need last coord = 0\n", " bits = bits_from_short_vec(row, n)\n", " if bits is None: bits = bits_from_short_vec(-row, n)\n", " if bits is not None: recovered = bits; break\n", "\n", "print(f'recovered = {recovered}')\n", "print(f'truth = {plain}')\n", "assert recovered == plain\n", "print(' -> Lagarias-Odlyzko via LLL succeeded.')\n" ] }, { "cell_type": "markdown", "id": "lll-018", "metadata": {}, "source": [ "### Application B — Coppersmith's small-root attack on RSA\n", "\n", "In 1996 Don Coppersmith showed that an integer polynomial $f \\in \\mathbb Z[x]$\n", "of degree $d$ has all its small roots modulo $N$ recoverable in polynomial\n", "time, provided the roots satisfy $|x_0| \\lesssim N^{1/d}$. The construction\n", "uses LLL on a lattice of polynomial-coefficient vectors.\n", "\n", "The cleanest cryptographic application: **stereotyped RSA messages**.\n", "Suppose Alice sends $c = m^e \\bmod N$ with $e = 3$ (low public exponent),\n", "and Eve already knows the *high-order* bits of $m$. Write $m = m_0 + x$\n", "with $|x| < 2^{B}$ small. Then $f(x) = (m_0 + x)^3 - c$ has $x$ as a small\n", "root mod $N$, and Coppersmith's theorem recovers it.\n", "\n", "We give a textbook 1-polynomial Coppersmith demo (no Howgrave-Graham\n", "shifting). It works whenever $|x| < N^{1/3}$, i.e. roughly when 1/3 of\n", "the message is unknown.\n" ] }, { "cell_type": "code", "execution_count": 8, "id": "lll-019", "metadata": { "execution": { "iopub.execute_input": "2026-05-12T08:45:43.247772Z", "iopub.status.busy": "2026-05-12T08:45:43.247700Z", "iopub.status.idle": "2026-05-12T08:45:43.256358Z", "shell.execute_reply": "2026-05-12T08:45:43.256030Z" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "modulus N = 10000004400000259 (~54-bit, N^(1/6) ~ 464)\n", "true m = 1234567890\n", "known high = 1234567680 (low 8 bits unknown, |x| < 256)\n", "ciphertext = 1866831500483285\n", "recovered low x = 210\n", "truth low x = 210\n", " -> Coppersmith via LLL recovered the unknown low bits.\n" ] } ], "source": [ "# B. Coppersmith small-root attack on RSA, e=3.\n", "def coppersmith_small_root(f_coeffs, N, X):\n", " '''Recover an integer root |x0| < X of f(x) = 0 (mod N), where\n", " f_coeffs gives the coefficients in INCREASING degree (f_0, f_1, ..., f_d).\n", "\n", " Single-polynomial Coppersmith. Builds the lattice\n", " rows N * X^i e_i for i = 0 .. d-1 (the \"Hensel\" rows)\n", " X^i * f(xX) coefficient row scaled\n", " Runs LLL, reads off a small integer-coefficient polynomial vanishing\n", " at x0, finds its real roots, and returns the integer one.\n", " '''\n", " f = list(f_coeffs)\n", " d = len(f) - 1 # polynomial degree\n", "\n", " # Build (d+1)x(d+1) lattice. Row i (for i < d) is X^i * N * e_i.\n", " # Last row is the coefficients of f(xX).\n", " L = [[0] * (d + 1) for _ in range(d + 1)]\n", " for i in range(d):\n", " L[i][i] = N * (X ** i)\n", " for i in range(d + 1):\n", " L[d][i] = f[i] * (X ** i)\n", " L = np.array(L, dtype=object) # big-int safe\n", "\n", " L_red, _ = lll(L.astype(float), delta=0.75)\n", "\n", " # Read out the smallest-norm reduced row -> g(x) = sum (row[i] / X^i) x^i.\n", " # Pick the LLL-reduced row with smallest Euclidean norm.\n", " norms = [float(np.linalg.norm(r)) for r in L_red]\n", " g_scaled = L_red[int(np.argmin(norms))]\n", " g = [int(g_scaled[i]) // (X ** i) if X**i else 0 for i in range(d + 1)]\n", " # Numpy roots: pass coefficients in DECREASING order.\n", " g_np = np.array(g[::-1], dtype=float)\n", " if abs(g_np[0]) < 1e-9: g_np = g_np[1:]\n", " roots = np.roots(g_np) if len(g_np) > 1 else []\n", " candidates = [int(round(r.real)) for r in roots if abs(r.imag) < 1e-3]\n", " for x0 in candidates:\n", " if abs(x0) <= X:\n", " # check we hit the original f mod N\n", " val = sum(c * (x0 ** i) for i, c in enumerate(f)) % N\n", " if val == 0:\n", " return x0\n", " return None\n", "\n", "\n", "# Demo: RSA with e=3 and a stereotyped message.\n", "#\n", "# Single-polynomial Coppersmith (no Howgrave-Graham shifts) has a TIGHT bound:\n", "# X < N^{2 / (d (d+1))}\n", "# For d = 3 that is X < N^{1/6}. We pick a 53-bit toy N so that 8-bit unknowns\n", "# fit comfortably inside the bound (N^{1/6} ~= 460 > 256 = 2^8). Real attacks\n", "# extend this with shifted polynomials to reach X < N^{1/d - eps}.\n", "p, q = 100000007, 100000037\n", "N = p * q # ~10^16 (53-bit) toy modulus\n", "e = 3\n", "m_true = 1234567890 # the secret message\n", "c = pow(m_true, e, N)\n", "\n", "# Eve knows the high bits of m: m = m_high + x with |x| < 2^8.\n", "unknown_bits = 8\n", "unknown_bound = 1 << unknown_bits\n", "m_high = (m_true >> unknown_bits) << unknown_bits # zero out low bits\n", "print(f'modulus N = {N} (~{N.bit_length()}-bit, N^(1/6) ~ {round(N ** (1/6))})')\n", "print(f'true m = {m_true}')\n", "print(f'known high = {m_high} (low {unknown_bits} bits unknown, |x| < {unknown_bound})')\n", "print(f'ciphertext = {c}')\n", "\n", "# f(x) = (m_high + x)^3 - c (mod N) has x_true = m_true - m_high as small root.\n", "# Expand: a + b*x + c1*x^2 + d*x^3 where a = m_high^3 - c, b = 3*m_high^2,\n", "# c1 = 3*m_high, d = 1.\n", "f0 = (m_high ** 3 - c) % N\n", "f1 = (3 * m_high ** 2) % N\n", "f2 = (3 * m_high) % N\n", "f3 = 1\n", "x0 = coppersmith_small_root([f0, f1, f2, f3], N, unknown_bound)\n", "print(f'recovered low x = {x0}')\n", "print(f'truth low x = {m_true - m_high}')\n", "assert x0 == m_true - m_high\n", "print(' -> Coppersmith via LLL recovered the unknown low bits.')\n" ] }, { "cell_type": "markdown", "id": "lll-020", "metadata": {}, "source": [ "### Application C — Integer relation detection\n", "\n", "Given approximate real numbers $\\alpha_1, \\ldots, \\alpha_n$, an **integer\n", "relation** is a non-zero $\\mathbf c \\in \\mathbb Z^n$ with\n", "$\\sum c_i \\alpha_i = 0$ (or $\\approx 0$ at floating-point precision).\n", "Finding such a relation is how a CAS *guesses* closed forms — the\n", "PSLQ algorithm is famous for this, but **LLL works almost as well**.\n", "\n", "Construct the lattice with rows\n", "\n", "$$\n", "b_i \\;=\\; (\\underbrace{0, \\ldots, 0, 1}_{\\text{position } i}, 0, \\ldots, 0,\\; \\lceil M \\alpha_i \\rceil)\n", "$$\n", "\n", "where $M$ is a large *precision multiplier*. A short vector\n", "$v = \\sum c_i b_i$ in this lattice has the form\n", "$(c_1, \\ldots, c_n,\\; M \\sum c_i \\alpha_i)$. If a true relation exists,\n", "the last coordinate is *small* (hence $v$ is short), and LLL finds it.\n", "\n", "Demo: rediscover that $\\alpha = \\sqrt 2$ satisfies $\\alpha^2 - 2 = 0$,\n", "given only the decimal expansion of $\\alpha$.\n" ] }, { "cell_type": "code", "execution_count": 9, "id": "lll-021", "metadata": { "execution": { "iopub.execute_input": "2026-05-12T08:45:43.257203Z", "iopub.status.busy": "2026-05-12T08:45:43.257144Z", "iopub.status.idle": "2026-05-12T08:45:43.260269Z", "shell.execute_reply": "2026-05-12T08:45:43.259911Z" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "alpha = sqrt(2) ~= 1.4142135623730951\n", "integer relation among (alpha^2, alpha, 1): [-1, 0, 2]\n", "check: -1 * alpha^2 + 0 * alpha + 2 = -4.44e-16\n", "\n", "phi = (1+sqrt 5)/2 ~= 1.618033988749895\n", "integer relation among (phi^2, phi, 1): [-1, 1, 1]\n", "check: -1 * phi^2 + 1 * phi + 1 = 0.00e+00\n" ] } ], "source": [ "# C. Integer relation detection: discover that sqrt(2) satisfies x^2 = 2.\n", "def integer_relation(alphas, M=10**12):\n", " '''Find a small integer relation among the real numbers in `alphas`.\n", "\n", " Returns (c_1, ..., c_n) such that sum c_i * alphas[i] is approximately 0,\n", " or None if LLL finds no plausibly-short relation.\n", " '''\n", " n = len(alphas)\n", " L = [[0] * (n + 1) for _ in range(n)]\n", " for i in range(n):\n", " L[i][i] = 1\n", " L[i][n] = int(round(M * alphas[i]))\n", " L = np.array(L, dtype=float)\n", " L_red, _ = lll(L, delta=0.75)\n", " # The shortest reduced row should have small last coord.\n", " candidates = sorted(L_red, key=lambda r: abs(r[-1]))\n", " best = candidates[0]\n", " return [int(x) for x in best[:n]]\n", "\n", "\n", "# alpha = sqrt(2); ask for a relation among (alpha^2, alpha, 1).\n", "alpha = math.sqrt(2)\n", "relation = integer_relation([alpha ** 2, alpha, 1], M=10 ** 12)\n", "print(f'alpha = sqrt(2) ~= {alpha}')\n", "print(f'integer relation among (alpha^2, alpha, 1): {relation}')\n", "print(f'check: {relation[0]} * alpha^2 + {relation[1]} * alpha + {relation[2]} '\n", " f'= {relation[0] * alpha ** 2 + relation[1] * alpha + relation[2]:.2e}')\n", "print()\n", "\n", "# Same trick for the golden ratio: phi^2 - phi - 1 = 0.\n", "phi = (1 + math.sqrt(5)) / 2\n", "relation = integer_relation([phi ** 2, phi, 1], M=10 ** 12)\n", "print(f'phi = (1+sqrt 5)/2 ~= {phi}')\n", "print(f'integer relation among (phi^2, phi, 1): {relation}')\n", "print(f'check: {relation[0]} * phi^2 + {relation[1]} * phi + {relation[2]} '\n", " f'= {relation[0] * phi ** 2 + relation[1] * phi + relation[2]:.2e}')\n" ] }, { "cell_type": "markdown", "id": "lll-022", "metadata": {}, "source": [ "### Application D — Hidden Number Problem (biased ECDSA nonces)\n", "\n", "The most cryptanalytically dramatic LLL application: **recovering an\n", "ECDSA secret key from biased nonces**. This is exactly the bug behind\n", "the PlayStation 3 firmware-signing key compromise (Sony reused\n", "nonces, but a partial-bias variant breaks the same way).\n", "\n", "```{admonition} Setup\n", ":class: important\n", "ECDSA signs $h_i = H(m_i)$ as $r_i = (k_i G)_x \\bmod n$ and\n", "$s_i = k_i^{-1} (h_i + r_i \\cdot d) \\bmod n$. Solving for $k_i$:\n", "\n", "$$\n", "k_i \\;\\equiv\\; s_i^{-1} h_i \\;+\\; (s_i^{-1} r_i)\\, d \\pmod n.\n", "$$\n", "\n", "If for some leak reason the most significant $\\ell$ bits of every $k_i$\n", "are zero — so $k_i < B := n / 2^\\ell$ — then for every signature\n", "\n", "$$\n", "t_i \\cdot d \\;-\\; k_i \\;\\equiv\\; -u_i \\pmod n,\n", "\\qquad t_i := s_i^{-1} r_i,\\;\\; u_i := s_i^{-1} h_i.\n", "$$\n", "\n", "That is the **Hidden Number Problem**: recover $d$ given many $(t_i,\n", "u_i)$ and the promise that $t_i d + u_i$ has small residue $k_i$ mod $n$.\n", "```\n", "\n", "Build the $(m+1) \\times (m+1)$ Boneh–Venkatesan lattice (rows = basis):\n", "\n", "$$\n", "\\begin{pmatrix}\n", "n & 0 & \\cdots & 0 & 0 \\\\\n", "0 & n & \\cdots & 0 & 0 \\\\\n", "\\vdots & & \\ddots & & \\vdots \\\\\n", "0 & 0 & \\cdots & n & 0 \\\\\n", "t_1 & t_2 & \\cdots & t_m & B/n\n", "\\end{pmatrix}\n", "$$\n", "\n", "A vector $(k_1, k_2, \\ldots, k_m, d \\cdot B / n) - (\\text{shift by }\n", "\\mathbf u)$ has all entries small. LLL on the lattice with target the\n", "shift recovers it (Babai's nearest-plane reduces CVP to LLL, but for\n", "demo we use the simpler embedding).\n" ] }, { "cell_type": "code", "execution_count": 10, "id": "lll-023", "metadata": { "execution": { "iopub.execute_input": "2026-05-12T08:45:43.261140Z", "iopub.status.busy": "2026-05-12T08:45:43.261082Z", "iopub.status.idle": "2026-05-12T08:45:45.073499Z", "shell.execute_reply": "2026-05-12T08:45:45.073151Z" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "toy group order n ~ 2^32 (32 bits, prime)\n" ] }, { "name": "stdout", "output_type": "stream", "text": [ "LLL on 41-dim BV lattice (416 swaps)\n", "best d candidate = 0xcafebabe (max bias = 15987859 = ~0.95 * B)\n", "recovered (passes B) = 0xcafebabe\n", "truth = 0xcafebabe\n", " -> Hidden number recovered from biased modular hints.\n" ] } ], "source": [ "# D. Hidden Number Problem -> recover a secret from biased modular hints.\n", "#\n", "# Setup (bias-only HNP). Given an unknown d in [0, n) and many random\n", "# multipliers t_i, suppose the residues\n", "# k_i := d * t_i mod n\n", "# are guaranteed to be small (k_i < B = n / 2^ell for some leak parameter\n", "# ell -- e.g. the top ell bits of every k_i are zero). Recover d.\n", "#\n", "# In real ECDSA (with non-zero message-hash term u_i), the same lattice gets\n", "# one more row via the Boneh-Venkatesan \"embedding\" trick; the analysis is\n", "# unchanged. We focus on the cleaner u=0 case so the lattice is explicit.\n", "\n", "def egcd(a, b):\n", " if b == 0: return a, 1, 0\n", " g, x1, y1 = egcd(b, a % b); return g, y1, x1 - (a // b) * y1\n", "\n", "def mod_inv(a, n):\n", " g, x, _ = egcd(a % n, n)\n", " if g != 1: raise ValueError('not invertible')\n", " return x % n\n", "\n", "def is_probable_prime(N, k=20):\n", " if N < 2: return False\n", " if N % 2 == 0: return N == 2\n", " d_pp, r_pp = N - 1, 0\n", " while d_pp % 2 == 0: d_pp //= 2; r_pp += 1\n", " for _ in range(k):\n", " a = _r.randrange(2, N - 1)\n", " x = pow(a, d_pp, N)\n", " if x in (1, N - 1): continue\n", " for _ in range(r_pp - 1):\n", " x = pow(x, 2, N)\n", " if x == N - 1: break\n", " else:\n", " return False\n", " return True\n", "\n", "\n", "# (1) Toy \"group order\" and secret. We deliberately keep n at 32 bits so\n", "# that the LLL Gram-Schmidt scratch still fits in IEEE 754 double\n", "# precision -- the same algorithm scales to real ECDSA primes once you\n", "# swap the GSO for a Fraction-based or fpylll-based implementation.\n", "n = (1 << 32) - 5\n", "while not is_probable_prime(n): n += 2\n", "print(f'toy group order n ~ 2^32 ({n.bit_length()} bits, prime)')\n", "\n", "secret_d = 0xCAFEBABE % n # the hidden number\n", "leak_bits = 8 # top 8 bits of every k_i are zero\n", "B_bound = n >> leak_bits # so 0 <= k_i < B (about 2^24)\n", "m_sigs = 40 # number of biased \"signatures\" --\n", " # large enough that the magic vector\n", " # is the unique shortest in L_BV.\n", "two_l = 1 << leak_bits # the scaling 2^ell\n", "\n", "# (2) Generate biased samples (t_i, k_i = d * t_i mod n, k_i < B).\n", "# We pick t_i so that d * t_i mod n is forced small -- exactly the\n", "# situation that arises from \"all top bits of the nonce are zero\".\n", "ts, true_ks = [], []\n", "rng_demo = _r.Random(2026)\n", "d_inv = mod_inv(secret_d, n)\n", "for i in range(m_sigs):\n", " k = rng_demo.randrange(1, B_bound) # small target residue\n", " t = (d_inv * k) % n # so d * t == k mod n\n", " ts.append(t); true_ks.append(k)\n", "\n", "# (3) Boneh-Venkatesan lattice (dim m+1, integer-only after scaling by 2^ell).\n", "# row i (i < m): (n * 2^ell) e_i\n", "# row m: (t_1*2^ell, t_2*2^ell, ..., t_m*2^ell, 1)\n", "# The vector (k_1*2^ell, ..., k_m*2^ell, d) lies in this lattice and is\n", "# SHORT: each entry is below n. Worst-case Gaussian-heuristic length is\n", "# roughly sqrt(m+1) * n, so the SHORT vector beats it once m * ell > log2 n.\n", "m = m_sigs\n", "L = [[0] * (m + 1) for _ in range(m + 1)]\n", "for i in range(m):\n", " L[i][i] = n * two_l\n", "for i in range(m):\n", " L[m][i] = ts[i] * two_l\n", "L[m][m] = 1\n", "\n", "L_red, swaps = lll(L, delta=0.75)\n", "print(f'LLL on {m+1}-dim BV lattice ({swaps} swaps)')\n", "\n", "# (4) Read off d. The target lattice vector has the shape\n", "# (k_1 * 2^ell, k_2 * 2^ell, ..., k_m * 2^ell, d)\n", "# with the first m entries of magnitude < 2^ell * B = n and the last entry\n", "# in [-n, n]. We scan reduced rows for a candidate d that makes EVERY\n", "# d * t_i mod n small. Both sign conventions are tried.\n", "def k_residue(d_cand, t):\n", " k = (d_cand * t) % n\n", " return min(k, n - k) # centred mod n\n", "\n", "best_d, best_score = None, n\n", "for row in L_red:\n", " last = int(round(row[m]))\n", " for sign in (+1, -1):\n", " cand = (sign * last) % n\n", " if cand == 0: continue\n", " score = max(k_residue(cand, t) for t in ts)\n", " if score < best_score:\n", " best_d, best_score = cand, score\n", "\n", "# The true secret has score < B by construction. Anything else is spurious.\n", "recovered_d = best_d if best_score <= B_bound else None\n", "print(f'best d candidate = {hex(best_d) if best_d else None}'\n", " f' (max bias = {best_score} = ~{best_score / B_bound:.2f} * B)')\n", "print(f'recovered (passes B) = {hex(recovered_d) if recovered_d else None}')\n", "print(f'truth = {hex(secret_d)}')\n", "assert recovered_d == secret_d\n", "print(' -> Hidden number recovered from biased modular hints.')\n" ] }, { "cell_type": "markdown", "id": "lll-024", "metadata": {}, "source": [ "## 49.9 Summary\n", "\n", "We built LLL bottom-up:\n", "\n", "1. **Mathematics.** Lattices, Gram–Schmidt, the Hadamard ratio.\n", "2. **Building blocks.** Size reduction (clean up a basis vector via\n", " integer combinations of earlier ones) and the Lovász swap test\n", " (force the leading orthogonal length to shrink by a constant factor).\n", "3. **Algorithm.** A 30-line Python implementation, polynomial-time, with\n", " the worst-case Hermite factor $2^{(n-1)/2}$ but typically $\\approx\n", " 1.022^n$ in practice.\n", "\n", "Then four direct applications:\n", "\n", "- **A.** Lagarias–Odlyzko: break low-density Merkle–Hellman knapsacks.\n", "- **B.** Coppersmith: recover unknown bits of an RSA plaintext when\n", " the public exponent is small.\n", "- **C.** Integer relation detection: rediscover algebraic identities\n", " from numerical data (the workhorse of computer-algebra exploration).\n", "- **D.** Hidden Number Problem: recover an ECDSA secret key from\n", " biased nonces — the same family of attacks that broke Sony's\n", " PlayStation 3 firmware-signing key.\n", "\n", "The same algorithm underlies *all four* attacks. That universality —\n", "plus the fact that LLL outputs an *upper* bound on $\\lambda_1$, not a\n", "solution to NP-hard SVP — is why it remains, four decades on, the\n", "single most important algorithm in applied lattice cryptanalysis.\n" ] }, { "cell_type": "markdown", "id": "lll-025", "metadata": {}, "source": [ "## 49.10 References\n", "\n", "1. **Lenstra, A. K., Lenstra, H. W., Lovász, L.** (1982). *Factoring\n", " polynomials with rational coefficients.* Mathematische Annalen\n", " **261**, 515–534.\n", "2. **Lagarias, J. C., Odlyzko, A. M.** (1985). *Solving low-density\n", " subset sum problems.* J. ACM **32**(1), 229–246.\n", "3. **Coster, M. J., Joux, A., LaMacchia, B. A., Odlyzko, A. M.,\n", " Schnorr, C.-P., Stern, J.** (1992). *Improved low-density\n", " subset sum algorithms.* Computational Complexity **2**, 111–128.\n", "4. **Coppersmith, D.** (1996). *Finding a small root of a univariate\n", " modular equation.* EUROCRYPT '96, LNCS 1070.\n", "5. **Howgrave-Graham, N. A.** (1997). *Finding small roots of\n", " univariate modular equations revisited.* Cryptography and Coding,\n", " LNCS 1355.\n", "6. **Boneh, D., Venkatesan, R.** (1996). *Hardness of computing the\n", " most significant bits of secret keys in Diffie–Hellman and related\n", " schemes.* CRYPTO '96, LNCS 1109.\n", "7. **Nguyen, P. Q., Shparlinski, I. E.** (2002). *The insecurity of\n", " the Digital Signature Algorithm with partially known nonces.*\n", " Journal of Cryptology **15**(3).\n", "8. **Galbraith, S. D.** (2012). *Mathematics of Public Key Cryptography.*\n", " Cambridge University Press. — *the* modern textbook on lattices in\n", " cryptography. Chapter 17 covers LLL.\n", "9. **Nguyen, P. Q., Vallée, B., eds.** (2010). *The LLL Algorithm:\n", " Survey and Applications.* Springer.\n", "10. **Albrecht, M. R., Player, R., Scott, S.** (2015). *On the concrete\n", " hardness of Learning with Errors.* J. Mathematical Cryptology\n", " **9**(3). — modern lattice-attack estimator behind every PQC\n", " parameter discussion.\n" ] } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.14.2" } }, "nbformat": 4, "nbformat_minor": 5 }