diff options
| -rw-r--r-- | epare/re.ipynb | 207 |
1 files changed, 147 insertions, 60 deletions
diff --git a/epare/re.ipynb b/epare/re.ipynb index 67cb658..e02b221 100644 --- a/epare/re.ipynb +++ b/epare/re.ipynb @@ -2,77 +2,105 @@ "cells": [ { "cell_type": "code", - "execution_count": null, + "execution_count": 2, "id": "3232df80-2a65-47ce-bc77-6a64f44d2404", "metadata": {}, "outputs": [], "source": [ + "import multiprocessing\n", + "import inspect\n", + "import tempfile\n", + "import sys\n", + "import pickle\n", + "\n", + "import matplotlib\n", + "import matplotlib.pyplot as plt\n", + "\n", + "from importlib import import_module, invalidate_caches\n", + "from functools import partial\n", + "from random import randint\n", + "from collections import Counter\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\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 random import randint\n", - "import matplotlib.pyplot as plt \n", - "from bs4 import BeautifulSoup\n", - "import pickle\n", - "import matplotlib" + "from pyecsca.misc.utils import TaskExecutor" ] }, { "cell_type": "code", - "execution_count": 16, + "execution_count": null, "id": "24de57fb-db3c-4c48-8d30-4d0814cce684", "metadata": {}, "outputs": [], "source": [ "model = ShortWeierstrassModel()\n", - "coords = model.coordinates[\"projective\"]\n", - "add = coords.formulas[\"add-2007-bl\"] # The formulas are irrelevant\n", - "dbl = coords.formulas[\"dbl-2007-bl\"]\n", - "neg = coords.formulas[\"neg\"]\n", - "\n", "\n", "# All dbl-and-add multipliers from https://github.com/J08nY/pyecsca/blob/master/pyecsca/ec/mult\n", "\n", - "window_mults = [SlidingWindowMultiplier(add,dbl,4), SlidingWindowMultiplier(add,dbl,5), SlidingWindowMultiplier(add,dbl,6),\\\n", - " FixedWindowLTRMultiplier(add,dbl,2**4), FixedWindowLTRMultiplier(add,dbl,2**5), FixedWindowLTRMultiplier(add,dbl,2**6),\\\n", - " WindowBoothMultiplier(add,dbl,neg,4), WindowBoothMultiplier(add,dbl,neg,5), WindowBoothMultiplier(add,dbl,neg,6)]\n", - "naf_mults = [WindowNAFMultiplier(add,dbl,neg,4),WindowNAFMultiplier(add,dbl,neg,5),WindowNAFMultiplier(add,dbl,neg,6),BinaryNAFMultiplier(add,dbl,neg)]\n", - "comb_mults = [CombMultiplier(add,dbl,4), \\\n", - " CombMultiplier(add,dbl,5), \\\n", - " CombMultiplier(add,dbl,6), \\\n", - " BGMWMultiplier(add,dbl,4),\\\n", - " BGMWMultiplier(add,dbl,5),\\\n", - " BGMWMultiplier(add,dbl,6)]\n", - "binary_mults = [LTRMultiplier(add,dbl), RTLMultiplier(add,dbl), CoronMultiplier(add,dbl)]\n", - "other_mults = [SimpleLadderMultiplier(add,dbl), FullPrecompMultiplier(add,dbl)]\n", - "with_precomputation = window_mults + naf_mults[:-1] + other_mults[:-1]+comb_mults\n", + "# Use partial funcs such that the \"multiples_computed\" method from RPA module can use fake formulas.\n", + "window_mults = [\n", + " partial(SlidingWindowMultiplier, width=4),\n", + " partial(SlidingWindowMultiplier, width=5),\n", + " partial(SlidingWindowMultiplier, width=6),\n", + " partial(FixedWindowLTRMultiplier, m=2**4),\n", + " partial(FixedWindowLTRMultiplier, m=2**5),\n", + " partial(FixedWindowLTRMultiplier, m=2**6),\n", + " partial(WindowBoothMultiplier, width=4),\n", + " partial(WindowBoothMultiplier, width=5),\n", + " partial(WindowBoothMultiplier, width=6)\n", + "]\n", + "naf_mults = [\n", + " partial(WindowNAFMultiplier, width=4),\n", + " partial(WindowNAFMultiplier, width=5),\n", + " partial(WindowNAFMultiplier, width=6),\n", + " partial(BinaryNAFMultiplier)\n", + "]\n", + "comb_mults = [\n", + " partial(CombMultiplier, width=4),\n", + " partial(CombMultiplier, width=5),\n", + " partial(CombMultiplier, width=6),\n", + " partial(BGMWMultiplier, width=4),\n", + " partial(BGMWMultiplier, width=5),\n", + " partial(BGMWMultiplier, width=6)\n", + "]\n", + "binary_mults = [\n", + " partial(LTRMultiplier),\n", + " partial(RTLMultiplier),\n", + " partial(CoronMultiplier)\n", + "]\n", + "other_mults = [\n", + " partial(SimpleLadderMultiplier),\n", + " partial(FullPrecompMultiplier)\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\n", - "\n" + "all_mults = window_mults + naf_mults + binary_mults + other_mults + comb_mults" ] }, { "cell_type": "code", - "execution_count": null, + "execution_count": 3, "id": "2bedc98a-f777-4dad-8e31-eb5d2ddeb8f4", "metadata": {}, "outputs": [], "source": [ - "def get_small_scalars(category, curve_name,mult, scalar, precomp_only = False):\n", - " \n", - " multiples = {}\n", - " params = get_params(category, curve_name, \"projective\")\n", - " with local(MultipleContext()) as ctx:\n", - " mult.init(params, params.generator)\n", - " if not precomp_only:\n", - " res = mult.multiply(scalar)\n", - " for m in ctx.points.values():\n", - " s = multiples.setdefault(m, set())\n", - " s.add(mult)\n", - " return list(ctx.points.values())\n", + "def get_small_scalars(params, mult, scalar, precomp_only = False):\n", + " mult_class = mult.func\n", + " if precomp_only:\n", + " use_init = True\n", + " use_multiply = False\n", + " else:\n", + " use_init = True\n", + " use_multiply = True\n", + " return multiples_computed(scalar, params, mult_class, mult, use_init, use_multiply)\n", "\n", "def divides_any(l,small_scalars):\n", " for s in small_scalars:\n", @@ -81,11 +109,15 @@ " return False\n", "\n", "def mult_label(mult):\n", - " try:\n", - " return f\"{mult.__class__.__name__}_{getattr(mult, 'width')}\"\n", - " except AttributeError:\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", - "\n", + " else:\n", + " # mult is a callable created from partial()\n", + " return f\"{mult.func.__name__}_{mult.args}_{mult.keywords}\"\n", "\n", "def get_general_distributions(divisors, bits, samples = 1000):\n", " distributions = {l:0 for l in divisors}\n", @@ -113,17 +145,30 @@ " distributions[l] = v/samples\n", " return distributions\n", "\n", - "def get_small_scalar_distributions(mult,category,curve, divisors, bits, samples = 100, precomp_only = False):\n", + "def get_small_scalar_distributions(mult, category, curve, divisors, bits, samples = 1000, precomp_only = False):\n", " small_scalars_distributions = {l:0 for l in divisors}\n", + " params = get_params(category, curve, \"projective\")\n", " for _ in range(samples):\n", " big_scalar = randint(1,2**bits)\n", - " small_scalars = get_small_scalars(category,curve,mult,big_scalar, precomp_only)\n", + " small_scalars = get_small_scalars(params, mult, big_scalar, precomp_only)\n", " for l in divisors:\n", " if divides_any(l, small_scalars):\n", " small_scalars_distributions[l]+=1\n", " for l,v in small_scalars_distributions.items():\n", " small_scalars_distributions[l] = v/samples\n", - " return small_scalars_distributions" + " return small_scalars_distributions\n", + "\n", + "def merge_probs(*prob_maps):\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()}" ] }, { @@ -152,23 +197,65 @@ "outputs": [], "source": [ "category = \"secg\"\n", - "curve=\"secp256r1\"\n", + "curve = \"secp256r1\"\n", + "num_workers = 16\n", "bits = 256\n", - "samples = 1000\n", + "samples = 10000\n", "selected_mults = all_mults\n", "selected_divisors = all_divisors\n", "\n", - "# distributions_mults = {mult:get_small_scalar_distributions(mult,category,curve,selected_divisors,bits, samples) for mult in selected_mults}\n", + "distributions_mults = {}\n", + "distributions_mults_precomp = {}" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "4bbf52ae-834e-4168-ad65-9eaa9b113e14", + "metadata": {}, + "outputs": [], + "source": [ + "with TaskExecutor(max_workers=num_workers) as pool:\n", + " for mult in selected_mults:\n", + " pool.submit_task(mult,\n", + " get_small_scalar_distributions,\n", + " mult, category, curve, selected_divisors, 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 mult not in distributions_mults:\n", + " distributions_mults[mult] = future.result()\n", + " else:\n", + " # Accumulate\n", + " distributions_mults[mult] = merge_probs(distributions_mults[mult], future.result())\n", + "\n", + "with TaskExecutor(max_workers=num_workers) as pool:\n", + " for mult in with_precomputation:\n", + " pool.submit_task(mult,\n", + " get_small_scalar_distributions,\n", + " mult, category, curve, selected_divisors, bits, samples, precomp_only=True)\n", + " for mult, future in tqdm(pool.as_completed(), desc=\"Computing small scalar distributions (precomp_only).\", total=len(pool.tasks)):\n", + " print(f\"Got {mult_label(mult)}.\")\n", + " if mult not in distributions_mults_precomp:\n", + " distributions_mults_precomp[mult] = future.result()\n", + " else:\n", + " # Accumulate\n", + " distributions_mults_precomp[mult] = merge_probs(distributions_mults_precomp[mult], future.result())\n", + "\n", + "# Single-core variant:\n", + "# distributions_mults = {mult:get_small_scalar_distributions(mult,category,curve,selected_divisors,bits, samples) for mult in tqdm(selected_mults)}\n", "# distributions_mults_precomp = {mult:get_small_scalar_distributions(mult,category,curve,selected_divisors,bits,samples,precomp_only=True) for mult in with_precomputation}\n", - "# with open(f\"distributions_{category}_{curve}_{bits}\",\"wb\") as h:\n", - "# pickle.dump(distributions_mults, h)\n", - "# with open(f\"distributions_{category}_{curve}_{bits}_precomp\",\"wb\") as h:\n", - "# pickle.dump(distributions_mults_precomp, h)\n", "\n", - "with open(f\"distributions_{category}_{curve}_{bits}\",\"rb\") as h:\n", - " distributions_mults = pickle.load(h)\n", - "with open(f\"distributions_{category}_{curve}_{bits}_precomp\",\"rb\") as h:\n", - " distributions_mults_precomp = pickle.load(h)" + "# Dump\n", + "with open(f\"distributions_{category}_{curve}_{bits}\",\"wb\") as h:\n", + " pickle.dump(distributions_mults, h)\n", + "with open(f\"distributions_{category}_{curve}_{bits}_precomp\",\"wb\") as h:\n", + " pickle.dump(distributions_mults_precomp, h)\n", + "\n", + "# Load\n", + "#with open(f\"distributions_{category}_{curve}_{bits}\",\"rb\") as h:\n", + "# distributions_mults = pickle.load(h)\n", + "#with open(f\"distributions_{category}_{curve}_{bits}_precomp\",\"rb\") as h:\n", + "# distributions_mults_precomp = pickle.load(h)" ] }, { @@ -613,7 +700,7 @@ "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", - "version": "3.10.12" + "version": "3.13.1" } }, "nbformat": 4, |