aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--epare/common.py87
-rw-r--r--epare/simulate.ipynb315
-rw-r--r--epare/visualize.ipynb692
3 files changed, 1094 insertions, 0 deletions
diff --git a/epare/common.py b/epare/common.py
new file mode 100644
index 0000000..3b10007
--- /dev/null
+++ b/epare/common.py
@@ -0,0 +1,87 @@
+import multiprocessing
+import inspect
+import tempfile
+import sys
+import os
+
+
+from contextlib import contextmanager
+from dataclasses import dataclass
+from functools import partial, cached_property
+from importlib import import_module, invalidate_caches
+from pathlib import Path
+from typing import Type, Any
+
+from pyecsca.ec.params import DomainParameters, get_params
+from pyecsca.ec.mult import *
+
+
+spawn_context = multiprocessing.get_context("spawn")
+
+# Allow to use "spawn" multiprocessing method for function defined in a Jupyter notebook.
+# https://neuromancer.sk/article/35
+@contextmanager
+def enable_spawn(func):
+ invalidate_caches()
+ source = inspect.getsource(func)
+ current_file_path = os.path.abspath(__file__)
+ with open(current_file_path, 'r') as self, tempfile.NamedTemporaryFile(suffix=".py", mode="w") as f:
+ f.write(self.read())
+ f.write(source)
+ f.flush()
+ path = Path(f.name)
+ directory = str(path.parent)
+ sys.path.append(directory)
+ module = import_module(str(path.stem))
+ yield getattr(module, func.__name__)
+ sys.path.remove(directory)
+
+
+@dataclass(frozen=True)
+class MultIdent:
+ klass: Type[ScalarMultiplier]
+ args: list[Any]
+ kwargs: dict[str, Any]
+
+ def __init__(self, klass: Type[ScalarMultiplier], *args, **kwargs):
+ object.__setattr__(self, "klass", klass)
+ object.__setattr__(self, "args", args if args is not None else [])
+ object.__setattr__(self, "kwargs", kwargs if kwargs is not None else {})
+
+ @cached_property
+ def partial(self):
+ return partial(self.klass, *self.args, **self.kwargs)
+
+ def __str__(self):
+ return f"{self.klass.__name__}_{self.args}_{self.kwargs}"
+
+ def __repr__(self):
+ return str(self)
+
+ def __hash__(self):
+ return hash((self.klass, tuple(self.args), tuple(self.kwargs.keys()), tuple(self.kwargs.values())))
+
+
+@dataclass
+class MultResults:
+ multiplications: list[set[int]]
+ samples: int
+
+ def merge(self, other: "MultResults"):
+ self.multiplications.extend(other.multiplications)
+ self.samples += other.samples
+
+ def __len__(self):
+ return self.samples
+
+ def __iter__(self):
+ yield from self.multiplications
+
+ def __getitem__(self, i):
+ return self.multiplications[i]
+
+ def __str__(self):
+ return f"MultResults({self.samples})"
+
+ def __repr__(self):
+ return str(self)
diff --git a/epare/simulate.ipynb b/epare/simulate.ipynb
new file mode 100644
index 0000000..0acc8f6
--- /dev/null
+++ b/epare/simulate.ipynb
@@ -0,0 +1,315 @@
+{
+ "cells": [
+ {
+ "cell_type": "markdown",
+ "id": "805d746e-610b-4d40-80d2-a8080a993f96",
+ "metadata": {},
+ "source": [
+ "# Simulating EPA-RE using points of low-order"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 4,
+ "id": "b4386513-cc14-434b-a748-2863f8657452",
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "import pickle\n",
+ "import itertools\n",
+ "\n",
+ "import matplotlib\n",
+ "import matplotlib.pyplot as plt\n",
+ "import numpy as np\n",
+ "\n",
+ "from collections import Counter\n",
+ "\n",
+ "from pathlib import Path\n",
+ "from random import randint\n",
+ "from typing import Type, Any\n",
+ "\n",
+ "from bs4 import BeautifulSoup\n",
+ "from tqdm.auto import tqdm, trange\n",
+ "\n",
+ "from pyecsca.ec.params import DomainParameters, get_params\n",
+ "from pyecsca.ec.mult import *\n",
+ "from pyecsca.sca.re.rpa import MultipleContext, rpa_distinguish, RPA, multiples_computed\n",
+ "from pyecsca.ec.context import DefaultContext, local\n",
+ "from pyecsca.ec.model import ShortWeierstrassModel\n",
+ "from pyecsca.ec.coordinates import AffineCoordinateModel\n",
+ "from pyecsca.misc.utils import TaskExecutor\n",
+ "\n",
+ "from common import MultIdent, MultResults, enable_spawn, spawn_context"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "id": "5b156d2a-7345-47f8-a76e-71a7d2be9d22",
+ "metadata": {},
+ "source": [
+ "## Initialize"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 5,
+ "id": "5c0e42dc-8c61-4e2e-962c-6af48f6eb321",
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "# All dbl-and-add multipliers from https://github.com/J08nY/pyecsca/blob/master/pyecsca/ec/mult\n",
+ "\n",
+ "window_mults = [\n",
+ " MultIdent(SlidingWindowMultiplier, width=3),\n",
+ " MultIdent(SlidingWindowMultiplier, width=4),\n",
+ " MultIdent(SlidingWindowMultiplier, width=5),\n",
+ " MultIdent(SlidingWindowMultiplier, width=6),\n",
+ " MultIdent(FixedWindowLTRMultiplier, m=2**4),\n",
+ " MultIdent(FixedWindowLTRMultiplier, m=2**5),\n",
+ " MultIdent(FixedWindowLTRMultiplier, m=2**6),\n",
+ " MultIdent(WindowBoothMultiplier, width=3),\n",
+ " MultIdent(WindowBoothMultiplier, width=4),\n",
+ " MultIdent(WindowBoothMultiplier, width=5),\n",
+ " MultIdent(WindowBoothMultiplier, width=6)\n",
+ "]\n",
+ "naf_mults = [\n",
+ " MultIdent(WindowNAFMultiplier, width=3),\n",
+ " MultIdent(WindowNAFMultiplier, width=4),\n",
+ " MultIdent(WindowNAFMultiplier, width=5),\n",
+ " MultIdent(WindowNAFMultiplier, width=6),\n",
+ " MultIdent(BinaryNAFMultiplier, direction=ProcessingDirection.LTR),\n",
+ " MultIdent(BinaryNAFMultiplier, direction=ProcessingDirection.RTL)\n",
+ "]\n",
+ "comb_mults = [\n",
+ " MultIdent(CombMultiplier, width=2),\n",
+ " MultIdent(CombMultiplier, width=3),\n",
+ " MultIdent(CombMultiplier, width=4),\n",
+ " MultIdent(CombMultiplier, width=5),\n",
+ " MultIdent(CombMultiplier, width=6),\n",
+ " MultIdent(BGMWMultiplier, width=2, direction=ProcessingDirection.LTR),\n",
+ " MultIdent(BGMWMultiplier, width=3, direction=ProcessingDirection.LTR),\n",
+ " MultIdent(BGMWMultiplier, width=4, direction=ProcessingDirection.LTR),\n",
+ " MultIdent(BGMWMultiplier, width=5, direction=ProcessingDirection.LTR),\n",
+ " MultIdent(BGMWMultiplier, width=6, direction=ProcessingDirection.LTR),\n",
+ " MultIdent(BGMWMultiplier, width=2, direction=ProcessingDirection.RTL),\n",
+ " MultIdent(BGMWMultiplier, width=3, direction=ProcessingDirection.RTL),\n",
+ " MultIdent(BGMWMultiplier, width=4, direction=ProcessingDirection.RTL),\n",
+ " MultIdent(BGMWMultiplier, width=5, direction=ProcessingDirection.RTL),\n",
+ " MultIdent(BGMWMultiplier, width=6, direction=ProcessingDirection.RTL)\n",
+ "]\n",
+ "binary_mults = [\n",
+ " MultIdent(LTRMultiplier, always=False),\n",
+ " MultIdent(LTRMultiplier, always=True),\n",
+ " MultIdent(RTLMultiplier, always=False),\n",
+ " MultIdent(RTLMultiplier, always=True),\n",
+ " MultIdent(CoronMultiplier)\n",
+ "]\n",
+ "other_mults = [\n",
+ " MultIdent(FullPrecompMultiplier, always=False),\n",
+ " MultIdent(FullPrecompMultiplier, always=True),\n",
+ " MultIdent(SimpleLadderMultiplier, complete=True),\n",
+ " MultIdent(SimpleLadderMultiplier, complete=False)\n",
+ "]\n",
+ "\n",
+ "all_mults = window_mults + naf_mults + binary_mults + other_mults + comb_mults"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 6,
+ "id": "a660e3ac-401b-47a0-92de-55afe63c420a",
+ "metadata": {},
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "41\n"
+ ]
+ }
+ ],
+ "source": [
+ "print(len(all_mults))"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 7,
+ "id": "07bc266d-35eb-4f6d-bdba-e9f6f66827f1",
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "# Needs imports on the inside to be spawn enabled to save memory.\n",
+ "\n",
+ "def get_general_multiples(bits: int, samples: int = 1000) -> MultResults:\n",
+ " from random import randint\n",
+ " results = []\n",
+ " for _ in range(samples):\n",
+ " big_scalar = randint(1, 2**bits)\n",
+ " results.append({big_scalar})\n",
+ " return MultResults(results, samples)\n",
+ "\n",
+ "def get_general_n_multiples(bits: int, n: int, samples: int = 1000) -> MultResults:\n",
+ " from random import randint\n",
+ " results = []\n",
+ " for _ in range(samples):\n",
+ " smult = set()\n",
+ " for i in range(n):\n",
+ " b = randint(1,256)\n",
+ " smult.add(randint(2**b,2**(b+1)))\n",
+ " results.append(smult)\n",
+ " return MultResults(results, samples)\n",
+ "\n",
+ "def get_small_scalar_multiples(mult: MultIdent, params: DomainParameters, bits: int, samples: int = 1000, use_init: bool = True, use_multiply: bool = True) -> MultResults:\n",
+ " from pyecsca.sca.re.rpa import multiples_computed\n",
+ " from random import randint\n",
+ " results = []\n",
+ " for _ in range(samples):\n",
+ " big_scalar = randint(1, 2**bits)\n",
+ " results.append(multiples_computed(big_scalar, params, mult.klass, mult.partial, use_init, use_multiply))\n",
+ " return MultResults(results, samples)"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "id": "8c5e9543-8447-4362-b9e2-c896d71f69a9",
+ "metadata": {},
+ "source": [
+ "## Prepare"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 8,
+ "id": "bb604b15-4ad6-43c0-9cfa-1b31611d73ce",
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "multiples_mults = {}"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 11,
+ "id": "4d5c7f10-618f-4612-b594-81d1607b0d1d",
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "category = \"secg\"\n",
+ "curve = \"secp256r1\"\n",
+ "params = get_params(category, curve, \"projective\")\n",
+ "num_workers = 20\n",
+ "bits = params.order.bit_length()\n",
+ "samples = 1000\n",
+ "selected_mults = all_mults"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "id": "3aaf712e-5b97-4390-8dd4-e1db1dfe36a2",
+ "metadata": {},
+ "source": [
+ "## Run\n",
+ "Run this cell as many times as you want. It will accumulate into multiples_mults."
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": null,
+ "id": "84359084-4116-436c-92cd-d43fdfeca842",
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "application/vnd.jupyter.widget-view+json": {
+ "model_id": "8050887d56444467ae4a9e8345acaab5",
+ "version_major": 2,
+ "version_minor": 0
+ },
+ "text/plain": [
+ "Computing small scalar distributions.: 0%| | 0/41 [00:00<?, ?it/s]"
+ ]
+ },
+ "metadata": {},
+ "output_type": "display_data"
+ }
+ ],
+ "source": [
+ "with TaskExecutor(max_workers=num_workers, mp_context=spawn_context) as pool, enable_spawn(get_small_scalar_multiples) as target:\n",
+ " for mult in selected_mults:\n",
+ " pool.submit_task(mult,\n",
+ " target,\n",
+ " mult, params, bits, samples)\n",
+ " for mult, future in tqdm(pool.as_completed(), desc=\"Computing small scalar distributions.\", total=len(pool.tasks)):\n",
+ " print(f\"Got {mult_label(mult)}.\")\n",
+ " if error := future.exception():\n",
+ " print(error)\n",
+ " continue\n",
+ " if mult not in multiples_mults:\n",
+ " multiples_mults[mult] = res\n",
+ " else:\n",
+ " # Accumulate\n",
+ " multiples_mults[mult].merge(res)"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "id": "6845ba69-74b0-4709-a64d-dd4860255ee2",
+ "metadata": {},
+ "source": [
+ "### Save"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": null,
+ "id": "0ae7f726-2981-48af-8ae3-a9afcf2dc18f",
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "with open(f\"multiples_{category}_{curve}_{bits}\",\"wb\") as h:\n",
+ " pickle.dump(multiples_mults, h)"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "id": "b4471a1d-fdc3-4be7-bd61-5ddd22180b41",
+ "metadata": {},
+ "source": [
+ "### Load"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": null,
+ "id": "3d291832-b0c7-4c3a-9989-22079e4e0f53",
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "with open(f\"multiples_{category}_{curve}_{bits}\", \"rb\") as f:\n",
+ " multiples_mults = pickle.load(f)"
+ ]
+ }
+ ],
+ "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.12.3"
+ }
+ },
+ "nbformat": 4,
+ "nbformat_minor": 5
+}
diff --git a/epare/visualize.ipynb b/epare/visualize.ipynb
new file mode 100644
index 0000000..8fa5bb1
--- /dev/null
+++ b/epare/visualize.ipynb
@@ -0,0 +1,692 @@
+{
+ "cells": [
+ {
+ "cell_type": "code",
+ "execution_count": null,
+ "id": "3232df80-2a65-47ce-bc77-6a64f44d2404",
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "import pickle\n",
+ "import itertools\n",
+ "\n",
+ "import matplotlib\n",
+ "import matplotlib.pyplot as plt\n",
+ "import numpy as np\n",
+ "\n",
+ "from collections import Counter\n",
+ "from pathlib import Path\n",
+ "from random import randint\n",
+ "\n",
+ "from bs4 import BeautifulSoup\n",
+ "from tqdm.auto import tqdm, trange\n",
+ "\n",
+ "from common import MultIdent, MultResults"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": null,
+ "id": "2130254b-4b88-4928-9fa0-88fa58de9fc7",
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "# All dbl-and-add multipliers from https://github.com/J08nY/pyecsca/blob/master/pyecsca/ec/mult\n",
+ "\n",
+ "window_mults = [\n",
+ " MultIdent(SlidingWindowMultiplier, width=4),\n",
+ " MultIdent(SlidingWindowMultiplier, width=5),\n",
+ " MultIdent(SlidingWindowMultiplier, width=6),\n",
+ " MultIdent(FixedWindowLTRMultiplier, m=2**4),\n",
+ " MultIdent(FixedWindowLTRMultiplier, m=2**5),\n",
+ " MultIdent(FixedWindowLTRMultiplier, m=2**6),\n",
+ " MultIdent(WindowBoothMultiplier, width=4),\n",
+ " MultIdent(WindowBoothMultiplier, width=5),\n",
+ " MultIdent(WindowBoothMultiplier, width=6)\n",
+ "]\n",
+ "naf_mults = [\n",
+ " MultIdent(WindowNAFMultiplier, width=4),\n",
+ " MultIdent(WindowNAFMultiplier, width=5),\n",
+ " MultIdent(WindowNAFMultiplier, width=6),\n",
+ " MultIdent(BinaryNAFMultiplier)\n",
+ "]\n",
+ "comb_mults = [\n",
+ " MultIdent(CombMultiplier, width=4),\n",
+ " MultIdent(CombMultiplier, width=5),\n",
+ " MultIdent(CombMultiplier, width=6),\n",
+ " MultIdent(BGMWMultiplier, width=4),\n",
+ " MultIdent(BGMWMultiplier, width=5),\n",
+ " MultIdent(BGMWMultiplier, width=6)\n",
+ "]\n",
+ "binary_mults = [\n",
+ " MultIdent(LTRMultiplier),\n",
+ " MultIdent(RTLMultiplier),\n",
+ " MultIdent(CoronMultiplier)\n",
+ "]\n",
+ "other_mults = [\n",
+ " MultIdent(FullPrecompMultiplier),\n",
+ " MultIdent(SimpleLadderMultiplier)\n",
+ "]\n",
+ "\n",
+ "with_precomputation = window_mults + naf_mults[:-1] + other_mults[:-1] + comb_mults\n",
+ "\n",
+ "all_mults = window_mults + naf_mults + binary_mults + other_mults + comb_mults"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": null,
+ "id": "2df8cd8c-9528-4755-83b5-10ecabaead54",
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "def divides_any(l: int, small_scalars: set[int]) -> bool:\n",
+ " if l in small_scalars:\n",
+ " return True\n",
+ " for s in small_scalars:\n",
+ " if s%l==0:\n",
+ " return True\n",
+ " return False\n",
+ "\n",
+ "def process_small_scalars(scalar_results: MultResults, divisors: set[int]) -> dict[int, float]:\n",
+ " result = {}\n",
+ " for divisor in tqdm(divisors, leave=False):\n",
+ " count = 0\n",
+ " for smult in scalar_results.multiplications:\n",
+ " if divides_any(divisor, smult):\n",
+ " count += 1\n",
+ " result[divisor] = count / scalar_results.samples\n",
+ " return result\n",
+ "\n",
+ "def merge_probs(*prob_maps: dict[int, float]) -> dict[int, float]:\n",
+ " # Merge two or more maps of \"small-scalar\" -> \"probability\" together by averaging them.\n",
+ " # This is correct if they were collected with the same amount of samples. If the\n",
+ " # amount of samples differs a lot this will not update as much as it should, but will\n",
+ " # update in the correct direction nonetheless.\n",
+ " counter = Counter()\n",
+ " nprobs = len(prob_maps)\n",
+ " for prob_map in prob_maps:\n",
+ " for k, v in prob_map.items():\n",
+ " counter[k] += v\n",
+ " return {k: v / nprobs for k, v in counter.items()}\n",
+ "\n",
+ "def mult_label(mult: MultIdent | ScalarMultiplier) -> str:\n",
+ " if isinstance(mult, ScalarMultiplier):\n",
+ " for attr in (\"width\", \"m\"):\n",
+ " if not hasattr(mult, attr):\n",
+ " continue\n",
+ " return f\"{mult.__class__.__name__}_{getattr(mult, attr)}\"\n",
+ " return mult.__class__.__name__\n",
+ " elif isinstance(mult, MultIdent):\n",
+ " return str(mult)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": null,
+ "id": "bab2a086-8b3d-4e76-bf5c-46ea2b617708",
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "def powers_of(k, max_power=10):\n",
+ " return [k**i for i in range(1, max_power)]\n",
+ "\n",
+ "def prod_combine(one, other):\n",
+ " return [a * b for a, b in itertools.product(one, other)]\n",
+ "\n",
+ "small_primes = [3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199]\n",
+ "medium_primes = [211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397]\n",
+ "large_primes = [401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997]\n",
+ "all_integers = list(range(1, 100))\n",
+ "\n",
+ "all_divisors = small_primes + medium_primes + large_primes #+ powers_of(2)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": null,
+ "id": "318ca5ac-66a6-4187-a01f-f0e2d27ba34e",
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "# Load\n",
+ "with open(f\"multiples_{category}_{curve}_{bits}\", \"rb\") as f:\n",
+ " multiples_mults = pickle.load(f)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": null,
+ "id": "4d2a0f19-8275-4db8-b3fc-c930d8ba2177",
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "selected_mults = all_mults\n",
+ "selected_divisors = all_divisors"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": null,
+ "id": "6b42d25f-6ce1-477a-bc5f-d7c2a8af87a3",
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "distributions_mults = {}\n",
+ "for mult, results in tqdm(multiples_mults.items()):\n",
+ " distributions_mults[mult] = process_small_scalars(results, selected_divisors)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": null,
+ "id": "906b5d78-b3a4-4cbb-8051-092d411ba735",
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "plot_mults = selected_mults\n",
+ "plot_divisors = selected_divisors\n",
+ "\n",
+ "colors = {mult:matplotlib.cm.tab20(range(len(plot_mults)))[i] for i,mult in enumerate(plot_mults)}\n",
+ "\n",
+ "fig = plt.subplots(figsize=(36, 12))\n",
+ "\n",
+ "L = len(plot_divisors)\n",
+ "plot_divisors = sorted(plot_divisors)\n",
+ "for mult in plot_mults:\n",
+ " y_values = [distributions_mults[mult][l] for l in plot_divisors]\n",
+ " plt.plot(list(range(L)), y_values, color=colors[mult], label=str(mult))\n",
+ "plt.plot(list(range(L)), var / np.max(var), label=\"cross-mult variance (normalized)\", ls=\"--\", lw=2, color=\"black\")\n",
+ "plt.xlabel(\"divisors\") \n",
+ "plt.ylabel(\"error probability\")\n",
+ "plt.xticks(list(range(L)), plot_divisors, rotation=90)\n",
+ "\n",
+ "plt.grid()\n",
+ "plt.legend()\n",
+ "plt.show() \n",
+ "fig[0].savefig(f\"graphs/re.png\",dpi=300)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": null,
+ "id": "b7fcd473-6cde-4913-9274-ff02f5ddb786",
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "plot_mults = [mult for mult in selected_mults if mult.klass not in (CombMultiplier, BGMWMultiplier)]\n",
+ "plot_divisors = selected_divisors\n",
+ "\n",
+ "colors = {mult:matplotlib.cm.tab20(range(len(plot_mults)))[i] for i,mult in enumerate(plot_mults)}\n",
+ "\n",
+ "fig = plt.subplots(figsize=(36, 12))\n",
+ "\n",
+ "L = len(plot_divisors)\n",
+ "N = len(plot_mults)\n",
+ "plot_divisors = sorted(plot_divisors)\n",
+ "vals = np.zeros((N, L))\n",
+ "for i, mult in enumerate(plot_mults):\n",
+ " for j, m in enumerate(plot_divisors):\n",
+ " y = distributions_mults[mult][m]\n",
+ " vals[i, j] = y\n",
+ "var = np.var(vals, axis=0)\n",
+ "plt.plot(list(range(L)), var, label=\"cross-mult variance\", ls=\"--\", lw=2, color=\"black\")\n",
+ "\n",
+ "plt.xlabel(\"divisors\")\n",
+ "plt.ylabel(\"variance\")\n",
+ "plt.xticks(list(range(L)), plot_divisors, rotation=90)\n",
+ "\n",
+ "plt.grid()\n",
+ "plt.legend()\n",
+ "plt.show() \n",
+ "fig[0].savefig(f\"graphs/cross_var.png\",dpi=300)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": null,
+ "id": "8454cb7a-5308-43c6-9cd0-5de7946ec72a",
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "# general_distributions = get_general_distributions(selected_divisors, bits, samples)\n",
+ "# general_n_distributions = get_general_n_distributions(selected_divisors, bits, 256, samples)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": null,
+ "id": "8eae8df8-0bf8-4a9d-a55e-deea6a9d6b07",
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "\n",
+ "selected_mults = all_mults#window_mults[0:1]+window_mults[5:6]+naf_mults[1:2]#[mult for mult in all_mults if not mult in comb_mults]\n",
+ "selected_divisors = all_divisors\n",
+ "colors = {mult:matplotlib.cm.tab20(range(len(distributions_mults_10k)))[i] for i,mult in enumerate(distributions_mults_10k)}\n",
+ "\n",
+ "\n",
+ "fig = plt.subplots(figsize =(36, 12)) \n",
+ "\n",
+ "L = len(selected_divisors)\n",
+ "selected_divisors = sorted(selected_divisors)\n",
+ "for mult in distributions_mults_10k:\n",
+ " y_values = [distributions_mults_10k[mult][l] for l in selected_divisors]\n",
+ " plt.plot([l for l in range(L)],y_values,color = colors[mult], label = mult_label(mult))\n",
+ "\n",
+ "# mult = list(fixedwindow_dist.keys())[0]\n",
+ "# plt.plot([l for l in range(L)],[fixedwindow_dist[l] for l in selected_divisors],color = \"pink\", label = mult_label(mult))\n",
+ "\n",
+ "# measured_dist = measured_distribution(library,selected_divisors)\n",
+ "# mes_x, mes_y = [],[]\n",
+ "# for i,l in enumerate(selected_divisors):\n",
+ "# if l in measured_dist:\n",
+ "# mes_y.append(measured_dist[l])\n",
+ "# mes_x.append(i)\n",
+ "# plt.scatter(mes_x,mes_y,color = \"black\", label = library)\n",
+ "\n",
+ "#attempts = 0\n",
+ "#fails =0\n",
+ "#for i in range(51):\n",
+ "# with open(f\"cards/jcop/199_{i}.txt\") as f:\n",
+ "# attempts += f.read().count(\"ALG_EC_SVDP_DH of remote pubkey and local privkey\")+1\n",
+ "# fails += 1\n",
+ "#plt.scatter([selected_divisors.index(199)],[fails/attempts],s=[40],color = \"black\", label = \"jcop\")\n",
+ "\n",
+ "#plt.plot([l for l in range(L)],[general_distributions[l] for l in selected_divisors],color = \"black\", label = \"prime-distribution\")\n",
+ "\n",
+ "\n",
+ "plt.xlabel('divisors') \n",
+ "plt.ylabel(\"prob\") \n",
+ "plt.xticks([r for r in range(L)], selected_divisors)\n",
+ "\n",
+ "plt.legend()\n",
+ "plt.show() \n",
+ "fig[0].savefig(f\"graphs/re.png\",dpi=300)\n"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": null,
+ "id": "d240059f-9ed6-4864-b4bf-525de576272f",
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "selected_mults = with_precomputation\n",
+ "selected_divisors = all_divisors\n",
+ "colors = {mult:matplotlib.cm.tab20(range(len(selected_mults)))[i] for i,mult in enumerate(selected_mults)}\n",
+ "\n",
+ "\n",
+ "fig = plt.subplots(figsize =(24, 12)) \n",
+ "\n",
+ "L = len(selected_divisors)\n",
+ "selected_divisors = sorted(selected_divisors)\n",
+ "for mult in selected_mults:\n",
+ " plt.plot([l for l in range(L)],[distributions_mults_precomp[mult][l] for l in selected_divisors],color = colors[mult], label = mult_label(mult))\n",
+ "\n",
+ "\n",
+ "#measured_dist = measured_distribution(library,selected_divisors)\n",
+ "#mes_x, mes_y = [],[]\n",
+ "#for i,l in enumerate(selected_divisors):\n",
+ "# if l in measured_dist:\n",
+ "# mes_y.append(measured_dist[l])\n",
+ "# mes_x.append(i)\n",
+ "#plt.scatter(mes_x,mes_y,color = \"black\", label = library)\n",
+ "\n",
+ "\n",
+ "plt.xlabel('divisors') \n",
+ "plt.ylabel(\"prob\") \n",
+ "plt.xticks([r for r in range(L)], selected_divisors)\n",
+ "\n",
+ "plt.legend()\n",
+ "plt.show() "
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": null,
+ "id": "0da0eed4-a5dc-4dde-9bd1-8b519d02375e",
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "def nok_ecdh(line):\n",
+ " return int(line.split(\";\")[-1].strip(),16)==0\n",
+ "\n",
+ "def measured_distribution(library, selected_divisors):\n",
+ " measured_distribution = {}\n",
+ " counts = {order:0 for order in selected_divisors}\n",
+ " for div in selected_divisors:\n",
+ " errors = 0\n",
+ " with open(f\"./ecdh/{library}/ecdh_{div}.txt\") as f:\n",
+ " for line in f.readlines()[1:]:\n",
+ " if nok_ecdh(line):\n",
+ " errors+=1\n",
+ " counts[div]+=1\n",
+ " measured_distribution[div] = errors\n",
+ " \n",
+ " for o,v in measured_distribution.items():\n",
+ " if counts[o]!=0:\n",
+ " measured_distribution[o] = v/counts[o]\n",
+ " return measured_distribution"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": null,
+ "id": "6f8b83e3-7e2e-409a-82bd-7d44316236c6",
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "selected_mults = other_mults[:1]+binary_mults[:1]+comb_mults[:1]+window_mults[:1]\n",
+ "selected_divisors = small_primes#all_divisors\n",
+ "library = \"tomcrypt\"\n",
+ "colors = {mult:matplotlib.cm.tab20(range(len(selected_mults)))[i] for i,mult in enumerate(selected_mults)}\n",
+ "\n",
+ "fig = plt.subplots(figsize =(24, 12)) \n",
+ "\n",
+ "L = len(selected_divisors)\n",
+ "selected_divisors = sorted(selected_divisors)\n",
+ "for mult in selected_mults:\n",
+ " plt.plot([l for l in range(L)],[distributions_mults[mult][l] for l in selected_divisors],color = colors[mult], label = mult_label(mult))\n",
+ "\n",
+ "\n",
+ "measured_dist = measured_distribution(library,selected_divisors)\n",
+ "mes_x, mes_y = [],[]\n",
+ "for i,l in enumerate(selected_divisors):\n",
+ " if l in measured_dist:\n",
+ " mes_y.append(measured_dist[l])\n",
+ " mes_x.append(i)\n",
+ "plt.scatter(mes_x,mes_y,color = \"black\", label = library)\n",
+ "\n",
+ "\n",
+ "plt.xlabel('divisors') \n",
+ "plt.ylabel(\"prob\") \n",
+ "plt.xticks([r for r in range(L)], selected_divisors)\n",
+ "plt.legend(loc=\"upper right\")\n",
+ "plt.show() \n",
+ "fig[0].savefig(f\"graphs/{library}/re.png\",dpi=300)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": null,
+ "id": "b7936e5b-76d2-410f-82b1-36333071bd12",
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "selected_mults = [mult for mult in with_precomputation if mult in comb_mults]\n",
+ "selected_divisors = small_primes#all_divisors\n",
+ "library = \"mbedtls\"\n",
+ "colors = {mult:matplotlib.cm.tab20(range(len(selected_mults)))[i] for i,mult in enumerate(selected_mults)}\n",
+ "\n",
+ "fig = plt.subplots(figsize =(24, 12)) \n",
+ "\n",
+ "L = len(selected_divisors)\n",
+ "selected_divisors = sorted(selected_divisors)\n",
+ "for mult in selected_mults:\n",
+ " plt.plot([l for l in range(L)],[distributions_mults_precomp[mult][l] for l in selected_divisors],color = colors[mult], label = mult_label(mult))\n",
+ "\n",
+ "\n",
+ "measured_dist = measured_distribution(library,selected_divisors)\n",
+ "mes_x, mes_y = [],[]\n",
+ "for i,l in enumerate(selected_divisors):\n",
+ " if l in measured_dist:\n",
+ " mes_y.append(measured_dist[l])\n",
+ " mes_x.append(i)\n",
+ "plt.scatter(mes_x,mes_y,color = \"black\", label = library)\n",
+ "\n",
+ "plt.xlabel('divisors') \n",
+ "plt.ylabel(\"prob\") \n",
+ "plt.xticks([r for r in range(L)], selected_divisors)\n",
+ "plt.legend()\n",
+ "plt.show() \n",
+ "fig[0].savefig(f\"graphs/{library}/re.png\",dpi=300)"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "id": "dbdd0219-3937-4ef3-8cb3-b90f03af9977",
+ "metadata": {},
+ "source": [
+ "BouncyCastle\n",
+ " - WindowBooth-5?\n",
+ "\n",
+ "Mbedtls\n",
+ " - CombMultiplier-4\n",
+ " - confirmed in library\n",
+ " \n",
+ "tomcrypt\n",
+ " - ladder or coron\n",
+ " - ladder confirmed in library\n",
+ "\n",
+ "OpenSSL, LibreSSL, Botan, Crypto++ and IPPCP followed the general distribution of divisibility by the primes. So they have some countermeasure.\n",
+ "\n",
+ "Note that some libraries for some orders output \"Invalid algorithm parameter: Not supported.\". For libcrypt, SunEC and Nettle it happened for all orders.\n",
+ "BoringSSL\n",
+ " - \"Invalid algorithm parameter: Error creating EC_GROUP, EC_GROUP_set_generator.\"\n"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": null,
+ "id": "34609ae2-fa8c-4437-a601-cd25a0708a19",
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "def scatter(library, color):\n",
+ " measured_dist = measured_distribution(library,selected_divisors)\n",
+ " mes_x, mes_y = [],[]\n",
+ " for i,l in enumerate(selected_divisors):\n",
+ " if l in measured_dist:\n",
+ " mes_y.append(measured_dist[l])\n",
+ " mes_x.append(i)\n",
+ " plt.scatter(mes_x,mes_y,color = color, label = library)\n",
+ "\n",
+ "selected_divisors = small_primes#all_divisors\n",
+ "\n",
+ "fig = plt.subplots(figsize =(24, 12)) \n",
+ "\n",
+ "L = len(selected_divisors)\n",
+ "\n",
+ "colors = matplotlib.cm.tab20(range(6))\n",
+ "scatter(\"openssl\",colors[0])\n",
+ "scatter(\"libressl\",colors[1])\n",
+ "scatter(\"botan\",colors[2])\n",
+ "scatter(\"Crypto++\",colors[3])\n",
+ "scatter(\"ippcp\",colors[4])\n",
+ "\n",
+ "plt.plot([l for l in range(L)],[general_distributions[l] for l in selected_divisors],color = colors[5], label = \"prime-distribution\")\n",
+ "\n",
+ "plt.xlabel('divisors') \n",
+ "plt.ylabel(\"prob\") \n",
+ "plt.xticks([r for r in range(L)], selected_divisors)\n",
+ "plt.legend()\n",
+ "plt.show() \n",
+ "fig[0].savefig(f\"graphs/resistant.png\",dpi=300)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": null,
+ "id": "1f403fa3-880d-45a8-aaf3-964b0fbc38d7",
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "def scatter(library, color):\n",
+ " measured_dist = measured_distribution(library,selected_divisors)\n",
+ " mes_x, mes_y = [],[]\n",
+ " for i,l in enumerate(selected_divisors):\n",
+ " if l in measured_dist:\n",
+ " mes_y.append(measured_dist[l])\n",
+ " mes_x.append(i)\n",
+ " # plt.scatter(mes_x,mes_y,color = color, label = library)\n",
+ " plt.plot(mes_x,mes_y,color = color, linewidth = 1, label = library)\n",
+ "\n",
+ "selected_divisors = small_primes[:12]#all_divisors\n",
+ "\n",
+ "fig = plt.subplots(figsize =(10, 4)) \n",
+ "\n",
+ "L = len(selected_divisors)\n",
+ "\n",
+ "colors = matplotlib.cm.tab20(range(9))\n",
+ "scatter(\"openssl\",colors[0])\n",
+ "scatter(\"libressl\",colors[1])\n",
+ "scatter(\"botan\",colors[2])\n",
+ "scatter(\"Crypto++\",colors[3])\n",
+ "scatter(\"mbedtls\",colors[4])\n",
+ "scatter(\"libressl\",colors[5])\n",
+ "scatter(\"BouncyCastle\",colors[6])\n",
+ "scatter(\"tomcrypt\",colors[7])\n",
+ "scatter(\"ippcp\",colors[8])\n",
+ "\n",
+ "\n",
+ "# plt.plot([l for l in range(L)],[general_distributions[l] for l in selected_divisors],color = colors[9], label = \"divison-distribution\")\n",
+ "\n",
+ "plt.xlabel('Input point order',fontsize=15) \n",
+ "plt.ylabel(\"Error rate\",fontsize=15) \n",
+ "plt.xticks([r for r in range(L)], [v if i%1==0 else \"\" for i,v in enumerate(selected_divisors)])\n",
+ "plt.legend(loc=\"center right\",prop={'size': 11})\n",
+ "plt.tight_layout()\n",
+ "plt.show() \n",
+ "fig[0].savefig(f\"graphs/lib_dists.png\",dpi=300)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": null,
+ "id": "a0415861-c9ee-4420-bb82-6fda216d401c",
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "def bars(library, color,shift,width):\n",
+ " measured_dist = measured_distribution(library,selected_divisors)\n",
+ " mes_x, mes_y = [],[]\n",
+ " for i,l in enumerate(selected_divisors):\n",
+ " offset = width*shift\n",
+ " if l in measured_dist:\n",
+ " mes_y.append(measured_dist[l])\n",
+ " mes_x.append(2*i+offset)\n",
+ " plt.bar(mes_x,mes_y,width=0.1,color = color,align ='center', label = labels.get(library,library))\n",
+ "\n",
+ "selected_divisors = small_primes[:12]#all_divisors\n",
+ "\n",
+ "fig = plt.subplots(figsize =(10, 4)) \n",
+ "\n",
+ "L = len(selected_divisors)\n",
+ "\n",
+ "colors = matplotlib.cm.tab20(range(9))\n",
+ "width = 0.2\n",
+ "for i,lib in enumerate((\"openssl\",\"libressl\",\"botan\",\"Crypto++\",\"mbedtls\",\"BouncyCastle\",\"tomcrypt\",\"ippcp\")):\n",
+ " bars(lib,colors[i],i,width)\n",
+ "\n",
+ "\n",
+ "plt.plot([2*l+4*width for l in range(L)],[general_distributions[l] for l in selected_divisors],color = colors[8], label = \"expected distribution\")\n",
+ "\n",
+ "plt.xlabel('Input point order',fontsize=15) \n",
+ "plt.ylabel(\"Error rate\",fontsize=15) \n",
+ "plt.xticks([2*r+4*width for r in range(L)], [v if i%1==0 else \"\" for i,v in enumerate(selected_divisors)])\n",
+ "plt.legend(loc=\"upper right\",prop={'size': 11})\n",
+ "plt.tight_layout()\n",
+ "plt.show() \n",
+ "fig[0].savefig(f\"graphs/lib_dists.png\",dpi=300)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": null,
+ "id": "e5f036c8-3d47-4105-9a67-79b2b8e1ecdb",
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "from math import sqrt\n",
+ "\n",
+ "selected_mults = all_mults#window_mults[0:1]+window_mults[5:6]+naf_mults[1:2]#[mult for mult in all_mults if not mult in comb_mults]\n",
+ "selected_divisors = small_primes#ll_divisors\n",
+ "colors = {mult:matplotlib.cm.tab20(range(len(selected_mults)))[i] for i,mult in enumerate(selected_mults)}\n",
+ "\n",
+ "\n",
+ "fig = plt.subplots(figsize =(30, 20)) \n",
+ "\n",
+ "L = len(selected_divisors)\n",
+ "selected_divisors = sorted(selected_divisors)\n",
+ "for mult in selected_mults:\n",
+ " y_values,y_values_mstd, y_values_pstd = [],[],[]\n",
+ " for l in selected_divisors:\n",
+ " p = distributions_mults[mult][l]\n",
+ " y_values.append(1/p)\n",
+ " y_values_mstd.append(1/p-sqrt((1-p)/p**2))\n",
+ " y_values_pstd.append(1/p+sqrt((1-p)/p**2))\n",
+ " plt.plot([l for l in range(L)],y_values,color = colors[mult], label = mult_label(mult))\n",
+ " plt.fill_between([l for l in range(L)], y_values_mstd , y_values_pstd, alpha = 0.1, color = colors[mult])\n",
+ " \n",
+ "# mult = list(fixedwindow_dist.keys())[0]\n",
+ "# plt.plot([l for l in range(L)],[fixedwindow_dist[l] for l in selected_divisors],color = \"pink\", label = mult_label(mult))\n",
+ "\n",
+ "# measured_dist = measured_distribution(library,selected_divisors)\n",
+ "# mes_x, mes_y = [],[]\n",
+ "# for i,l in enumerate(selected_divisors):\n",
+ "# if l in measured_dist:\n",
+ "# mes_y.append(measured_dist[l])\n",
+ "# mes_x.append(i)\n",
+ "# plt.scatter(mes_x,mes_y,color = \"black\", label = library)\n",
+ "\n",
+ "plt.plot([l for l in range(L)],[1/general_distributions[l] for l in selected_divisors],color = \"black\", label = \"prime-distribution\")\n",
+ "\n",
+ "steps_dist = {}\n",
+ "for i in range(51):\n",
+ " with open(f\"cards/jcop/199_{i}.txt\") as f:\n",
+ " steps = f.read().count(\"ALG_EC_SVDP_DH of remote pubkey and local privkey\")\n",
+ " if not steps in steps_dist:\n",
+ " steps_dist[steps] = 0\n",
+ " steps_dist[steps]+=1\n",
+ "ys = sorted(list(steps_dist.keys()))\n",
+ "plt.scatter([selected_divisors.index(199)]*len(ys),ys, s=[steps_dist[y]*20 for y in ys],color=\"black\")\n",
+ "for i, y in enumerate(ys):\n",
+ " plt.annotate(str(steps_dist[y]), (selected_divisors.index(199)-1, y))\n",
+ "avg = 0\n",
+ "for s,c in steps_dist.items():\n",
+ " avg+=s*c\n",
+ "avg = avg/sum(steps_dist.values())\n",
+ "plt.scatter([selected_divisors.index(199)],[avg], s=[30],color=\"yellow\")\n",
+ " \n",
+ "plt.xlabel('divisors') \n",
+ "plt.ylabel(\"prob\") \n",
+ "plt.yticks(range(12))\n",
+ "plt.xticks([r for r in range(L)], selected_divisors)\n",
+ "\n",
+ "plt.legend()\n",
+ "plt.show() \n",
+ "fig[0].savefig(f\"graphs/re.png\",dpi=300)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": null,
+ "id": "37a64963-e63a-4c74-8414-6d29482e7151",
+ "metadata": {},
+ "outputs": [],
+ "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.12.3"
+ }
+ },
+ "nbformat": 4,
+ "nbformat_minor": 5
+}
generated by cgit v1.2.3-70-g09d2 (git 2.51.2) at 2025-11-08 15:14:31 +0000