Add docs to formulas notebook.

1 files changed, 109 insertions, 31 deletions

diff --git a/re/formulas.ipynb b/re/formulas.ipynb
index 9054781..20263a0 100644
--- a/re/formulas.ipynb
+++ b/re/formulas.ipynb
@@ -1,6 +1,14 @@
 {
  "cells": [
   {
+   "cell_type": "markdown",
+   "id": "0577f61d-635c-436c-96ca-1471265ac1fb",
+   "metadata": {},
+   "source": [
+    "# Exploration of formulas in open-source ECC libraries"
+   ]
+  },
+  {
    "cell_type": "code",
    "execution_count": null,
    "id": "397771ed-7408-47a6-8b82-75e047e100fe",
@@ -9,19 +17,48 @@
    "source": [
     "import itertools\n",
     "import tabulate\n",
+    "import pickle\n",
     "import numpy as np\n",
-    "from matplotlib import pyplot as plt\n",
+    "import inspect\n",
+    "import tempfile\n",
+    "import sys\n",
+    "import multiprocessing\n",
+    "\n",
     "from copy import deepcopy\n",
-    "from IPython.display import HTML, display\n",
+    "from concurrent.futures import ProcessPoolExecutor, as_completed\n",
+    "from contextlib import contextmanager\n",
+    "from importlib import import_module, invalidate_caches\n",
     "from pathlib import Path\n",
+    "\n",
+    "from matplotlib import pyplot as plt\n",
+    "from IPython.display import HTML, display\n",
+    "from tqdm.notebook import tqdm\n",
     "from importlib_resources import files, as_file\n",
-    "import pyecsca\n",
     "\n",
-    "from pyecsca.ec.model import ShortWeierstrassModel,TwistedEdwardsModel,MontgomeryModel\n",
-    "from pyecsca.ec.formula import AdditionEFDFormula,DoublingEFDFormula,LadderEFDFormula\n",
+    "import pyecsca\n",
+    "from pyecsca.ec.model import ShortWeierstrassModel, TwistedEdwardsModel, MontgomeryModel\n",
+    "from pyecsca.ec.formula import AdditionEFDFormula, DoublingEFDFormula, LadderEFDFormula\n",
     "from pyecsca.ec.params import get_params\n",
-    "from pyecsca.sca.re.structural import formula_similarity, formula_similarity_fuzz\n",
-    "from pyecsca.sca.re.zvp import unroll_formula_expr, unroll_formula"
+    "from pyecsca.ec.formula.metrics import formula_similarity, formula_similarity_fuzz\n",
+    "from pyecsca.ec.formula.unroll import unroll_formula_expr, unroll_formula\n",
+    "from pyecsca.ec.formula.expand import expand_formula_set\n",
+    "\n",
+    "\n",
+    "# Allow to use \"spawn\" multiprocessing method for function defined in a Jupyter notebook.\n",
+    "# https://neuromancer.sk/article/35\n",
+    "@contextmanager\n",
+    "def enable_spawn(func):\n",
+    "    invalidate_caches()\n",
+    "    source = inspect.getsource(func)\n",
+    "    with tempfile.NamedTemporaryFile(suffix=\".py\", mode=\"w\") as f:\n",
+    "        f.write(source)\n",
+    "        f.flush()\n",
+    "        path = Path(f.name)\n",
+    "        directory = str(path.parent)\n",
+    "        sys.path.append(directory)\n",
+    "        module = import_module(str(path.stem))\n",
+    "        yield getattr(module, func.__name__)\n",
+    "        sys.path.remove(directory)"
    ]
   },
   {
@@ -36,7 +73,7 @@
     "te = TwistedEdwardsModel()\n",
     "\n",
     "curve25519 = get_params(\"other\", \"Curve25519\", \"xz\")\n",
-    "ed5519 = get_params(\"other\", \"Ed25519\", \"extended\")\n",
+    "ed25519 = get_params(\"other\", \"Ed25519\", \"extended\")\n",
     "p256_jac3 = get_params(\"secg\", \"secp256r1\", \"jacobian-3\")\n",
     "p256_jac = get_params(\"secg\", \"secp256r1\", \"jacobian\")\n",
     "p256_mod = get_params(\"secg\", \"secp256r1\", \"modified\")\n",
@@ -44,6 +81,15 @@
    ]
   },
   {
+   "cell_type": "markdown",
+   "id": "0d686ad1-4b20-4327-95be-36d6e92052b3",
+   "metadata": {},
+   "source": [
+    "## The formulas\n",
+    "The following formulas were collected from open-source cryptographic libraries and are stored in the tests directory of the pyecsca toolkit."
+   ]
+  },
+  {
    "cell_type": "code",
    "execution_count": null,
    "id": "21572b7d-380c-4570-b5bd-2043306adc3e",
@@ -272,6 +318,14 @@
    ]
   },
   {
+   "cell_type": "markdown",
+   "id": "176fcb8c-e725-4e3b-9835-729cfb795206",
+   "metadata": {},
+   "source": [
+    "Let's load the formulas now."
+   ]
+  },
+  {
    "cell_type": "code",
    "execution_count": null,
    "id": "0cfcbf60-7d6b-4ab0-b957-e998037ff8ab",
@@ -284,28 +338,26 @@
     "    meta_path = base_path / formula_def[0]\n",
     "    op3_path = base_path / (formula_def[0] + \".op3\")\n",
     "    model = formula_def[1]()\n",
-    "    formula = formula_def[4](meta_path, op3_path, formula_def[0], model.coordinates[formula_def[2]])\n",
+    "    formula = formula_def[4](meta_path, op3_path, formula_def[0], model.coordinates[formula_def[2]]).to_code()\n",
     "    lib_formulas[formula_def[0]] = formula"
    ]
   },
   {
    "cell_type": "code",
    "execution_count": null,
-   "id": "00de3dd3-f54b-4af5-8bff-8485f8eb5f2c",
+   "id": "74002746-f3f3-4528-9042-b9ab51791bc2",
    "metadata": {},
    "outputs": [],
    "source": [
-    "lib_formulas"
+    "len(lib_formulas)"
    ]
   },
   {
-   "cell_type": "code",
-   "execution_count": null,
-   "id": "74002746-f3f3-4528-9042-b9ab51791bc2",
+   "cell_type": "markdown",
+   "id": "5800e043-85bc-4fac-8c40-75c234beec1c",
    "metadata": {},
-   "outputs": [],
    "source": [
-    "len(lib_formulas)"
+    "Now we can setup some code for examining the similarities between the formulas."
    ]
   },
   {
@@ -537,35 +589,61 @@
    ]
   },
   {
-   "cell_type": "code",
-   "execution_count": null,
-   "id": "597afe6e-04b5-423a-b5d6-f6adba38cc79",
+   "cell_type": "markdown",
+   "id": "39f642c2-2350-4310-b365-3be6c3f6fcdb",
    "metadata": {},
-   "outputs": [],
    "source": [
-    "r = unroll_formula(lib_formulas[\"add-openssl-z256\"])\n",
-    "for e in r:\n",
-    "    if e[0] in (\"X3\", \"Y3\", \"Z3\"):\n",
-    "        print(e)"
+    "## Expand\n",
+    "We can also expand the set of formulas by applying various transformations (like swapping the order of commutative operations).\n",
+    "\n",
+    "Note that this computation is parallelized and you should set an appropriate number of workers."
    ]
   },
   {
    "cell_type": "code",
    "execution_count": null,
-   "id": "6665f43f-a037-4dd3-9dd7-d4f0451448f3",
+   "id": "f3c2c134-a42d-4bb2-b729-0ec1ddcbcdef",
    "metadata": {},
    "outputs": [],
    "source": [
-    "r = unroll_formula(lib_formulas[\"add-openssl-z256a\"])\n",
-    "for e in r:\n",
-    "    if e[0] in (\"X3\", \"Y3\", \"Z3\"):\n",
-    "        print(e)"
+    "def expand_out(formulas, name):\n",
+    "    from pyecsca.ec.formula.expand import expand_formula_set\n",
+    "    import pickle\n",
+    "\n",
+    "    expanded = expand_formula_set(formulas)\n",
+    "    with open(name, \"wb\") as f:\n",
+    "        pickle.dump(expanded, f)\n",
+    "    return name, len(expanded)\n",
+    "\n",
+    "# 22 is really a maximum usable number here, as there are only 22 \"jobs\".\n",
+    "context = multiprocessing.get_context(\"spawn\")\n",
+    "with ProcessPoolExecutor(max_workers=22, mp_context=context) as pool, enable_spawn(expand_out) as expand_func:\n",
+    "    futures = []\n",
+    "    args = []\n",
+    "    for coord_name, coords in tqdm(sw.coordinates.items(), desc=\"Submitting\"):\n",
+    "        adds = [formula for formula in coords.formulas.values() if formula.name.startswith(\"add\")]\n",
+    "        lib_adds = [formula for formula in lib_formulas.values() if formula.coordinate_model == coords and formula.name.startswith(\"add\")]\n",
+    "        dbls = [formula for formula in coords.formulas.values() if formula.name.startswith(\"dbl\")]\n",
+    "        lib_dbls = [formula for formula in lib_formulas.values() if formula.coordinate_model == coords and formula.name.startswith(\"dbl\")]\n",
+    "        futures.append(pool.submit(expand_func, adds + lib_adds, f\"sw_{coord_name}_adds.pickle\"))\n",
+    "        args.append(f\"sw_{coord_name}_adds.pickle\")\n",
+    "        futures.append(pool.submit(expand_func, dbls + lib_dbls, f\"sw_{coord_name}_dbls.pickle\"))\n",
+    "        args.append(f\"sw_{coord_name}_dbls.pickle\")\n",
+    "    for future in tqdm(as_completed(futures), total=len(futures), smoothing=0, desc=\"Computing\"):\n",
+    "        j = futures.index(future)\n",
+    "        arg = args[j]\n",
+    "        error = future.exception()\n",
+    "        if error:\n",
+    "            print(arg, error)\n",
+    "        else:\n",
+    "            res = future.result()\n",
+    "            print(*res)"
    ]
   },
   {
    "cell_type": "code",
    "execution_count": null,
-   "id": "cac8e061-b7a2-4ba9-9b57-7958b0c91d94",
+   "id": "a5b1ccd8-1b2b-4e1a-85e1-5cab2b45300c",
    "metadata": {},
    "outputs": [],
    "source": []
@@ -587,7 +665,7 @@
    "name": "python",
    "nbconvert_exporter": "python",
    "pygments_lexer": "ipython3",
-   "version": "3.11.5"
+   "version": "3.11.4"
   }
  },
  "nbformat": 4,