path: root/configuration_space.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Configuration space\n",
    "This notebook explores the configuration space of Elliptic Curve crypto\n",
    "implementations.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "An ECC implementation configuration in **pyecsca** has the following attributes: "
   ]
  },
  {
   "cell_type": "code",
   "metadata": {},
   "source": [
    "from typing import get_args\n",
    "from pyecsca.ec.configuration import Configuration\n",
    "from dataclasses import fields\n",
    "\n",
    "for field in fields(Configuration):\n",
    "\tname = field.name\n",
    "\ttp = field.type\n",
    "\tdoc = tp.__doc__\n",
    "\tif get_args(field.type):\n",
    "\t\tdoc = get_args(field.type)[0].__doc__\n",
    "\tprint(name, tp)\n",
    "\tprint(\"   \", doc.strip().split(\"\\n\")[0])\n",
    "\tif hasattr(tp, \"names\"):\n",
    "\t\tfor enum_name in tp.names():\n",
    "\t\t\tprint(\"       \", enum_name)\n",
    "\tprint()"
   ],
   "outputs": [],
   "execution_count": null
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": "It is represented by the [Configuration](../api/pyecsca.ec.configuration.rst#pyecsca.ec.configuration.Configuration) class."
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Enumerating configurations\n",
    "\n",
    "The possible configurations can be generated using the [all_configurations()](../api/pyecsca.ec.configuration.rst#pyecsca.ec.configuration.all_configurations) function.\n",
    "The whole space of configurations is quite huge.\n",
    "\n",
    "<div class=\"alert alert-warning\">\n",
    "\n",
    "Note that the amount of possible parametrizations of some scalar multipliers is very large (e.g. window size) so **pyecsca** has\n",
    "to restrict this to a reasonable selection. Specifically the function below only considers a few options for window size and\n",
    "similar parameters. **Even then, the cell below takes roughly 10 minutes to run.**\n",
    "\n",
    "</div>"
   ]
  },
  {
   "cell_type": "code",
   "metadata": {},
   "source": [
    "from pyecsca.ec.configuration import all_configurations\n",
    "\n",
    "total = sum(1 for _ in all_configurations())\n",
    "print(total)"
   ],
   "outputs": [],
   "execution_count": null
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A large part of the configuration space is due to the independent options which consist of:\n",
    " \n",
    " - `hash_type` of type `HashType` $*6$\n",
    " - `mod_rand` of type `RandomMod` $*2$\n",
    " - `mult` of type `Multiplication` $*4$\n",
    " - `sqr` of type `Squaring` $*4$\n",
    " - `red` of type `Reduction` $*3$\n",
    " - `inv` of type `Inversion` $*2$\n",
    "\n",
    "Without these, the space is somewhat smaller:"
   ]
  },
  {
   "cell_type": "code",
   "metadata": {},
   "source": [
    "no_hash_and_rand = (4*4*3*2)\n",
    "no_ff = (6*2)\n",
    "no_indep = no_ff * no_hash_and_rand"
   ],
   "outputs": [],
   "execution_count": null
  },
  {
   "cell_type": "code",
   "metadata": {},
   "source": [
    "print(total // no_indep)"
   ],
   "outputs": [],
   "execution_count": null
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To restrict the generated configurations, pass keyword arguments to the\n",
    "`all_configurations` matching the names of the attributes of the `Configuration` object."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {},
   "source": [
    "from pyecsca.ec.configuration import HashType, RandomMod, Multiplication, Squaring, Reduction, Inversion\n",
    "from pyecsca.ec.model import ShortWeierstrassModel\n",
    "from pyecsca.ec.mult import LTRMultiplier\n",
    "\n",
    "model = ShortWeierstrassModel()\n",
    "coords = model.coordinates[\"projective\"]\n",
    "scalarmult = LTRMultiplier\n",
    "independent_opts = {\n",
    "\t\"hash_type\": HashType.SHA256,\n",
    "\t\"mod_rand\": RandomMod.SAMPLE,\n",
    "\t\"mult\": Multiplication.KARATSUBA,\n",
    "\t\"sqr\": Squaring.KARATSUBA,\n",
    "\t\"red\": Reduction.MONTGOMERY,\n",
    "    \"inv\": Inversion.GCD\n",
    "}\n",
    "\n",
    "configs = list(all_configurations(model=model, coords=coords, scalarmult=scalarmult,\n",
    "\t\t\t\t\t\t\t \t  **independent_opts))\n",
    "print(len(configs))"
   ],
   "outputs": [],
   "execution_count": null
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We see that when we fixed all parameters except for the scalar multiplier arguments \n",
    "(see the [LTRMultiplier](../api/pyecsca.ec.mult.binary.rst#pyecsca.ec.mult.binary.LTRMultiplier) constructor) we obtained 1280 configurations. That number expresses all of the possible ways to use addition formulas for the `projective` coordinate system in the binary left-to-right multiplier as well as internal options of that multiplier:\n",
    "\n",
    " - whether it is \"complete\" in a sense that it starts processing at a constant bit (the bit-length od the order)\n",
    " - whether it is \"double-and-add-always\"\n",
    " - whether it \"short-circuits\" the formulas, i.e. detects that an exceptional point was input into them and returns correctly\n",
    "   without executing them."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Models"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can explore the number of configurations for each of the supported curve models."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {},
   "source": [
    "from IPython.display import HTML, display\n",
    "import tabulate\n",
    "from pyecsca.ec.model import *\n",
    "from pyecsca.ec.mult import ProcessingDirection, AccumulationOrder\n",
    "\n",
    "model_counts = [[\"Model\", \"All\", \"Without independent options\", \"Without independent options and scaling\", \"Without independent options and scalarmult options\"]]\n",
    "totals = [\"Total\", 0, 0, 0, 0]\n",
    "for model in (ShortWeierstrassModel(), MontgomeryModel(), EdwardsModel(), TwistedEdwardsModel()):\n",
    "\tname = model.__class__.__name__\n",
    "\tcount = sum(1 for _ in all_configurations(model=model, **independent_opts))\n",
    "\tcount_no_scl = sum(1 for _ in all_configurations(model=model, **independent_opts, scalarmult={\"scl\": None}))\n",
    "\tcount_no_opts = sum(1 for _ in all_configurations(model=model, **independent_opts, scalarmult={\"scl\": None, \"always\": True, \"short_circuit\": True, \"complete\": False, \"precompute_negation\": True, \"width\": 3, \"m\": 3, \"direction\": ProcessingDirection.LTR, \"accumulation_order\": AccumulationOrder.PeqPR, \"recoding_direction\": ProcessingDirection.LTR}))\n",
    "\tmodel_counts.append([name, count * no_ff, count, count_no_scl, count_no_opts])\n",
    "\ttotals[1] += count * no_ff\n",
    "\ttotals[2] += count\n",
    "\ttotals[3] += count_no_scl\n",
    "\ttotals[4] += count_no_opts\n",
    "model_counts.append(totals)\n",
    "display(HTML(tabulate.tabulate(model_counts, tablefmt=\"html\", headers=\"firstrow\")))"
   ],
   "outputs": [],
   "execution_count": null
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Coordinate systems"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's now look at the configuration split for coordinate systems:"
   ]
  },
  {
   "cell_type": "code",
   "metadata": {},
   "source": [
    "coords_counts = [[\"Model\", \"Coords\", \"All\", \"Without independent options\", \"Without independent options and scaling\", \"Without independent options and scalarmult options\"]]\n",
    "for model in (ShortWeierstrassModel(), MontgomeryModel(), EdwardsModel(), TwistedEdwardsModel()):\n",
    "\tmodel_name = model.__class__.__name__\n",
    "\tcoords_counts.append([model_name, \"\", \"\", \"\", \"\", \"\"])\n",
    "\tfor coords in sorted(model.coordinates.values(), key=lambda c: c.name):\n",
    "\t\tcoords_name = coords.name\n",
    "\t\tcount = sum(1 for _ in all_configurations(model=model, coords=coords, **independent_opts))\n",
    "\t\tcount_no_scl = sum(1 for _ in all_configurations(model=model, coords=coords, **independent_opts, scalarmult={\"scl\": None}))\n",
    "\t\tcount_no_opts = sum(1 for _ in all_configurations(model=model, coords=coords, **independent_opts, scalarmult={\"scl\": None, \"always\": True, \"short_circuit\": True, \"complete\": False, \"precompute_negation\": True, \"width\": 3, \"m\": 3, \"direction\": ProcessingDirection.LTR, \"accumulation_order\": AccumulationOrder.PeqPR, \"recoding_direction\": ProcessingDirection.LTR}))\n",
    "\t\tcoords_counts.append([\"\", coords_name, count * no_ff, count, count_no_scl, count_no_opts])\n",
    "display(HTML(tabulate.tabulate(coords_counts, tablefmt=\"html\", headers=\"firstrow\")))"
   ],
   "outputs": [],
   "execution_count": null
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": "### Scalar multipliers"
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": "Let's examine the split between different scalar multipliers."
  },
  {
   "cell_type": "code",
   "metadata": {},
   "source": [
    "from pyecsca.ec.mult import ScalarMultiplier\n",
    "\n",
    "def leaf_subclasses(cls):\n",
    "    subs = cls.__subclasses__()\n",
    "    result = set()\n",
    "    for subclass in subs:\n",
    "        if subclass.__subclasses__():\n",
    "            result.update(leaf_subclasses(subclass))\n",
    "        else:\n",
    "            result.add(subclass)\n",
    "    return result\n",
    "\n",
    "mult_counts = [[\"ScalarMultiplier\", \"All\", \"Without independent options\", \"Without independent options and scaling\", \"Without independent options and scalarmult options\"]]\n",
    "for mult_cls in leaf_subclasses(ScalarMultiplier):\n",
    "\tcount = sum(1 for _ in all_configurations(**independent_opts, scalarmult=mult_cls))\n",
    "\tcount_no_scl = sum(1 for _ in all_configurations(**independent_opts, scalarmult={\"cls\": mult_cls, \"scl\": None}))\n",
    "\tcount_no_opts = sum(1 for _ in all_configurations(**independent_opts, scalarmult={\"cls\": mult_cls, \"scl\": None, \"always\": True, \"short_circuit\": True, \"complete\": False, \"precompute_negation\": True, \"width\": 3, \"m\": 3, \"direction\": ProcessingDirection.LTR, \"accumulation_order\": AccumulationOrder.PeqPR, \"recoding_direction\": ProcessingDirection.LTR}))\n",
    "\tmult_counts.append([mult_cls.__name__, count * no_ff, count, count_no_scl, count_no_opts])\n",
    "display(HTML(tabulate.tabulate(mult_counts, tablefmt=\"html\", headers=\"firstrow\")))\n"
   ],
   "outputs": [],
   "execution_count": null
  },
  {
   "cell_type": "code",
   "metadata": {},
   "source": [],
   "outputs": [],
   "execution_count": null
  }
 ],
 "metadata": {
  "@webio": {
   "lastCommId": "cde560b9f2c044d9845711a0a2b208b6",
   "lastKernelId": "fb83e665-19e4-4332-b620-9e2ea7aa7c62"
  },
  "hide_input": false,
  "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.4"
  },
  "latex_envs": {
   "LaTeX_envs_menu_present": true,
   "autoclose": false,
   "autocomplete": true,
   "bibliofile": "biblio.bib",
   "cite_by": "apalike",
   "current_citInitial": 1,
   "eqLabelWithNumbers": true,
   "eqNumInitial": 1,
   "hotkeys": {
    "equation": "Ctrl-E",
    "itemize": "Ctrl-I"
   },
   "labels_anchors": false,
   "latex_user_defs": false,
   "report_style_numbering": false,
   "user_envs_cfg": false
  },
  "pycharm": {
   "stem_cell": {
    "cell_type": "raw",
    "metadata": {
     "collapsed": false
    },
    "source": []
   }
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}