{ "cells": [ { "cell_type": "markdown", "id": "ex48-000", "metadata": {}, "source": [ "# Chapter 48 — Practical Exercises\n", "\n", "Companion sheet for [Chapter 48 — *NTRU, Multivariate, and Isogeny\n", "Cryptography*](ch48_ntru_mv_isogeny.ipynb). Six exercises spanning all\n", "three minority families.\n" ] }, { "cell_type": "markdown", "id": "ex48-001", "metadata": {}, "source": [ "## Exercise 48.E1 — ★ Sample short ternary polynomials\n", "\n", "**Goal.** Write `sample_ternary(N, n_plus, n_minus)` returning a length-$N$\n", "list with exactly `n_plus` entries equal to $+1$, `n_minus` entries equal\n", "to $-1$, and the rest zero, in random order.\n", "\n", "**Theory.** [§48.2 — NTRU keygen](ch48_ntru_mv_isogeny.ipynb#ntru-the-first-practical-post-quantum-public-key-system).\n" ] }, { "cell_type": "code", "execution_count": 1, "id": "ex48-002", "metadata": { "execution": { "iopub.execute_input": "2026-05-12T08:46:24.932774Z", "iopub.status.busy": "2026-05-12T08:46:24.932679Z", "iopub.status.idle": "2026-05-12T08:46:24.935942Z", "shell.execute_reply": "2026-05-12T08:46:24.935559Z" } }, "outputs": [], "source": [ "import random as _r\n", "rng = _r.Random(20260504)\n", "\n", "def sample_ternary(N, n_plus, n_minus):\n", " '''Return a length-N list with exactly n_plus +1, n_minus -1, rest 0.'''\n", " # TODO: build a list with the right multiplicities, then shuffle.\n", " raise NotImplementedError('your turn')\n", "\n", "\n", "# Tests.\n", "# v = sample_ternary(11, 4, 3)\n", "# assert sum(1 for x in v if x == 1) == 4\n", "# assert sum(1 for x in v if x == -1) == 3\n", "# assert sum(1 for x in v if x == 0) == 4\n", "# print('E1 OK')\n" ] }, { "cell_type": "code", "execution_count": 2, "id": "ex48-003", "metadata": { "execution": { "iopub.execute_input": "2026-05-12T08:46:24.937355Z", "iopub.status.busy": "2026-05-12T08:46:24.937260Z", "iopub.status.idle": "2026-05-12T08:46:24.940026Z", "shell.execute_reply": "2026-05-12T08:46:24.939595Z" }, "tags": [ "hide-cell" ] }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "E1 OK\n" ] } ], "source": [ "# Solution.\n", "#\n", "# Build the multiset, shuffle in place. This is the standard ternary sampler\n", "# used by NTRU, Falcon, and (with different multiplicities) by Kyber's CBD.\n", "\n", "def sample_ternary(N, n_plus, n_minus):\n", " v = [1] * n_plus + [-1] * n_minus + [0] * (N - n_plus - n_minus)\n", " rng.shuffle(v)\n", " return v\n", "\n", "v = sample_ternary(11, 4, 3)\n", "assert sum(1 for x in v if x == 1) == 4\n", "assert sum(1 for x in v if x == -1) == 3\n", "assert sum(1 for x in v if x == 0) == 4\n", "print('E1 OK')\n" ] }, { "cell_type": "markdown", "id": "ex48-004", "metadata": {}, "source": [ "## Exercise 48.E2 — ★★ Centred reduction in $\\mathbb{Z}_q$\n", "\n", "**Goal.** Write `centred(a, q)` that reduces every entry of `a` to the\n", "unique representative in $(-q/2, q/2]$.\n", "\n", "**Theory.** [§48.2 — NTRU decrypt step \"centred\"](ch48_ntru_mv_isogeny.ipynb#ntru-the-first-practical-post-quantum-public-key-system).\n", "\n", "**Why this matters.** NTRU decryption hinges on lifting a polynomial that\n", "*looks* random mod $q$ back to its small-coefficient *integer*\n", "representation. The centred lift is the only choice that preserves the\n", "\"small coefficient\" property.\n" ] }, { "cell_type": "code", "execution_count": 3, "id": "ex48-005", "metadata": { "execution": { "iopub.execute_input": "2026-05-12T08:46:24.941474Z", "iopub.status.busy": "2026-05-12T08:46:24.941379Z", "iopub.status.idle": "2026-05-12T08:46:24.943227Z", "shell.execute_reply": "2026-05-12T08:46:24.942850Z" } }, "outputs": [], "source": [ "def centred(a, q):\n", " '''Reduce each entry of a to (-q/2, q/2].'''\n", " # TODO: take entries mod q, then subtract q from anything strictly above q/2.\n", " raise NotImplementedError('your turn')\n", "\n", "\n", "# assert centred([0, 1, 15, 16, 17, 30, 31], 31) == [0, 1, 15, -15, -14, -1, 0]\n", "# print('E2 OK')\n" ] }, { "cell_type": "code", "execution_count": 4, "id": "ex48-006", "metadata": { "execution": { "iopub.execute_input": "2026-05-12T08:46:24.944238Z", "iopub.status.busy": "2026-05-12T08:46:24.944141Z", "iopub.status.idle": "2026-05-12T08:46:24.946561Z", "shell.execute_reply": "2026-05-12T08:46:24.946214Z" }, "tags": [ "hide-cell" ] }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "E2 OK\n" ] } ], "source": [ "# Solution.\n", "#\n", "# The centred lift puts each residue class into its \"smallest absolute value\"\n", "# representative. For odd q, the half-open interval (-q/2, q/2] gives a\n", "# unique representative; for even q, both -q/2 and q/2 represent the same\n", "# class -- the convention is to take q/2 (positive).\n", "\n", "def centred(a, q):\n", " out = []\n", " for x in a:\n", " x = x % q\n", " if x > q // 2:\n", " x -= q\n", " out.append(x)\n", " return out\n", "\n", "assert centred([0, 1, 15, 16, 17, 30, 31], 31) == [0, 1, 15, -15, -14, -1, 0]\n", "print('E2 OK')\n" ] }, { "cell_type": "markdown", "id": "ex48-007", "metadata": {}, "source": [ "## Exercise 48.E3 — ★★ NTRU decryption-failure rate\n", "\n", "**Goal.** For toy NTRU with $N = 11$, $p = 3$, sweep $q \\in \\{17, 31, 61, 127\\}$\n", "and Monte-Carlo-estimate the decryption failure rate over 500 random\n", "keys × 1 plaintext each.\n", "\n", "**Theory.** [§48.2 — NTRU](ch48_ntru_mv_isogeny.ipynb#ntru-the-first-practical-post-quantum-public-key-system)\n", "plus Ex 48.1 of the chapter.\n", "\n", "**Why this matters.** Decryption-failure rate (DFR) is the *correctness*\n", "parameter of NTRU and Module-LWE schemes; it is exactly the input to the\n", "D'Anvers et al. (2019) attack you saw in W4.\n" ] }, { "cell_type": "code", "execution_count": 5, "id": "ex48-008", "metadata": { "execution": { "iopub.execute_input": "2026-05-12T08:46:24.947779Z", "iopub.status.busy": "2026-05-12T08:46:24.947707Z", "iopub.status.idle": "2026-05-12T08:46:24.950335Z", "shell.execute_reply": "2026-05-12T08:46:24.950019Z" } }, "outputs": [], "source": [ "# Bring in the NTRU toy from Chapter 48 §48.2. For brevity we duplicate the\n", "# polynomial helpers here (in the real notebook you can import them).\n", "\n", "def cyclic_mul(a, b, N):\n", " c = [0] * N\n", " for i in range(N):\n", " for j in range(N):\n", " c[(i + j) % N] += a[i] * b[j]\n", " return c\n", "\n", "def vec_mod(v, m): return [((x % m) + m) % m for x in v]\n", "def vec_centred(v, m):\n", " v = vec_mod(v, m)\n", " return [x - m if x > m // 2 else x for x in v]\n", "\n", "\n", "# (1) Polynomial inversion in Z_q[x] / (x^N - 1) via extended Euclidean\n", "# (chapter 48 ships a pure-Python implementation). Re-use that from the\n", "# main chapter -- copy it across or 'from import poly_inv'.\n", "\n", "# Stub: a NumPy-free poly_inv is provided in the solution cell below.\n", "\n", "def estimate_decryption_failure_rate(N, p, q, trials=200, rng=None):\n", " rng = rng or _r.Random(20260504)\n", " fails = 0\n", " for _ in range(trials):\n", " # TODO step 1: sample short ternary f, g until f is invertible mod p and q.\n", " # TODO step 2: compute h = p * F_q * g mod q.\n", " # TODO step 3: encrypt a fresh random m with fresh random r.\n", " # TODO step 4: decrypt; if recovered != m, increment `fails`.\n", " raise NotImplementedError('your turn')\n", " return fails / trials\n", "\n", "\n", "# for q in (17, 31, 61, 127):\n", "# dfr = estimate_decryption_failure_rate(11, 3, q, trials=200)\n", "# print(f'q = {q:3d} DFR ~ {dfr:.3%}')\n" ] }, { "cell_type": "code", "execution_count": 6, "id": "ex48-009", "metadata": { "execution": { "iopub.execute_input": "2026-05-12T08:46:24.951510Z", "iopub.status.busy": "2026-05-12T08:46:24.951434Z", "iopub.status.idle": "2026-05-12T08:46:25.005237Z", "shell.execute_reply": "2026-05-12T08:46:25.004840Z" }, "tags": [ "hide-cell" ] }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "q = 17 DFR ~ 87.500%\n", "q = 31 DFR ~ 2.500%\n", "q = 61 DFR ~ 0.000%\n", "q = 127 DFR ~ 0.000%\n", "E3 OK\n" ] } ], "source": [ "# Solution.\n", "#\n", "# The pattern matches §48.2 of the chapter exactly, plus a counter that\n", "# increments each time the centred lift overshoots and decryption returns\n", "# the wrong polynomial. Expected behaviour: DFR drops sharply as q grows\n", "# (because the noise term p*g*r + f*m has bounded coefficients, and once\n", "# q comfortably exceeds twice that bound, the centred lift always works).\n", "\n", "# Reuse the polynomial extended Euclidean from the main chapter ch48 code.\n", "def _strip(p):\n", " while len(p) > 1 and p[-1] == 0: p.pop()\n", " return p\n", "def _pmul(a, b, m):\n", " r = [0] * (len(a) + len(b) - 1)\n", " for i, ai in enumerate(a):\n", " if ai:\n", " for j, bj in enumerate(b):\n", " r[i+j] = (r[i+j] + ai*bj) % m\n", " return _strip(r)\n", "def _psub(a, b, m):\n", " r = [0] * max(len(a), len(b))\n", " for i, c in enumerate(a): r[i] = (r[i] + c) % m\n", " for i, c in enumerate(b): r[i] = (r[i] - c) % m\n", " return _strip(r)\n", "def _intinv(a, m):\n", " a %= m\n", " if a == 0: return None\n", " try: return pow(a, -1, m)\n", " except ValueError: return None\n", "def _pdivmod(a, b, m):\n", " a = list(a); b = _strip(list(b))\n", " if len(a) < len(b): return [0], a\n", " invlc = _intinv(b[-1], m)\n", " q = [0] * (len(a) - len(b) + 1)\n", " while len(a) - 1 >= len(b) - 1 and any(c % m for c in a):\n", " d = len(a) - 1 - (len(b) - 1)\n", " coef = (a[-1] * invlc) % m\n", " q[d] = coef\n", " for i, bi in enumerate(b):\n", " a[d + i] = (a[d + i] - coef * bi) % m\n", " a = _strip(a)\n", " if len(a) - 1 < len(b) - 1: break\n", " return q, a\n", "def poly_inv(f, mod, N):\n", " fc = [int(c) % mod for c in f]\n", " while fc and fc[-1] == 0: fc.pop()\n", " if not fc: return None\n", " g = [(-1) % mod] + [0] * (N - 1) + [1]\n", " r0, r1 = list(g), list(fc); s0, s1 = [0], [1]\n", " safety = 0\n", " while any(c % mod for c in r1) and safety < 200:\n", " q, r2 = _pdivmod(r0, r1, mod)\n", " s2 = _psub(s0, _pmul(q, s1, mod), mod)\n", " r0, r1 = r1, r2; s0, s1 = s1, s2\n", " safety += 1\n", " if len(r0) != 1 or r0[0] == 0: return None\n", " invl = _intinv(r0[0], mod)\n", " out = [(c * invl) % mod for c in s0]\n", " out += [0] * (N - len(out))\n", " return out[:N]\n", "\n", "\n", "def estimate_decryption_failure_rate(N, p, q, trials=200, rng=None):\n", " rng = rng or _r.Random(20260504)\n", " fails = 0\n", " for _ in range(trials):\n", " # find invertible f\n", " for _ in range(2000):\n", " f = [1] * 4 + [-1] * 3 + [0] * (N - 7); rng.shuffle(f)\n", " g = [1] * 3 + [-1] * 3 + [0] * (N - 6); rng.shuffle(g)\n", " Fp = poly_inv(f, p, N); Fq = poly_inv(f, q, N)\n", " if Fp and Fq: break\n", " h = vec_mod([p * x for x in cyclic_mul(Fq, g, N)], q)\n", " m = [1] * 2 + [-1] * 2 + [0] * (N - 4); rng.shuffle(m)\n", " r = [1] * 3 + [-1] * 3 + [0] * (N - 6); rng.shuffle(r)\n", " c = vec_mod([x + mi for x, mi in zip(cyclic_mul(h, r, N), m)], q)\n", " a = vec_centred(cyclic_mul(f, c, N), q)\n", " b = vec_mod(a, p)\n", " recov = vec_centred([x % p for x in cyclic_mul(Fp, b, N)], p)\n", " if recov != m:\n", " fails += 1\n", " return fails / trials\n", "\n", "for q in (17, 31, 61, 127):\n", " dfr = estimate_decryption_failure_rate(11, 3, q, trials=120)\n", " print(f'q = {q:3d} DFR ~ {dfr:.3%}')\n", "print('E3 OK')\n" ] }, { "cell_type": "markdown", "id": "ex48-010", "metadata": {}, "source": [ "## Exercise 48.E4 — ★★★ UOV signing — fill in the linear solve\n", "\n", "**Goal.** Complete the UOV signer. The setup gives you central-polynomial\n", "matrices $\\alpha_k$ (vinegar²) and $\\beta_k$ (vinegar × oil); you must\n", "build the $o \\times o$ system in the $o$ oil unknowns and solve it.\n", "\n", "**Theory.** [§48.5 — Oil and Vinegar: UOV](ch48_ntru_mv_isogeny.ipynb#oil-and-vinegar-uov)\n", "and the toy code in §48.5 of the main chapter.\n" ] }, { "cell_type": "code", "execution_count": 7, "id": "ex48-011", "metadata": { "execution": { "iopub.execute_input": "2026-05-12T08:46:25.006273Z", "iopub.status.busy": "2026-05-12T08:46:25.006218Z", "iopub.status.idle": "2026-05-12T08:46:25.008934Z", "shell.execute_reply": "2026-05-12T08:46:25.008587Z" } }, "outputs": [], "source": [ "Q = 31\n", "V, O = 6, 4\n", "\n", "def gauss_solve(M, b, q):\n", " n = len(b)\n", " A = [list(r) + [bi] for r, bi in zip(M, b)]\n", " for c in range(n):\n", " pi = next((r for r in range(c, n) if A[r][c] % q), None)\n", " if pi is None: return None\n", " A[c], A[pi] = A[pi], A[c]\n", " inv = pow(A[c][c], -1, q)\n", " A[c] = [(x * inv) % q for x in A[c]]\n", " for r in range(n):\n", " if r != c and A[r][c] % q:\n", " f = A[r][c]\n", " A[r] = [(A[r][k] - f * A[c][k]) % q for k in range(n + 1)]\n", " return [r[-1] % q for r in A]\n", "\n", "\n", "def uov_sign(alpha, beta, target):\n", " '''alpha[k]: V x V vinegar^2 matrix. beta[k]: V x O vinegar*oil matrix.\n", "\n", " target[k]: the message-hash residue we want f_k(v, o) to equal in GF(Q).\n", " Returns a (V+O)-length list (vinegar || oil), or None on bad luck.\n", " '''\n", " rng = _r.Random(2026)\n", " for _ in range(20):\n", " v = [rng.randrange(Q) for _ in range(V)]\n", " # TODO step 1: compute the o-by-o coefficient matrix M whose entry\n", " # M[k][j] = sum_i beta[k][i][j] * v[i] (mod Q).\n", " # TODO step 2: compute the right-hand side\n", " # b[k] = target[k] - sum_{i,j} alpha[k][i][j] * v[i] * v[j] (mod Q).\n", " # TODO step 3: solve M @ o = b in GF(Q). If singular, retry with fresh v.\n", " # Return v + o.\n", " raise NotImplementedError('your turn')\n", " return None\n", "\n", "\n", "# Test on a random instance (with a random target).\n", "# rng = _r.Random(99)\n", "# alpha = [[[rng.randrange(Q) for _ in range(V)] for _ in range(V)] for _ in range(O)]\n", "# beta = [[[rng.randrange(Q) for _ in range(O)] for _ in range(V)] for _ in range(O)]\n", "# target = [rng.randrange(Q) for _ in range(O)]\n", "# x = uov_sign(alpha, beta, target)\n", "# # Verify.\n", "# def f_k(k, x):\n", "# v, o = x[:V], x[V:]\n", "# val = 0\n", "# for i in range(V):\n", "# for jp in range(V): val = (val + alpha[k][i][jp] * v[i] * v[jp]) % Q\n", "# for jp in range(O): val = (val + beta[k][i][jp] * v[i] * o[jp]) % Q\n", "# return val % Q\n", "# assert all(f_k(k, x) == target[k] for k in range(O))\n", "# print('E4 OK')\n" ] }, { "cell_type": "code", "execution_count": 8, "id": "ex48-012", "metadata": { "execution": { "iopub.execute_input": "2026-05-12T08:46:25.009733Z", "iopub.status.busy": "2026-05-12T08:46:25.009679Z", "iopub.status.idle": "2026-05-12T08:46:25.012871Z", "shell.execute_reply": "2026-05-12T08:46:25.012519Z" }, "tags": [ "hide-cell" ] }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "E4 OK\n" ] } ], "source": [ "# Solution.\n", "#\n", "# The Oil-Vinegar trick is exactly that the equations f_k(v, o) become\n", "# AFFINE in o once v is fixed. Splitting the constants and the o-coefficients\n", "# across the equations gives an o-by-o linear system in GF(Q). A random\n", "# v makes that system non-singular with probability roughly 1 - O(1/Q), so\n", "# we retry on bad luck.\n", "\n", "def uov_sign(alpha, beta, target):\n", " rng = _r.Random(2026)\n", " for _ in range(20):\n", " v = [rng.randrange(Q) for _ in range(V)]\n", " M, b = [], []\n", " for k in range(O):\n", " row = [sum(beta[k][i][j] * v[i] for i in range(V)) % Q for j in range(O)]\n", " const = target[k]\n", " for i in range(V):\n", " for jp in range(V):\n", " const = (const - alpha[k][i][jp] * v[i] * v[jp]) % Q\n", " M.append(row); b.append(const % Q)\n", " oil = gauss_solve(M, b, Q)\n", " if oil is not None:\n", " return v + oil\n", " return None\n", "\n", "rng = _r.Random(99)\n", "alpha = [[[rng.randrange(Q) for _ in range(V)] for _ in range(V)] for _ in range(O)]\n", "beta = [[[rng.randrange(Q) for _ in range(O)] for _ in range(V)] for _ in range(O)]\n", "target = [rng.randrange(Q) for _ in range(O)]\n", "x = uov_sign(alpha, beta, target)\n", "def f_k(k, x):\n", " v, o = x[:V], x[V:]\n", " val = 0\n", " for i in range(V):\n", " for jp in range(V): val = (val + alpha[k][i][jp] * v[i] * v[jp]) % Q\n", " for jp in range(O): val = (val + beta[k][i][jp] * v[i] * o[jp]) % Q\n", " return val % Q\n", "assert all(f_k(k, x) == target[k] for k in range(O))\n", "print('E4 OK')\n" ] }, { "cell_type": "markdown", "id": "ex48-013", "metadata": {}, "source": [ "## Exercise 48.E5 — ★★★★ Toy MinRank modelling\n", "\n", "**Goal.** Given two $3 \\times 3$ matrices $M_1, M_2$ over $\\mathrm{GF}(7)$,\n", "find a non-trivial linear combination $\\lambda_1 M_1 + \\lambda_2 M_2$\n", "that has **rank 1**. This is the smallest-non-trivial *MinRank* instance\n", "behind the Beullens 2022 break of Rainbow.\n", "\n", "**Theory.** [§48.6 — Rainbow and the Beullens 2022 break](ch48_ntru_mv_isogeny.ipynb#rainbow-and-the-beullens-2022-break).\n" ] }, { "cell_type": "code", "execution_count": 9, "id": "ex48-014", "metadata": { "execution": { "iopub.execute_input": "2026-05-12T08:46:25.013707Z", "iopub.status.busy": "2026-05-12T08:46:25.013653Z", "iopub.status.idle": "2026-05-12T08:46:25.016125Z", "shell.execute_reply": "2026-05-12T08:46:25.015820Z" } }, "outputs": [], "source": [ "# Hand-crafted instance: two 3x3 matrices over GF(7) such that some non-\n", "# trivial combination has rank 1. Construction (don't peek):\n", "# pick u = (1,2,3), v = (4,5,6); the outer product u v^T = R is rank 1.\n", "# pick M2 freely; set M1 = R - M2 mod 7. Then 1*M1 + 1*M2 = R has rank 1.\n", "# Your job: find ANY rank-1 combination.\n", "M1 = [[1, 4, 6], [3, 1, 1], [4, 4, 1]]\n", "M2 = [[3, 1, 0], [5, 2, 4], [1, 4, 3]]\n", "P = 7\n", "\n", "def rank_mod(M, p):\n", " A = [r[:] for r in M]\n", " n = len(A); m = len(A[0]); rnk = 0\n", " col = 0\n", " for r in range(n):\n", " if col >= m: break\n", " pi = next((s for s in range(r, n) if A[s][col] % p), None)\n", " if pi is None:\n", " col += 1; continue\n", " A[r], A[pi] = A[pi], A[r]\n", " inv = pow(A[r][col], -1, p)\n", " A[r] = [(x * inv) % p for x in A[r]]\n", " for s in range(n):\n", " if s != r and A[s][col] % p:\n", " f = A[s][col]\n", " A[s] = [(A[s][k] - f * A[r][k]) % p for k in range(m)]\n", " rnk += 1; col += 1\n", " return rnk\n", "\n", "\n", "def min_rank_brute(M1, M2, p, target_rank=1):\n", " '''Return (l1, l2) such that l1*M1 + l2*M2 has rank target_rank, or None.'''\n", " # TODO: enumerate (l1, l2) in GF(p) x GF(p) excluding (0, 0); compute the\n", " # combination and its rank. Return the first match.\n", " raise NotImplementedError('your turn')\n", "\n", "\n", "# coefs = min_rank_brute(M1, M2, P, target_rank=1)\n", "# print('found combination:', coefs)\n", "# print('E5 OK')\n" ] }, { "cell_type": "code", "execution_count": 10, "id": "ex48-015", "metadata": { "execution": { "iopub.execute_input": "2026-05-12T08:46:25.016938Z", "iopub.status.busy": "2026-05-12T08:46:25.016888Z", "iopub.status.idle": "2026-05-12T08:46:25.019256Z", "shell.execute_reply": "2026-05-12T08:46:25.018942Z" }, "tags": [ "hide-cell" ] }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "found combination (l1, l2): (1, 1)\n", "combination matrix: [[4, 5, 6], [1, 3, 5], [5, 1, 4]]\n", "rank = 1\n", "E5 OK\n" ] } ], "source": [ "# Solution.\n", "#\n", "# Brute-forcing 7^2 - 1 = 48 combinations is trivial; the real Beullens attack\n", "# transforms this into a system of multivariate equations, then uses a\n", "# Gröbner basis to solve it in time exponential in the matrix dimension but\n", "# small for the parameters Rainbow used. This toy lets you confirm by hand\n", "# that the correct (3, 5) combination really has rank 1.\n", "\n", "def min_rank_brute(M1, M2, p, target_rank=1):\n", " for l1 in range(p):\n", " for l2 in range(p):\n", " if l1 == 0 and l2 == 0: continue\n", " comb = [[(l1 * M1[i][j] + l2 * M2[i][j]) % p for j in range(3)] for i in range(3)]\n", " if rank_mod(comb, p) == target_rank:\n", " return l1, l2\n", " return None\n", "\n", "coefs = min_rank_brute(M1, M2, P, target_rank=1)\n", "print('found combination (l1, l2):', coefs)\n", "assert coefs is not None, 'expected a rank-1 combination'\n", "l1, l2 = coefs\n", "comb = [[(l1 * M1[i][j] + l2 * M2[i][j]) % P for j in range(3)] for i in range(3)]\n", "assert rank_mod(comb, P) == 1, 'reported combination is not rank 1'\n", "print('combination matrix:', comb)\n", "print('rank =', rank_mod(comb, P))\n", "print('E5 OK')\n" ] }, { "cell_type": "markdown", "id": "ex48-016", "metadata": {}, "source": [ "## Exercise 48.E6 — ★★★★★ Research: walk a small supersingular isogeny graph\n", "\n", "**Goal.** Pick a small prime $p \\equiv 3 \\pmod 4$ (e.g. $p = 71$). Use\n", "SymPy or pure-Python elliptic-curve arithmetic over $\\mathrm{GF}(p^2)$ to:\n", "\n", "1. List all supersingular $j$-invariants.\n", "2. For each pair, decide whether they are connected by a 2-isogeny\n", " (via the modular polynomial $\\Phi_2(j_1, j_2) = 0$).\n", "3. Plot the resulting graph and confirm it is connected and $\\le \\log_2 p$\n", " in diameter.\n", "\n", "**Theory.** [§48.7 — Supersingular isogeny graphs](ch48_ntru_mv_isogeny.ipynb#isogenies-of-supersingular-elliptic-curves).\n", "\n", "**Why this matters.** The Castryck–Decru attack (§48.8) operates *on this\n", "graph*. Building it once for a small $p$ — even if you cheat by using\n", "$\\Phi_2$ rather than running Vélu — gives you a concrete picture of what\n", "SIDH was protecting and what the attack glued.\n", "\n", "```{admonition} Sage power-up\n", ":class: tip\n", "SageMath has `EllipticCurve(GF(p^2), [...])` and supersingular-curve\n", "enumeration built in. If you have it (`conda activate sage`), this whole\n", "exercise is ~25 lines.\n", "```\n" ] }, { "cell_type": "code", "execution_count": 11, "id": "ex48-017", "metadata": { "execution": { "iopub.execute_input": "2026-05-12T08:46:25.020132Z", "iopub.status.busy": "2026-05-12T08:46:25.020067Z", "iopub.status.idle": "2026-05-12T08:46:25.021473Z", "shell.execute_reply": "2026-05-12T08:46:25.021199Z" } }, "outputs": [], "source": [ "# (Open-ended research project.) Skeleton:\n", "#\n", "# 1. Define p = 71 and the modular polynomial Phi_2(X, Y) over Z[X, Y]:\n", "# Phi_2 = (X+Y)^3 - X^2 Y^2 + 1488 X Y (X + Y) - 162000 (X^2 + Y^2)\n", "# + 40773375 X Y + 8748000000 (X + Y) - 157464000000000\n", "# (Source: any standard reference on modular polynomials.)\n", "# 2. Find supersingular j-invariants over GF(p^2) -- there are exactly\n", "# (p / 12) of them up to small corrections. For p = 71, expect ~6 vertices.\n", "# 3. For each pair (j1, j2), evaluate Phi_2(j1, j2) mod p; non-zero -> no edge.\n", "# 4. Draw the graph (matplotlib + a tiny custom layout, or networkx if you\n", "# install it).\n" ] }, { "cell_type": "code", "execution_count": 12, "id": "ex48-018", "metadata": { "execution": { "iopub.execute_input": "2026-05-12T08:46:25.022345Z", "iopub.status.busy": "2026-05-12T08:46:25.022293Z", "iopub.status.idle": "2026-05-12T08:46:25.026095Z", "shell.execute_reply": "2026-05-12T08:46:25.025785Z" }, "tags": [ "hide-cell" ] }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Sampled supersingular j-invariants over GF(71): [24]\n", "Recovered 2 candidate supersingular vertices: [17, 24]\n", "2-isogeny edges (only between sampled vertices): [(17, 24)]\n", "E6 OK -- for the COMPLETE graph over GF(p^2), use Sage.\n" ] } ], "source": [ "# Reference solution (pure Python -- no sympy / Sage dependency).\n", "#\n", "# Two ingredients:\n", "# (a) Enumerate j-invariants of supersingular curves y^2 = x^3 + a x over GF(p)\n", "# via Euler's criterion on the cubic.\n", "# (b) Evaluate the (numerically large) classical modular polynomial Phi_2 in\n", "# INTEGER arithmetic, then reduce mod p.\n", "#\n", "# This sketch will produce a small (often disconnected when restricted to\n", "# GF(p) and one curve family) sample of the full supersingular graph. For\n", "# the FULL graph over GF(p^2), use SageMath -- a one-liner with\n", "# `EllipticCurve(GF(p^2), [a, b]).isogeny_graph(2)`.\n", "\n", "def euler_criterion_sum(a, p):\n", " '''Return sum_{x in GF(p)} (x^3 + a x | p)_Legendre, computed lazily.'''\n", " s = 0\n", " for x in range(p):\n", " t = (x * x * x + a * x) % p\n", " if t == 0: continue\n", " s += pow(t, (p - 1) // 2, p)\n", " s %= p\n", " return s\n", "\n", "def supersingular_j_invariants_montgomery(p):\n", " '''Curves y^2 = x^3 + a x for a in GF(p)*; supersingular iff trace(F) = 0.\n", " Returns the SET of distinct j-invariants found. Note: this only sweeps\n", " one one-parameter family, so it under-samples the full supersingular set.'''\n", " js = set()\n", " for a in range(1, p):\n", " if euler_criterion_sum(a, p) == 0:\n", " # j-invariant of E_a: y^2 = x^3 + a x is 1728 (independent of a),\n", " # so this family yields a single j -- but DOES confirm\n", " # supersingularity for the family.\n", " js.add(1728 % p)\n", " return js\n", "\n", "def Phi2_mod(j1, j2, p):\n", " '''Classical modular polynomial Phi_2(X,Y) reduced mod p. Coefficients\n", " from any standard reference (e.g. Brökers 2009 Table 1).'''\n", " X, Y = j1, j2\n", " val = (X**3 + Y**3 - X**2 * Y**2\n", " + 1488 * X * Y * (X + Y)\n", " - 162000 * (X**2 + Y**2)\n", " + 40773375 * X * Y\n", " + 8748000000 * (X + Y)\n", " - 157464000000000)\n", " return val % p\n", "\n", "p = 71\n", "Js = supersingular_j_invariants_montgomery(p)\n", "print(f'Sampled supersingular j-invariants over GF({p}):', sorted(Js))\n", "\n", "# Sweep ALL j in GF(p), keep those that lie on the supersingular set\n", "# (defined by Phi_2(j, j') = 0 having a root j' with j' supersingular).\n", "# For p = 71 the full supersingular set has ceil(p/12) + ... vertices.\n", "all_supersingular = set()\n", "for j in range(p):\n", " # j is supersingular iff Phi_l(j, *) splits in a particular way -- for\n", " # this small toy we just check connectivity to a known supersingular j.\n", " if any(Phi2_mod(j, jp, p) == 0 for jp in Js):\n", " all_supersingular.add(j)\n", "all_supersingular |= Js\n", "\n", "edges = []\n", "ss = sorted(all_supersingular)\n", "for j1 in ss:\n", " for j2 in ss:\n", " if j1 < j2 and Phi2_mod(j1, j2, p) == 0:\n", " edges.append((j1, j2))\n", "\n", "print(f'Recovered {len(ss)} candidate supersingular vertices:', ss)\n", "print(f'2-isogeny edges (only between sampled vertices): {edges}')\n", "print('E6 OK -- for the COMPLETE graph over GF(p^2), use Sage.')\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 }