From ed6448c1e3c1d972c1d49ebdd873ea98436390f1 Mon Sep 17 00:00:00 2001
From: J08nY
Date: Sun, 20 Apr 2025 21:40:08 +0200
Subject: Rename countermeasures pyecsca notebook to simulation.
---
analysis/countermeasures/countermeasures.ipynb | 1045 -------------
analysis/countermeasures/simulation.ipynb | 1910 ++++++++++++++++++++++++
2 files changed, 1910 insertions(+), 1045 deletions(-)
delete mode 100644 analysis/countermeasures/countermeasures.ipynb
create mode 100644 analysis/countermeasures/simulation.ipynb
diff --git a/analysis/countermeasures/countermeasures.ipynb b/analysis/countermeasures/countermeasures.ipynb
deleted file mode 100644
index 58c654d..0000000
--- a/analysis/countermeasures/countermeasures.ipynb
+++ /dev/null
@@ -1,1045 +0,0 @@
-{
- "cells": [
- {
- "cell_type": "markdown",
- "id": "bafc2f4e-05a3-4120-bcd6-5d1f5fb91cd9",
- "metadata": {},
- "source": [
- "# Distinguishing countermeasures by output"
- ]
- },
- {
- "cell_type": "code",
- "execution_count": 69,
- "id": "33ee6084-2ac3-4f95-9610-0fbc06026538",
- "metadata": {},
- "outputs": [],
- "source": [
- "import io\n",
- "import random\n",
- "import itertools\n",
- "import warnings\n",
- "\n",
- "import cypari2\n",
- "from cysignals.alarm import alarm, AlarmInterrupt\n",
- "\n",
- "from matplotlib import pyplot as plt\n",
- "from collections import Counter\n",
- "from tqdm.auto import tqdm, trange\n",
- "\n",
- "from pyecsca.misc.utils import TaskExecutor\n",
- "from pyecsca.ec.mod import mod, RandomModAction\n",
- "from pyecsca.ec.point import Point\n",
- "from pyecsca.ec.model import ShortWeierstrassModel\n",
- "from pyecsca.ec.params import load_params_ectester\n",
- "from pyecsca.ec.mult import LTRMultiplier\n",
- "from pyecsca.ec.context import local, DefaultContext\n",
- "from pyecsca.ec.countermeasures import GroupScalarRandomization, AdditiveSplitting, MultiplicativeSplitting, EuclideanSplitting, BrumleyTuveri\n",
- "\n",
- "%matplotlib ipympl"
- ]
- },
- {
- "cell_type": "code",
- "execution_count": null,
- "id": "b1b9596c-1eba-4ace-af84-8cb279d84cc2",
- "metadata": {},
- "outputs": [],
- "source": [
- "model = ShortWeierstrassModel()\n",
- "coords = model.coordinates[\"projective\"]"
- ]
- },
- {
- "cell_type": "code",
- "execution_count": null,
- "id": "b0afb195-8390-44c5-931e-75a70ccd4e9e",
- "metadata": {},
- "outputs": [],
- "source": [
- "add = coords.formulas[\"add-2015-rcb\"]\n",
- "dbl = coords.formulas[\"dbl-2015-rcb\"]\n",
- "mult = LTRMultiplier(add, dbl, complete=False)"
- ]
- },
- {
- "cell_type": "code",
- "execution_count": null,
- "id": "52c877e1-5021-4ec2-9daa-dd20bec6bcb2",
- "metadata": {},
- "outputs": [],
- "source": [
- "gsr = GroupScalarRandomization(mult)\n",
- "asplit = AdditiveSplitting(mult)\n",
- "msplit = MultiplicativeSplitting(mult)\n",
- "esplit = EuclideanSplitting(mult)\n",
- "bt = BrumleyTuveri(mult)"
- ]
- },
- {
- "cell_type": "markdown",
- "id": "27626337-dcbc-497c-a54e-02d50e2b8f34",
- "metadata": {},
- "source": [
- "## 3n test"
- ]
- },
- {
- "cell_type": "code",
- "execution_count": null,
- "id": "c3088419-161b-4193-a1b6-6f623f217fcd",
- "metadata": {},
- "outputs": [],
- "source": [
- "key3n = 0x20959f2b437de1e522baf6d814911938157390d3ea5118660b852ab0d5387006\n",
- "params3n = load_params_ectester(io.BytesIO(b\"0xc381bb0394f34b5ed061c9107b66974f4d0a8ec89b9fe73b98b6d1368c7d974d,0x5ca6c5ee0a10097af291a8f125303fb1a3e35e8100411902245d691e0e5cb497,0x385a5a8bb8af94721f6fd10b562606d9b9df931f7fd966e96859bb9bd7c05836,0x4616af1898b92cac0f902a9daee24bbae63571cead270467c6a7886ced421f5e,0x34e896bdb1337e0ae5960fa3389fb59c2c8d6c7dbfd9aac33a844f8f98e433ef,0x412b3e5686fbc3ca4575edb0292232702ae721a7d4a230cc170a5561aa70e00f,0x01\"), \"projective\")\n",
- "bits3n = params3n.full_order.bit_length()\n",
- "point3n = Point(X=mod(0x4a48addb2e471767b7cd0f6f1d4c27fe46f4a828fc20f950bd1f72c939b36a84, params3n.curve.prime),\n",
- " Y=mod(0x13384d38c353f862832c0f067e46a3e510bb6803c20745dfb31929f4a18d890d, params3n.curve.prime),\n",
- " Z=mod(1, params3n.curve.prime), model=coords)"
- ]
- },
- {
- "cell_type": "code",
- "execution_count": null,
- "id": "a8dde7e6-cd48-4f99-9677-23a19e4c2e5b",
- "metadata": {},
- "outputs": [],
- "source": [
- "print(f\"prime:\\t0x{params3n.curve.prime:x}\")\n",
- "print(f\"a:\\t0x{params3n.curve.parameters['a']:x}\")\n",
- "print(f\"b:\\t0x{params3n.curve.parameters['b']:x}\")\n",
- "print(f\"G:\\t[0x{params3n.generator.X:x},\\n\\t 0x{params3n.generator.Y:x}]\")\n",
- "print(f\"n:\\t0x{params3n.order:x}\")\n",
- "print(f\"3n:\\t0x{3 * params3n.order:x}\")\n",
- "print(f\"\\nP:\\t[0x{point3n.X:x},\\n\\t 0x{point3n.Y:x}]\")"
- ]
- },
- {
- "cell_type": "code",
- "execution_count": null,
- "id": "cd6f8500-7509-45b0-8b23-471ee5014f42",
- "metadata": {},
- "outputs": [],
- "source": [
- "def generate_scalars_mod3(rem, samples):\n",
- " scalars = []\n",
- " while True:\n",
- " scalar = random.randint(0, params3n.full_order)\n",
- " if scalar % 3 == rem:\n",
- " scalars.append(scalar)\n",
- " if len(scalars) == samples:\n",
- " break\n",
- " return scalars\n",
- "\n",
- "def test_3n(countermeasure, scalars):\n",
- " ctr = Counter()\n",
- " for k in tqdm(scalars, leave=False):\n",
- " mult.init(params3n, point3n)\n",
- " kP = mult.multiply(k).to_affine()\n",
- " mult.init(params3n, point3n)\n",
- " knP = mult.multiply(k + params3n.full_order).to_affine()\n",
- " mult.init(params3n, point3n)\n",
- " k2nP = mult.multiply(k + 2 * params3n.full_order).to_affine()\n",
- "\n",
- " countermeasure.init(params3n, point3n)\n",
- " res = countermeasure.multiply(k)\n",
- " aff = res.to_affine()\n",
- " if aff.equals(kP):\n",
- " ctr[\"k\"] += 1\n",
- " elif aff.equals(knP):\n",
- " ctr[\"k + 1n\"] += 1\n",
- " elif aff.equals(k2nP):\n",
- " ctr[\"k + 2n\"] += 1\n",
- " else:\n",
- " ctr[aff] += 1\n",
- " for name, count in sorted(ctr.items()):\n",
- " print(f\"{name}:\\t{count}\")\n",
- "\n",
- "def test_3n_fixed_scalar(countermeasure, samples):\n",
- " test_3n(countermeasure, [key3n for _ in range(samples)])\n",
- "\n",
- "def test_3n_random_scalar(countermeasure, samples):\n",
- " test_3n(countermeasure, [random.randint(0, params3n.full_order) for _ in range(samples)])\n",
- "\n",
- "def test_3n_random_scalar_projected(countermeasure, samples):\n",
- " print(\"k = 0 mod 3\")\n",
- " test_3n(countermeasure, generate_scalars_mod3(0, samples))\n",
- " print()\n",
- " print(\"k = 1 mod 3\")\n",
- " test_3n(countermeasure, generate_scalars_mod3(1, samples))\n",
- " print()\n",
- " print(\"k = 2 mod 3\")\n",
- " test_3n(countermeasure, generate_scalars_mod3(2, samples))"
- ]
- },
- {
- "cell_type": "markdown",
- "id": "46b8f74a-433d-48c9-b5b9-6bb7d2731246",
- "metadata": {},
- "source": [
- "### Fixed scalar experiments"
- ]
- },
- {
- "cell_type": "markdown",
- "id": "fc82d4b9-91cd-423c-83aa-89721efa1ae9",
- "metadata": {},
- "source": [
- "#### Group scalar randomization"
- ]
- },
- {
- "cell_type": "code",
- "execution_count": null,
- "id": "86532d50-2db7-4370-b449-c545b330a852",
- "metadata": {},
- "outputs": [],
- "source": [
- "test_3n_fixed_scalar(gsr, 1000)"
- ]
- },
- {
- "cell_type": "markdown",
- "id": "aba3e713-6246-435d-93af-2e8b42ee9582",
- "metadata": {},
- "source": [
- "#### Additive splitting"
- ]
- },
- {
- "cell_type": "code",
- "execution_count": null,
- "id": "ad421630-606f-4666-9bbf-1a446eec1b59",
- "metadata": {},
- "outputs": [],
- "source": [
- "test_3n_fixed_scalar(asplit, 1000)"
- ]
- },
- {
- "cell_type": "markdown",
- "id": "a1284a11-4ace-437d-9826-2035cce36756",
- "metadata": {},
- "source": [
- "#### Multiplicative splitting"
- ]
- },
- {
- "cell_type": "code",
- "execution_count": null,
- "id": "3ed5d7f3-0ba1-4b62-9635-aeb492499175",
- "metadata": {},
- "outputs": [],
- "source": [
- "test_3n_fixed_scalar(msplit, 1000)"
- ]
- },
- {
- "cell_type": "markdown",
- "id": "5e40f8e9-d26f-41e7-adbf-a0fbdb680677",
- "metadata": {},
- "source": [
- "#### Euclidean splitting"
- ]
- },
- {
- "cell_type": "code",
- "execution_count": null,
- "id": "314447c6-a1fb-4d3a-8988-b34c8912dd5e",
- "metadata": {},
- "outputs": [],
- "source": [
- "test_3n_fixed_scalar(esplit, 1000)"
- ]
- },
- {
- "cell_type": "markdown",
- "id": "ff7185a2-3cd9-44d7-b1a9-982eaed561dc",
- "metadata": {},
- "source": [
- "#### Brumley and Tuveri bit-length fixing"
- ]
- },
- {
- "cell_type": "code",
- "execution_count": null,
- "id": "f41dfc1d-1017-4aa0-bcd4-6569c53bf81e",
- "metadata": {},
- "outputs": [],
- "source": [
- "test_3n_fixed_scalar(bt, 1000)"
- ]
- },
- {
- "cell_type": "markdown",
- "id": "28915553-b5e6-4108-bc23-e5844b6a63b8",
- "metadata": {},
- "source": [
- "### Random scalar experiments"
- ]
- },
- {
- "cell_type": "markdown",
- "id": "566ddd10-2d0e-4b32-9b27-60770ab68155",
- "metadata": {},
- "source": [
- "#### Group scalar randomization"
- ]
- },
- {
- "cell_type": "code",
- "execution_count": null,
- "id": "7255321a-6ad6-4938-8ec9-dd8d977686db",
- "metadata": {},
- "outputs": [],
- "source": [
- "test_3n_random_scalar(gsr, 1000)"
- ]
- },
- {
- "cell_type": "markdown",
- "id": "376c0da8-b92d-4151-ac30-839ab5c0ceae",
- "metadata": {},
- "source": [
- "#### Additive splitting"
- ]
- },
- {
- "cell_type": "code",
- "execution_count": null,
- "id": "b0146a9a-0803-43c4-ab29-8ba6e15934b5",
- "metadata": {},
- "outputs": [],
- "source": [
- "test_3n_random_scalar(asplit, 1000)"
- ]
- },
- {
- "cell_type": "markdown",
- "id": "96823352-cd63-4cf8-8ab7-cf6e025837b9",
- "metadata": {},
- "source": [
- "#### Multiplicative splitting"
- ]
- },
- {
- "cell_type": "code",
- "execution_count": null,
- "id": "5645ae6f-f5f4-419d-ba47-248532dc2114",
- "metadata": {},
- "outputs": [],
- "source": [
- "test_3n_random_scalar(msplit, 1000)"
- ]
- },
- {
- "cell_type": "markdown",
- "id": "1784d763-932a-4f66-a1da-d7ef51cbc88a",
- "metadata": {},
- "source": [
- "#### Euclidean splitting"
- ]
- },
- {
- "cell_type": "code",
- "execution_count": null,
- "id": "c9fc4f35-1c25-4cac-bb63-8bd70263db47",
- "metadata": {},
- "outputs": [],
- "source": [
- "test_3n_random_scalar(esplit, 1000)"
- ]
- },
- {
- "cell_type": "markdown",
- "id": "8917dfd5-1548-414b-846a-685857bfb427",
- "metadata": {},
- "source": [
- "#### Brumley and Tuveri bit-length fixing"
- ]
- },
- {
- "cell_type": "code",
- "execution_count": null,
- "id": "4fd6b288-08a9-4dbe-9145-e96401805315",
- "metadata": {},
- "outputs": [],
- "source": [
- "test_3n_random_scalar(bt, 1000)"
- ]
- },
- {
- "cell_type": "markdown",
- "id": "ee9e23f6-edd9-4fc2-9e7c-b5c176991071",
- "metadata": {},
- "source": [
- "### Random scalar experiments projected to scalar divisor classes mod 3"
- ]
- },
- {
- "cell_type": "markdown",
- "id": "e17fcb12-1e02-4bcf-a2b7-785c16c03028",
- "metadata": {},
- "source": [
- "#### Group scalar randomization"
- ]
- },
- {
- "cell_type": "code",
- "execution_count": null,
- "id": "6c46fdbb-2ffb-4169-8e00-6d93b8407ee5",
- "metadata": {},
- "outputs": [],
- "source": [
- "test_3n_random_scalar_projected(gsr, 1000)"
- ]
- },
- {
- "cell_type": "markdown",
- "id": "b9d635c8-f788-4700-876b-ac48e89557a7",
- "metadata": {},
- "source": [
- "#### Additive splitting"
- ]
- },
- {
- "cell_type": "code",
- "execution_count": null,
- "id": "344a4f90-3470-40e9-a75f-b925a88c2480",
- "metadata": {},
- "outputs": [],
- "source": [
- "test_3n_random_scalar_projected(asplit, 1000)"
- ]
- },
- {
- "cell_type": "markdown",
- "id": "78aaf83f-a689-40ad-ae88-58ab20e5e6f9",
- "metadata": {},
- "source": [
- "#### Multiplicative splitting"
- ]
- },
- {
- "cell_type": "code",
- "execution_count": null,
- "id": "616a7726-01e6-4e9c-b7f2-fe8f14b60071",
- "metadata": {},
- "outputs": [],
- "source": [
- "test_3n_random_scalar_projected(msplit, 1000)"
- ]
- },
- {
- "cell_type": "markdown",
- "id": "018c8f31-d7c3-497b-bdaf-580c6465753f",
- "metadata": {},
- "source": [
- "#### Euclidean splitting"
- ]
- },
- {
- "cell_type": "code",
- "execution_count": null,
- "id": "adced4e4-37a7-43ed-97b5-01cb5d274d6b",
- "metadata": {},
- "outputs": [],
- "source": [
- "test_3n_random_scalar_projected(esplit, 1000)"
- ]
- },
- {
- "cell_type": "markdown",
- "id": "8d7b0a42-7be7-464d-932d-8386ad912034",
- "metadata": {},
- "source": [
- "#### Brumley and Tuveri bit-length fixing"
- ]
- },
- {
- "cell_type": "code",
- "execution_count": null,
- "id": "fe8d8295-3e69-4b60-b8c3-5710deaeb0b3",
- "metadata": {},
- "outputs": [],
- "source": [
- "test_3n_random_scalar_projected(bt, 1000)"
- ]
- },
- {
- "cell_type": "markdown",
- "id": "43b309af-5683-4384-9623-d7633723177c",
- "metadata": {},
- "source": [
- "## Mask recovery\n",
- "Using a composite order curve we can recover the size and the actual mask values (in a known key scenario) in both GSR and multiplicative splitting. However, real-world targets do not like composite order curves and may either check the order or otherwise fail to compute on such curves. Thus, we lie to them and set the order to the next-prime of the true order, in this case $n + 92$."
- ]
- },
- {
- "cell_type": "code",
- "execution_count": null,
- "id": "20a26f27-620d-4d7f-92bd-b949482b5c9a",
- "metadata": {},
- "outputs": [],
- "source": [
- "pari = cypari2.Pari(256_000_000, 2_000_000_000)"
- ]
- },
- {
- "cell_type": "code",
- "execution_count": null,
- "id": "144340bd-5372-4beb-a46e-fd60c596b254",
- "metadata": {},
- "outputs": [],
- "source": [
- "real_n = 0xa9fa3419aca88bade2cba14e317816c6828910c6ce04fcd2a2e857d25df50775\n",
- "# = 2898786277 * 2916913393 * 3067509271 * 3248233993 * 3894099889 * 4099407227 * 4101666977 * 13936975277\n",
- "real_n_facts = pari.factor(real_n)\n",
- "params92pn = load_params_ectester(io.BytesIO(b\"0xa9fa3419aca88bade2cba14e317816c79d52481d463dc9bcb12c37f45aa3b4e1,0x2ea3bfe6659f8e035735349b91fbfa2baf0cf8e640315f0fe03c1136813dec99,0x2b07c518e04b02158651e3dbbef7720015dd496bf15af02f8439f8e1503b8370,0x90fb04b1af19e8e20396ac052f260a9fb5f736b97e3cd4af08fe81a1e75dac6d,0x2302bcf700d3d5899f04d0c7441f5017c9758bfafd6ce15dbe36fb4eea76baec,0xa9fa3419aca88bade2cba14e317816c6828910c6ce04fcd2a2e857d25df507d1,0x01\"), \"projective\")\n",
- "e = pari.ellinit([int(params92pn.curve.parameters[\"a\"]), int(params92pn.curve.parameters[\"b\"])], int(params92pn.curve.prime))\n",
- "e[15][0] = real_n"
- ]
- },
- {
- "cell_type": "code",
- "execution_count": null,
- "id": "f103129c-17d3-4217-999b-94ecb4ec523d",
- "metadata": {},
- "outputs": [],
- "source": [
- "print(f\"prime:\\t0x{params92pn.curve.prime:x}\")\n",
- "print(f\"a:\\t0x{params92pn.curve.parameters['a']:x}\")\n",
- "print(f\"b:\\t0x{params92pn.curve.parameters['b']:x}\")\n",
- "print(f\"G:\\t[0x{params92pn.generator.X:x},\\n\\t 0x{params92pn.generator.Y:x}]\")\n",
- "print(f\"n+92:\\t0x{params92pn.order:x} (fake order, given to the target, prime)\")\n",
- "print(f\"n:\\t0x{real_n:x} (real order, composite)\")"
- ]
- },
- {
- "cell_type": "markdown",
- "id": "322d2e68-5259-4ea6-9748-2b0aa21b557f",
- "metadata": {},
- "source": [
- "### Group scalar randomization\n",
- "In GSR getting the mask out this way is quite simple. The target believes it is operating on a curve of order $n+92$ so it will use that value multiplied with the mask to randomize the scalar. Thus as a result we get:\n",
- "$$ P = [k + r(n + 92)]G $$\n",
- "\n",
- "However, the curve is truly of order $n$, thus arithmetic on its group will make this equal to: \n",
- "$$ P = [k + r 92]G $$\n",
- "\n",
- "Since this is a composite order curve, we can solve the dlog and obtain $k + r 92$ and since we assume we know $k$ we can easily compute both the mask size and mask value $r$."
- ]
- },
- {
- "cell_type": "code",
- "execution_count": null,
- "id": "08d99bd5-2b87-4a04-995d-7a87f9b67102",
- "metadata": {},
- "outputs": [],
- "source": [
- "key = 0x20959f2b437de1e522baf6d814911938157390d3ea5118660b852ab0d5387006 # any key works ofc\n",
- "gsr.init(params92pn, params92pn.generator)\n",
- "res = gsr.multiply(key)"
- ]
- },
- {
- "cell_type": "code",
- "execution_count": null,
- "id": "2a869bed-8e21-46af-8f70-065f4afd6a82",
- "metadata": {},
- "outputs": [],
- "source": [
- "affine_gen = params92pn.generator.to_affine()\n",
- "affine_res = res.to_affine()"
- ]
- },
- {
- "cell_type": "code",
- "execution_count": null,
- "id": "e440399a-bc01-488b-8822-08cc0bf1672d",
- "metadata": {},
- "outputs": [],
- "source": [
- "dlog = pari.elllog(e,\n",
- " [int(affine_res.x), int(affine_res.y)],\n",
- " [int(affine_gen.x), int(affine_gen.y)],\n",
- " real_n)"
- ]
- },
- {
- "cell_type": "code",
- "execution_count": null,
- "id": "7ea6d6ae-a6f5-4b53-8c40-787d79970cb6",
- "metadata": {},
- "outputs": [],
- "source": [
- "mask = int((dlog - key) / 92)\n",
- "mask_len = mask.bit_length()\n",
- "print(mask)\n",
- "print(mask_len)"
- ]
- },
- {
- "cell_type": "markdown",
- "id": "d40ec035-0656-4eda-8ef4-c14f9d53f49f",
- "metadata": {},
- "source": [
- "### Multiplicative splitting\n",
- "In multiplicative splitting the situation is a bit more complicated. Doing the same computation, where the target thinks the curve order is $n+92$ leads to:\n",
- "$$ P = [k r^{-1}\\pmod{n+92}][r \\mod n]G $$\n",
- "\n",
- "Since the curve is composite order we can easily compute the dlog $d$ of P to G, we get:\n",
- "$$ d = (k r^{-1})\\pmod{n+92}\\: r = k + t (n + 92) $$\n",
- "\n",
- "However, the dlog is computed $\\mod n$ so we really get: $ d = k + t 92$. We extract the $t$ out of this.\n",
- "Note that $t$ will have roughly the same size as the mask $r$, since at the left side we have $(k r^{-1}) {\\mod (n+92)}$\n",
- "of size $n$ and $r$ of size of the mask and on the right size we have $t n$ that dominates.\n",
- "Thus at this point we have recovered the mask size.\n",
- "However, $t$ is always smaller than $r$, sometimes also in bitsize.\n",
- "\n",
- "Now that we have $s$ we can go back to the original equation and get:\n",
- "$$ (k r^{-1})\\pmod{n+92}\\: r = k + t (n + 92) $$\n",
- "\n",
- "We can then factor this value, lets call it $full$, and look for divisors that are larger than $t$ but smaller than the mask length\n",
- "that we recovered before. There may be multiple candidates here and we don't know how to distinguish between\n",
- "them. It holds for all of the candidates $c$ that the rest of the value $full$ is equal to the inverse of $c \\mod (n+92)$.\n",
- "However, sometimes there is only one candidate, which is equal to the true mask value $r$."
- ]
- },
- {
- "cell_type": "code",
- "execution_count": 80,
- "id": "b5f398fc-90d7-455e-97bd-62b682d55961",
- "metadata": {},
- "outputs": [],
- "source": [
- "def divisors(primes, powers):\n",
- " for comb in itertools.product(*[range(power+1) for power in powers]):\n",
- " value = 1\n",
- " for prime, power in zip(primes, comb):\n",
- " value *= prime**power\n",
- " yield value\n",
- "\n",
- "def pari_factor(number, flag=1+8, duration=5*60):\n",
- " # Use the 1 + 8 option to factorint to skip some costly factorization methods, we don't need the huge factors.\n",
- " # This means that some factors may remain, which in turn means that sometimes we may not find the true mask.\n",
- " pari = cypari2.Pari(256_000_000, 2_000_000_000)\n",
- " with warnings.catch_warnings(category=RuntimeWarning):\n",
- " warnings.simplefilter(\"ignore\")\n",
- " try:\n",
- " alarm(duration)\n",
- " factors = pari.factorint(number, flag)\n",
- " except AlarmInterrupt:\n",
- " return None\n",
- " primes = list(map(int, factors[0]))\n",
- " powers = list(map(int, factors[1]))\n",
- " return primes, powers\n",
- "\n",
- "def pari_dlog(params, P, G, real_n, facts_str):\n",
- " pari = cypari2.Pari(256_000_000, 2_000_000_000)\n",
- " e = pari.ellinit([int(params.curve.parameters[\"a\"]), int(params.curve.parameters[\"b\"])], int(params.curve.prime))\n",
- " e[15][0] = real_n\n",
- " facts = pari(facts_str)\n",
- " dlog = pari.elllog(e, P, G, facts)\n",
- " return int(dlog)"
- ]
- },
- {
- "cell_type": "code",
- "execution_count": 81,
- "id": "5f03e586-33df-4525-a722-f5f63d6ca28d",
- "metadata": {},
- "outputs": [
- {
- "data": {
- "application/vnd.jupyter.widget-view+json": {
- "model_id": "c3b98a7bfa2e4e568f83ee3d035266bb",
- "version_major": 2,
- "version_minor": 0
- },
- "text/plain": [
- "Collecting scalarmults: 0%| | 0/1000 [00:00, ?it/s]"
- ]
- },
- "metadata": {},
- "output_type": "display_data"
- },
- {
- "data": {
- "application/vnd.jupyter.widget-view+json": {
- "model_id": "3768e6da82324ae9891666bcf6d952b7",
- "version_major": 2,
- "version_minor": 0
- },
- "text/plain": [
- "Computing dlogs: 0%| | 0/1000 [00:00, ?it/s]"
- ]
- },
- "metadata": {},
- "output_type": "display_data"
- },
- {
- "name": "stdout",
- "output_type": "stream",
- "text": [
- "32 True\n"
- ]
- }
- ],
- "source": [
- "key = 0x20959f2b437de1e522baf6d814911938157390d3ea5118660b852ab0d5387006 # any key works\n",
- "msplit = MultiplicativeSplitting(mult, rand_bits=32) # change the mask size here to your liking\n",
- "tries = 1000\n",
- "num_workers = 30\n",
- "\n",
- "blens = [None for _ in range(tries)]\n",
- "dlogs = [None for _ in range(tries)]\n",
- "ts = [None for _ in range(tries)]\n",
- "\n",
- "results = [None for _ in range(tries)]\n",
- "rs = [None for _ in range(tries)]\n",
- "\n",
- "with TaskExecutor(max_workers=num_workers) as pool:\n",
- " for i in trange(tries, desc=\"Collecting scalarmults\"):\n",
- " msplit.init(params92pn, params92pn.generator)\n",
- " with local(DefaultContext()) as ctx:\n",
- " res = msplit.multiply(key)\n",
- " \n",
- " affine_res = res.to_affine()\n",
- " affine_gen = params92pn.generator.to_affine()\n",
- " results[i] = affine_res\n",
- " \n",
- " rval = []\n",
- " ctx.actions[0].walk(lambda action: rval.append(int(action.result)) if isinstance(action, RandomModAction) else None)\n",
- " rs[i] = rval[0]\n",
- " \n",
- " pool.submit_task(i,\n",
- " pari_dlog,\n",
- " params92pn,\n",
- " [int(affine_res.x), int(affine_res.y)],\n",
- " [int(affine_gen.x), int(affine_gen.y)],\n",
- " real_n,\n",
- " repr(real_n_facts))\n",
- " \n",
- " for i, future in tqdm(pool.as_completed(), desc=\"Computing dlogs\", total=len(pool.tasks)):\n",
- " dlog = future.result()\n",
- " val = dlog - key\n",
- " if val % 92 != 0:\n",
- " print(f\"Bad val! {i}\")\n",
- " t = val // 92\n",
- " ts[i] = t\n",
- " dlogs[i] = dlog\n",
- " blens[i] = t.bit_length()\n",
- "\n",
- "mask_len = max(blens)\n",
- "print(mask_len, mask_len == msplit.rand_bits)"
- ]
- },
- {
- "cell_type": "code",
- "execution_count": 85,
- "id": "5fbf8a38-983d-49a6-9cac-5350f960dc3e",
- "metadata": {},
- "outputs": [
- {
- "data": {
- "application/vnd.jupyter.widget-view+json": {
- "model_id": "8237fd8893084365a474553995944794",
- "version_major": 2,
- "version_minor": 0
- },
- "text/plain": [
- "Factoring: 0%| | 0/1000 [00:00, ?it/s]"
- ]
- },
- "metadata": {},
- "output_type": "display_data"
- }
- ],
- "source": [
- "with TaskExecutor(max_workers=num_workers) as pool:\n",
- " fulls = []\n",
- " for t in ts:\n",
- " full = t * (real_n + 92) + key\n",
- " fulls.append(full)\n",
- " pool.submit_task(t,\n",
- " pari_factor,\n",
- " full, flag=0)\n",
- " facts = [None for _ in ts]\n",
- " for t, future in tqdm(pool.as_completed(), desc=\"Factoring\", total=len(ts)):\n",
- " result = future.result()\n",
- " if result is None:\n",
- " print(\"Timed out.\")\n",
- " facts[ts.index(t)] = result"
- ]
- },
- {
- "cell_type": "code",
- "execution_count": 86,
- "id": "0973fe4b-cdf5-4e91-850b-25375eeabb7e",
- "metadata": {},
- "outputs": [
- {
- "name": "stdout",
- "output_type": "stream",
- "text": [
- "Only one candidate, we got the mask: 2842006421 True \n",
- "Only one candidate, we got the mask: 1367232818 True \n",
- "Only one candidate, we got the mask: 2240904829 True \n",
- "Only one candidate, we got the mask: 1039351451 True \n",
- "Only one candidate, we got the mask: 108996955 True \n",
- "Only one candidate, we got the mask: 2881524907 True \n",
- "Only one candidate, we got the mask: 2189838553 True \n",
- "Only one candidate, we got the mask: 3969096149 True \n",
- "Only one candidate, we got the mask: 2287426132 True \n",
- "Only one candidate, we got the mask: 4074964099 True \n",
- "Only one candidate, we got the mask: 2669990606 True \n",
- "Only one candidate, we got the mask: 1456246563 True \n",
- "Only one candidate, we got the mask: 2710951939 True \n",
- "Only one candidate, we got the mask: 2825913889 True \n",
- "Only one candidate, we got the mask: 1638243357 True \n",
- "Only one candidate, we got the mask: 3811276388 True \n",
- "Only one candidate, we got the mask: 3123140239 True \n",
- "Only one candidate, we got the mask: 3595726430 True \n",
- "Only one candidate, we got the mask: 4044959749 True \n",
- "Only one candidate, we got the mask: 1018157261 True \n",
- "Only one candidate, we got the mask: 3129245929 True \n",
- "Only one candidate, we got the mask: 2809475199 True \n",
- "Only one candidate, we got the mask: 3952225418 True \n",
- "Only one candidate, we got the mask: 832268494 True \n",
- "Only one candidate, we got the mask: 1264726273 True \n",
- "Only one candidate, we got the mask: 616082151 True \n",
- "Only one candidate, we got the mask: 2208359603 True \n",
- "Only one candidate, we got the mask: 4071547089 True \n",
- "Only one candidate, we got the mask: 12516967 True \n",
- "Only one candidate, we got the mask: 3559760625 True \n",
- "Only one candidate, we got the mask: 2760746593 True \n",
- "Only one candidate, we got the mask: 3819292718 True \n",
- "Only one candidate, we got the mask: 2244540383 True \n",
- "Only one candidate, we got the mask: 3057851337 True \n",
- "Only one candidate, we got the mask: 2604694145 True \n",
- "Only one candidate, we got the mask: 2715382871 True \n",
- "Only one candidate, we got the mask: 4149507669 True \n",
- "Only one candidate, we got the mask: 2502506233 True \n",
- "Only one candidate, we got the mask: 4060064857 True \n",
- "Only one candidate, we got the mask: 3733544567 True \n",
- "Only one candidate, we got the mask: 4274624339 True \n",
- "Only one candidate, we got the mask: 2590849447 True \n",
- "Only one candidate, we got the mask: 3426697997 True \n",
- "Only one candidate, we got the mask: 3882456323 True \n",
- "Only one candidate, we got the mask: 3269089457 True \n",
- "Only one candidate, we got the mask: 3761164241 True \n",
- "Only one candidate, we got the mask: 2802249770 True \n",
- "Only one candidate, we got the mask: 2199311258 True \n",
- "Only one candidate, we got the mask: 4044571507 True \n",
- "Only one candidate, we got the mask: 2531874111 True \n",
- "Only one candidate, we got the mask: 3110772661 True \n",
- "Only one candidate, we got the mask: 1450255847 True \n",
- "Only one candidate, we got the mask: 3506577773 True \n",
- "Only one candidate, we got the mask: 864589123 True \n",
- "Only one candidate, we got the mask: 2460981459 True \n",
- "Only one candidate, we got the mask: 1852927003 True \n",
- "Only one candidate, we got the mask: 4049366217 True \n",
- "Only one candidate, we got the mask: 4139493739 True \n",
- "Only one candidate, we got the mask: 1970200502 True \n",
- "Only one candidate, we got the mask: 2982933973 True \n",
- "Only one candidate, we got the mask: 1185834757 True \n",
- "Only one candidate, we got the mask: 4057506562 True \n",
- "Only one candidate, we got the mask: 3553777159 True \n",
- "Only one candidate, we got the mask: 3228784961 True \n",
- "Only one candidate, we got the mask: 3361181844 True \n",
- "Only one candidate, we got the mask: 1946286323 True \n",
- "Only one candidate, we got the mask: 3295077587 True \n",
- "Only one candidate, we got the mask: 5406775 True \n",
- "Only one candidate, we got the mask: 2712315191 True \n",
- "Only one candidate, we got the mask: 97620847 True \n",
- "Only one candidate, we got the mask: 3352788414 True \n",
- "Only one candidate, we got the mask: 2067199152 True \n",
- "Only one candidate, we got the mask: 2780511079 True \n",
- "Only one candidate, we got the mask: 2422242923 True \n",
- "Only one candidate, we got the mask: 1410524515 True \n",
- "Only one candidate, we got the mask: 1313538691 True \n",
- "Only one candidate, we got the mask: 2212262809 True \n",
- "Only one candidate, we got the mask: 1889821971 True \n",
- "Only one candidate, we got the mask: 4205618623 True \n",
- "Only one candidate, we got the mask: 368456507 True \n",
- "Only one candidate, we got the mask: 3659588587 True \n",
- "Only one candidate, we got the mask: 3907266774 True \n",
- "Only one candidate, we got the mask: 1421268181 True \n",
- "Only one candidate, we got the mask: 3594406679 True \n",
- "Only one candidate, we got the mask: 2835610927 True \n",
- "Only one candidate, we got the mask: 1750708313 True \n",
- "Only one candidate, we got the mask: 3994812597 True \n",
- "Only one candidate, we got the mask: 3416127039 True \n",
- "Only one candidate, we got the mask: 2918932879 True \n",
- "Only one candidate, we got the mask: 2903903777 True \n",
- "Only one candidate, we got the mask: 3751353247 True \n",
- "Only one candidate, we got the mask: 1914133021 True \n",
- "Only one candidate, we got the mask: 1041740814 True \n",
- "Only one candidate, we got the mask: 2717146511 True \n",
- "Only one candidate, we got the mask: 3787563800 True \n",
- "Only one candidate, we got the mask: 2532401805 True \n",
- "Only one candidate, we got the mask: 1580928500 True \n",
- "Only one candidate, we got the mask: 3553660109 True \n",
- "Only one candidate, we got the mask: 3548089540 True \n",
- "Only one candidate, we got the mask: 3102746041 True \n",
- "Only one candidate, we got the mask: 4065155265 True \n",
- "Only one candidate, we got the mask: 3111552963 True \n",
- "Only one candidate, we got the mask: 922382643 True \n",
- "Only one candidate, we got the mask: 1896551582 True \n",
- "Only one candidate, we got the mask: 4036077281 True \n",
- "Only one candidate, we got the mask: 1202517347 True \n",
- "Only one candidate, we got the mask: 4166638824 True \n",
- "Only one candidate, we got the mask: 4196515943 True \n",
- "Only one candidate, we got the mask: 2409770161 True \n",
- "Only one candidate, we got the mask: 2156195057 True \n",
- "Only one candidate, we got the mask: 3303218539 True \n",
- "Only one candidate, we got the mask: 4019401523 True \n",
- "Only one candidate, we got the mask: 3383631109 True \n",
- "Only one candidate, we got the mask: 4045144939 True \n",
- "Total recovered masks: 114 out of 1000\n"
- ]
- }
- ],
- "source": [
- "candidate_amounts = []\n",
- "i = 0\n",
- "for dlog, t, blen, r, fact, full, result in zip(dlogs, ts, blens, rs, facts, fulls, results):\n",
- " if fact is None:\n",
- " continue\n",
- " \n",
- " (primes, powers) = fact\n",
- " complete = True\n",
- " for prime in primes:\n",
- " if not pari.isprime(prime):\n",
- " complete = False\n",
- " break\n",
- "\n",
- " i += 1\n",
- " candidates = set()\n",
- " for divisor in divisors(primes, powers):\n",
- " if divisor.bit_length() <= mask_len and divisor >= t:\n",
- " candidates.add(divisor)\n",
- " candidate_amounts.append(len(candidates))\n",
- " if len(candidates) == 1:\n",
- " candidate = candidates.pop()\n",
- " print(\"Only one candidate, we got the mask:\", candidate, candidate == r, \"incomplete factoring this may not be the r\" if not complete else \"\")\n",
- "print(f\"Total recovered masks: {len(list(filter(lambda a: a == 1, candidate_amounts)))} out of {i}\")"
- ]
- },
- {
- "cell_type": "code",
- "execution_count": 89,
- "id": "6274ff91-325f-4c6b-a4d7-d66b994d730f",
- "metadata": {},
- "outputs": [
- {
- "data": {
- "application/vnd.jupyter.widget-view+json": {
- "model_id": "3a03974d3d6c4f159824b17e4bfb0467",
- "version_major": 2,
- "version_minor": 0
- },
- "image/png": "iVBORw0KGgoAAAANSUhEUgAAAoAAAAHgCAYAAAA10dzkAAAAOnRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjEwLjEsIGh0dHBzOi8vbWF0cGxvdGxpYi5vcmcvc2/+5QAAAAlwSFlzAAAPYQAAD2EBqD+naQAAQIRJREFUeJzt3X98z/X+//H72377sfkx9sOPIb+Z0TCbvkdlmY5icmr5dJB0SvkxVgrF+qFGRYTDoeKUI3IqSTU/dtCJMTY7UX4lx8R+oGyZYm3P7x9dvE9vhuH9ts3rdr1c3pfa6/18PR/P13te3nfP1y+bMcYIAAAAllGlvAcAAACA64sACAAAYDEEQAAAAIshAAIAAFgMARAAAMBiCIAAAAAWQwAEAACwGAIgAACAxRAAAQAALIYACAAAYDEEQAAAAIshAAIAAFgMARAAAMBiCIAAAAAWQwAEAACwGAIgAACAxRAAAQAALIYACAAAYDEEQAAAAIshAAIAAFgMARAAAMBiCIAAAAAWQwAEAACwGAIgAACAxRAAAQAALIYACAAAYDEEQAAAAIshAAIAAFgMARAAAMBiCIAAAAAWQwAEAACwGAIgAACAxRAAAQAALIYACAAAYDEEQAAAAIshAAIAAFgMARAAAMBiCIAAAAAWQwAEAACwGAIgAACAxRAAAQAALIYACAAAYDEEQAAAAIshAAIAAFgMARAAAMBiCIAAAAAWQwAEAACwGAIgAACAxRAAAQAALIYACAAAYDEEQAAAAIshAAIAAFgMARAAAMBiCIAAAAAWQwAEAACwGAIgAACAxbiX9wAqs5KSEh09elQ1atSQzWYr7+EAAIAyMMbop59+UnBwsKpUseZcGAHwGhw9elQNGzYs72EAAICrcPjwYTVo0KC8h1EuCIDXoEaNGpJ++wPk6+tbzqMBAABlUVBQoIYNG9q/x62IAHgNzh329fX1JQACAFDJWPn0LWse+AYAALAwAiAAAIDFEAABAAAshgAIAABgMQRAAAAAiyEAAgAAWAwBEAAAwGIIgAAAABZDAAQAALAYAiAAAIDFEAABAAAshgAIAABgMQRAAAAAiyEAAgAAWIx7eQ/AahqP+9TlNf47pbfLawAAgMqLGUAAAACLIQACAABYDAEQAADAYgiAAAAAFkMABAAAsBgCIAAAgMUQAAEAACyGAAgAAGAxBEAAAACLIQACAABYDAEQAADAYgiAAAAAFkMABAAAsBgCIAAAgMUQAAEAACyGAAgAAGAxBEAAAACLIQACAABYDAEQAADAYgiAAAAAFkMABAAAsBgCIAAAgMUQAAEAACyGAAgAAGAxBEAAAACLIQACAABYDAEQAADAYgiAAAAAFkMABAAAsBgCIAAAgMUQAAEAACyGAAgAAGAxBEAAAACLIQACAABYDAEQAADAYgiAAAAAFkMABAAAsBgCIAAAgMVUmgA4Z84cNW7cWN7e3oqIiFBaWtpF23799dfq37+/GjduLJvNphkzZlxznwAAADeKShEAly1bpoSEBCUmJiojI0NhYWGKiYlRXl5eqe1Pnz6tpk2basqUKQoMDHRKnwAAADeKShEAp0+frr/85S8aMmSI2rRpo3nz5qlq1ap6++23S23fuXNnvfrqq7r//vvl5eXllD4BAABuFBU+AJ49e1bp6emKjo62L6tSpYqio6OVmppaYfoEAACoLNzLewCXc/z4cRUXFysgIMBheUBAgPbs2XNd+zxz5ozOnDlj/7mgoOCq6gMAAJSnCj8DWJEkJSXJz8/P/mrYsGF5DwkAAOCKVfgA6O/vLzc3N+Xm5josz83NvegFHq7qc/z48crPz7e/Dh8+fFX1AQAAylOFD4Cenp4KDw9XSkqKfVlJSYlSUlIUGRl5Xfv08vKSr6+vwwsAAKCyqfDnAEpSQkKCBg8erE6dOqlLly6aMWOGCgsLNWTIEEnSoEGDVL9+fSUlJUn67SKPb775xv7/R44cUWZmpqpXr65mzZqVqU8AAIAbVaUIgHFxcTp27JgmTZqknJwcdejQQcnJyfaLOLKyslSlyv8mM48ePaqOHTvaf37ttdf02muvqXv37tqwYUOZ+gQAALhR2YwxprwHUVkVFBTIz89P+fn5ZT4c3Hjcpy4elfTfKb1dXgMAgMrqar6/bzQV/hxAAAAAOBcBEAAAwGIIgAAAABZDAAQAALAYAiAAAIDFEAABAAAshgAIAABgMQRAAAAAiyEAAgAAWEyleBQcrgxPGwEAAJfCDCAAAIDFEAABAAAshgAIAABgMQRAAAAAiyEAAgAAWAwBEAAAwGIIgAAAABZDAAQAALAYAiAAAIDFEAABAAAshgAIAABgMQRAAAAAiyEAAgAAWAwBEAAAwGIIgAAAABZDAAQAALAYAiAAAIDFEAABAAAshgAIAABgMQRAAAAAiyEAAgAAWAwBEAAAwGIIgAAAABZDAAQAALAYAiAAAIDFEAABAAAshgAIAABgMQRAAAAAiyEAAgAAWAwBEAAAwGIIgAAAABZDAAQAALAYAiAAAIDFEAABAAAshgAIAABgMQRAAAAAiyEAAgAAWAwBEAAAwGIIgAAAABZDAAQAALAYAiAAAIDFVJoAOGfOHDVu3Fje3t6KiIhQWlraJdsvX75crVq1kre3t0JDQ/XZZ585vH/q1CmNGDFCDRo0kI+Pj9q0aaN58+a5chMAAAAqhEoRAJctW6aEhAQlJiYqIyNDYWFhiomJUV5eXqntN2/erAEDBmjo0KHasWOHYmNjFRsbq127dtnbJCQkKDk5WYsXL9bu3bs1evRojRgxQitXrrxemwUAAFAubMYYU96DuJyIiAh17txZs2fPliSVlJSoYcOGGjlypMaNG3dB+7i4OBUWFmrVqlX2ZV27dlWHDh3ss3zt2rVTXFycJk6caG8THh6uO++8U5MnTy7TuAoKCuTn56f8/Hz5+vqWaZ3G4z4tU7uK7r9Tepf3EAAAuCpX8/19o6nwM4Bnz55Venq6oqOj7cuqVKmi6OhopaamlrpOamqqQ3tJiomJcWgfFRWllStX6siRIzLGaP369dq3b5969ux50bGcOXNGBQUFDi8AAIDKpsIHwOPHj6u4uFgBAQEOywMCApSTk1PqOjk5OZdtP2vWLLVp00YNGjSQp6enevXqpTlz5ugPf/jDRceSlJQkPz8/+6thw4bXsGUAAADlo8IHQFeZNWuWtmzZopUrVyo9PV3Tpk3T8OHDtW7duouuM378eOXn59tfhw8fvo4jBgAAcA738h7A5fj7+8vNzU25ubkOy3NzcxUYGFjqOoGBgZds//PPP2vChAn66KOP1Lv3b+eytW/fXpmZmXrttdcuOHx8jpeXl7y8vK51kwAAAMpVhQ+Anp6eCg8PV0pKimJjYyX9dhFISkqKRowYUeo6kZGRSklJ0ejRo+3L1q5dq8jISElSUVGRioqKVKWK4wSom5ubSkpKXLIdN5rrcTELF5oAAOAaFT4ASr/dsmXw4MHq1KmTunTpohkzZqiwsFBDhgyRJA0aNEj169dXUlKSJCk+Pl7du3fXtGnT1Lt3by1dulTbt2/X/PnzJUm+vr7q3r27xo4dKx8fH4WEhGjjxo165513NH369HLbTgAAgOuhUgTAuLg4HTt2TJMmTVJOTo46dOig5ORk+4UeWVlZDrN5UVFRWrJkiZ599llNmDBBzZs314oVK9SuXTt7m6VLl2r8+PF64IEH9MMPPygkJEQvvfSShg0bdt23DwAA4HqqFPcBrKisfB/A64FDwAAAV+A+gBa+ChgAAMCqCIAAAAAWQwAEAACwGAIgAACAxRAAAQAALIYACAAAYDEEQAAAAIshAAIAAFgMARAAAMBiCIAAAAAWQwAEAACwGAIgAACAxRAAAQAALIYACAAAYDEEQAAAAIshAAIAAFgMARAAAMBiCIAAAAAWQwAEAACwGAIgAACAxRAAAQAALIYACAAAYDEEQAAAAItxd3WB/fv3a/369crLy1NJSYnDe5MmTXJ1eQAAAJzHpQFwwYIFeuyxx+Tv76/AwEDZbDb7ezabjQAIAABQDlwaACdPnqyXXnpJTz/9tCvLAAAA4Aq49BzAH3/8Uffee68rSwAAAOAKuTQA3nvvvVqzZo0rSwAAAOAKufQQcLNmzTRx4kRt2bJFoaGh8vDwcHh/1KhRriwPAACAUtiMMcZVnTdp0uTihW02fffdd64qfV0UFBTIz89P+fn58vX1LdM6jcd96uJR3Tj+O6V3eQ8BAHADuprv7xuNS2cADx486MrucYO7HmGZkAkAsKLrdiNoY4xcONkIAACAMnJ5AHznnXcUGhoqHx8f+fj4qH379nr33XddXRYAAAAX4dJDwNOnT9fEiRM1YsQIdevWTZL05ZdfatiwYTp+/LjGjBnjyvIAAAAohUsD4KxZszR37lwNGjTIvqxPnz5q27atnnvuOQIgAABAOXDpIeDs7GxFRUVdsDwqKkrZ2dmuLA0AAICLcGkAbNasmd5///0Lli9btkzNmzd3ZWkAAABchEsPAT///POKi4vTF198YT8HcNOmTUpJSSk1GAIAAMD1XDoD2L9/f23dulX+/v5asWKFVqxYIX9/f6Wlpalfv36uLA0AAICLcOkMoCSFh4dr8eLFri4DAACAMnJ6ACwoKLA/VqWgoOCSba36+BUAAIDy5PQAWKtWLWVnZ6tevXqqWbOmbDbbBW2MMbLZbCouLnZ2eQAAAFyG0wPgv/71L9WuXVuStH79emd3DwAAgGvk9ADYvXt3+/83adJEDRs2vGAW0Bijw4cPO7s0AAAAysClVwE3adJEx44du2D5Dz/8oCZNmriyNAAAAC7CpQHw3Ll+5zt16pS8vb1dWRoAAAAX4ZLbwCQkJEiSbDabJk6cqKpVq9rfKy4u1tatW9WhQwdXlAYAAMBluCQA7tixQ9JvM4A7d+6Up6en/T1PT0+FhYXpySefdEVpAAAAXIZLAuC5q3+HDBmiN954QzVq1HBFGQAAAFwFl50DWFRUpHfffVeHDh1yVQkAAABcBZcFQA8PDzVq1IibPQMAAFQwLr0K+JlnntGECRP0ww8/XHNfc+bMUePGjeXt7a2IiAilpaVdsv3y5cvVqlUreXt7KzQ0VJ999tkFbXbv3q0+ffrIz89P1apVU+fOnZWVlXXNYwUAAKjIXBoAZ8+erS+++ELBwcFq2bKlbr75ZodXWS1btkwJCQlKTExURkaGwsLCFBMTo7y8vFLbb968WQMGDNDQoUO1Y8cOxcbGKjY2Vrt27bK3OXDggG655Ra1atVKGzZs0FdffaWJEydyexoAAHDDsxljjKs6f/755y/5fmJiYpn6iYiIUOfOnTV79mxJUklJiRo2bKiRI0dq3LhxF7SPi4tTYWGhVq1aZV/WtWtXdejQQfPmzZMk3X///fLw8NC7775b1s25QEFBgfz8/JSfny9fX98yrdN43KdXXQ/O998pvct7CACA6+xqvr9vNC65Cvicsga8Szl79qzS09M1fvx4+7IqVaooOjpaqamppa6TmppqvxfhOTExMVqxYoWk3wLkp59+qqeeekoxMTHasWOHmjRpovHjxys2NvaiYzlz5ozOnDlj/7mgoODqNwwAAKCcuDQAnpOenq7du3dLktq2bauOHTuWed3jx4+ruLhYAQEBDssDAgK0Z8+eUtfJyckptX1OTo4kKS8vT6dOndKUKVM0efJkTZ06VcnJybrnnnu0fv16h+cZ/15SUtJlZzVRubh6RpYZRgBAReTSAJiXl6f7779fGzZsUM2aNSVJJ0+e1G233aalS5eqbt26rix/USUlJZKkvn37asyYMZKkDh06aPPmzZo3b95FA+D48eMdZhYLCgrUsGFD1w8YAADAiVx6EcjIkSP1008/6euvv9YPP/ygH374Qbt27VJBQYFGjRpVpj78/f3l5uam3Nxch+W5ubkKDAwsdZ3AwMBLtvf395e7u7vatGnj0KZ169aXvArYy8tLvr6+Di8AAIDKxqUBMDk5WX/961/VunVr+7I2bdpozpw5+vzzz8vUh6enp8LDw5WSkmJfVlJSopSUFEVGRpa6TmRkpEN7SVq7dq29vaenpzp37qy9e/c6tNm3b59CQkLKNC4AAIDKyqWHgEtKSuTh4XHBcg8PD/th2LJISEjQ4MGD1alTJ3Xp0kUzZsxQYWGhhgwZIkkaNGiQ6tevr6SkJElSfHy8unfvrmnTpql3795aunSptm/frvnz59v7HDt2rOLi4vSHP/xBt912m5KTk/XJJ59ow4YN17bRAAAAFZxLZwBvv/12xcfH6+jRo/ZlR44c0ZgxY9SjR48y9xMXF6fXXntNkyZNUocOHZSZmank5GT7hR5ZWVnKzs62t4+KitKSJUs0f/58hYWF6Z///KdWrFihdu3a2dv069dP8+bN0yuvvKLQ0FC9+eab+uCDD3TLLbc4YcsBAAAqLpfeB/Dw4cPq06ePvv76a/vFEocPH1a7du20cuVKNWjQwFWlrwvuA4jL4SpgAKh4uA+giw8BN2zYUBkZGVq3bp39li2tW7dWdHS0K8sCAADgElx+H0CbzaY77rhDd9xxh6tLAQAAoAxceg6gJKWkpOiuu+7STTfdpJtuukl33XWX1q1b5+qyAAAAuAiXBsC//vWv6tWrl2rUqKH4+HjFx8fL19dXf/zjHzVnzhxXlgYAAMBFuPQQ8Msvv6zXX39dI0aMsC8bNWqUunXrppdfflnDhw93ZXkAAACUwqUzgCdPnlSvXr0uWN6zZ0/l5+e7sjQAAAAuwqUBsE+fPvroo48uWP7xxx/rrrvucmVpAAAAXIRLDwG3adNGL730kjZs2GB/DNuWLVu0adMmPfHEE3rjjTfsbcv6bGAAAABcG5feCLpJkyZlG4TNpu+++85Vw3AZbgSNy+FG0ABQ8XAjaBfPAB48eNCV3QMAAOAquPw+gOcYY+TCyUYAAACUkcsD4DvvvKPQ0FD5+PjIx8dH7du317vvvuvqsgAAALgIlx4Cnj59uiZOnKgRI0aoW7dukqQvv/xSw4YN0/HjxzVmzBhXlgcAAEApXBoAZ82apblz52rQoEH2ZX369FHbtm313HPPEQABAADKgUsPAWdnZysqKuqC5VFRUcrOznZlaQAAAFyESwNgs2bN9P7771+wfNmyZWrevLkrSwMAAOAiXHoI+Pnnn1dcXJy++OIL+zmAmzZtUkpKSqnBEAAAAK7n0hnA/v37Ky0tTf7+/lqxYoVWrFghf39/paWlqV+/fq4sDQAAgItw2QxgUVGRHn30UU2cOFGLFy92VRkAAABcIZfNAHp4eOiDDz5wVfcAAAC4Si49BBwbG6sVK1a4sgQAAACukEsvAmnevLleeOEFbdq0SeHh4apWrZrD+6NGjXJleQAAAJTCpQHwrbfeUs2aNZWenq709HSH92w2GwEQAACgHLg0AB48eND+/8YYSb8FPwAAAJQfl54DKP02C9iuXTt5e3vL29tb7dq105tvvunqsgAAALgIl84ATpo0SdOnT9fIkSMVGRkpSUpNTdWYMWOUlZWlF154wZXlAQAAUAqXBsC5c+dqwYIFGjBggH1Znz591L59e40cOZIACAAAUA5cegi4qKhInTp1umB5eHi4fv31V1eWBgAAwEW4NAAOHDhQc+fOvWD5/Pnz9cADD7iyNAAAAC7CpYeApd8uAlmzZo26du0qSdq6dauysrI0aNAgJSQk2NtNnz7d1UMBAACAXBwAd+3apZtvvlmSdODAAUmSv7+//P39tWvXLns7bg2DG1XjcZ+6vMZ/p/R2eQ0AwI3FpQFw/fr1ruweAAAAV8Hl9wEEAABAxUIABAAAsBgCIAAAgMUQAAEAACyGAAgAAGAxBEAAAACLIQACAABYDAEQAADAYgiAAAAAFkMABAAAsBgCIAAAgMUQAAEAACyGAAgAAGAxBEAAAACLIQACAABYDAEQAADAYgiAAAAAFkMABAAAsJhKFQDnzJmjxo0by9vbWxEREUpLS7tk++XLl6tVq1by9vZWaGioPvvss4u2HTZsmGw2m2bMmOHkUQMAAFQslSYALlu2TAkJCUpMTFRGRobCwsIUExOjvLy8Uttv3rxZAwYM0NChQ7Vjxw7FxsYqNjZWu3btuqDtRx99pC1btig4ONjVmwEAAFDuKk0AnD59uv7yl79oyJAhatOmjebNm6eqVavq7bffLrX9zJkz1atXL40dO1atW7fWiy++qJtvvlmzZ892aHfkyBGNHDlS//jHP+Th4XE9NgUAAKBcVYoAePbsWaWnpys6Otq+rEqVKoqOjlZqamqp66Smpjq0l6SYmBiH9iUlJRo4cKDGjh2rtm3bumbwAAAAFYx7eQ+gLI4fP67i4mIFBAQ4LA8ICNCePXtKXScnJ6fU9jk5Ofafp06dKnd3d40aNapM4zhz5ozOnDlj/7mgoKCsmwAAAFBhVIoZQFdIT0/XzJkztWjRItlstjKtk5SUJD8/P/urYcOGLh4lAACA81WKAOjv7y83Nzfl5uY6LM/NzVVgYGCp6wQGBl6y/b///W/l5eWpUaNGcnd3l7u7uw4dOqQnnnhCjRs3LrXP8ePHKz8/3/46fPjwtW8cAADAdVYpAqCnp6fCw8OVkpJiX1ZSUqKUlBRFRkaWuk5kZKRDe0lau3atvf3AgQP11VdfKTMz0/4KDg7W2LFjtXr16lL79PLykq+vr8MLAACgsqkU5wBKUkJCggYPHqxOnTqpS5cumjFjhgoLCzVkyBBJ0qBBg1S/fn0lJSVJkuLj49W9e3dNmzZNvXv31tKlS7V9+3bNnz9fklSnTh3VqVPHoYaHh4cCAwPVsmXL67txAAAA11GlCYBxcXE6duyYJk2apJycHHXo0EHJycn2Cz2ysrJUpcr/JjSjoqK0ZMkSPfvss5owYYKaN2+uFStWqF27duW1CQAAABWCzRhjynsQlVVBQYH8/PyUn59f5sPBjcd96uJRwWr+O6V3eQ8BACqVq/n+vtFUinMAAQAA4DwEQAAAAIshAAIAAFhMpbkIBEDprsd5pZxnCAA3FmYAAQAALIYACAAAYDEcAgZwWRxmBoAbCzOAAAAAFkMABAAAsBgCIAAAgMUQAAEAACyGAAgAAGAxBEAAAACLIQACAABYDAEQAADAYgiAAAAAFkMABAAAsBgCIAAAgMUQAAEAACyGAAgAAGAxBEAAAACLIQACAABYDAEQAADAYgiAAAAAFkMABAAAsBgCIAAAgMUQAAEAACyGAAgAAGAxBEAAAACLIQACAABYDAEQAADAYgiAAAAAFkMABAAAsBgCIAAAgMW4l/cAAOB6aTzuU5f2/98pvV3aPwA4CzOAAAAAFkMABAAAsBgOAQOoEFx9eBYA8D/MAAIAAFgMARAAAMBiCIAAAAAWQwAEAACwGAIgAACAxRAAAQAALIYACAAAYDEEQAAAAIvhRtAAAAfX46bcPDcZKF/MAAIAAFgMARAAAMBiCIAAAAAWQwAEAACwmEoVAOfMmaPGjRvL29tbERERSktLu2T75cuXq1WrVvL29lZoaKg+++wz+3tFRUV6+umnFRoaqmrVqik4OFiDBg3S0aNHXb0ZAAAA5arSBMBly5YpISFBiYmJysjIUFhYmGJiYpSXl1dq+82bN2vAgAEaOnSoduzYodjYWMXGxmrXrl2SpNOnTysjI0MTJ05URkaGPvzwQ+3du1d9+vS5npsFAABw3dmMMaa8B1EWERER6ty5s2bPni1JKikpUcOGDTVy5EiNGzfugvZxcXEqLCzUqlWr7Mu6du2qDh06aN68eaXW2LZtm7p06aJDhw6pUaNGlx1TQUGB/Pz8lJ+fL19f3zJtx/W4vQKA8nGj3NqE28DgRnc13983mkoxA3j27Fmlp6crOjravqxKlSqKjo5WampqqeukpqY6tJekmJiYi7aXpPz8fNlsNtWsWdMp4wYAAKiIKsWNoI8fP67i4mIFBAQ4LA8ICNCePXtKXScnJ6fU9jk5OaW2/+WXX/T0009rwIABF/3XwJkzZ3TmzBn7zwUFBVeyGQAAABVCpZgBdLWioiLdd999MsZo7ty5F22XlJQkPz8/+6thw4bXcZQAAADOUSkCoL+/v9zc3JSbm+uwPDc3V4GBgaWuExgYWKb258LfoUOHtHbt2kueCzB+/Hjl5+fbX4cPH77KLQIAACg/lSIAenp6Kjw8XCkpKfZlJSUlSklJUWRkZKnrREZGOrSXpLVr1zq0Pxf+9u/fr3Xr1qlOnTqXHIeXl5d8fX0dXgAAAJVNpTgHUJISEhI0ePBgderUSV26dNGMGTNUWFioIUOGSJIGDRqk+vXrKykpSZIUHx+v7t27a9q0aerdu7eWLl2q7du3a/78+ZJ+C39/+tOflJGRoVWrVqm4uNh+fmDt2rXl6elZPhsKAADgYpUmAMbFxenYsWOaNGmScnJy1KFDByUnJ9sv9MjKylKVKv+b0IyKitKSJUv07LPPasKECWrevLlWrFihdu3aSZKOHDmilStXSpI6dOjgUGv9+vW69dZbr8t2AQAAXG+V5j6AFRH3AQTwezfKve24DyBudNwHsBLNAAJARUdwAlBZVIqLQAAAAOA8BEAAAACLIQACAABYDAEQAADAYgiAAAAAFkMABAAAsBgCIAAAgMUQAAEAACyGG0EDQCXC04QAOAMzgAAAABZDAAQAALAYDgEDAG5Irj5cznOZUZkxAwgAAGAxBEAAAACL4RAwAAAWdj2uLOdwecXDDCAAAIDFEAABAAAshgAIAABgMQRAAAAAiyEAAgAAWAxXAQMArrsb4ZnGXD1bsVzJ76PkzGkXjqRyYAYQAADAYgiAAAAAFkMABAAAsBgCIAAAgMUQAAEAACyGAAgAAGAxBEAAAACLIQACAABYDDeCBgCggroRbpiNiokZQAAAAIshAAIAAFgMARAAAMBiCIAAAAAWQwAEAACwGAIgAACAxRAAAQAALIYACAAAYDEEQAAAAIvhSSAAAMCleKJJxcMMIAAAgMUQAAEAACyGAAgAAGAxBEAAAACLIQACAABYDAEQAADAYgiAAAAAFkMABAAAsBgCIAAAgMUQAAEAACymUgXAOXPmqHHjxvL29lZERITS0tIu2X758uVq1aqVvL29FRoaqs8++8zhfWOMJk2apKCgIPn4+Cg6Olr79+935SYAAACUu0oTAJctW6aEhAQlJiYqIyNDYWFhiomJUV5eXqntN2/erAEDBmjo0KHasWOHYmNjFRsbq127dtnbvPLKK3rjjTc0b948bd26VdWqVVNMTIx++eWX67VZAAAA153NGGPKexBlERERoc6dO2v27NmSpJKSEjVs2FAjR47UuHHjLmgfFxenwsJCrVq1yr6sa9eu6tChg+bNmydjjIKDg/XEE0/oySeflCTl5+crICBAixYt0v3333/ZMRUUFMjPz0/5+fny9fUt03bwQGwAAMpXyZnTOjzjviv6/r7RuJf3AMri7NmzSk9P1/jx4+3LqlSpoujoaKWmppa6TmpqqhISEhyWxcTEaMWKFZKkgwcPKicnR9HR0fb3/fz8FBERodTU1FID4JkzZ3TmzBn7z/n5+ZJ+C4JlVXLmdJnbAgAA5zv3XVxJ5sBcolIEwOPHj6u4uFgBAQEOywMCArRnz55S18nJySm1fU5Ojv39c8su1uZ8SUlJev755y9Y3rBhw7JtCAAAqDBOnDghPz+/8h5GuagUAbCiGD9+vMOs4smTJxUSEqKsrCyX/QEqKChQw4YNdfjwYZdNU7u6xo2wDdSoOP1To2LVuBG2gRoVp//rVSM/P1+NGjVS7dq1XdJ/ZVApAqC/v7/c3NyUm5vrsDw3N1eBgYGlrhMYGHjJ9uf+m5ubq6CgIIc2HTp0KLVPLy8veXl5XbDcz8/P5ecQ+Pr6VvoaN8I2UKPi9E+NilXjRtgGalSc/q9XjSpVKs21sE5XKbbc09NT4eHhSklJsS8rKSlRSkqKIiMjS10nMjLSob0krV271t6+SZMmCgwMdGhTUFCgrVu3XrRPAACAG0GlmAGUpISEBA0ePFidOnVSly5dNGPGDBUWFmrIkCGSpEGDBql+/fpKSkqSJMXHx6t79+6aNm2aevfuraVLl2r79u2aP3++JMlms2n06NGaPHmymjdvriZNmmjixIkKDg5WbGxseW0mAACAy1WaABgXF6djx45p0qRJysnJUYcOHZScnGy/iCMrK8thKjcqKkpLlizRs88+qwkTJqh58+ZasWKF2rVrZ2/z1FNPqbCwUI888ohOnjypW265RcnJyfL29i7TmLy8vJSYmFjqYWFnuRFq3AjbQI2K0z81KlaNG2EbqFFx+r+RalR0leY+gAAAAHCOSnEOIAAAAJyHAAgAAGAxBEAAAACLIQACAABYDAHwKs2ZM0eNGzeWt7e3IiIilJaW5tT+v/jiC919990KDg6WzWazP8PYWZKSktS5c2fVqFFD9erVU2xsrPbu3evUGnPnzlX79u3tN/OMjIzU559/7tQa55syZYr9Fj/O8txzz8lmszm8WrVq5bT+JenIkSP685//rDp16sjHx0ehoaHavn270/pv3LjxBdtgs9k0fPhwp9UoLi7WxIkT1aRJE/n4+Oimm27Siy++6PRnbf70008aPXq0QkJC5OPjo6ioKG3btu2q+7vcvmaM0aRJkxQUFCQfHx9FR0dr//79Tuv/ww8/VM+ePVWnTh3ZbDZlZmY6dRuKior09NNPKzQ0VNWqVVNwcLAGDRqko0ePOq2G9Nt+0qpVK1WrVk21atVSdHS0tm7d6tQavzds2DDZbDbNmDHDqTUefPDBC/aTXr16OXUbdu/erT59+sjPz0/VqlVT586dlZWV5bQape3rNptNr776qtNqnDp1SiNGjFCDBg3k4+OjNm3aaN68eWXuvyw1cnNz9eCDDyo4OFhVq1ZVr169rmjfK8v33C+//KLhw4erTp06ql69uvr373/BQyRuVATAq7Bs2TIlJCQoMTFRGRkZCgsLU0xMjPLy8pxWo7CwUGFhYZozZ47T+vy9jRs3avjw4dqyZYvWrl2roqIi9ezZU4WFhU6r0aBBA02ZMkXp6enavn27br/9dvXt21dff/2102r83rZt2/S3v/1N7du3d3rfbdu2VXZ2tv315ZdfOq3vH3/8Ud26dZOHh4c+//xzffPNN5o2bZpq1arltBrbtm1zGP/atWslSffee6/TakydOlVz587V7NmztXv3bk2dOlWvvPKKZs2a5bQakvTwww9r7dq1evfdd7Vz50717NlT0dHROnLkyFX1d7l97ZVXXtEbb7yhefPmaevWrapWrZpiYmL0yy+/OKX/wsJC3XLLLZo6depVjf9yNU6fPq2MjAxNnDhRGRkZ+vDDD7V371716dPHaTUkqUWLFpo9e7Z27typL7/8Uo0bN1bPnj117Ngxp9U456OPPtKWLVsUHBx8RdtQ1hq9evVy2F/ee+89p/V/4MAB3XLLLWrVqpU2bNigr776ShMnTizz7cfKUuP3Y8/Oztbbb78tm82m/v37O61GQkKCkpOTtXjxYu3evVujR4/WiBEjtHLlSqfUMMYoNjZW3333nT7++GPt2LFDISEhio6OLvP3VFm+58aMGaNPPvlEy5cv18aNG3X06FHdc889Zd6GSs3ginXp0sUMHz7c/nNxcbEJDg42SUlJLqknyXz00Ucu6fucvLw8I8ls3LjRpXVq1apl3nzzTaf3+9NPP5nmzZubtWvXmu7du5v4+Hin9Z2YmGjCwsKc1t/5nn76aXPLLbe4rP/SxMfHm5tuusmUlJQ4rc/evXubhx56yGHZPffcYx544AGn1Th9+rRxc3Mzq1atclh+8803m2eeeeaa+z9/XyspKTGBgYHm1VdftS87efKk8fLyMu+999419/97Bw8eNJLMjh07rrjfstY4Jy0tzUgyhw4dclmN/Px8I8msW7fOqTW+//57U79+fbNr1y4TEhJiXn/99avq/2I1Bg8ebPr27XvVfV6u/7i4OPPnP//ZKf1frMb5+vbta26//Xan1mjbtq154YUXHJZdy354fo29e/caSWbXrl32ZcXFxaZu3bpmwYIFV1Xj/O+5kydPGg8PD7N8+XJ7m927dxtJJjU19apqVCbMAF6hs2fPKj09XdHR0fZlVapUUXR0tFJTU8txZNcmPz9fklz2YOzi4mItXbpUhYWFLnnU3vDhw9W7d2+H34sz7d+/X8HBwWratKkeeOCBKzpcczkrV65Up06ddO+996pevXrq2LGjFixY4LT+z3f27FktXrxYDz30kGw2m9P6jYqKUkpKivbt2ydJ+s9//qMvv/xSd955p9Nq/PrrryouLr5gtsTHx8eps7LnHDx4UDk5OQ5/rvz8/BQREVHp93ebzaaaNWu6pP+zZ89q/vz58vPzU1hYmNP6LSkp0cCBAzV27Fi1bdvWaf2eb8OGDapXr55atmypxx57TCdOnHBKvyUlJfr000/VokULxcTEqF69eoqIiHD6KT6/l5ubq08//VRDhw51ar9RUVFauXKljhw5ImOM1q9fr3379qlnz55O6f/MmTOS5LCvV6lSRV5eXle9r5//PZeenq6ioiKH/btVq1Zq1KhRpd6/y4oAeIWOHz+u4uJi+xNIzgkICFBOTk45jeralJSUaPTo0erWrZvDk1KcYefOnapevbq8vLw0bNgwffTRR2rTpo1TayxdulQZGRn2xwA6W0REhBYtWqTk5GTNnTtXBw8e1P/7f/9PP/30k1P6/+677zR37lw1b95cq1ev1mOPPaZRo0bp73//u1P6P9+KFSt08uRJPfjgg07td9y4cbr//vvVqlUreXh4qGPHjho9erQeeOABp9WoUaOGIiMj9eKLL+ro0aMqLi7W4sWLlZqaquzsbKfVOefcPn0j7e+//PKLnn76aQ0YMEC+vr5O7XvVqlWqXr26vL299frrr2vt2rXy9/d3Wv9Tp06Vu7u7Ro0a5bQ+z9erVy+98847SklJ0dSpU7Vx40bdeeedKi4uvua+8/LydOrUKU2ZMkW9evXSmjVr1K9fP91zzz3auHGjE0Z/ob///e+qUaOG0w9rzpo1S23atFGDBg3k6empXr16ac6cOfrDH/7glP7PBbHx48frxx9/1NmzZzV16lR9//33V7Wvl/Y9l5OTI09Pzwv+IVSZ9+8rUWkeBQfXGT58uHbt2uWSGZSWLVsqMzNT+fn5+uc//6nBgwdr48aNTguBhw8fVnx8vNauXXtF59Bcid/PYLVv314REREKCQnR+++/75R/VZeUlKhTp056+eWXJUkdO3bUrl27NG/ePA0ePPia+z/fW2+9pTvvvPOqzp+6lPfff1//+Mc/tGTJErVt21aZmZkaPXq0goODnbod7777rh566CHVr19fbm5uuvnmmzVgwAClp6c7rcaNqqioSPfdd5+MMZo7d67T+7/tttuUmZmp48ePa8GCBbrvvvu0detW1atX75r7Tk9P18yZM5WRkeHUmevz3X///fb/Dw0NVfv27XXTTTdpw4YN6tGjxzX1XVJSIknq27evxowZI0nq0KGDNm/erHnz5ql79+7X1H9p3n77bT3wwANO//tx1qxZ2rJli1auXKmQkBB98cUXGj58uIKDg51yJMbDw0Mffvihhg4dqtq1a8vNzU3R0dG68847r+rCMld+z1VWzABeIX9/f7m5uV1wlVBubq4CAwPLaVRXb8SIEVq1apXWr1+vBg0aOL1/T09PNWvWTOHh4UpKSlJYWJhmzpzptP7T09OVl5enm2++We7u7nJ3d9fGjRv1xhtvyN3d3Sn/aj9fzZo11aJFC3377bdO6S8oKOiCQNy6dWunHmY+59ChQ1q3bp0efvhhp/c9duxY+yxgaGioBg4cqDFjxjh9Zvamm27Sxo0bderUKR0+fFhpaWkqKipS06ZNnVpHkn2fvhH293Ph79ChQ1q7dq3TZ/8kqVq1amrWrJm6du2qt956S+7u7nrrrbec0ve///1v5eXlqVGjRvZ9/dChQ3riiSfUuHFjp9QoTdOmTeXv7++U/d3f31/u7u7XbX//97//rb179zp9f//55581YcIETZ8+XXfffbfat2+vESNGKC4uTq+99prT6oSHhyszM1MnT55Udna2kpOTdeLEiSve1y/2PRcYGKizZ8/q5MmTDu0r4/59NQiAV8jT01Ph4eFKSUmxLyspKVFKSopLzm1zFWOMRowYoY8++kj/+te/1KRJk+tSt6SkxH5uhzP06NFDO3fuVGZmpv3VqVMnPfDAA8rMzJSbm5vTap1z6tQpHThwQEFBQU7pr1u3bhfcmmDfvn0KCQlxSv+/t3DhQtWrV0+9e/d2et+nT59WlSqOf6W4ubnZZz2crVq1agoKCtKPP/6o1atXq2/fvk6v0aRJEwUGBjrs7wUFBdq6dWul2t/Phb/9+/dr3bp1qlOnznWp68z9feDAgfrqq68c9vXg4GCNHTtWq1evdkqN0nz//fc6ceKEU/Z3T09Pde7c+brt72+99ZbCw8Odeh6m9Nufp6Kiouu2v/v5+alu3brav3+/tm/fXuZ9/XLfc+Hh4fLw8HDYv/fu3ausrKxKtX9fLQ4BX4WEhAQNHjxYnTp1UpcuXTRjxgwVFhZqyJAhTqtx6tQph39xHjx4UJmZmapdu7YaNWp0zf0PHz5cS5Ys0ccff6waNWrYz3fw8/OTj4/PNfcvSePHj9edd96pRo0a6aefftKSJUu0YcMGp/5lXaNGjQvOW6xWrZrq1KnjtPMZn3zySd19990KCQnR0aNHlZiYKDc3Nw0YMMAp/Y8ZM0ZRUVF6+eWXdd999yktLU3z58/X/PnzndL/OSUlJVq4cKEGDx4sd3fn7/p33323XnrpJTVq1Eht27bVjh07NH36dD300ENOrbN69WoZY9SyZUt9++23Gjt2rFq1anXV+9/l9rXRo0dr8uTJat68uZo0aaKJEycqODhYsbGxTun/hx9+UFZWlv2+fOfCQWBgYJlnIS5VIygoSH/605+UkZGhVatWqbi42L6/165dW56entdco06dOnrppZfUp08fBQUF6fjx45ozZ46OHDlyRbcautxndX5w9fDwUGBgoFq2bOmUGrVr19bzzz+v/v37KzAwUAcOHNBTTz2lZs2aKSYmxinbMHbsWMXFxekPf/iDbrvtNiUnJ+uTTz7Rhg0bnLIN574fCgoKtHz5ck2bNq3M/V5Jje7du2vs2LHy8fFRSEiINm7cqHfeeUfTp093Wo3ly5erbt26atSokXbu3Kn4+HjFxsaW+UKTy33P+fn5aejQoUpISFDt2rXl6+urkSNHKjIyUl27di3zdlRa5XkJcmU2a9Ys06hRI+Pp6Wm6dOlitmzZ4tT+169fbyRd8Bo8eLBT+i+tb0lm4cKFTunfGGMeeughExISYjw9PU3dunVNjx49zJo1a5zW/8U4+zYwcXFxJigoyHh6epr69eubuLg48+233zqtf2OM+eSTT0y7du2Ml5eXadWqlZk/f75T+zfGmNWrVxtJZu/evU7v2xhjCgoKTHx8vGnUqJHx9vY2TZs2Nc8884w5c+aMU+ssW7bMNG3a1Hh6eprAwEAzfPhwc/Lkyavu73L7WklJiZk4caIJCAgwXl5epkePHlf0GV6u/4ULF5b6fmJiolNqnLu9TGmv9evXO6XGzz//bPr162eCg4ONp6enCQoKMn369DFpaWll7r8sn9X5ruY2MJeqcfr0adOzZ09Tt25d4+HhYUJCQsxf/vIXk5OT49RteOutt0yzZs2Mt7e3CQsLMytWrHDaNpzzt7/9zfj4+Fz1vnG5GtnZ2ebBBx80wcHBxtvb27Rs2dJMmzbtim4tdbkaM2fONA0aNDAeHh6mUaNG5tlnn72iv0/K8j33888/m8cff9zUqlXLVK1a1fTr189kZ2eXuUZlZjPGybfpBwAAQIXGOYAAAAAWQwAEAACwGAIgAACAxRAAAQAALIYACAAAYDEEQAAAAIshAAIAAFgMARBAqW699VaNHj26vIdhZ4zRI488otq1a8tmsykzM7O8h2S3aNEi1axZ0/7zc889pw4dOlxynQcffLDMTxO5EZTlMwFw/RAAAVQKycnJWrRokVatWqXs7GynPerPFZ588kmH54s6w3//+98KF3wBVF48CxjAdVNcXCybzXbBQ+TL4sCBAwoKClJUVJQLRuZc1atXV/Xq1ct7GABwUcwAAhXYrbfeqlGjRumpp55S7dq1FRgYqOeee87+fmmzQidPnpTNZrM/XH7Dhg2y2WxavXq1OnbsKB8fH91+++3Ky8vT559/rtatW8vX11f/93//p9OnTzvU//XXXzVixAj5+fnJ399fEydO1O+fHnnmzBk9+eSTql+/vqpVq6aIiAiHh9qfOzS6cuVKtWnTRl5eXsrKyip1Wzdu3KguXbrIy8tLQUFBGjdunH799VdJvx0uHTlypLKysmSz2dS4ceOLfmabNm3SrbfeqqpVq6pWrVqKiYnRjz/+KOm3WcRbbrlFNWvWVJ06dXTXXXfpwIEDF3yeH374oW677TZVrVpVYWFhSk1NdaixaNEiNWrUSFWrVlW/fv104sQJh/fPP9xZXFyshIQEe92nnnpK5z+F83Jja9KkiSSpY8eOstlsuvXWW+3vvfnmm2rdurW8vb3VqlUr/fWvf73o5yP99udq5MiRGj16tGrVqqWAgAAtWLBAhYWFGjJkiGrUqKFmzZrp888/d9iGoUOHqkmTJvLx8VHLli01c+ZMh343bNigLl26qFq1aqpZs6a6deumQ4cOlTqGAwcOqGnTphoxYoSMMTp06JDuvvtu1apVS9WqVVPbtm312WefXXI7AFyD8nwQMYBL6969u/H19TXPPfec2bdvn/n73/9ubDabWbNmjTHGmIMHDxpJZseOHfZ1fvzxRyPJrF+/3hjzvweud+3a1Xz55ZcmIyPDNGvWzHTv3t307NnTZGRkmC+++MLUqVPHTJkyxaF29erVTXx8vNmzZ49ZvHixqVq1qpk/f769zcMPP2yioqLMF198Yb799lvz6quvGi8vL7Nv3z5jjDELFy40Hh4eJioqymzatMns2bPHFBYWXrCd33//valatap5/PHHze7du81HH31k/P39TWJiojHGmJMnT5oXXnjBNGjQwGRnZ5u8vLxSP68dO3YYLy8v89hjj5nMzEyza9cuM2vWLHPs2DFjjDH//Oc/zQcffGD2799vduzYYe6++24TGhpqiouLHT7PVq1amVWrVpm9e/eaP/3pTyYkJMQUFRUZY4zZsmWLqVKlipk6darZu3evmTlzpqlZs6bx8/OzjyMxMdGEhYXZf546daqpVauW+eCDD8w333xjhg4damrUqGH69u1rb3O5saWlpRlJZt26dSY7O9ucOHHCGGPM4sWLTVBQkPnggw/Md999Zz744ANTu3Zts2jRolI/o3O/2xo1apgXX3zR7Nu3z7z44ovGzc3N3HnnnWb+/Plm37595rHHHjN16tSx/77Onj1rJk2aZLZt22a+++47+5+HZcuWGWOMKSoqMn5+fubJJ5803377rfnmm2/MokWLzKFDhy74TP7zn/+YwMBA88wzz9jH1Lt3b3PHHXeYr776yhw4cMB88sknZuPGjRfdBgDXhgAIVGDdu3c3t9xyi8Oyzp07m6efftoYc2UBcN26dfY2SUlJRpI5cOCAfdmjjz5qYmJiHGq3bt3alJSU2Jc9/fTTpnXr1sYYYw4dOmTc3NzMkSNHHMbXo0cPM378eGPMbwFQksnMzLzkdk6YMMG0bNnSodacOXNM9erV7QHo9ddfNyEhIZfsZ8CAAaZbt26XbPN7x44dM5LMzp07jTH/+zzffPNNe5uvv/7aSDK7d++21/jjH//o0E9cXNwlA2BQUJB55ZVX7D8XFRWZBg0aOATAso7t979rY4y56aabzJIlSxyWvfjiiyYyMvKifZ//5+rXX3811apVMwMHDrQvy87ONpJMamrqRfsZPny46d+/vzHGmBMnThhJZsOGDaW2PfeZbNq0ydSqVcu89tprDu+Hhoaa55577qK1ADgXh4CBCq59+/YOPwcFBSkvL++a+gkICFDVqlXVtGlTh2Xn99u1a1fZbDb7z5GRkdq/f7+Ki4u1c+dOFRcXq0WLFvZz3qpXr66NGzc6HLr09PS8YBvOt3v3bkVGRjrU6tatm06dOqXvv/++zNuYmZmpHj16XPT9/fv3a8CAAWratKl8fX3th5LPPyz9+/EGBQVJkv2z2b17tyIiIhzaR0ZGXrRmfn6+srOzHdZxd3dXp06drmpsv1dYWKgDBw5o6NChDr+DyZMnO/wOSvP7bXRzc1OdOnUUGhpqXxYQEOCw3ZI0Z84chYeHq27duqpevbrmz59vH1/t2rX14IMPKiYmRnfffbdmzpyp7Oxsh5pZWVm64447NGnSJD3xxBMO740aNUqTJ09Wt27dlJiYqK+++uqS4wdwbQiAQAXn4eHh8LPNZlNJSYkk2S+mML87n6yoqOiy/dhstkv2WxanTp2Sm5ub0tPTlZmZaX/t3r3b4dwwHx8fh2DnSj4+Ppd8/+6779YPP/ygBQsWaOvWrdq6dask6ezZsw7tzv+sJF3RZ3M1yjq23zt16pQkacGCBQ6/g127dmnLli2XrFfa7/9S27106VI9+eSTGjp0qNasWaPMzEwNGTLEYXwLFy5UamqqoqKitGzZMrVo0cJhHHXr1lWXLl303nvvqaCgwKH+ww8/rO+++04DBw7Uzp071alTJ82aNeuS2wDg6hEAgUqsbt26kuQw0+LM24ScCyHnbNmyRc2bN5ebm5s6duyo4uJi5eXlqVmzZg6vwMDAK6rTunVrpaamOgTZTZs2qUaNGmrQoEGZ+2nfvv1Fb79y4sQJ7d27V88++6x69Oih1q1b2y8OudKxlva5XIyfn5+CgoIc1vn111+Vnp5+RWPz9PSU9NvFGOcEBAQoODhY33333QW/g3MXjTjLpk2bFBUVpccff1wdO3ZUs2bNSp1l7Nixo8aPH6/NmzerXbt2WrJkif09Hx8frVq1St7e3oqJidFPP/3ksG7Dhg01bNgwffjhh3riiSe0YMECp24DgP8hAAKVmI+Pj7p27aopU6Zo9+7d2rhxo5599lmn9Z+VlaWEhATt3btX7733nmbNmqX4+HhJUosWLfTAAw9o0KBB+vDDD3Xw4EGlpaUpKSlJn3766RXVefzxx3X48GGNHDlSe/bs0ccff6zExEQlJCRc0S1jxo8fr23btunxxx/XV199pT179mju3Lk6fvy4atWqpTp16mj+/Pn69ttv9a9//UsJCQlXNE7pt0OVycnJeu2117R//37Nnj1bycnJl1wnPj5eU6ZM0YoVK7Rnzx49/vjjOnnypP39soytXr168vHxUXJysnJzc5Wfny9Jev7555WUlKQ33nhD+/bt086dO7Vw4UJNnz79irftUpo3b67t27dr9erV2rdvnyZOnKht27bZ3z948KDGjx+v1NRUHTp0SGvWrNH+/fvVunVrh36qVaumTz/9VO7u7rrzzjvts5ijR4/W6tWrdfDgQWVkZGj9+vUXrAvAeQiAQCX39ttv69dff1V4eLhGjx6tyZMnO63vQYMG6eeff1aXLl00fPhwxcfH65FHHrG/v3DhQg0aNEhPPPGEWrZsqdjYWG3btk2NGjW6ojr169fXZ599prS0NIWFhWnYsGEaOnToFYfZFi1aaM2aNfrPf/6jLl26KDIyUh9//LHc3d1VpUoVLV26VOnp6WrXrp3GjBmjV1999Yr6l347L3LBggWaOXOmwsLCtGbNmsuO84knntDAgQM1ePBgRUZGqkaNGurXr5/9/bKMzd3dXW+88Yb+9re/KTg4WH379pX026HTN998UwsXLlRoaKi6d++uRYsWOX0G8NFHH9U999yjuLg4RURE6MSJE3r88cft71etWlV79uxR//791aJFCz3yyCMaPny4Hn300Qv6ql69uj7//HMZY9S7d28VFhaquLhYw4cPV+vWrdWrVy+1aNHisrezAXD1bMacdzMqAAAA3NCYAQQAALAYAiAAAIDFEAABAAAshgAIAABgMQRAAAAAiyEAAgAAWAwBEAAAwGIIgAAAABZDAAQAALAYAiAAAIDFEAABAAAshgAIAABgMf8fc4D/5Gd+91sAAAAASUVORK5CYII=",
- "text/html": [
- "\n",
- "
\n",
- "
\n",
- " Figure\n",
- "
\n",
- "

\n",
- "
\n",
- " "
- ],
- "text/plain": [
- "Canvas(toolbar=Toolbar(toolitems=[('Home', 'Reset original view', 'home', 'home'), ('Back', 'Back to previous …"
- ]
- },
- "metadata": {},
- "output_type": "display_data"
- }
- ],
- "source": [
- "max_amount = max(candidate_amounts)\n",
- "fig = plt.subplots()\n",
- "plt.hist(candidate_amounts, range=(1, max_amount), align=\"left\", density=True, bins=range(1, max_amount))#, bins=list(range(20)) + list(range(20, 100, 5)) + list(range(100, max(candidate_amounts), 10)))\n",
- "plt.xlabel(\"number of candidate masks\")\n",
- "plt.ylabel(\"proportion\")\n",
- "plt.xticks(range(max_amount))\n",
- "plt.xlim(0, 20);\n",
- "plt.show()"
- ]
- },
- {
- "cell_type": "code",
- "execution_count": 90,
- "id": "9f22ca9d-bdc2-4ea5-b2bc-249a256bb8ad",
- "metadata": {},
- "outputs": [
- {
- "data": {
- "application/vnd.jupyter.widget-view+json": {
- "model_id": "2710c2726d1e452d8abbcb45d8cff8e0",
- "version_major": 2,
- "version_minor": 0
- },
- "image/png": "iVBORw0KGgoAAAANSUhEUgAAAoAAAAHgCAYAAAA10dzkAAAAOnRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjEwLjEsIGh0dHBzOi8vbWF0cGxvdGxpYi5vcmcvc2/+5QAAAAlwSFlzAAAPYQAAD2EBqD+naQAAOuBJREFUeJzt3XtcVXW+//H3BuTiBVBJ8IJiaamJaCgI9js0I4UNZThNQx5PmuNMmTcUs8RUbKrBmSlHU0ePNukpx9Gcihw10khtUhRFKSlvqYljXDRHUCpU+P7+8OEet4JhsoXNej0fj/UY9nd91/p+P3sZvGetvda2GWOMAAAAYBludT0BAAAA3FwEQAAAAIshAAIAAFgMARAAAMBiCIAAAAAWQwAEAACwGAIgAACAxRAAAQAALIYACAAAYDEEQAAAAIshAAIAAFgMARAAAMBiCIAAAAAWQwAEAACwGAIgAACAxRAAAQAALIYACAAAYDEEQAAAAIshAAIAAFgMARAAAMBiCIAAAAAWQwAEAACwGAIgAACAxRAAAQAALIYACAAAYDEEQAAAAIshAAIAAFgMARAAAMBiCIAAAAAWQwAEAACwGAIgAACAxRAAAQAALIYACAAAYDEEQAAAAIshAAIAAFgMARAAAMBiCIAAAAAWQwAEAACwGAIgAACAxRAAAQAALIYACAAAYDEEQAAAAIshAAIAAFgMARAAAMBiCIAAAAAWQwAEAACwGAIgAACAxRAAAQAALIYACAAAYDEEQAAAAIshAAIAAFgMARAAAMBiCIAAAAAWQwAEAACwGAIgAACAxRAAAQAALMajrifgyiorK/X111+rWbNmstlsdT0dAABQA8YYnTlzRm3atJGbmzXPhREAb8DXX3+t4ODgup4GAAD4EY4dO6Z27drV9TTqBAHwBjRr1kzSxX9Avr6+dTwbAABQE6WlpQoODrb/HbciAuANuHTZ19fXlwAIAICLsfLHt6x54RsAAMDCCIAAAAAWQwAEAACwGAIgAACAxRAAAQAALIYACAAAYDEEQAAAAIshAAIAAFgMARAAAMBiCIAAAAAWQwAEAACwGAIgAACAxRAAAQAALIYACAAAYDEEQAAAAIshAAIAAFgMARAAAMBiCIAAAAAWQwAEAACwGAIgAACAxRAAAQAALIYACAAAYDEEQAAAAIshAAIAAFgMARAAAMBiCIAAAAAWQwAEAACwGAIgAACAxRAAAQAALIYACAAAYDEEQAAAAIshAAIAAFgMARAAAMBiCIAAAAAWQwAEAACwGAIgAACAxRAAAQAALIYACAAAYDEEQAAAAIshAAIAAFgMARAAAMBiCIAAAAAWQwAEAACwGAIgAACAxRAAAQAALIYACAAAYDEEQAAAAIshAAIAAFgMARAAAMBiCIAAAAAWQwAEAACwGAIgAACAxRAAAQAALMZlAuD8+fMVEhIib29vRUZGKjs7u9q+n3/+uR5++GGFhITIZrNp9uzZN7xPAACAhsIlAuDKlSuVnJys1NRU7dq1S2FhYYqLi1NxcXGV/b/99lvdeuutmjlzpoKCgmplnwAAAA2FzRhj6noSPyQyMlJ9+vTRvHnzJEmVlZUKDg7W2LFjNXny5GtuGxISovHjx2v8+PG1ts9LSktL5efnp5KSEvn6+l5/YQAA4Kbj77cLnAE8d+6ccnJyFBsba29zc3NTbGyssrKy6s0+AQAAXIVHXU/gh5w8eVIVFRUKDAx0aA8MDNS+fftu6j7Ly8tVXl5uf11aWvqjxgcAAKhL9f4MYH2SlpYmPz8/+xIcHFzXUwIAALhu9T4ABgQEyN3dXUVFRQ7tRUVF1d7g4ax9pqSkqKSkxL4cO3bsR40PAABQl+p9APT09FR4eLgyMzPtbZWVlcrMzFRUVNRN3aeXl5d8fX0dFgAAAFdT7z8DKEnJyckaNmyYevfurYiICM2ePVtlZWUaPny4JGno0KFq27at0tLSJF28yeOLL76w/3z8+HHl5uaqadOm6tSpU432CQAA0FC5RABMTEzUiRMnNH36dBUWFqpnz57KyMiw38SRn58vN7f/nMz8+uuv1atXL/vrl19+WS+//LJiYmK0adOmGu0TAACgoXKJ5wDWVzxHCAAA18Pfbxf4DCAAAABqFwEQAADAYgiAAAAAFkMABAAAsBgCIAAAgMUQAAEAACyGAAgAAGAxBEAAAACLIQACAABYDAGwHguZvLaupwAAABogAiAAAIDFEAABAAAshgAIAABgMQRAAAAAiyEAAgAAWAwBEAAAwGIIgAAAABZDAAQAALAYAiAAAIDFEAABAAAshgAIAABgMQRAAAAAiyEAAgAAWAwBEAAAwGIIgAAAABZDAAQAALAYAiAAAIDFEAABAAAshgAIAABgMQRAAAAAiyEAAgAAWAwBEAAAwGIIgAAAABZDAAQAALAYAiAAAIDFEAABAAAshgAIAABgMQRAAAAAiyEAAgAAWAwBEAAAwGIIgAAAABZDAAQAALAYAiAAAIDFEAABAAAshgAIAABgMQRAAAAAiyEAAgAAWAwBEAAAwGIIgAAAABZDAAQAALAYAiAAAIDFuEwAnD9/vkJCQuTt7a3IyEhlZ2dfs/+qVavUpUsXeXt7KzQ0VOvWrXNYf/bsWY0ZM0bt2rWTj4+PunXrpoULFzqzBAAAgHrBJQLgypUrlZycrNTUVO3atUthYWGKi4tTcXFxlf23bt2qwYMHa8SIEdq9e7cSEhKUkJCgvLw8e5/k5GRlZGRo2bJl2rt3r8aPH68xY8Zo9erVN6ssAACAOmEzxpi6nsQPiYyMVJ8+fTRv3jxJUmVlpYKDgzV27FhNnjz5qv6JiYkqKyvTmjVr7G19+/ZVz5497Wf5unfvrsTERE2bNs3eJzw8XPfff79efPHFGs2rtLRUfn5+Kikpka+v742UWKWQyWv11cz4Wt8vAABW5uy/366g3p8BPHfunHJychQbG2tvc3NzU2xsrLKysqrcJisry6G/JMXFxTn0j46O1urVq3X8+HEZY7Rx40YdOHBA9913X7VzKS8vV2lpqcMCAADgaup9ADx58qQqKioUGBjo0B4YGKjCwsIqtyksLPzB/nPnzlW3bt3Url07eXp6asCAAZo/f77+67/+q9q5pKWlyc/Pz74EBwffQGUAAAB1o94HQGeZO3eutm3bptWrVysnJ0evvPKKRo8erQ8//LDabVJSUlRSUmJfjh07dhNnDAAAUDs86noCPyQgIEDu7u4qKipyaC8qKlJQUFCV2wQFBV2z/3fffacpU6bo3XffVXz8xc/Y9ejRQ7m5uXr55Zevunx8iZeXl7y8vG60JAAAgDpV788Aenp6Kjw8XJmZmfa2yspKZWZmKioqqsptoqKiHPpL0oYNG+z9z58/r/Pnz8vNzbF8d3d3VVZW1nIFAAAA9Uu9PwMoXXxky7Bhw9S7d29FRERo9uzZKisr0/DhwyVJQ4cOVdu2bZWWliZJSkpKUkxMjF555RXFx8drxYoV2rlzpxYtWiRJ8vX1VUxMjCZNmiQfHx916NBBmzdv1htvvKFZs2bVWZ0AAAA3g0sEwMTERJ04cULTp09XYWGhevbsqYyMDPuNHvn5+Q5n86Kjo7V8+XJNnTpVU6ZMUefOnZWenq7u3bvb+6xYsUIpKSkaMmSITp06pQ4dOuill17SyJEjb3p9AAAAN5NLPAewvuI5gAAAuB6eA+gCnwEEAABA7SIAAgAAWAwBEAAAwGIIgAAAABZDAAQAALAYAiAAAIDFEAABAAAshgAIAABgMQRAAAAAiyEAAgAAWAwBEAAAwGIIgAAAABZDAAQAALAYAiAAAIDFEAABAAAshgAIAABgMQRAAAAAiyEAAgAAWAwBEAAAwGIIgAAAABZDAAQAALAYAiAAAIDFEAABAAAsxsPZAxw8eFAbN25UcXGxKisrHdZNnz7d2cMDAADgCk4NgIsXL9ZTTz2lgIAABQUFyWaz2dfZbDYCIAAAQB1wagB88cUX9dJLL+nZZ5915jAAAAC4Dk79DOC///1vPfLII84cAgAAANfJqQHwkUce0fr16505BAAAAK6TUy8Bd+rUSdOmTdO2bdsUGhqqRo0aOawfN26cM4cHAABAFWzGGOOsnXfs2LH6gW02HT582FlD3xSlpaXy8/NTSUmJfH19a33/IZPX6quZ8bW+XwAArMzZf79dgVPPAB45csSZu7cEQiAAAKhtN+1B0MYYOfFkIwAAAGrI6QHwjTfeUGhoqHx8fOTj46MePXrozTffdPawAAAAqIZTLwHPmjVL06ZN05gxY9SvXz9J0ieffKKRI0fq5MmTmjBhgjOHBwAAQBWcGgDnzp2rBQsWaOjQofa2gQMH6s4779SMGTMIgAAAAHXAqZeACwoKFB0dfVV7dHS0CgoKnDk0AAAAquHUANipUye99dZbV7WvXLlSnTt3dubQAAAAqIZTLwE///zzSkxM1Mcff2z/DOCWLVuUmZlZZTAEAACA8zn1DODDDz+s7du3KyAgQOnp6UpPT1dAQICys7M1aNAgZw4NAACAajj1DKAkhYeHa9myZc4eBgAAADVU6wGwtLTU/rUqpaWl1+xr1a9fAQAAqEu1HgCbN2+ugoICtWrVSv7+/rLZbFf1McbIZrOpoqKitocHAADAD6j1APjRRx+pRYsWkqSNGzfW9u4BAABwg2o9AMbExNh/7tixo4KDg686C2iM0bFjx2p7aAAAANSAU+8C7tixo06cOHFV+6lTp9SxY0dnDg0AAIBqODUAXvqs35XOnj0rb29vZw4NAACAajjlMTDJycmSJJvNpmnTpqlx48b2dRUVFdq+fbt69uzpjKEBAADwA5wSAHfv3i3p4hnAPXv2yNPT077O09NTYWFhevrpp50xNAAAAH6AUwLgpbt/hw8frldffVXNmjVzxjAAAAD4EZz2GcDz58/rzTff1NGjR501BAAAAH4EpwXARo0aqX379jzsGQAAoJ5x6l3Azz33nKZMmaJTp07d8L7mz5+vkJAQeXt7KzIyUtnZ2dfsv2rVKnXp0kXe3t4KDQ3VunXrruqzd+9eDRw4UH5+fmrSpIn69Omj/Pz8G54rAABAfebUADhv3jx9/PHHatOmje644w7dddddDktNrVy5UsnJyUpNTdWuXbsUFhamuLg4FRcXV9l/69atGjx4sEaMGKHdu3crISFBCQkJysvLs/c5dOiQ7r77bnXp0kWbNm3SZ599pmnTpvF4GgAA0ODZjDHGWTt//vnnr7k+NTW1RvuJjIxUnz59NG/ePElSZWWlgoODNXbsWE2ePPmq/omJiSorK9OaNWvsbX379lXPnj21cOFCSdKjjz6qRo0a6c0336xpOVcpLS2Vn5+fSkpK5Ovr+6P3U52QyWslSV/NjK/1fQMAYFXO/vvtCpxyF/AlNQ1413Lu3Dnl5OQoJSXF3ubm5qbY2FhlZWVVuU1WVpb9WYSXxMXFKT09XdLFALl27Vo988wziouL0+7du9WxY0elpKQoISGh2rmUl5ervLzc/rq0tPTHFwYAAFBHnHoJ+JKcnBwtW7ZMy5Ytsz8jsKZOnjypiooKBQYGOrQHBgaqsLCwym0KCwuv2b+4uFhnz57VzJkzNWDAAK1fv16DBg3Sz3/+c23evLnauaSlpcnPz8++BAcHX1ctAAAA9YFTzwAWFxfr0Ucf1aZNm+Tv7y9JOn36tH7yk59oxYoVuuWWW5w5fLUqKyslSQ899JAmTJggSerZs6e2bt2qhQsXKiYmpsrtUlJSHM4slpaWEgIBAIDLceoZwLFjx+rMmTP6/PPPderUKZ06dUp5eXkqLS3VuHHjarSPgIAAubu7q6ioyKG9qKhIQUFBVW4TFBR0zf4BAQHy8PBQt27dHPp07dr1mncBe3l5ydfX12EBAABwNU4NgBkZGfrzn/+srl272tu6deum+fPn6/3336/RPjw9PRUeHq7MzEx7W2VlpTIzMxUVFVXlNlFRUQ79JWnDhg32/p6enurTp4/279/v0OfAgQPq0KFDjeYFAADgqpx6CbiyslKNGjW6qr1Ro0b2y7A1kZycrGHDhql3796KiIjQ7NmzVVZWpuHDh0uShg4dqrZt2yotLU2SlJSUpJiYGL3yyiuKj4/XihUrtHPnTi1atMi+z0mTJikxMVH/9V//pZ/85CfKyMjQP/7xD23atOnGigYAAKjnnHoG8Kc//amSkpL09ddf29uOHz+uCRMmqH///jXeT2Jiol5++WVNnz5dPXv2VG5urjIyMuw3euTn56ugoMDePzo6WsuXL9eiRYsUFhamv//970pPT1f37t3tfQYNGqSFCxfqD3/4g0JDQ/Xaa6/p7bff1t13310LlQMAANRfTn0O4LFjxzRw4EB9/vnn9psljh07pu7du2v16tVq166ds4a+KXgOIAAArofnADr5EnBwcLB27dqlDz/8UPv27ZN08UaL2NhYZw4LAACAa3BqAJQkm82me++9V/fee6+zhwIAAEANOP1B0JmZmXrggQd022236bbbbtMDDzygDz/80NnDAgAAoBpODYB//vOfNWDAADVr1kxJSUlKSkqSr6+vfvazn2n+/PnOHBoAAADVcOol4N/97nf605/+pDFjxtjbxo0bp379+ul3v/udRo8e7czhAQAAUAWnngE8ffq0BgwYcFX7fffdp5KSEmcODQAAgGo4NQAOHDhQ77777lXt7733nh544AFnDg0AAIBqOPUScLdu3fTSSy9p06ZN9q9h27Ztm7Zs2aKJEyfq1Vdftfet6XcDAwAA4MY49UHQHTt2rNkkbDYdPnzYWdNwGh4EDQCA6+FB0E4+A3jkyBFn7h4AAAA/gtOfA3iJMUZOPNkIAACAGnJ6AHzjjTcUGhoqHx8f+fj4qEePHnrzzTedPSwAAACq4dRLwLNmzdK0adM0ZswY9evXT5L0ySefaOTIkTp58qQmTJjgzOEBAABQBacGwLlz52rBggUaOnSovW3gwIG68847NWPGDAIgAABAHXDqJeCCggJFR0df1R4dHa2CggJnDg0AAIBqODUAdurUSW+99dZV7StXrlTnzp2dOTQAAACq4dRLwM8//7wSExP18ccf2z8DuGXLFmVmZlYZDAEAAOB8Tj0D+PDDDys7O1sBAQFKT09Xenq6AgIClJ2drUGDBjlzaAAAAFTDaWcAz58/ryeffFLTpk3TsmXLnDUMAAAArpPTzgA2atRIb7/9trN2DwAAgB/JqZeAExISlJ6e7swhAAAAcJ2cehNI586d9dvf/lZbtmxReHi4mjRp4rB+3LhxzhweAAAAVXBqAPzLX/4if39/5eTkKCcnx2GdzWYjAAIAANQBpwbAI0eO2H82xki6GPwAAABQd5z6GUDp4lnA7t27y9vbW97e3urevbtee+01Zw8LAACAajj1DOD06dM1a9YsjR07VlFRUZKkrKwsTZgwQfn5+frtb3/rzOEBAABQBacGwAULFmjx4sUaPHiwvW3gwIHq0aOHxo4dSwAEAACoA069BHz+/Hn17t37qvbw8HBduHDBmUMDAACgGk4NgI899pgWLFhwVfuiRYs0ZMgQZw4NAACAajj1ErB08SaQ9evXq2/fvpKk7du3Kz8/X0OHDlVycrK936xZs5w9FQAAAMjJATAvL0933XWXJOnQoUOSpICAAAUEBCgvL8/ej0fDXFvI5LX6amZ8XU8DAAA0EE4NgBs3bnTm7gEAAPAjOP05gAAAAKhfCIAAAAAWQwAEAACwGAIgAACAxRAAAQAALIYACAAAYDEEQAAAAIshAAIAAFgMARAAAMBiCIAAAAAWQwAEAACwGAIgAACAxRAAAQAALIYACAAAYDEEQAAAAIshAAIAAFgMARAAAMBiCIAAAAAW41IBcP78+QoJCZG3t7ciIyOVnZ19zf6rVq1Sly5d5O3trdDQUK1bt67aviNHjpTNZtPs2bNredYAAAD1i8sEwJUrVyo5OVmpqanatWuXwsLCFBcXp+Li4ir7b926VYMHD9aIESO0e/duJSQkKCEhQXl5eVf1fffdd7Vt2za1adPG2WUAAADUOZcJgLNmzdJvfvMbDR8+XN26ddPChQvVuHFjvf7661X2nzNnjgYMGKBJkyapa9eueuGFF3TXXXdp3rx5Dv2OHz+usWPH6q9//asaNWp0M0oBAACoUy4RAM+dO6ecnBzFxsba29zc3BQbG6usrKwqt8nKynLoL0lxcXEO/SsrK/XYY49p0qRJuvPOO50zeQAAgHrGo64nUBMnT55URUWFAgMDHdoDAwO1b9++KrcpLCyssn9hYaH99e9//3t5eHho3LhxNZpHeXm5ysvL7a9LS0trWgIAAEC94RJnAJ0hJydHc+bM0dKlS2Wz2Wq0TVpamvz8/OxLcHCwk2cJAABQ+1wiAAYEBMjd3V1FRUUO7UVFRQoKCqpym6CgoGv2/+c//6ni4mK1b99eHh4e8vDw0NGjRzVx4kSFhIRUuc+UlBSVlJTYl2PHjt14cQAAADeZSwRAT09PhYeHKzMz095WWVmpzMxMRUVFVblNVFSUQ39J2rBhg73/Y489ps8++0y5ubn2pU2bNpo0aZI++OCDKvfp5eUlX19fhwUAAMDVuMRnACUpOTlZw4YNU+/evRUREaHZs2errKxMw4cPlyQNHTpUbdu2VVpamiQpKSlJMTExeuWVVxQfH68VK1Zo586dWrRokSSpZcuWatmypcMYjRo1UlBQkO64446bWxwAAMBN5DIBMDExUSdOnND06dNVWFionj17KiMjw36jR35+vtzc/nNCMzo6WsuXL9fUqVM1ZcoUde7cWenp6erevXtdlQAAAFAv2Iwxpq4n4apKS0vl5+enkpISp1wODpm81v7zVzPja33/AABYkbP/frsCl/gMIAAAAGoPARAAAMBiCIAAAAAWQwAEAACwGAIgAACAxRAAAQAALIYA6CIufyQMAADAjSAAAgAAWAwBEAAAwGIIgAAAABZDAAQAALAYAiAAAIDFEAABAAAshgAIAABgMQRAAAAAiyEAAgAAWAwBEAAAwGIIgAAAABZDAAQAALAYAiAAAIDFEAABAAAshgAIAABgMQRAAAAAiyEAAgAAWAwBEAAAwGIIgAAAABZDAAQAALAYAiAAAIDFEAABAAAshgAIAABgMQRAAAAAiyEAAgAAWAwBEAAAwGIIgAAAABZDAAQAALAYAiAAAIDFEAABAAAshgDoQkImr63rKQAAgAaAAAgAAGAxBEAAAACLIQACAABYDAEQAADAYgiAAAAAFkMABAAAsBgCIAAAgMUQAAEAACyGAOiCeCA0AAC4EQRAAAAAiyEAAgAAWAwBEAAAwGIIgAAAABbjUgFw/vz5CgkJkbe3tyIjI5WdnX3N/qtWrVKXLl3k7e2t0NBQrVu3zr7u/PnzevbZZxUaGqomTZqoTZs2Gjp0qL7++mtnlwEAAFCnXCYArly5UsnJyUpNTdWuXbsUFhamuLg4FRcXV9l/69atGjx4sEaMGKHdu3crISFBCQkJysvLkyR9++232rVrl6ZNm6Zdu3bpnXfe0f79+zVw4MCbWRYAAMBNZzPGmLqeRE1ERkaqT58+mjdvniSpsrJSwcHBGjt2rCZPnnxV/8TERJWVlWnNmjX2tr59+6pnz55auHBhlWPs2LFDEREROnr0qNq3b/+DcyotLZWfn59KSkrk6+v7IyurXlWPe/lqZrxCJq/VVzPja308AACswNl/v12BS5wBPHfunHJychQbG2tvc3NzU2xsrLKysqrcJisry6G/JMXFxVXbX5JKSkpks9nk7+9fK/MGAACojzzqegI1cfLkSVVUVCgwMNChPTAwUPv27atym8LCwir7FxYWVtn/+++/17PPPqvBgwdX+/8GysvLVV5ebn9dWlp6PWUAAADUCy5xBtDZzp8/r1/+8pcyxmjBggXV9ktLS5Ofn599CQ4OvomzBAAAqB0uEQADAgLk7u6uoqIih/aioiIFBQVVuU1QUFCN+l8Kf0ePHtWGDRuu+VmAlJQUlZSU2Jdjx479yIoAAADqjksEQE9PT4WHhyszM9PeVllZqczMTEVFRVW5TVRUlEN/SdqwYYND/0vh7+DBg/rwww/VsmXLa87Dy8tLvr6+DgsAAICrcYnPAEpScnKyhg0bpt69eysiIkKzZ89WWVmZhg8fLkkaOnSo2rZtq7S0NElSUlKSYmJi9Morryg+Pl4rVqzQzp07tWjRIkkXw98vfvEL7dq1S2vWrFFFRYX984EtWrSQp6dn3RQKAADgZC4TABMTE3XixAlNnz5dhYWF6tmzpzIyMuw3euTn58vN7T8nNKOjo7V8+XJNnTpVU6ZMUefOnZWenq7u3btLko4fP67Vq1dLknr27Okw1saNG3XPPffclLoAAABuNpd5DmB9xHMAAQBwPTwH0EU+A4j/qCoUAgAAXA8CIAAAgMUQAAEAACyGAAgAAGAxBEAAAACLIQACAABYDAEQAADAYgiAAAAAFkMABAAAsBgCYAPEw6IBAMC1EAABAAAshgAIAABgMQRAF8VlXgAA8GMRAAEAACyGAAgAAGAxBEAXx6VgAABwvQiAAAAAFkMABAAAsBgCIAAAgMUQAAEAACyGAAgAAGAxBEAXdukO4GvdCcxdwgAA4EoEQAAAAIshAAIAAFgMARAAAMBiCIAAAAAWQwAEAACwGAJgA8HdvgAAoKYIgAAAABZDAAQAALAYAiAAAIDFEAABAAAshgAIAABgMQRAAAAAiyEANlA8FgYAAFSHAAgAAGAxBEAAAACLIQA2MJdf+r3yMjCXhQEAgEQABAAAsBwCIAAAgMUQAAEAACyGAAgAAGAxBEAAAACL8ajrCeDmuHQHcMjktfpqZrxD2yWX2gEAQMPGGUAAAACLIQACAABYjM0YY+p6Eq6qtLRUfn5+Kikpka+vb63vvy4e3HzlZeBLc7hZl4cvv0QNAIAzOPvvtyvgDCAAAIDFEAABAAAshgAIByGT1zos1+pX0/3dyHoAAFD7CIAAAAAW41IBcP78+QoJCZG3t7ciIyOVnZ19zf6rVq1Sly5d5O3trdDQUK1bt85hvTFG06dPV+vWreXj46PY2FgdPHjQmSUAAADUOZcJgCtXrlRycrJSU1O1a9cuhYWFKS4uTsXFxVX237p1qwYPHqwRI0Zo9+7dSkhIUEJCgvLy8ux9/vCHP+jVV1/VwoULtX37djVp0kRxcXH6/vvvb1ZZLuXKy8KXP1z68p+r2q4mbVWtv/KSdHWXpquaw7XmdCNzu95+Ne1fHy+H19Wc6uN7URPOmLervhd1xVnvF8cBDY3LBMBZs2bpN7/5jYYPH65u3bpp4cKFaty4sV5//fUq+8+ZM0cDBgzQpEmT1LVrV73wwgu66667NG/ePEkXz/7Nnj1bU6dO1UMPPaQePXrojTfe0Ndff6309PSbWBkAAMDN5RJfBXfu3Dnl5OQoJSXF3ubm5qbY2FhlZWVVuU1WVpaSk5Md2uLi4uzh7siRIyosLFRsbKx9vZ+fnyIjI5WVlaVHH330qn2Wl5ervLzc/rqkpETSxecJOUNl+bdO2e+PUVpaap/PD/18+ftx+brLXepXVf/L26t7D6ra35VzqG6MqubxQ2013fZG+l/v/m6GuppTfXwvasIZ83bV96KuOOv94jg0LJeOpaUfhWxcwPHjx40ks3XrVof2SZMmmYiIiCq3adSokVm+fLlD2/z5802rVq2MMcZs2bLFSDJff/21Q59HHnnE/PKXv6xyn6mpqUYSCwsLCwsLSwNYjh079mOjictziTOA9UVKSorDWcXKykqdOnVKLVu2lM1mq7VxSktLFRwcrGPHjjXYJ5Q39Boben1Sw6+R+lxfQ6+xodcnOa9GY4zOnDmjNm3a1No+XY1LBMCAgAC5u7urqKjIob2oqEhBQUFVbhMUFHTN/pf+t6ioSK1bt3bo07Nnzyr36eXlJS8vL4c2f3//6ynluvj6+jbY/6gvaeg1NvT6pIZfI/W5voZeY0OvT3JOjX5+frW6P1fjEjeBeHp6Kjw8XJmZmfa2yspKZWZmKioqqsptoqKiHPpL0oYNG+z9O3bsqKCgIIc+paWl2r59e7X7BAAAaAhc4gygJCUnJ2vYsGHq3bu3IiIiNHv2bJWVlWn48OGSpKFDh6pt27ZKS0uTJCUlJSkmJkavvPKK4uPjtWLFCu3cuVOLFi2SJNlsNo0fP14vvviiOnfurI4dO2ratGlq06aNEhIS6qpMAAAAp3OZAJiYmKgTJ05o+vTpKiwsVM+ePZWRkaHAwEBJUn5+vtzc/nNCMzo6WsuXL9fUqVM1ZcoUde7cWenp6erevbu9zzPPPKOysjI98cQTOn36tO6++25lZGTI29v7ptd3OS8vL6Wmpl51ubkhaeg1NvT6pIZfI/W5voZeY0OvT7JGjXXFZoyV74EGAACwHpf4DCAAAABqDwEQAADAYgiAAAAAFkMABAAAsBgCYD00f/58hYSEyNvbW5GRkcrOzq7rKdXIxx9/rAcffFBt2rSRzWazf+/yJcYYTZ8+Xa1bt5aPj49iY2N18OBBhz6nTp3SkCFD5OvrK39/f40YMUJnz569iVVULy0tTX369FGzZs3UqlUrJSQkaP/+/Q59vv/+e40ePVotW7ZU06ZN9fDDD1/1QPL8/HzFx8ercePGatWqlSZNmqQLFy7czFKqtWDBAvXo0cP+0NWoqCi9//779vWuXt+VZs6caX8k1CWuXOOMGTNks9kcli5dutjXu3Jtlzt+/Lj+53/+Ry1btpSPj49CQ0O1c+dO+3pX/l0TEhJy1TG02WwaPXq0pIZxDCsqKjRt2jR17NhRPj4+uu222/TCCy84fC+vKx9Dl1GHX0OHKqxYscJ4enqa119/3Xz++efmN7/5jfH39zdFRUV1PbUftG7dOvPcc8+Zd955x0gy7777rsP6mTNnGj8/P5Oenm4+/fRTM3DgQNOxY0fz3Xff2fsMGDDAhIWFmW3btpl//vOfplOnTmbw4ME3uZKqxcXFmSVLlpi8vDyTm5trfvazn5n27dubs2fP2vuMHDnSBAcHm8zMTLNz507Tt29fEx0dbV9/4cIF0717dxMbG2t2795t1q1bZwICAkxKSkpdlHSV1atXm7Vr15oDBw6Y/fv3mylTpphGjRqZvLw8Y4zr13e57OxsExISYnr06GGSkpLs7a5cY2pqqrnzzjtNQUGBfTlx4oR9vSvXdsmpU6dMhw4dzOOPP262b99uDh8+bD744APz5Zdf2vu48u+a4uJih+O3YcMGI8ls3LjRGNMwjuFLL71kWrZsadasWWOOHDliVq1aZZo2bWrmzJlj7+PKx9BVEADrmYiICDN69Gj764qKCtOmTRuTlpZWh7O6flcGwMrKShMUFGT++Mc/2ttOnz5tvLy8zN/+9jdjjDFffPGFkWR27Nhh7/P+++8bm81mjh8/ftPmXlPFxcVGktm8ebMx5mI9jRo1MqtWrbL32bt3r5FksrKyjDEXQ7Kbm5spLCy091mwYIHx9fU15eXlN7eAGmrevLl57bXXGlR9Z86cMZ07dzYbNmwwMTEx9gDo6jWmpqaasLCwKte5em2XPPvss+buu++udn1D+12TlJRkbrvtNlNZWdlgjmF8fLz51a9+5dD285//3AwZMsQY0/COYX3FJeB65Ny5c8rJyVFsbKy9zc3NTbGxscrKyqrDmd24I0eOqLCw0KE2Pz8/RUZG2mvLysqSv7+/evfube8TGxsrNzc3bd++/abP+YeUlJRIklq0aCFJysnJ0fnz5x1q7NKli9q3b+9QY2hoqP0B5pIUFxen0tJSff755zdx9j+soqJCK1asUFlZmaKiohpUfaNHj1Z8fLxDLVLDOIYHDx5UmzZtdOutt2rIkCHKz8+X1DBqk6TVq1erd+/eeuSRR9SqVSv16tVLixcvtq9vSL9rzp07p2XLlulXv/qVbDZbgzmG0dHRyszM1IEDByRJn376qT755BPdf//9khrWMazPXOabQKzg5MmTqqiocPgPV5ICAwO1b9++OppV7SgsLJSkKmu7tK6wsFCtWrVyWO/h4aEWLVrY+9QXlZWVGj9+vPr162f/dpnCwkJ5enrK39/foe+VNVb1HlxaVx/s2bNHUVFR+v7779W0aVO9++676tatm3JzcxtEfStWrNCuXbu0Y8eOq9a5+jGMjIzU0qVLdccdd6igoEDPP/+8/t//+3/Ky8tz+douOXz4sBYsWKDk5GRNmTJFO3bs0Lhx4+Tp6alhw4Y1qN816enpOn36tB5//HFJrv/v85LJkyertLRUXbp0kbu7uyoqKvTSSy9pyJAhkhre34v6igAI/AijR49WXl6ePvnkk7qeSq274447lJubq5KSEv3973/XsGHDtHnz5rqeVq04duyYkpKStGHDhjr/ykdnuHQGRZJ69OihyMhIdejQQW+99ZZ8fHzqcGa1p7KyUr1799bvfvc7SVKvXr2Ul5enhQsXatiwYXU8u9r1l7/8Rffff7/atGlT11OpVW+99Zb++te/avny5brzzjuVm5ur8ePHq02bNg3uGNZnXAKuRwICAuTu7n7VHV1FRUUKCgqqo1nVjkvzv1ZtQUFBKi4udlh/4cIFnTp1ql7VP2bMGK1Zs0YbN25Uu3bt7O1BQUE6d+6cTp8+7dD/yhqreg8urasPPD091alTJ4WHhystLU1hYWGaM2dOg6gvJydHxcXFuuuuu+Th4SEPDw9t3rxZr776qjw8PBQYGOjyNV7O399ft99+u7788ssGcfwkqXXr1urWrZtDW9euXe2XuhvK75qjR4/qww8/1K9//Wt7W0M5hpMmTdLkyZP16KOPKjQ0VI899pgmTJigtLQ0SQ3nGNZ3BMB6xNPTU+Hh4crMzLS3VVZWKjMzU1FRUXU4sxvXsWNHBQUFOdRWWlqq7du322uLiorS6dOnlZOTY+/z0UcfqbKyUpGRkTd9zlcyxmjMmDF699139dFHH6ljx44O68PDw9WoUSOHGvfv36/8/HyHGvfs2ePwi2vDhg3y9fW96o9afVFZWany8vIGUV///v21Z88e5ebm2pfevXtryJAh9p9dvcbLnT17VocOHVLr1q0bxPGTpH79+l31+KUDBw6oQ4cOkhrG7xpJWrJkiVq1aqX4+Hh7W0M5ht9++63c3Bzjh7u7uyorKyU1nGNY79X1XShwtGLFCuPl5WWWLl1qvvjiC/PEE08Yf39/hzu66qszZ86Y3bt3m927dxtJZtasWWb37t3m6NGjxpiLt/X7+/ub9957z3z22WfmoYceqvK2/l69epnt27ebTz75xHTu3Lne3Nb/1FNPGT8/P7Np0yaHxzR8++239j4jR4407du3Nx999JHZuXOniYqKMlFRUfb1lx7RcN9995nc3FyTkZFhbrnllnrziIbJkyebzZs3myNHjpjPPvvMTJ482dhsNrN+/XpjjOvXV5XL7wI2xrVrnDhxotm0aZM5cuSI2bJli4mNjTUBAQGmuLjYGOPatV2SnZ1tPDw8zEsvvWQOHjxo/vrXv5rGjRubZcuW2fu4+u+aiooK0759e/Pss89eta4hHMNhw4aZtm3b2h8D884775iAgADzzDPP2Pu4+jF0BQTAemju3Lmmffv2xtPT00RERJht27bV9ZRqZOPGjUbSVcuwYcOMMRdv7Z82bZoJDAw0Xl5epn///mb//v0O+/jmm2/M4MGDTdOmTY2vr68ZPny4OXPmTB1Uc7WqapNklixZYu/z3XffmVGjRpnmzZubxo0bm0GDBpmCggKH/Xz11Vfm/vvvNz4+PiYgIMBMnDjRnD9//iZXU7Vf/epXpkOHDsbT09Pccsstpn///vbwZ4zr11eVKwOgK9eYmJhoWrdubTw9PU3btm1NYmKiw/PxXLm2y/3jH/8w3bt3N15eXqZLly5m0aJFDutd/XfNBx98YCRdNWdjGsYxLC0tNUlJSaZ9+/bG29vb3Hrrrea5555zeEyNqx9DV2Az5rJHbwMAAKDB4zOAAAAAFkMABAAAsBgCIAAAgMUQAAEAACyGAAgAAGAxBEAAAACLIQACAABYDAEQQJXuuecejR8/vq6nYWeM0RNPPKEWLVrIZrMpNze3rqdkt3TpUvn7+9tfz5gxQz179rzmNo8//rgSEhKcOq/6pCbvCYCbhwAIwCVkZGRo6dKlWrNmjQoKCtS9e/e6nlK1nn76aYfvMa0NX331Vb0LvgBcl0ddTwCAdVRUVMhms131RfA1cejQIbVu3VrR0dFOmFntatq0qZo2bVrX0wCAanEGEKjH7rnnHo0bN07PPPOMWrRooaCgIM2YMcO+vqqzQqdPn5bNZtOmTZskSZs2bZLNZtMHH3ygXr16ycfHRz/96U9VXFys999/X127dpWvr6/++7//W99++63D+BcuXNCYMWPk5+engIAATZs2TZd/e2R5ebmefvpptW3bVk2aNFFkZKR9XOk/l0ZXr16tbt26ycvLS/n5+VXWunnzZkVERMjLy0utW7fW5MmTdeHCBUkXL5eOHTtW+fn5stlsCgkJqfY927Jli+655x41btxYzZs3V1xcnP79739LungW8e6775a/v79atmypBx54QIcOHbrq/XznnXf0k5/8RI0bN1ZYWJiysrIcxli6dKnat2+vxo0ba9CgQfrmm28c1l95ubOiokLJycn2cZ955hld+S2cPzS3jh07SpJ69eolm82me+65x77utddeU9euXeXt7a0uXbroz3/+c7Xvj3Tx39XYsWM1fvx4NW/eXIGBgVq8eLHKyso0fPhwNWvWTJ06ddL777/vUMOIESPUsWNH+fj46I477tCcOXMc9rtp0yZFRESoSZMm8vf3V79+/XT06NEq53Do0CHdeuutGjNmjIwxOnr0qB588EE1b95cTZo00Z133ql169Zdsw4AN6Auv4gYwLXFxMQYX19fM2PGDHPgwAHzf//3f8Zms5n169cbY4w5cuSIkWR2795t3+bf//63kWQ2btxojDFm48aNRpLp27ev+eSTT8yuXbtMp06dTExMjLnvvvvMrl27zMcff2xatmxpZs6c6TB206ZNTVJSktm3b59ZtmyZady4sVm0aJG9z69//WsTHR1tPv74Y/Pll1+aP/7xj8bLy8scOHDAGGPMkiVLTKNGjUx0dLTZsmWL2bdvnykrK7uqzn/961+mcePGZtSoUWbv3r3m3XffNQEBASY1NdUYY8zp06fNb3/7W9OuXTtTUFBgiouLq3y/du/ebby8vMxTTz1lcnNzTV5enpk7d645ceKEMcaYv//97+btt982Bw8eNLt37zYPPvigCQ0NNRUVFQ7vZ5cuXcyaNWvM/v37zS9+8QvToUMHc/78eWOMMdu2bTNubm7m97//vdm/f7+ZM2eO8ff3N35+fvZ5pKammrCwMPvr3//+96Z58+bm7bffNl988YUZMWKEadasmXnooYfsfX5obtnZ2UaS+fDDD01BQYH55ptvjDHGLFu2zLRu3dq8/fbb5vDhw+btt982LVq0MEuXLq3yPbp0bJs1a2ZeeOEFc+DAAfPCCy8Yd3d3c//995tFixaZAwcOmKeeesq0bNnSfrzOnTtnpk+fbnbs2GEOHz5s//ewcuVKY4wx58+fN35+fubpp582X375pfniiy/M0qVLzdGjR696Tz799FMTFBRknnvuOfuc4uPjzb333ms+++wzc+jQIfOPf/zDbN68udoaANwYAiBQj8XExJi7777boa1Pnz7m2WefNcZcXwD88MMP7X3S0tKMJHPo0CF725NPPmni4uIcxu7atauprKy0tz377LOma9euxhhjjh49atzd3c3x48cd5te/f3+TkpJijLkYACWZ3Nzca9Y5ZcoUc8cddziMNX/+fNO0aVN7APrTn/5kOnTocM39DB482PTr1++afS534sQJI8ns2bPHGPOf9/O1116z9/n888+NJLN37177GD/72c8c9pOYmHjNANi6dWvzhz/8wf76/Pnzpl27dg4BsKZzu/xYG2PMbbfdZpYvX+7Q9sILL5ioqKhq933lv6sLFy6YJk2amMcee8zeVlBQYCSZrKysavczevRo8/DDDxtjjPnmm2+MJLNp06Yq+156T7Zs2WKaN29uXn75ZYf1oaGhZsaMGdWOBaB2cQkYqOd69Ojh8Lp169YqLi6+of0EBgaqcePGuvXWWx3artxv3759ZbPZ7K+joqJ08OBBVVRUaM+ePaqoqNDtt99u/8xb06ZNtXnzZodLl56enlfVcKW9e/cqKirKYax+/frp7Nmz+te//lXjGnNzc9W/f/9q1x88eFCDBw/WrbfeKl9fX/ul5CsvS18+39atW0uS/b3Zu3evIiMjHfpHRUVVO2ZJSYkKCgoctvHw8FDv3r1/1NwuV1ZWpkOHDmnEiBEOx+DFF190OAZVubxGd3d3tWzZUqGhofa2wMBAh7olaf78+QoPD9ctt9yipk2batGiRfb5tWjRQo8//rji4uL04IMPas6cOSooKHAYMz8/X/fee6+mT5+uiRMnOqwbN26cXnzxRfXr10+pqan67LPPrjl/ADeGAAjUc40aNXJ4bbPZVFlZKUn2mynMZZ8nO3/+/A/ux2azXXO/NXH27Fm5u7srJydHubm59mXv3r0Onw3z8fFxCHbO5OPjc831Dz74oE6dOqXFixdr+/bt2r59uyTp3LlzDv2ufK8kXdd782PUdG6XO3v2rCRp8eLFDscgLy9P27Ztu+Z4VR3/a9W9YsUKPf300xoxYoTWr1+v3NxcDR8+3GF+S5YsUVZWlqKjo7Vy5UrdfvvtDvO45ZZbFBERob/97W8qLS11GP/Xv/61Dh8+rMcee0x79uxR7969NXfu3GvWAODHIwACLuyWW26RJIczLbX5mJBLIeSSbdu2qXPnznJ3d1evXr1UUVGh4uJiderUyWEJCgq6rnG6du2qrKwshyC7ZcsWNWvWTO3atavxfnr06FHt41e++eYb7d+/X1OnTlX//v3VtWtX+80h1zvXqt6X6vj5+al169YO21y4cEE5OTnXNTdPT09JF2/GuCQwMFBt2rTR4cOHrzoGl24aqS1btmxRdHS0Ro0apV69eqlTp05VnmXs1auXUlJStHXrVnXv3l3Lly+3r/Px8dGaNWvk7e2tuLg4nTlzxmHb4OBgjRw5Uu+8844mTpyoxYsX12oNAP6DAAi4MB8fH/Xt21czZ87U3r17tXnzZk2dOrXW9p+fn6/k5GTt379ff/vb3zR37lwlJSVJkm6//XYNGTJEQ4cO1TvvvKMjR44oOztbaWlpWrt27XWNM2rUKB07dkxjx47Vvn379N577yk1NVXJycnX9ciYlJQU7dixQ6NGjdJnn32mffv2acGCBTp58qSaN2+uli1batGiRfryyy/10UcfKTk5+brmKV28VJmRkaGXX35ZBw8e1Lx585SRkXHNbZKSkjRz5kylp6dr3759GjVqlE6fPm1fX5O5tWrVSj4+PsrIyFBRUZFKSkokSc8//7zS0tL06quv6sCBA9qzZ4+WLFmiWbNmXXdt19K5c2ft3LlTH3zwgQ4cOKBp06Zpx44d9vVHjhxRSkqKsrKydPToUa1fv14HDx5U165dHfbTpEkTrV27Vh4eHrr//vvtZzHHjx+vDz74QEeOHNGuXbu0cePGq7YFUHsIgICLe/3113XhwgWFh4dr/PjxevHFF2tt30OHDtV3332niIgIjR49WklJSXriiSfs65csWaKhQ4dq4sSJuuOOO5SQkKAdO3aoffv21zVO27ZttW7dOmVnZyssLEwjR47UiBEjrjvM3n777Vq/fr0+/fRTRUREKCoqSu+99548PDzk5uamFStWKCcnR927d9eECRP0xz/+8br2L138XOTixYs1Z84chYWFaf369T84z4kTJ+qxxx7TsGHDFBUVpWbNmmnQoEH29TWZm4eHh1599VX97//+r9q0aaOHHnpI0sVLp6+99pqWLFmi0NBQxcTEaOnSpbV+BvDJJ5/Uz3/+cyUmJioyMlLffPONRo0aZV/fuHFj7du3Tw8//LBuv/12PfHEExo9erSefPLJq/bVtGlTvf/++zLGKD4+XmVlZaqoqNDo0aPVtWtXDRgwQLfffvsPPs4GwI9nM+aKh1EBAACgQeMMIAAAgMUQAAEAACyGAAgAAGAxBEAAAACLIQACAABYDAEQAADAYgiAAAAAFkMABAAAsBgCIAAAgMUQAAEAACyGAAgAAGAxBEAAAACL+f8THfKzmukKHwAAAABJRU5ErkJggg==",
- "text/html": [
- "\n",
- " \n",
- "
\n",
- " Figure\n",
- "
\n",
- "

\n",
- "
\n",
- " "
- ],
- "text/plain": [
- "Canvas(toolbar=Toolbar(toolitems=[('Home', 'Reset original view', 'home', 'home'), ('Back', 'Back to previous …"
- ]
- },
- "metadata": {},
- "output_type": "display_data"
- }
- ],
- "source": [
- "max_amount = max(candidate_amounts)\n",
- "fig = plt.subplots()\n",
- "plt.hist(candidate_amounts, range=(1, max_amount), align=\"left\", density=True, bins=range(1, max_amount))#, bins=list(range(20)) + list(range(20, 100, 5)) + list(range(100, max(candidate_amounts), 10)))\n",
- "plt.xlabel(\"number of candidate masks\")\n",
- "plt.ylabel(\"proportion\")\n",
- "plt.show()"
- ]
- },
- {
- "cell_type": "code",
- "execution_count": null,
- "id": "b323aec4-e6d6-4722-b677-1ed1b04a5b02",
- "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
-}
diff --git a/analysis/countermeasures/simulation.ipynb b/analysis/countermeasures/simulation.ipynb
new file mode 100644
index 0000000..1d1a8d5
--- /dev/null
+++ b/analysis/countermeasures/simulation.ipynb
@@ -0,0 +1,1910 @@
+{
+ "cells": [
+ {
+ "cell_type": "markdown",
+ "id": "bafc2f4e-05a3-4120-bcd6-5d1f5fb91cd9",
+ "metadata": {},
+ "source": [
+ "# Distinguishing countermeasures by output"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 1,
+ "id": "33ee6084-2ac3-4f95-9610-0fbc06026538",
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "import io\n",
+ "import math\n",
+ "import random\n",
+ "import itertools\n",
+ "import warnings\n",
+ "\n",
+ "import cypari2\n",
+ "from cysignals.alarm import alarm, AlarmInterrupt\n",
+ "\n",
+ "from matplotlib import pyplot as plt\n",
+ "from collections import Counter\n",
+ "from tqdm.auto import tqdm, trange\n",
+ "\n",
+ "from pyecsca.misc.utils import TaskExecutor\n",
+ "from pyecsca.ec.mod import mod, RandomModAction\n",
+ "from pyecsca.ec.point import Point\n",
+ "from pyecsca.ec.model import ShortWeierstrassModel\n",
+ "from pyecsca.ec.params import load_params_ectester, get_params\n",
+ "from pyecsca.ec.mult import LTRMultiplier, RTLMultiplier, ScalarMultiplicationAction\n",
+ "from pyecsca.ec.context import local, DefaultContext\n",
+ "from pyecsca.ec.countermeasures import GroupScalarRandomization, AdditiveSplitting, MultiplicativeSplitting, EuclideanSplitting, BrumleyTuveri\n",
+ "\n",
+ "%matplotlib ipympl"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 2,
+ "id": "b1b9596c-1eba-4ace-af84-8cb279d84cc2",
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "model = ShortWeierstrassModel()\n",
+ "coords = model.coordinates[\"projective\"]"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 3,
+ "id": "b0afb195-8390-44c5-931e-75a70ccd4e9e",
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "add = coords.formulas[\"add-2007-bl\"]\n",
+ "dbl = coords.formulas[\"dbl-2007-bl\"]\n",
+ "ltr = LTRMultiplier(add, dbl, complete=False)\n",
+ "rtl = RTLMultiplier(add, dbl, complete=False)\n",
+ "mult = ltr"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 4,
+ "id": "52c877e1-5021-4ec2-9daa-dd20bec6bcb2",
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "gsr = GroupScalarRandomization(mult)\n",
+ "asplit = AdditiveSplitting(mult)\n",
+ "msplit = MultiplicativeSplitting(mult)\n",
+ "esplit = EuclideanSplitting(mult)\n",
+ "bt = BrumleyTuveri(mult)"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "id": "27626337-dcbc-497c-a54e-02d50e2b8f34",
+ "metadata": {},
+ "source": [
+ "## 3n test"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 5,
+ "id": "c3088419-161b-4193-a1b6-6f623f217fcd",
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "key3n = 0x20959f2b437de1e522baf6d814911938157390d3ea5118660b852ab0d5387006\n",
+ "params3n = load_params_ectester(io.BytesIO(b\"0xc381bb0394f34b5ed061c9107b66974f4d0a8ec89b9fe73b98b6d1368c7d974d,0x5ca6c5ee0a10097af291a8f125303fb1a3e35e8100411902245d691e0e5cb497,0x385a5a8bb8af94721f6fd10b562606d9b9df931f7fd966e96859bb9bd7c05836,0x4616af1898b92cac0f902a9daee24bbae63571cead270467c6a7886ced421f5e,0x34e896bdb1337e0ae5960fa3389fb59c2c8d6c7dbfd9aac33a844f8f98e433ef,0x412b3e5686fbc3ca4575edb0292232702ae721a7d4a230cc170a5561aa70e00f,0x01\"), \"projective\")\n",
+ "bits3n = params3n.full_order.bit_length()\n",
+ "point3n = Point(X=mod(0x4a48addb2e471767b7cd0f6f1d4c27fe46f4a828fc20f950bd1f72c939b36a84, params3n.curve.prime),\n",
+ " Y=mod(0x13384d38c353f862832c0f067e46a3e510bb6803c20745dfb31929f4a18d890d, params3n.curve.prime),\n",
+ " Z=mod(1, params3n.curve.prime), model=coords)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 6,
+ "id": "a8dde7e6-cd48-4f99-9677-23a19e4c2e5b",
+ "metadata": {},
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "prime:\t0xc381bb0394f34b5ed061c9107b66974f4d0a8ec89b9fe73b98b6d1368c7d974d\n",
+ "a:\t0x5ca6c5ee0a10097af291a8f125303fb1a3e35e8100411902245d691e0e5cb497\n",
+ "b:\t0x385a5a8bb8af94721f6fd10b562606d9b9df931f7fd966e96859bb9bd7c05836\n",
+ "G:\t[0x4616af1898b92cac0f902a9daee24bbae63571cead270467c6a7886ced421f5e,\n",
+ "\t 0x34e896bdb1337e0ae5960fa3389fb59c2c8d6c7dbfd9aac33a844f8f98e433ef]\n",
+ "n:\t0x412b3e5686fbc3ca4575edb0292232702ae721a7d4a230cc170a5561aa70e00f\n",
+ "3n:\t0xc381bb0394f34b5ed061c9107b66975080b564f77de69264451f0024ff52a02d\n",
+ "\n",
+ "P:\t[0x4a48addb2e471767b7cd0f6f1d4c27fe46f4a828fc20f950bd1f72c939b36a84,\n",
+ "\t 0x13384d38c353f862832c0f067e46a3e510bb6803c20745dfb31929f4a18d890d]\n"
+ ]
+ }
+ ],
+ "source": [
+ "print(f\"prime:\\t0x{params3n.curve.prime:x}\")\n",
+ "print(f\"a:\\t0x{params3n.curve.parameters['a']:x}\")\n",
+ "print(f\"b:\\t0x{params3n.curve.parameters['b']:x}\")\n",
+ "print(f\"G:\\t[0x{params3n.generator.X:x},\\n\\t 0x{params3n.generator.Y:x}]\")\n",
+ "print(f\"n:\\t0x{params3n.order:x}\")\n",
+ "print(f\"3n:\\t0x{3 * params3n.order:x}\")\n",
+ "print(f\"\\nP:\\t[0x{point3n.X:x},\\n\\t 0x{point3n.Y:x}]\")"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 7,
+ "id": "cd6f8500-7509-45b0-8b23-471ee5014f42",
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "def generate_scalars_mod3(rem, samples):\n",
+ " scalars = []\n",
+ " while True:\n",
+ " scalar = random.randint(0, params3n.full_order)\n",
+ " if scalar % 3 == rem:\n",
+ " scalars.append(scalar)\n",
+ " if len(scalars) == samples:\n",
+ " break\n",
+ " return scalars\n",
+ "\n",
+ "def test_3n(countermeasure, scalars):\n",
+ " ctr = Counter()\n",
+ " for k in tqdm(scalars, leave=False):\n",
+ " mult.init(params3n, point3n)\n",
+ " kP = mult.multiply(k).to_affine()\n",
+ " mult.init(params3n, point3n)\n",
+ " knP = mult.multiply(k + params3n.full_order).to_affine()\n",
+ " mult.init(params3n, point3n)\n",
+ " k2nP = mult.multiply(k + 2 * params3n.full_order).to_affine()\n",
+ "\n",
+ " countermeasure.init(params3n, point3n)\n",
+ " res = countermeasure.multiply(k)\n",
+ " aff = res.to_affine()\n",
+ " if aff.equals(kP):\n",
+ " ctr[\"k\"] += 1\n",
+ " elif aff.equals(knP):\n",
+ " ctr[\"k + 1n\"] += 1\n",
+ " elif aff.equals(k2nP):\n",
+ " ctr[\"k + 2n\"] += 1\n",
+ " else:\n",
+ " ctr[aff] += 1\n",
+ " for name, count in sorted(ctr.items()):\n",
+ " print(f\"{name}:\\t{count}\")\n",
+ "\n",
+ "def test_3n_fixed_scalar(countermeasure, samples):\n",
+ " test_3n(countermeasure, [key3n for _ in range(samples)])\n",
+ "\n",
+ "def test_3n_random_scalar(countermeasure, samples):\n",
+ " test_3n(countermeasure, [random.randint(0, params3n.full_order) for _ in range(samples)])\n",
+ "\n",
+ "def test_3n_random_scalar_projected(countermeasure, samples):\n",
+ " print(\"k = 0 mod 3\")\n",
+ " test_3n(countermeasure, generate_scalars_mod3(0, samples))\n",
+ " print()\n",
+ " print(\"k = 1 mod 3\")\n",
+ " test_3n(countermeasure, generate_scalars_mod3(1, samples))\n",
+ " print()\n",
+ " print(\"k = 2 mod 3\")\n",
+ " test_3n(countermeasure, generate_scalars_mod3(2, samples))"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "id": "46b8f74a-433d-48c9-b5b9-6bb7d2731246",
+ "metadata": {},
+ "source": [
+ "### Fixed scalar experiments"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "id": "fc82d4b9-91cd-423c-83aa-89721efa1ae9",
+ "metadata": {},
+ "source": [
+ "#### Group scalar randomization"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 8,
+ "id": "86532d50-2db7-4370-b449-c545b330a852",
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "application/vnd.jupyter.widget-view+json": {
+ "model_id": "7c11b83ca4fa40eaac982481494bd7ce",
+ "version_major": 2,
+ "version_minor": 0
+ },
+ "text/plain": [
+ " 0%| | 0/1000 [00:00, ?it/s]"
+ ]
+ },
+ "metadata": {},
+ "output_type": "display_data"
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "k:\t354\n",
+ "k + 1n:\t318\n",
+ "k + 2n:\t328\n"
+ ]
+ }
+ ],
+ "source": [
+ "test_3n_fixed_scalar(gsr, 1000)"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "id": "aba3e713-6246-435d-93af-2e8b42ee9582",
+ "metadata": {},
+ "source": [
+ "#### Additive splitting"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 9,
+ "id": "ad421630-606f-4666-9bbf-1a446eec1b59",
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "application/vnd.jupyter.widget-view+json": {
+ "model_id": "4ac4f4baa0864f4ab34d422e13507754",
+ "version_major": 2,
+ "version_minor": 0
+ },
+ "text/plain": [
+ " 0%| | 0/1000 [00:00, ?it/s]"
+ ]
+ },
+ "metadata": {},
+ "output_type": "display_data"
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "k:\t508\n",
+ "k + 1n:\t492\n"
+ ]
+ }
+ ],
+ "source": [
+ "test_3n_fixed_scalar(asplit, 1000)"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "id": "a1284a11-4ace-437d-9826-2035cce36756",
+ "metadata": {},
+ "source": [
+ "#### Multiplicative splitting"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 10,
+ "id": "3ed5d7f3-0ba1-4b62-9635-aeb492499175",
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "application/vnd.jupyter.widget-view+json": {
+ "model_id": "4193d9eadc644cad957e15d9c9ca98a7",
+ "version_major": 2,
+ "version_minor": 0
+ },
+ "text/plain": [
+ " 0%| | 0/1000 [00:00, ?it/s]"
+ ]
+ },
+ "metadata": {},
+ "output_type": "display_data"
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "k:\t192\n",
+ "k + 1n:\t575\n",
+ "k + 2n:\t233\n"
+ ]
+ }
+ ],
+ "source": [
+ "test_3n_fixed_scalar(msplit, 1000)"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "id": "5e40f8e9-d26f-41e7-adbf-a0fbdb680677",
+ "metadata": {},
+ "source": [
+ "#### Euclidean splitting"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 11,
+ "id": "314447c6-a1fb-4d3a-8988-b34c8912dd5e",
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "application/vnd.jupyter.widget-view+json": {
+ "model_id": "8fce34bb47b44e17a2eaf9b20041e5db",
+ "version_major": 2,
+ "version_minor": 0
+ },
+ "text/plain": [
+ " 0%| | 0/1000 [00:00, ?it/s]"
+ ]
+ },
+ "metadata": {},
+ "output_type": "display_data"
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "k:\t1000\n"
+ ]
+ }
+ ],
+ "source": [
+ "test_3n_fixed_scalar(esplit, 1000)"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "id": "ff7185a2-3cd9-44d7-b1a9-982eaed561dc",
+ "metadata": {},
+ "source": [
+ "#### Brumley and Tuveri bit-length fixing"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 12,
+ "id": "f41dfc1d-1017-4aa0-bcd4-6569c53bf81e",
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "application/vnd.jupyter.widget-view+json": {
+ "model_id": "f6bb27fe24f7463e85b1b37848f5444d",
+ "version_major": 2,
+ "version_minor": 0
+ },
+ "text/plain": [
+ " 0%| | 0/1000 [00:00, ?it/s]"
+ ]
+ },
+ "metadata": {},
+ "output_type": "display_data"
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "k + 2n:\t1000\n"
+ ]
+ }
+ ],
+ "source": [
+ "test_3n_fixed_scalar(bt, 1000)"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "id": "28915553-b5e6-4108-bc23-e5844b6a63b8",
+ "metadata": {},
+ "source": [
+ "### Random scalar experiments"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "id": "566ddd10-2d0e-4b32-9b27-60770ab68155",
+ "metadata": {},
+ "source": [
+ "#### Group scalar randomization"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 13,
+ "id": "7255321a-6ad6-4938-8ec9-dd8d977686db",
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "application/vnd.jupyter.widget-view+json": {
+ "model_id": "0c52e094bfd84c70874bd1444cec7c18",
+ "version_major": 2,
+ "version_minor": 0
+ },
+ "text/plain": [
+ " 0%| | 0/1000 [00:00, ?it/s]"
+ ]
+ },
+ "metadata": {},
+ "output_type": "display_data"
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "k:\t331\n",
+ "k + 1n:\t339\n",
+ "k + 2n:\t330\n"
+ ]
+ }
+ ],
+ "source": [
+ "test_3n_random_scalar(gsr, 1000)"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "id": "376c0da8-b92d-4151-ac30-839ab5c0ceae",
+ "metadata": {},
+ "source": [
+ "#### Additive splitting"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 14,
+ "id": "b0146a9a-0803-43c4-ab29-8ba6e15934b5",
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "application/vnd.jupyter.widget-view+json": {
+ "model_id": "c98aabf325d14c85844ce03540166769",
+ "version_major": 2,
+ "version_minor": 0
+ },
+ "text/plain": [
+ " 0%| | 0/1000 [00:00, ?it/s]"
+ ]
+ },
+ "metadata": {},
+ "output_type": "display_data"
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "k:\t499\n",
+ "k + 1n:\t501\n"
+ ]
+ }
+ ],
+ "source": [
+ "test_3n_random_scalar(asplit, 1000)"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "id": "96823352-cd63-4cf8-8ab7-cf6e025837b9",
+ "metadata": {},
+ "source": [
+ "#### Multiplicative splitting"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 15,
+ "id": "5645ae6f-f5f4-419d-ba47-248532dc2114",
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "application/vnd.jupyter.widget-view+json": {
+ "model_id": "ad009d473f5345f89f72f5d892886672",
+ "version_major": 2,
+ "version_minor": 0
+ },
+ "text/plain": [
+ " 0%| | 0/1000 [00:00, ?it/s]"
+ ]
+ },
+ "metadata": {},
+ "output_type": "display_data"
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "k:\t313\n",
+ "k + 1n:\t352\n",
+ "k + 2n:\t335\n"
+ ]
+ }
+ ],
+ "source": [
+ "test_3n_random_scalar(msplit, 1000)"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "id": "1784d763-932a-4f66-a1da-d7ef51cbc88a",
+ "metadata": {},
+ "source": [
+ "#### Euclidean splitting"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 16,
+ "id": "c9fc4f35-1c25-4cac-bb63-8bd70263db47",
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "application/vnd.jupyter.widget-view+json": {
+ "model_id": "59c26f78ce4d48e6b0f48c56cb2a1957",
+ "version_major": 2,
+ "version_minor": 0
+ },
+ "text/plain": [
+ " 0%| | 0/1000 [00:00, ?it/s]"
+ ]
+ },
+ "metadata": {},
+ "output_type": "display_data"
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "k:\t1000\n"
+ ]
+ }
+ ],
+ "source": [
+ "test_3n_random_scalar(esplit, 1000)"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "id": "8917dfd5-1548-414b-846a-685857bfb427",
+ "metadata": {},
+ "source": [
+ "#### Brumley and Tuveri bit-length fixing"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 17,
+ "id": "4fd6b288-08a9-4dbe-9145-e96401805315",
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "application/vnd.jupyter.widget-view+json": {
+ "model_id": "0a9b4d4abf5544658185577fb6a6d7c8",
+ "version_major": 2,
+ "version_minor": 0
+ },
+ "text/plain": [
+ " 0%| | 0/1000 [00:00, ?it/s]"
+ ]
+ },
+ "metadata": {},
+ "output_type": "display_data"
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "k + 1n:\t28\n",
+ "k + 2n:\t972\n"
+ ]
+ }
+ ],
+ "source": [
+ "test_3n_random_scalar(bt, 1000)"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "id": "ee9e23f6-edd9-4fc2-9e7c-b5c176991071",
+ "metadata": {},
+ "source": [
+ "### Random scalar experiments projected to scalar divisor classes mod 3"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "id": "e17fcb12-1e02-4bcf-a2b7-785c16c03028",
+ "metadata": {},
+ "source": [
+ "#### Group scalar randomization"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 18,
+ "id": "6c46fdbb-2ffb-4169-8e00-6d93b8407ee5",
+ "metadata": {},
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "k = 0 mod 3\n"
+ ]
+ },
+ {
+ "data": {
+ "application/vnd.jupyter.widget-view+json": {
+ "model_id": "d99eea3415564fac926c237689f65b3c",
+ "version_major": 2,
+ "version_minor": 0
+ },
+ "text/plain": [
+ " 0%| | 0/1000 [00:00, ?it/s]"
+ ]
+ },
+ "metadata": {},
+ "output_type": "display_data"
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "k:\t312\n",
+ "k + 1n:\t357\n",
+ "k + 2n:\t331\n",
+ "\n",
+ "k = 1 mod 3\n"
+ ]
+ },
+ {
+ "data": {
+ "application/vnd.jupyter.widget-view+json": {
+ "model_id": "9d75e1bf8df240bf9c19d3885d253186",
+ "version_major": 2,
+ "version_minor": 0
+ },
+ "text/plain": [
+ " 0%| | 0/1000 [00:00, ?it/s]"
+ ]
+ },
+ "metadata": {},
+ "output_type": "display_data"
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "k:\t291\n",
+ "k + 1n:\t358\n",
+ "k + 2n:\t351\n",
+ "\n",
+ "k = 2 mod 3\n"
+ ]
+ },
+ {
+ "data": {
+ "application/vnd.jupyter.widget-view+json": {
+ "model_id": "d43f5b16d2d444cda559bf18976a2e2a",
+ "version_major": 2,
+ "version_minor": 0
+ },
+ "text/plain": [
+ " 0%| | 0/1000 [00:00, ?it/s]"
+ ]
+ },
+ "metadata": {},
+ "output_type": "display_data"
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "k:\t342\n",
+ "k + 1n:\t338\n",
+ "k + 2n:\t320\n"
+ ]
+ }
+ ],
+ "source": [
+ "test_3n_random_scalar_projected(gsr, 1000)"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "id": "b9d635c8-f788-4700-876b-ac48e89557a7",
+ "metadata": {},
+ "source": [
+ "#### Additive splitting"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 19,
+ "id": "344a4f90-3470-40e9-a75f-b925a88c2480",
+ "metadata": {},
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "k = 0 mod 3\n"
+ ]
+ },
+ {
+ "data": {
+ "application/vnd.jupyter.widget-view+json": {
+ "model_id": "e60f8fd6e60f4edc8c841a194e874a70",
+ "version_major": 2,
+ "version_minor": 0
+ },
+ "text/plain": [
+ " 0%| | 0/1000 [00:00, ?it/s]"
+ ]
+ },
+ "metadata": {},
+ "output_type": "display_data"
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "k:\t500\n",
+ "k + 1n:\t500\n",
+ "\n",
+ "k = 1 mod 3\n"
+ ]
+ },
+ {
+ "data": {
+ "application/vnd.jupyter.widget-view+json": {
+ "model_id": "f08cebf9ab274dad8164b57f18417627",
+ "version_major": 2,
+ "version_minor": 0
+ },
+ "text/plain": [
+ " 0%| | 0/1000 [00:00, ?it/s]"
+ ]
+ },
+ "metadata": {},
+ "output_type": "display_data"
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "k:\t528\n",
+ "k + 1n:\t472\n",
+ "\n",
+ "k = 2 mod 3\n"
+ ]
+ },
+ {
+ "data": {
+ "application/vnd.jupyter.widget-view+json": {
+ "model_id": "772c89d8a3a048f5934cb451f0b12be3",
+ "version_major": 2,
+ "version_minor": 0
+ },
+ "text/plain": [
+ " 0%| | 0/1000 [00:00, ?it/s]"
+ ]
+ },
+ "metadata": {},
+ "output_type": "display_data"
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "k:\t531\n",
+ "k + 1n:\t469\n"
+ ]
+ }
+ ],
+ "source": [
+ "test_3n_random_scalar_projected(asplit, 1000)"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "id": "78aaf83f-a689-40ad-ae88-58ab20e5e6f9",
+ "metadata": {},
+ "source": [
+ "#### Multiplicative splitting"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 20,
+ "id": "616a7726-01e6-4e9c-b7f2-fe8f14b60071",
+ "metadata": {},
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "k = 0 mod 3\n"
+ ]
+ },
+ {
+ "data": {
+ "application/vnd.jupyter.widget-view+json": {
+ "model_id": "0dfabf99286f48c9b2015742783669b9",
+ "version_major": 2,
+ "version_minor": 0
+ },
+ "text/plain": [
+ " 0%| | 0/1000 [00:00, ?it/s]"
+ ]
+ },
+ "metadata": {},
+ "output_type": "display_data"
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "k:\t571\n",
+ "k + 1n:\t190\n",
+ "k + 2n:\t239\n",
+ "\n",
+ "k = 1 mod 3\n"
+ ]
+ },
+ {
+ "data": {
+ "application/vnd.jupyter.widget-view+json": {
+ "model_id": "d310342f047747a097f635e63540c42a",
+ "version_major": 2,
+ "version_minor": 0
+ },
+ "text/plain": [
+ " 0%| | 0/1000 [00:00, ?it/s]"
+ ]
+ },
+ "metadata": {},
+ "output_type": "display_data"
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "k:\t217\n",
+ "k + 1n:\t232\n",
+ "k + 2n:\t551\n",
+ "\n",
+ "k = 2 mod 3\n"
+ ]
+ },
+ {
+ "data": {
+ "application/vnd.jupyter.widget-view+json": {
+ "model_id": "5581e145df664b6c87957f1791aea1b3",
+ "version_major": 2,
+ "version_minor": 0
+ },
+ "text/plain": [
+ " 0%| | 0/1000 [00:00, ?it/s]"
+ ]
+ },
+ "metadata": {},
+ "output_type": "display_data"
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "k:\t209\n",
+ "k + 1n:\t546\n",
+ "k + 2n:\t245\n"
+ ]
+ }
+ ],
+ "source": [
+ "test_3n_random_scalar_projected(msplit, 1000)"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "id": "018c8f31-d7c3-497b-bdaf-580c6465753f",
+ "metadata": {},
+ "source": [
+ "#### Euclidean splitting"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 21,
+ "id": "adced4e4-37a7-43ed-97b5-01cb5d274d6b",
+ "metadata": {},
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "k = 0 mod 3\n"
+ ]
+ },
+ {
+ "data": {
+ "application/vnd.jupyter.widget-view+json": {
+ "model_id": "29f009a782ee4dd4bff9938d655db831",
+ "version_major": 2,
+ "version_minor": 0
+ },
+ "text/plain": [
+ " 0%| | 0/1000 [00:00, ?it/s]"
+ ]
+ },
+ "metadata": {},
+ "output_type": "display_data"
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "k:\t1000\n",
+ "\n",
+ "k = 1 mod 3\n"
+ ]
+ },
+ {
+ "data": {
+ "application/vnd.jupyter.widget-view+json": {
+ "model_id": "f2d438308994479b8e1086621b24466e",
+ "version_major": 2,
+ "version_minor": 0
+ },
+ "text/plain": [
+ " 0%| | 0/1000 [00:00, ?it/s]"
+ ]
+ },
+ "metadata": {},
+ "output_type": "display_data"
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "k:\t1000\n",
+ "\n",
+ "k = 2 mod 3\n"
+ ]
+ },
+ {
+ "data": {
+ "application/vnd.jupyter.widget-view+json": {
+ "model_id": "00f137d1135741ada0978bd00c9ff194",
+ "version_major": 2,
+ "version_minor": 0
+ },
+ "text/plain": [
+ " 0%| | 0/1000 [00:00, ?it/s]"
+ ]
+ },
+ "metadata": {},
+ "output_type": "display_data"
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "k:\t1000\n"
+ ]
+ }
+ ],
+ "source": [
+ "test_3n_random_scalar_projected(esplit, 1000)"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "id": "8d7b0a42-7be7-464d-932d-8386ad912034",
+ "metadata": {},
+ "source": [
+ "#### Brumley and Tuveri bit-length fixing"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 22,
+ "id": "fe8d8295-3e69-4b60-b8c3-5710deaeb0b3",
+ "metadata": {},
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "k = 0 mod 3\n"
+ ]
+ },
+ {
+ "data": {
+ "application/vnd.jupyter.widget-view+json": {
+ "model_id": "4448b9a556cc4acd8d31e60277e09488",
+ "version_major": 2,
+ "version_minor": 0
+ },
+ "text/plain": [
+ " 0%| | 0/1000 [00:00, ?it/s]"
+ ]
+ },
+ "metadata": {},
+ "output_type": "display_data"
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "k + 1n:\t35\n",
+ "k + 2n:\t965\n",
+ "\n",
+ "k = 1 mod 3\n"
+ ]
+ },
+ {
+ "data": {
+ "application/vnd.jupyter.widget-view+json": {
+ "model_id": "1dbe7fc3fbbf4f92a889ca37b66a27b3",
+ "version_major": 2,
+ "version_minor": 0
+ },
+ "text/plain": [
+ " 0%| | 0/1000 [00:00, ?it/s]"
+ ]
+ },
+ "metadata": {},
+ "output_type": "display_data"
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "k + 1n:\t36\n",
+ "k + 2n:\t964\n",
+ "\n",
+ "k = 2 mod 3\n"
+ ]
+ },
+ {
+ "data": {
+ "application/vnd.jupyter.widget-view+json": {
+ "model_id": "56b3afd278b8491e80dabc3b1d676631",
+ "version_major": 2,
+ "version_minor": 0
+ },
+ "text/plain": [
+ " 0%| | 0/1000 [00:00, ?it/s]"
+ ]
+ },
+ "metadata": {},
+ "output_type": "display_data"
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "k + 1n:\t37\n",
+ "k + 2n:\t963\n"
+ ]
+ }
+ ],
+ "source": [
+ "test_3n_random_scalar_projected(bt, 1000)"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "id": "43b309af-5683-4384-9623-d7633723177c",
+ "metadata": {},
+ "source": [
+ "## Mask recovery ($n + \\epsilon$ test)\n",
+ "Using a composite order curve we can recover the size and the actual mask values (in a known key scenario) in both GSR and multiplicative splitting. However, real-world targets do not like composite order curves and may either check the order or otherwise fail to compute on such curves. Thus, we lie to them and set the order to the next-prime of the true order, in this case $n + 92$."
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 23,
+ "id": "20a26f27-620d-4d7f-92bd-b949482b5c9a",
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "pari = cypari2.Pari(256_000_000, 2_000_000_000)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 24,
+ "id": "144340bd-5372-4beb-a46e-fd60c596b254",
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "real_n = 0xa9fa3419aca88bade2cba14e317816c6828910c6ce04fcd2a2e857d25df50775\n",
+ "# = 2898786277 * 2916913393 * 3067509271 * 3248233993 * 3894099889 * 4099407227 * 4101666977 * 13936975277\n",
+ "real_n_facts = pari.factor(real_n)\n",
+ "params92pn = load_params_ectester(io.BytesIO(b\"0xa9fa3419aca88bade2cba14e317816c79d52481d463dc9bcb12c37f45aa3b4e1,0x2ea3bfe6659f8e035735349b91fbfa2baf0cf8e640315f0fe03c1136813dec99,0x2b07c518e04b02158651e3dbbef7720015dd496bf15af02f8439f8e1503b8370,0x90fb04b1af19e8e20396ac052f260a9fb5f736b97e3cd4af08fe81a1e75dac6d,0x2302bcf700d3d5899f04d0c7441f5017c9758bfafd6ce15dbe36fb4eea76baec,0xa9fa3419aca88bade2cba14e317816c6828910c6ce04fcd2a2e857d25df507d1,0x01\"), \"projective\")\n",
+ "e = pari.ellinit([int(params92pn.curve.parameters[\"a\"]), int(params92pn.curve.parameters[\"b\"])], int(params92pn.curve.prime))\n",
+ "e[15][0] = real_n"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 25,
+ "id": "f103129c-17d3-4217-999b-94ecb4ec523d",
+ "metadata": {},
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "prime:\t0xa9fa3419aca88bade2cba14e317816c79d52481d463dc9bcb12c37f45aa3b4e1\n",
+ "a:\t0x2ea3bfe6659f8e035735349b91fbfa2baf0cf8e640315f0fe03c1136813dec99\n",
+ "b:\t0x2b07c518e04b02158651e3dbbef7720015dd496bf15af02f8439f8e1503b8370\n",
+ "G:\t[0x90fb04b1af19e8e20396ac052f260a9fb5f736b97e3cd4af08fe81a1e75dac6d,\n",
+ "\t 0x2302bcf700d3d5899f04d0c7441f5017c9758bfafd6ce15dbe36fb4eea76baec]\n",
+ "n+92:\t0xa9fa3419aca88bade2cba14e317816c6828910c6ce04fcd2a2e857d25df507d1 (fake order, given to the target, prime)\n",
+ "n:\t0xa9fa3419aca88bade2cba14e317816c6828910c6ce04fcd2a2e857d25df50775 (real order, composite)\n"
+ ]
+ }
+ ],
+ "source": [
+ "print(f\"prime:\\t0x{params92pn.curve.prime:x}\")\n",
+ "print(f\"a:\\t0x{params92pn.curve.parameters['a']:x}\")\n",
+ "print(f\"b:\\t0x{params92pn.curve.parameters['b']:x}\")\n",
+ "print(f\"G:\\t[0x{params92pn.generator.X:x},\\n\\t 0x{params92pn.generator.Y:x}]\")\n",
+ "print(f\"n+92:\\t0x{params92pn.order:x} (fake order, given to the target, prime)\")\n",
+ "print(f\"n:\\t0x{real_n:x} (real order, composite)\")"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "id": "322d2e68-5259-4ea6-9748-2b0aa21b557f",
+ "metadata": {},
+ "source": [
+ "### Group scalar randomization\n",
+ "In GSR getting the mask out this way is quite simple. The target believes it is operating on a curve of order $n+92$ so it will use that value multiplied with the mask to randomize the scalar. Thus as a result we get:\n",
+ "$$ P = [k + r(n + 92)]G $$\n",
+ "\n",
+ "However, the curve is truly of order $n$, thus arithmetic on its group will make this equal to: \n",
+ "$$ P = [k + r 92]G $$\n",
+ "\n",
+ "Since this is a composite order curve, we can solve the dlog and obtain $k + r 92$ and since we assume we know $k$ we can easily compute both the mask size and mask value $r$."
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 26,
+ "id": "08d99bd5-2b87-4a04-995d-7a87f9b67102",
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "key = 0x20959f2b437de1e522baf6d814911938157390d3ea5118660b852ab0d5387006 # any key works ofc\n",
+ "gsr.init(params92pn, params92pn.generator)\n",
+ "res = gsr.multiply(key)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 27,
+ "id": "2a869bed-8e21-46af-8f70-065f4afd6a82",
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "affine_gen = params92pn.generator.to_affine()\n",
+ "affine_res = res.to_affine()"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 28,
+ "id": "e440399a-bc01-488b-8822-08cc0bf1672d",
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "dlog = pari.elllog(e,\n",
+ " [int(affine_res.x), int(affine_res.y)],\n",
+ " [int(affine_gen.x), int(affine_gen.y)],\n",
+ " real_n)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 29,
+ "id": "7ea6d6ae-a6f5-4b53-8c40-787d79970cb6",
+ "metadata": {},
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "2799400670\n",
+ "32\n"
+ ]
+ }
+ ],
+ "source": [
+ "mask = int((dlog - key) / 92)\n",
+ "mask_len = mask.bit_length()\n",
+ "print(mask)\n",
+ "print(mask_len)"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "id": "d40ec035-0656-4eda-8ef4-c14f9d53f49f",
+ "metadata": {},
+ "source": [
+ "### Multiplicative splitting\n",
+ "In multiplicative splitting the situation is a bit more complicated. Doing the same computation, where the target thinks the curve order is $n+92$ leads to:\n",
+ "$$ P = [k r^{-1}\\pmod{n+92}][r \\mod n]G $$\n",
+ "\n",
+ "Since the curve is composite order we can easily compute the dlog $d$ of P to G, we get:\n",
+ "$$ d = (k r^{-1})\\pmod{n+92}\\: r = k + t (n + 92) $$\n",
+ "\n",
+ "However, the dlog is computed $\\mod n$ so we really get: $ d = k + t 92$. We extract the $t$ out of this.\n",
+ "Note that $t$ will have roughly the same size as the mask $r$, since at the left side we have $(k r^{-1}) {\\mod (n+92)}$\n",
+ "of size $n$ and $r$ of size of the mask and on the right size we have $t n$ that dominates.\n",
+ "Thus at this point we have recovered the mask size.\n",
+ "However, $t$ is always smaller than $r$, sometimes also in bitsize.\n",
+ "\n",
+ "Now that we have $s$ we can go back to the original equation and get:\n",
+ "$$ (k r^{-1})\\pmod{n+92}\\: r = k + t (n + 92) $$\n",
+ "\n",
+ "We can then factor this value, lets call it $full$, and look for divisors that are larger than $t$ but smaller than the mask length\n",
+ "that we recovered before. There may be multiple candidates here and we don't know how to distinguish between\n",
+ "them. It holds for all of the candidates $c$ that the rest of the value $full$ is equal to the inverse of $c \\mod (n+92)$.\n",
+ "However, sometimes there is only one candidate, which is equal to the true mask value $r$."
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 30,
+ "id": "b5f398fc-90d7-455e-97bd-62b682d55961",
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "def divisors(primes, powers):\n",
+ " for comb in itertools.product(*[range(power+1) for power in powers]):\n",
+ " value = 1\n",
+ " for prime, power in zip(primes, comb):\n",
+ " value *= prime**power\n",
+ " yield value\n",
+ "\n",
+ "def pari_factor(number, flag=1+8, duration=5*60):\n",
+ " # Use the 1 + 8 option to factorint to skip some costly factorization methods, we don't need the huge factors.\n",
+ " # This means that some factors may remain, which in turn means that sometimes we may not find the true mask.\n",
+ " pari = cypari2.Pari(256_000_000, 2_000_000_000)\n",
+ " with warnings.catch_warnings(category=RuntimeWarning):\n",
+ " warnings.simplefilter(\"ignore\")\n",
+ " try:\n",
+ " alarm(duration)\n",
+ " factors = pari.factorint(number, flag)\n",
+ " except AlarmInterrupt:\n",
+ " return None\n",
+ " primes = list(map(int, factors[0]))\n",
+ " powers = list(map(int, factors[1]))\n",
+ " return primes, powers\n",
+ "\n",
+ "def pari_dlog(params, P, G, real_n, facts_str):\n",
+ " pari = cypari2.Pari(256_000_000, 2_000_000_000)\n",
+ " e = pari.ellinit([int(params.curve.parameters[\"a\"]), int(params.curve.parameters[\"b\"])], int(params.curve.prime))\n",
+ " e[15][0] = real_n\n",
+ " facts = pari(facts_str)\n",
+ " dlog = pari.elllog(e, P, G, facts)\n",
+ " return int(dlog)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 31,
+ "id": "5f03e586-33df-4525-a722-f5f63d6ca28d",
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "application/vnd.jupyter.widget-view+json": {
+ "model_id": "28ab3630b5084b6aa80ae732f85fd8c9",
+ "version_major": 2,
+ "version_minor": 0
+ },
+ "text/plain": [
+ "Collecting scalarmults: 0%| | 0/1000 [00:00, ?it/s]"
+ ]
+ },
+ "metadata": {},
+ "output_type": "display_data"
+ },
+ {
+ "data": {
+ "application/vnd.jupyter.widget-view+json": {
+ "model_id": "b79a4b8ae44c494e81087a5c0e413ec9",
+ "version_major": 2,
+ "version_minor": 0
+ },
+ "text/plain": [
+ "Computing dlogs: 0%| | 0/1000 [00:00, ?it/s]"
+ ]
+ },
+ "metadata": {},
+ "output_type": "display_data"
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "32 True\n"
+ ]
+ }
+ ],
+ "source": [
+ "key = 0x20959f2b437de1e522baf6d814911938157390d3ea5118660b852ab0d5387006 # any key works\n",
+ "msplit = MultiplicativeSplitting(mult, rand_bits=32) # change the mask size here to your liking\n",
+ "tries = 1000\n",
+ "num_workers = 30\n",
+ "\n",
+ "blens = [None for _ in range(tries)]\n",
+ "dlogs = [None for _ in range(tries)]\n",
+ "ts = [None for _ in range(tries)]\n",
+ "\n",
+ "results = [None for _ in range(tries)]\n",
+ "rs = [None for _ in range(tries)]\n",
+ "\n",
+ "with TaskExecutor(max_workers=num_workers) as pool:\n",
+ " for i in trange(tries, desc=\"Collecting scalarmults\"):\n",
+ " msplit.init(params92pn, params92pn.generator)\n",
+ " with local(DefaultContext()) as ctx:\n",
+ " res = msplit.multiply(key)\n",
+ " \n",
+ " affine_res = res.to_affine()\n",
+ " affine_gen = params92pn.generator.to_affine()\n",
+ " results[i] = affine_res\n",
+ " \n",
+ " rval = []\n",
+ " ctx.actions[0].walk(lambda action: rval.append(int(action.result)) if isinstance(action, RandomModAction) else None)\n",
+ " rs[i] = rval[0]\n",
+ " \n",
+ " pool.submit_task(i,\n",
+ " pari_dlog,\n",
+ " params92pn,\n",
+ " [int(affine_res.x), int(affine_res.y)],\n",
+ " [int(affine_gen.x), int(affine_gen.y)],\n",
+ " real_n,\n",
+ " repr(real_n_facts))\n",
+ " \n",
+ " for i, future in tqdm(pool.as_completed(), desc=\"Computing dlogs\", total=len(pool.tasks)):\n",
+ " dlog = future.result()\n",
+ " val = dlog - key\n",
+ " if val % 92 != 0:\n",
+ " print(f\"Bad val! {i}\")\n",
+ " t = val // 92\n",
+ " ts[i] = t\n",
+ " dlogs[i] = dlog\n",
+ " blens[i] = t.bit_length()\n",
+ "\n",
+ "mask_len = max(blens)\n",
+ "print(mask_len, mask_len == msplit.rand_bits)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": null,
+ "id": "5fbf8a38-983d-49a6-9cac-5350f960dc3e",
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "application/vnd.jupyter.widget-view+json": {
+ "model_id": "239ea218388d4c988e39e3ec54765325",
+ "version_major": 2,
+ "version_minor": 0
+ },
+ "text/plain": [
+ "Factoring: 0%| | 0/1000 [00:00, ?it/s]"
+ ]
+ },
+ "metadata": {},
+ "output_type": "display_data"
+ }
+ ],
+ "source": [
+ "with TaskExecutor(max_workers=num_workers) as pool:\n",
+ " fulls = []\n",
+ " for t in ts:\n",
+ " full = t * (real_n + 92) + key\n",
+ " fulls.append(full)\n",
+ " pool.submit_task(t,\n",
+ " pari_factor,\n",
+ " full, flag=0)\n",
+ " facts = [None for _ in ts]\n",
+ " for t, future in tqdm(pool.as_completed(), desc=\"Factoring\", total=len(ts)):\n",
+ " result = future.result()\n",
+ " if result is None:\n",
+ " print(\"Timed out.\")\n",
+ " facts[ts.index(t)] = result"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": null,
+ "id": "0973fe4b-cdf5-4e91-850b-25375eeabb7e",
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "candidate_amounts = []\n",
+ "i = 0\n",
+ "for dlog, t, blen, r, fact, full, result in zip(dlogs, ts, blens, rs, facts, fulls, results):\n",
+ " if fact is None:\n",
+ " continue\n",
+ " \n",
+ " (primes, powers) = fact\n",
+ " complete = True\n",
+ " for prime in primes:\n",
+ " if not pari.isprime(prime):\n",
+ " complete = False\n",
+ " break\n",
+ "\n",
+ " i += 1\n",
+ " candidates = set()\n",
+ " for divisor in divisors(primes, powers):\n",
+ " if divisor.bit_length() <= mask_len and divisor >= t:\n",
+ " candidates.add(divisor)\n",
+ " candidate_amounts.append(len(candidates))\n",
+ " if len(candidates) == 1:\n",
+ " candidate = candidates.pop()\n",
+ " print(\"Only one candidate, we got the mask:\", candidate, candidate == r, \"incomplete factoring this may not be the r\" if not complete else \"\")\n",
+ "print(f\"Total recovered masks: {len(list(filter(lambda a: a == 1, candidate_amounts)))} out of {i}\")"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": null,
+ "id": "6274ff91-325f-4c6b-a4d7-d66b994d730f",
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "max_amount = max(candidate_amounts)\n",
+ "fig = plt.subplots()\n",
+ "plt.hist(candidate_amounts, range=(1, max_amount), align=\"left\", density=True, bins=range(1, max_amount))#, bins=list(range(20)) + list(range(20, 100, 5)) + list(range(100, max(candidate_amounts), 10)))\n",
+ "plt.xlabel(\"number of candidate masks\")\n",
+ "plt.ylabel(\"proportion\")\n",
+ "plt.xticks(range(max_amount))\n",
+ "plt.xlim(0, 20);\n",
+ "plt.show()"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": null,
+ "id": "9f22ca9d-bdc2-4ea5-b2bc-249a256bb8ad",
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "max_amount = max(candidate_amounts)\n",
+ "fig = plt.subplots()\n",
+ "plt.hist(candidate_amounts, range=(1, max_amount), align=\"left\", density=True, bins=range(1, max_amount))#, bins=list(range(20)) + list(range(20, 100, 5)) + list(range(100, max(candidate_amounts), 10)))\n",
+ "plt.xlabel(\"number of candidate masks\")\n",
+ "plt.ylabel(\"proportion\")\n",
+ "plt.show()"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "id": "91bbda3c-5670-49c9-85f0-99fb36a8acf9",
+ "metadata": {},
+ "source": [
+ "## $k = 10$ test"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": null,
+ "id": "92781e99-15fc-4499-a24e-5ccc20ed3707",
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "paramsk10 = get_params(\"secg\", \"secp256r1\", \"projective\")"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": null,
+ "id": "b31b2023-c0f7-47b2-8e99-b1f7f6e734b6",
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "def test_k10(countermeasure, samples, k_range = None, zero_fails = True, plot=True):\n",
+ " G = paramsk10.generator\n",
+ " Gaff = G.to_affine()\n",
+ " if k_range is None:\n",
+ " ks = list(range(2, 21))\n",
+ " else:\n",
+ " ks = list(k_range)\n",
+ " fails = []\n",
+ " for k in ks:\n",
+ " correct = 0\n",
+ " failed = 0\n",
+ " expected = paramsk10.curve.affine_multiply(Gaff, k).to_model(paramsk10.curve.coordinate_model, paramsk10.curve)\n",
+ " for _ in range(samples):\n",
+ " with local(DefaultContext()) as ctx:\n",
+ " countermeasure.init(paramsk10, paramsk10.generator)\n",
+ " res = countermeasure.multiply(k)\n",
+ " smults = set()\n",
+ " ctx.actions[0].walk(lambda action: smults.add(action.scalar) if isinstance(action, ScalarMultiplicationAction) else None)\n",
+ " if 0 in smults and zero_fails:\n",
+ " failed += 1\n",
+ " continue\n",
+ " try:\n",
+ " if res.equals_scaled(expected):\n",
+ " correct += 1\n",
+ " else:\n",
+ " failed += 1\n",
+ " except:\n",
+ " failed += 1\n",
+ " print(f\"k = {k}: failed in {failed} out of {samples}.\")\n",
+ " fails.append(failed / samples)\n",
+ " if plot:\n",
+ " fig, ax = plt.subplots()\n",
+ " xs = list(range(len(ks)))\n",
+ " ax.plot(xs, fails, label=\"Error rate\")\n",
+ " if any(k > 100 for k in ks):\n",
+ " ax.set_xticks(xs, (f\"2^{int(math.log2(k))}\" for k in ks))\n",
+ " else:\n",
+ " ax.set_xticks(xs, ks)\n",
+ " ax.set_ylim(-0.05, 1.05)\n",
+ " ax.set_xlabel(\"k\")\n",
+ " ax.set_ylabel(\"Error rate\")\n",
+ " ax.legend()\n",
+ " plt.show()\n",
+ " return fails"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "id": "37e1ce04-5487-484c-9bf1-d6a8f7076390",
+ "metadata": {},
+ "source": [
+ "### Group scalar randomization\n",
+ "\n",
+ "In GSR, the LTR simple double-and-add errors quite a lot for small scalars."
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": null,
+ "id": "d4f5298c-6277-40f4-af5d-590df6d61d6e",
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "test_k10(gsr, 100);"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "id": "fa4e3ee7-2900-4b30-9b85-066d4fa5db96",
+ "metadata": {},
+ "source": [
+ "However, the RTL double-and-add does not error at all."
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": null,
+ "id": "b4271143-5365-43b1-9767-d14feb278939",
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "test_k10(GroupScalarRandomization(rtl), 100);"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "id": "8eda1c29-f522-4c61-b445-c1c48278e88f",
+ "metadata": {},
+ "source": [
+ "### Multiplicative splitting\n",
+ "Multiplicative splitting has no reason to error out."
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": null,
+ "id": "7cd5bbf5-46e4-4d27-a803-79e35585c250",
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "test_k10(msplit, 100);"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "id": "ca68b8f2-c256-40f9-9135-961877342736",
+ "metadata": {},
+ "source": [
+ "### Euclidean splitting\n",
+ "In Euclidean splitting, it matters whether we consider the computation $[0]G$ to error or not, i.e., whether the implementation is setup to handle a zero scalar gracefully. If it is not, we get 100% of errors for small scalars."
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": null,
+ "id": "f205287f-1174-4815-bc0a-2a56ff806f11",
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "test_k10(esplit, 100);"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "id": "cab4594e-8489-4512-98f5-dc56bef3472f",
+ "metadata": {},
+ "source": [
+ "However, if it **is** setup to handle a zero scalar, we get no errors on small scalars."
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": null,
+ "id": "a6b36c65-3016-4d83-a352-3cb409319e31",
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "test_k10(esplit, 100, zero_fails=False);"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "id": "b1f68d3e-0b55-450e-a831-fa0a85fd06a1",
+ "metadata": {},
+ "source": [
+ "When we look back at the case where a zero scalar is mishandled, we see the errors drop-off when we reach the size of tha random mask."
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": null,
+ "id": "54716a04-ed6b-4ad3-b92f-2d49ddbcdd73",
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "test_k10(esplit, 100, (2**i for i in range(120, 134)));"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "id": "a0402510-6565-4a63-a72c-fef5fc0cd7f4",
+ "metadata": {},
+ "source": [
+ "In the \"no-error-on-zero\" case, we see no errors even up to and past the random mask size."
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": null,
+ "id": "187be558-c52e-4ae5-8b1e-a492e913cfb9",
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "test_k10(esplit, 100, (2**i for i in range(2, 34)), zero_fails=False);"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "id": "98ec9216-b704-4d63-a83a-322d4b1eced0",
+ "metadata": {},
+ "source": [
+ "### Additive splitting\n",
+ "Additive splitting has no reason to error out."
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": null,
+ "id": "ca9068dc-7752-482e-b56d-de69c0849a07",
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "test_k10(asplit, 100);"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "id": "867fedf2-0d95-4012-b57c-f2e3dcf0826c",
+ "metadata": {},
+ "source": [
+ "## Composite test"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": null,
+ "id": "7fdd24cc-7c52-4222-b473-79b09c0df810",
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "composite = load_params_ectester(io.BytesIO(b\"0x5033ba46674a215a5d62c329a1d017a7909408d59823423b9b273a129828ccc3,0x0b0600851039db449b034a92fd9a7120ab7ee4186c805da4ae42d1755c5f199d,0x2f86acaeaf18553eb283bc126d07f84e9f388d36f5745789b64042bd5ee0277c,0x20a7d7eb71da5e6cbf7dfb64c3e7f6183ffa85f47b58fe0c934fcfb234067664,0x071727449f4309638e74b6a0dad7daa707657427cef3ef8441386b393e4ebf90,0x1abbe8c2226e0b1e1f20ebb88b455d383402bf0803931d1b48eff141bacf7801,0x01\"), \"projective\")\n",
+ "factors = [2524621529, 2536125749, 2667393247, 3038161487, 3561529459, 3938093561, 4007208383, 4146424241]"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": null,
+ "id": "9db677c5-34e3-4b5e-93dc-11b9b7e2cf3a",
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "print(f\"prime:\\t0x{composite.curve.prime:x}\")\n",
+ "print(f\"a:\\t0x{composite.curve.parameters['a']:x}\")\n",
+ "print(f\"b:\\t0x{composite.curve.parameters['b']:x}\")\n",
+ "print(f\"G:\\t[0x{composite.generator.X:x},\\n\\t 0x{composite.generator.Y:x}]\")\n",
+ "print(f\"n:\\t0x{composite.order:x}\")"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": null,
+ "id": "db1e4115-d0cf-4558-93e5-d60781407548",
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "def test_composite(countermeasure, samples):\n",
+ " G = composite.generator\n",
+ " Gaff = G.to_affine()\n",
+ " correct = 0\n",
+ " failed = 0\n",
+ " for _ in range(samples):\n",
+ " k = random.randrange(0, composite.full_order)\n",
+ " countermeasure.init(composite, G)\n",
+ " res = countermeasure.multiply(k)\n",
+ " res_aff = composite.curve.affine_multiply(Gaff, k)\n",
+ " try:\n",
+ " if res.equals_scaled(res_aff.to_model(composite.curve.coordinate_model, composite.curve)):\n",
+ " correct += 1\n",
+ " else:\n",
+ " failed += 1\n",
+ " except:\n",
+ " failed += 1\n",
+ " print(f\"{failed} errors\")"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": null,
+ "id": "9946acdf-41db-4aa2-864a-1e1e771bc6cc",
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "test_composite(ltr, 100)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": null,
+ "id": "48eff976-9c37-471f-94ab-d09fd6cd53ae",
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "test_composite(rtl, 100)"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "id": "54c9ef0f-bc9e-47b9-a7e4-3821c2a2f93a",
+ "metadata": {},
+ "source": [
+ "### Group scalar randomization"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": null,
+ "id": "3420068e-70f3-4fd7-a986-b61e6e21cb54",
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "test_composite(gsr, 100)"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "id": "fea32f4e-dca2-4a5c-bd93-6580183e2d02",
+ "metadata": {},
+ "source": [
+ "### Multiplicative splitting"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": null,
+ "id": "1f540d89-af11-47ff-9477-32db8ccee045",
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "test_composite(msplit, 100)"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "id": "189d4f2a-1f0c-473f-b9fe-988bf4fbe9f7",
+ "metadata": {},
+ "source": [
+ "### Additive splitting"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": null,
+ "id": "c5fb0d90-0f65-44a5-abdc-10d12345a132",
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "test_composite(asplit, 100)"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "id": "287b7945-c538-4b40-a65b-1081f68107ab",
+ "metadata": {},
+ "source": [
+ "### Euclidean splitting"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": null,
+ "id": "61936c3a-6350-45dc-9870-20bac5b8c3e3",
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "test_composite(esplit, 100)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": null,
+ "id": "f1532a7a-b089-4c27-bc52-c515d71e1a7a",
+ "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
+}
--
cgit v1.2.3-70-g09d2