aboutsummaryrefslogtreecommitdiff
path: root/analysis/countermeasures/simulation.ipynb
diff options
context:
space:
mode:
Diffstat (limited to 'analysis/countermeasures/simulation.ipynb')
-rw-r--r--analysis/countermeasures/simulation.ipynb1910
1 files changed, 1910 insertions, 0 deletions
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
+}
generated by cgit v1.2.3-70-g09d2 (git 2.51.2) at 2025-11-08 09:16:54 +0000