path: root/re/epa.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "18343664-ebec-4e95-88f2-0231082b6b6e",
   "metadata": {},
   "source": [
    "# EPA-based reverse engineering\n",
    "This notebook showcases the EPA-based reverse-engineering technique for addition formulas.\n",
    "\n",
    " - [Exploration](#Exploration)\n",
    " - [Reverse-engineering](#Reverse-engineering)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "dac3b016-508b-4e63-897a-8ab46cb4f6ed",
   "metadata": {},
   "outputs": [],
   "source": [
    "import io\n",
    "import tabulate\n",
    "import secrets\n",
    "from tqdm.notebook import tqdm, trange\n",
    "from functools import partial\n",
    "from itertools import product\n",
    "from IPython.display import HTML, display\n",
    "from sympy.ntheory import factorint\n",
    "from sympy.ntheory.modular import crt\n",
    "from anytree import Node\n",
    "\n",
    "from pyecsca.ec.model import ShortWeierstrassModel\n",
    "from pyecsca.ec.coordinates import AffineCoordinateModel\n",
    "from pyecsca.ec.curve import EllipticCurve\n",
    "from pyecsca.ec.params import DomainParameters, load_params_ectester\n",
    "from pyecsca.ec.mod import mod, miller_rabin, gcd\n",
    "from pyecsca.ec.point import Point, InfinityPoint\n",
    "from pyecsca.ec.error import NonInvertibleError\n",
    "from pyecsca.ec.mult import LTRMultiplier, AccumulationOrder\n",
    "from pyecsca.ec.context import local\n",
    "from pyecsca.ec.error import UnsatisfiedAssumptionError\n",
    "from pyecsca.ec.formula.base import *\n",
    "from pyecsca.ec.formula.fake import FakeAdditionFormula, FakeDoublingFormula, FakePoint\n",
    "from pyecsca.ec.formula.unroll import unroll_formula_expr\n",
    "from pyecsca.sca.re.tree import Map, Tree\n",
    "from pyecsca.sca.re.rpa import MultipleContext\n",
    "from pyecsca.misc.utils import log, warn"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0f7d1396-3b56-4f9a-bd21-33e8906ab600",
   "metadata": {},
   "source": [
    "A few curves with composite \"p\"."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "9506f889-75cf-4b27-8535-e71cb8d5301e",
   "metadata": {},
   "outputs": [],
   "source": [
    "curves = [\n",
    "    # phi(p)/p =\n",
    "    # 0.8286039438617044\n",
    "    \"dfb2da5e1b7bd7bb098cb975966293ed,d9c4372806e8131b18d0036e8f832749,bcae41be8e808acdc04bb769dead91e2,0e2f983c0f852bef381f567448f0d488,1599bba77ed1cb8dec41555098958492,10fcabd48fffc71e6300d44acc236157d,0001\",\n",
    "    # 0.633325621696952\n",
    "    \"cca6f6718a06cad7094962b2a35f067d,67aa9464eb493fbb7b509d29381b9a9d,cafc69aa517b654a6a608644996cc8d1,4c092beb06cc00751eec39675f680cb8,82800378a47dd6f26ff6a50f69e4c4e6,18a22d20b6de3ff6bdc49329c21163f77,0001\",\n",
    "    # 0.8508806646440022 \n",
    "    \"b3755d654bad73114e4191e9f5f36af9,9fe4f88cfbacba71f4b767ace8580c74,4610526fdcfbd69aed453ac2ee6efeef,542d8e0bbafe40dae36f25cbc350add6,68a65f5a5dc304bfd0d8fe963c250206,118a34a1ea295e78b3a3c960b6f680ee1,0001\",\n",
    "    \n",
    "    # 0.9845701775215489 (has a = 0 for a subcurve)\n",
    "    \"de1406450d5d7e91d81907956019c0c1,5fbe46b9f1086011e18f5d823c6110ce,a859c36ceeadb39c7a978f7b1b0563ee,1cba89c3f099c29401ecf3fe1806e822,345d7282a0114070be91f95fe3db1faa,0fcd24d24e57a40547814b6766b9ea735,0001\",\n",
    "    # 0.980582605794486  (does not have a = 0 for any subcurve)\n",
    "    \"cab298b495875d4ab2c8ee3eb03016a7,a7c4f56f286d9eae44424c85c8b2fcb9,5e8c439d939273fdcb5503acbda7d3f8,816c9f865c831223067a88046bf00d75,972ce29ed18d5d73f15cef31187659be,0b0e97ff8c3e72e7ae75eb3f5e759fe03,0001\",\n",
    "    \n",
    "    # 0.9547100843537808\n",
    "    \"f1a8a441b6d0e9600e33ccf16f9b8291,b3f55185bd6a63528e3d560c6a7b729a,c2fee2d65350e870eda0ac5e2b96b810,29b3e793822fad03a3c2ebca3cf62c12,b937d5389b6c5d0212d0f53e26843092,1153442389f9e1da8dd130bc93c6ef42b,0001\",\n",
    "    # 0.7214369438844093\n",
    "    \"a4dfa4b6b065c40b45980474266c9fbb,2c3486e725755b44a7c119473c5b9c64,329078ab070fc18edc6ce53047e00a39,9f6209be91b66943d9e8e0b61c4aae4e,05271c9ac628351b9add9e1be69a9fa4,0cef2e52ffe86ebc6dd323912ac7d9a87,0001\",\n",
    "    # 0.4716485170445178 (160-bit)\n",
    "    \"db49063db56b7783fa01dd62077c5a88dfa28009,aee572fdd4790bcd4729bb3b612b52a573df46e9,dab9e68366a593ca1df9cb2f20890a578729d6ef,d4a3aaf43bdb25be7c308b69ae54f639e6e32e8c,7b6c82140bb427ac6e2a64507f60775949b2c8ce,34a9fbe62b272f930b2e5027780a32300feb0dd8f,0001\"\n",
    "]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "6e92cdd8-9040-4c6d-9700-f992d09195ee",
   "metadata": {},
   "outputs": [],
   "source": [
    "model = ShortWeierstrassModel()\n",
    "affine = AffineCoordinateModel(model)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8e0ffde3-27e1-4d28-92af-69686e42f3e6",
   "metadata": {},
   "source": [
    "## Exploration\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c4274c9c-5efa-4c4a-8b70-0c7ca6eb89de",
   "metadata": {},
   "source": [
    "Now, let's define some functions for picking random scalars mod $n$ and random points on the curve.\n",
    "There are several ways to do so, some guarantee that the scalars will be \"trivial\" w.r.t. the curve order $n$\n",
    "or even that all subscalars for a given scalarmult algo will be trivial w.r.t. the curve order."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "21ad6946-bb69-40b8-9407-d6c78537db47",
   "metadata": {},
   "outputs": [],
   "source": [
    "def random_scalar(n):\n",
    "    \"\"\"Generate a random scalar mod n.\"\"\"\n",
    "    return secrets.randbelow(n)\n",
    "\n",
    "def random_scalar_trivial(n):\n",
    "    \"\"\"Generate a random scalar with trivial gcd mod n.\"\"\"\n",
    "    scalar = secrets.randbelow(n)\n",
    "    while gcd(scalar, n) != 1:\n",
    "        scalar = secrets.randbelow(n)\n",
    "    return scalar\n",
    "\n",
    "def random_scalar_fully_trivial(n, mult):\n",
    "    \"\"\"Generate a random scalar with trivial gcd mod n, and also ensure that the given mult computes only multiples with trivial gcd mod n.\"\"\"\n",
    "    scalar = random_scalar_trivial(n)\n",
    "    while True:\n",
    "        with local(MultipleContext()) as ctx:\n",
    "            mult.multiply(scalar)\n",
    "        if all(map(lambda x: gcd(x, n) == 1, ctx.points.values())):\n",
    "            return scalar\n",
    "        scalar = random_scalar_trivial(n)\n",
    "\n",
    "def fixed_point(params):\n",
    "    \"\"\"Generate a fixed point on the params.\"\"\"\n",
    "    return params.generator\n",
    "\n",
    "def random_point(splitted, top, randomized=False):\n",
    "    \"\"\"Generate a random point on the splitted params.\"\"\"\n",
    "    results = {}\n",
    "    for factor, params in splitted.items():\n",
    "        results[factor] = params.curve.affine_random()\n",
    "    factors = list(results.keys())\n",
    "    xs = list(map(lambda factor: int(results[factor].x), factors))\n",
    "    ys = list(map(lambda factor: int(results[factor].y), factors))\n",
    "    res_x = mod(int(crt(factors, xs)[0]), top.curve.prime)\n",
    "    res_y = mod(int(crt(factors, ys)[0]), top.curve.prime)\n",
    "    res = Point(affine, x=res_x, y=res_y)\n",
    "    return res.to_model(top.curve.coordinate_model, top.curve, randomized=randomized)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "48727195-4c38-4b7f-8953-7108e46db98c",
   "metadata": {},
   "source": [
    "Let's also define a way to project the points down to a subcurve, a way to split the curve to subcurves and a scalarmult algo that correctly computes on the top curve by splitting over the subcurves."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "b6e888d3-38a0-4028-add5-a7b428b8b6cd",
   "metadata": {},
   "outputs": [],
   "source": [
    "def project_down(point, subcurve):\n",
    "    \"\"\"Project a point down onto a subcurve.\"\"\"\n",
    "    return Point(subcurve.coordinate_model, **{name: mod(int(value), subcurve.prime) for name, value in point.coords.items()})\n",
    "\n",
    "def split_params(params):\n",
    "    \"\"\"Split composite \"p\" params into subcurves.\"\"\"\n",
    "    factors = factorint(params.curve.prime)\n",
    "    if set(factors.values()) != {1}:\n",
    "        raise ValueError(\"Not squarefree\")\n",
    "    results = {}\n",
    "    # Construct the curves\n",
    "    for factor in sorted(factors.keys()):\n",
    "        p_i = factor\n",
    "        parameters_i = {name: mod(int(value), p_i) for name, value in params.curve.parameters.items()}\n",
    "        curve_i = EllipticCurve(params.curve.model, params.curve.coordinate_model, p_i, params.curve.neutral, parameters_i)\n",
    "        generator_i = project_down(params.generator, curve_i)\n",
    "        params_i = DomainParameters(curve_i, generator_i, 0, 1)\n",
    "        results[factor] = params_i\n",
    "    # Now map the orders to the curves\n",
    "    orders = list(factorint(params.order).keys())\n",
    "    orders.sort()\n",
    "    for factor_i, params_i in results.items():\n",
    "        for order in orders:\n",
    "            try:\n",
    "                params_i.curve.affine_multiply(params_i.generator.to_affine(), order)\n",
    "            except NonInvertibleError:\n",
    "                params_i.order = order\n",
    "                orders.remove(order)\n",
    "                break\n",
    "    return results\n",
    "\n",
    "def split_scalarmult(splitted, top, point, scalar):\n",
    "    \"\"\"Perform affine scalarmult of \"point\" by \"scalar\" on the splitted params.\"\"\"\n",
    "    results = {}\n",
    "    for factor, params in splitted.items():\n",
    "        order = params.order\n",
    "        projected = project_down(point, params.curve)\n",
    "        partial_scalar = scalar % order\n",
    "        if partial_scalar == 0:\n",
    "            result = InfinityPoint(params.curve.coordinate_model)\n",
    "        else:\n",
    "            result = params.curve.affine_multiply(projected.to_affine(), partial_scalar)\n",
    "        results[factor] = result\n",
    "    if any(map(lambda point: isinstance(point, InfinityPoint), results.values())):\n",
    "        # This is actually undefined if only one point is the infinity point.\n",
    "        return InfinityPoint(top.curve.coordinate_model)\n",
    "    factors = list(results.keys())\n",
    "    xs = list(map(lambda factor: int(results[factor].x), factors))\n",
    "    ys = list(map(lambda factor: int(results[factor].y), factors))\n",
    "    res_x = mod(int(crt(factors, xs)[0]), top.curve.prime)\n",
    "    res_y = mod(int(crt(factors, ys)[0]), top.curve.prime)\n",
    "    return Point(affine, x=res_x, y=res_y)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ba3d3c51-0c84-4374-a85c-019462f7a55c",
   "metadata": {},
   "source": [
    "With all of that we can now explore the behavior of the formulas, focusing on projective coordinates for now."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "703da72a-1c41-41a9-886d-453da1160932",
   "metadata": {},
   "outputs": [],
   "source": [
    "which = \"projective\"\n",
    "coords = model.coordinates[which]\n",
    "\n",
    "params = load_params_ectester(io.BytesIO(curves[4].encode()), which)\n",
    "curve = params.curve\n",
    "p = params.curve.prime\n",
    "g = params.generator\n",
    "n = params.order\n",
    "\n",
    "adds = list(filter(lambda formula: formula.name.startswith(\"add\"), coords.formulas.values()))\n",
    "dbls = list(filter(lambda formula: formula.name.startswith(\"dbl\"), coords.formulas.values()))\n",
    "formula_pairs = list(product(adds, dbls))\n",
    "\n",
    "fake_add = FakeAdditionFormula(params.curve.coordinate_model)\n",
    "fake_dbl = FakeDoublingFormula(params.curve.coordinate_model)\n",
    "fake_mult = LTRMultiplier(fake_add, fake_dbl, None, False, AccumulationOrder.PeqPR, True, True)\n",
    "fake_mult.init(params, FakePoint(params.curve.coordinate_model))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "c72b0fd3-21d1-4333-9a6b-f8c0d020c87d",
   "metadata": {},
   "outputs": [],
   "source": [
    "def simulate_table(scalars, points, split, params, formula_pairs, adds, dbls):\n",
    "    results = []\n",
    "    chains = []\n",
    "    gcds = []\n",
    "    fgcds = []\n",
    "    for scalar, point in tqdm(zip(scalars, points), desc=\"Precomp\", total=len(scalars)):\n",
    "        try:\n",
    "            result = split_scalarmult(split, params, point, scalar)\n",
    "        except NonInvertibleError:\n",
    "            result = None\n",
    "        results.append(result)\n",
    "        with local(MultipleContext()) as ctx:\n",
    "            fake_mult.multiply(scalar)\n",
    "        chains.append(list(ctx.points.values()))\n",
    "        scalar_trivial_gcd = gcd(scalar, n) == 1\n",
    "        all_subscalars_trivial_gcd = all(map(lambda x: gcd(x, n) == 1, ctx.points.values()))\n",
    "        gcds.append(scalar_trivial_gcd)\n",
    "        fgcds.append(all_subscalars_trivial_gcd)\n",
    "    \n",
    "    table = [[\"Pair\", \"scalars with trivial gcd\", \"scalars with all multiples with trivial gcds\", \"scalars with invertible final zs\", \"scalars with all multiples's zs invertible\", \"scalars with correct result\"]]\n",
    "    pair_table = [[None for _ in dbls] for _ in adds]\n",
    "    for pair in tqdm(formula_pairs):\n",
    "        mult = LTRMultiplier(*pair, None, False, AccumulationOrder.PeqPR, True, True)\n",
    "        inv = []\n",
    "        correct = []\n",
    "        zs = []\n",
    "        for scalar, point, result in tqdm(zip(scalars, points, results), leave=None, total=len(scalars)):\n",
    "            mult.init(params, point)\n",
    "            with local(MultipleContext()) as ctx:\n",
    "                res = mult.multiply(scalar)\n",
    "            \n",
    "            all_submultiples_invertible_z = all(map(lambda x: gcd(int(x.Z), p) == 1, ctx.points.keys()))\n",
    "            result_invertible_z = False\n",
    "            result_correct = False\n",
    "            try:\n",
    "                res_aff = res.to_affine()\n",
    "                result_invertible_z = True\n",
    "                if res_aff == result:\n",
    "                    result_correct = True\n",
    "            except NonInvertibleError as e:\n",
    "                pass\n",
    "            zs.append(all_submultiples_invertible_z)\n",
    "            inv.append(result_invertible_z)\n",
    "            correct.append(result_correct)\n",
    "        pair_table[adds.index(pair[0])][dbls.index(pair[1])] = sum(inv)\n",
    "        for i in inv:\n",
    "            print(\"x\" if i else \".\", end=\"\")\n",
    "        print()\n",
    "        table.append([f\"{pair[0].name}, {pair[1].name}\", sum(gcds), sum(fgcds), sum(inv), sum(zs), sum(correct)])\n",
    "    for pl, add in zip(pair_table, adds):\n",
    "        pl.insert(0, add.name)\n",
    "    pair_table.insert(0, [None] + [dbl.name for dbl in dbls])\n",
    "    return table, pair_table"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "ffce5b71-3029-4219-a45a-1c8d78748fee",
   "metadata": {},
   "outputs": [],
   "source": [
    "split = split_params(params)\n",
    "scalars = [random_scalar_trivial(n) for _ in trange(50, desc=\"Generate scalars\")]\n",
    "random_points = [random_point(split, params, randomized=False) for _ in trange(50, desc=\"Generate points\")]\n",
    "fixed_points = [fixed_point(params) for _ in trange(50, desc=\"Generate points\")]\n",
    "\n",
    "table, pair_table = simulate_table(scalars, random_points, split, params, formula_pairs, adds, dbls)\n",
    "display(HTML(tabulate.tabulate(table, tablefmt=\"html\", headers=\"firstrow\")))\n",
    "display(HTML(tabulate.tabulate(pair_table, tablefmt=\"html\", headers=\"firstrow\")))\n",
    "\n",
    "table, pair_table = simulate_table(scalars, fixed_points, split, params, formula_pairs, adds, dbls)\n",
    "display(HTML(tabulate.tabulate(table, tablefmt=\"html\", headers=\"firstrow\")))\n",
    "display(HTML(tabulate.tabulate(pair_table, tablefmt=\"html\", headers=\"firstrow\")))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cf709ab1-4520-41f1-a38a-19c9c9a6ff32",
   "metadata": {},
   "source": [
    "## Reverse-engineering"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "f47c0743-a6cf-408a-8c6e-dca6732278e2",
   "metadata": {},
   "outputs": [],
   "source": [
    "def simulate_epa_oracle(affine_params, affine_point, scalar, real_coord_name=\"projective\", real_add_name=\"add-2007-bl\", real_dbl_name=\"dbl-2007-bl\"):\n",
    "    \"\"\"\n",
    "    Simulate an EPA oracle that computes a scalar multiplication of `affine_point` by `scalar` on `affine_params`.\n",
    "    To select the \"real\" implementation, change the `real_coord_name`, `real_add_name` and `real_dbl_name` parameters.\n",
    "\n",
    "    This simulates an LTR multiplier, we assume we already know the multiplier at this point.\n",
    "    \"\"\"\n",
    "    real_coords = model.coordinates[real_coord_name]\n",
    "    real_add = real_coords.formulas[real_add_name]\n",
    "    real_dbl = real_coords.formulas[real_dbl_name]\n",
    "    real_mult = LTRMultiplier(real_add, real_dbl, None, False, AccumulationOrder.PeqPR, True, True)\n",
    "    params = affine_params.to_coords(real_coords)\n",
    "    point = affine_point.to_model(real_coords, params.curve)\n",
    "    real_mult.init(params, point)\n",
    "    res = real_mult.multiply(scalar)\n",
    "    try:\n",
    "        res.to_affine()\n",
    "        return True\n",
    "    except NonInvertibleError as e:\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "1a4457b4-78e8-4b82-af3d-e3563125d6d7",
   "metadata": {},
   "outputs": [],
   "source": [
    "def epa_precomp(affine_params, mult_factory, mult_class, model, queries=30):\n",
    "    \"\"\"\n",
    "    Precompute a map of (cfg) -> set of indices into inputs for which the given cfg oracle will answer True,\n",
    "    where inputs is a list of (scalar, point) pairs.\n",
    "\n",
    "    Returns the list of inputs, the mapping and all of the considered cfgs.\n",
    "    Note that the mapping might be restricted over a subset of the cfgs.\n",
    "    \"\"\"\n",
    "    split = split_params(affine_params)\n",
    "    scalars = [random_scalar_trivial(n) for _ in trange(queries, desc=\"Generate scalars\")]\n",
    "    random_points = [random_point(split, affine_params, randomized=False) for _ in trange(queries, desc=\"Generate points\")]\n",
    "    formula_classes = list(filter(lambda klass: klass in mult_class.requires, [AdditionFormula, DifferentialAdditionFormula, DoublingFormula, LadderFormula, NegationFormula]))\n",
    "    results = {}\n",
    "    inputs = list(zip(scalars, random_points))\n",
    "    configs = set()\n",
    "    for coord_name, coords in tqdm(model.coordinates.items(), desc=\"Precompute for coord systems\"):\n",
    "        try:\n",
    "            params = affine_params.to_coords(coords)\n",
    "        except UnsatisfiedAssumptionError:\n",
    "            log(f\"Skipping {coords.name}, does not fit.\")\n",
    "            continue\n",
    "        log(f\"Precomputing {coords.name}.\")\n",
    "        mapped_inputs = [(scalar, point.to_model(coords, params.curve)) for scalar, point in inputs]\n",
    "        \n",
    "        formula_groups = [list(filter(lambda formula: isinstance(formula, formula_class) and (formula.name.startswith(\"add\") or formula.name.startswith(\"dbl\")), coords.formulas.values())) for formula_class in formula_classes]\n",
    "        formula_combinations = list(product(*formula_groups))\n",
    "        \n",
    "        for formulas in tqdm(formula_combinations, desc=coord_name, leave=False):\n",
    "            cfg = tuple(formulas)\n",
    "            configs.add(cfg)\n",
    "            mult = mult_factory(*formulas)\n",
    "            result = set()\n",
    "            for i, pair in enumerate(mapped_inputs):\n",
    "                scalar, point = pair\n",
    "                mult.init(params, point)\n",
    "                try:\n",
    "                    res = mult.multiply(scalar)\n",
    "                except UnsatisfiedAssumptionError as e:\n",
    "                    break\n",
    "                try:\n",
    "                    res.to_affine()\n",
    "                    result.add(i)\n",
    "                except NonInvertibleError as e:\n",
    "                    pass\n",
    "            else:\n",
    "                results[cfg] = result\n",
    "    return inputs, results, configs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "07638de9-bdb9-45d6-87c5-349f48f864d4",
   "metadata": {},
   "outputs": [],
   "source": [
    "def epa_distinguish_precomp(inputs, precomp, configs, affine_params, oracle):\n",
    "    \"\"\"\n",
    "    Distinguish the coordinate system and formulas using EPA given the precomputation.\n",
    "    \"\"\"\n",
    "    dmap = Map.from_sets(configs, precomp)\n",
    "    tree = Tree.build(configs, dmap)\n",
    "    log(\"Built distinguishing tree.\")\n",
    "    log(tree.render())\n",
    "\n",
    "    current_node = tree.root\n",
    "    cfgs = list(precomp.keys())\n",
    "    while current_node.children:\n",
    "        best_distinguishing_index = current_node.dmap_input\n",
    "        scalar, point = inputs[best_distinguishing_index]\n",
    "        response = oracle(affine_params, point, scalar)\n",
    "        log(f\"Oracle response -> {response}\")\n",
    "        for cfg in cfgs:\n",
    "            log(cfg, best_distinguishing_index in precomp[cfg])\n",
    "        response_map = {child.response: child for child in current_node.children}\n",
    "        current_node = response_map[response]\n",
    "        cfgs = current_node.cfgs\n",
    "        log(cfgs)\n",
    "        log()\n",
    "    return cfgs"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b966e32e-2ed4-4437-bc68-17494a56d559",
   "metadata": {},
   "source": [
    "Now we can run the precomp and the EPA reverse-engineering."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "413c49eb-c096-485c-8471-18ac9c1b9523",
   "metadata": {},
   "outputs": [],
   "source": [
    "affine_params = load_params_ectester(io.BytesIO(curves[3].encode()), \"affine\")\n",
    "inputs, precomp, configs = epa_precomp(affine_params, lambda add,dbl:LTRMultiplier(add, dbl, None, False, AccumulationOrder.PeqPR, True, True), LTRMultiplier, model)\n",
    "epa_distinguish_precomp(inputs, precomp, configs, affine_params, simulate_epa_oracle)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1248a648-e70f-433c-91b6-5449b70b6516",
   "metadata": {},
   "source": [
    "### Miscellaneous"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "6cca69c8-48a8-4f82-bba0-35f9df7c440e",
   "metadata": {},
   "outputs": [],
   "source": [
    "param_categories = {\n",
    "    \"a=-1\": [\"projective-1\"],\n",
    "    \"a=-3\": [\"projective-3\", \"jacobian-3\", \"xyzz-3\"],\n",
    "    \"a=0\": [\"jacobian-0\"],\n",
    "    \"generic\": [\"jacobian\", \"projective\", \"modified\", \"xyzz\", \"xz\"],\n",
    "    \"b=0\": [\"w12-0\"]\n",
    "}\n",
    "cfg_categories = {}\n",
    "for name, coord_names in param_categories.items():\n",
    "    category_cfgs = set()\n",
    "    for coord_name in coord_names:\n",
    "        coords = model.coordinates[coord_name]\n",
    "        category_cfgs.update(filter(lambda cfg: cfg[0].coordinate_model == coords and cfg[1].coordinate_model == coords, configs))\n",
    "    cfg_categories[name] = category_cfgs\n",
    "category_map = {cfg: {\"category\": name} for name, category_cfgs in cfg_categories.items() for cfg in category_cfgs}\n",
    "dmap_categories = Map.from_io_maps(configs, category_map)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "6388a793-5433-4815-960e-7b2cc0f2211a",
   "metadata": {},
   "outputs": [],
   "source": [
    "dmap = Map.from_sets(configs, precomp, deduplicate=True)\n",
    "tree = Tree.build(configs, dmap)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "a975e6eb-51ea-4221-b2c6-c86ac8eb1739",
   "metadata": {},
   "outputs": [],
   "source": [
    "print(tree.describe())"
   ]
  },
  {
   "cell_type": "raw",
   "id": "71501ace-e964-48ad-b8fd-9859363ed28d",
   "metadata": {},
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.11.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}