From d814afb34f044c6ea1486e17a32c8d4691d9b6a9 Mon Sep 17 00:00:00 2001 From: J08nY Date: Tue, 2 Apr 2024 14:15:32 +0200 Subject: Add docs to formulas notebook. --- re/formulas.ipynb | 140 ++++++++++++++++++++++++++++++++++++++++++------------ 1 file 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,5 +1,13 @@ { "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, @@ -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,13 +73,22 @@ "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", "p256_proj3 = get_params(\"secg\", \"secp256r1\", \"projective-3\")" ] }, + { + "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, @@ -271,6 +317,14 @@ "]" ] }, + { + "cell_type": "markdown", + "id": "176fcb8c-e725-4e3b-9835-729cfb795206", + "metadata": {}, + "source": [ + "Let's load the formulas now." + ] + }, { "cell_type": "code", "execution_count": null, @@ -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, -- cgit v1.3.1