{
"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
}
