diff options
| -rw-r--r-- | analysis/countermeasures/combinations.ipynb | 1854 |
1 files changed, 1854 insertions, 0 deletions
diff --git a/analysis/countermeasures/combinations.ipynb b/analysis/countermeasures/combinations.ipynb new file mode 100644 index 0000000..e54c5ab --- /dev/null +++ b/analysis/countermeasures/combinations.ipynb @@ -0,0 +1,1854 @@ +{ + "cells": [ + { + "cell_type": "code", + "execution_count": null, + "id": "50a9e566", + "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.cfg import TemporaryConfig\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 countermeasures import GroupScalarRandomization, AdditiveSplitting, MultiplicativeSplitting, EuclideanSplitting, BrumleyTuveri\n", + "from pyecsca.ec.formula import AdditionFormula\n", + "from pyecsca.ec.mod import Mod, mod\n", + "from pyecsca.ec.mult import ScalarMultiplier, ScalarMultiplicationAction\n", + "from pyecsca.ec.params import DomainParameters\n", + "from pyecsca.ec.point import Point\n", + "from countermeasures import *\n", + "from public import public\n", + "from abc import ABC, abstractmethod\n", + "from typing import Optional\n", + "# %matplotlib ipympl" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "39788eba", + "metadata": {}, + "outputs": [], + "source": [ + "# copy from simulation notebook\n", + "\n", + "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", + " \n", + " print(ctr)\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": "code", + "execution_count": null, + "id": "03ab7450", + "metadata": {}, + "outputs": [], + "source": [ + "model = ShortWeierstrassModel()\n", + "coords = model.coordinates[\"projective\"]\n", + "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\n", + "gsr = GroupScalarRandomization(mult)\n", + "gsr160 = GroupScalarRandomization(mult, 160)\n", + "asplit = AdditiveSplitting(mult)\n", + "msplit = MultiplicativeSplitting(mult)\n", + "esplit = EuclideanSplitting(mult,add)\n", + "bt = BrumleyTuveri(mult)" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "ef143ca2", + "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": "markdown", + "id": "c7535814", + "metadata": {}, + "source": [ + "## GSR + Add" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "ae49446a", + "metadata": {}, + "outputs": [], + "source": [ + "@public\n", + "class GSR_Add_1(ScalarMultiplierCountermeasure):\n", + " r\"\"\"\n", + " GSR with Add, option 1.\n", + " [k+rn-s]+[s]\n", + " \"\"\"\n", + "\n", + " rand_bits: int\n", + "\n", + " def __init__(self, mult: ScalarMultiplier, rand_bits: int = 32, add = None):\n", + " \"\"\"\n", + " :param mult: The multiplier to use.\n", + " :param rand_bits: How many random bits to sample.\n", + " \"\"\"\n", + " super().__init__(mult)\n", + " self.rand_bits = rand_bits\n", + " self.add = add\n", + " self.r = None\n", + " self.s = None\n", + "\n", + " def init(self, params: DomainParameters, point: Point):\n", + " self.params = params\n", + " self.point = point\n", + " self.mult.init(\n", + " self.params,\n", + " self.point,\n", + " bits=params.full_order.bit_length() + self.rand_bits,\n", + " )\n", + "\n", + " def multiply(self, scalar: int) -> Point:\n", + " if self.params is None or self.point is None:\n", + " raise ValueError(\"Not initialized.\")\n", + " with ScalarMultiplicationAction(self.point, self.params, scalar) as action:\n", + " order = self.params.order\n", + " r = int(Mod.random(1 << self.rand_bits)) if self.r is None else self.r\n", + " order = self.params.order\n", + " s = Mod.random(order) if self.s is None else self.s\n", + " gsr_scalar = scalar + r * order\n", + " m1 = self.mult.multiply(int(gsr_scalar-s))\n", + " m2 = self.mult.multiply(int(s))\n", + " if self.add is None:\n", + " res = self.mult._add(m1, m2) # noqa: This is OK.\n", + " else:\n", + " res = self.add(\n", + " self.params.curve.prime, m1, m2, **self.params.curve.parameters\n", + " )[0]\n", + " return action.exit(res)\n", + " \n", + "@public\n", + "class GSR_Add_2(ScalarMultiplierCountermeasure):\n", + " r\"\"\"\n", + " GSR with Add, option 2.\n", + " [k-s+r_1*n]+[s+r_2*n]\n", + " \"\"\"\n", + "\n", + " rand_bits: int\n", + "\n", + " def __init__(self, mult: ScalarMultiplier, rand_bits: int = 32, add = None):\n", + " \"\"\"\n", + " :param mult: The multiplier to use.\n", + " :param rand_bits: How many random bits to sample.\n", + " \"\"\"\n", + " super().__init__(mult)\n", + " self.rand_bits = rand_bits\n", + " self.add = add\n", + " self.r1 = None\n", + " self.r2 = None\n", + " self.s = None\n", + "\n", + " def init(self, params: DomainParameters, point: Point):\n", + " self.params = params\n", + " self.point = point\n", + " self.mult.init(\n", + " self.params,\n", + " self.point,\n", + " bits=params.full_order.bit_length() + self.rand_bits,\n", + " )\n", + "\n", + " def multiply(self, scalar: int) -> Point:\n", + " if self.params is None or self.point is None:\n", + " raise ValueError(\"Not initialized.\")\n", + " with ScalarMultiplicationAction(self.point, self.params, scalar) as action:\n", + " order = self.params.order\n", + " r1 = int(Mod.random(1 << self.rand_bits)) if self.r1 is None else self.r1\n", + " r2 = int(Mod.random(1 << self.rand_bits)) if self.r2 is None else self.r2\n", + " order = self.params.order\n", + " s = Mod.random(order) if self.s is None else self.s\n", + " add_scalar = scalar - s\n", + " \n", + " m1 = self.mult.multiply(int(add_scalar+r1*order))\n", + " m2 = self.mult.multiply(int(s+r2*order))\n", + " if self.add is None:\n", + " res = self.mult._add(m1, m2) # noqa: This is OK.\n", + " else:\n", + " res = self.add(\n", + " self.params.curve.prime, m1, m2, **self.params.curve.parameters\n", + " )[0]\n", + " return action.exit(res)" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "7c0875b7", + "metadata": {}, + "outputs": [], + "source": [ + "ga1 = GSR_Add_1(mult)\n", + "ga2 = GSR_Add_2(mult)" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "acda2816", + "metadata": {}, + "outputs": [], + "source": [ + "test_3n_random_scalar(ga1, 10)" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "d3441ab5", + "metadata": {}, + "outputs": [], + "source": [ + "test_3n_random_scalar(ga2, 10)" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "c93eb468", + "metadata": {}, + "outputs": [], + "source": [ + "test_3n_random_scalar_projected(ga1,10)" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "b9a181a2", + "metadata": {}, + "outputs": [], + "source": [ + "test_3n_random_scalar_projected(ga2, 10)" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "4c81fbba", + "metadata": {}, + "outputs": [], + "source": [ + "test_3n_fixed_scalar(ga1,10)" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "f6a635ad", + "metadata": {}, + "outputs": [], + "source": [ + "test_3n_fixed_scalar(ga2, 10)" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "e532becf", + "metadata": {}, + "outputs": [], + "source": [ + "gsrbits = 32\n", + "ga1 = GSR_Add_1(mult)\n", + "ga1.r1 = int(Mod.random(1 << gsrbits))\n", + "ga1.r2 = int(Mod.random(1 << gsrbits))\n", + "ga2 = GSR_Add_2(mult)\n", + "ga2.r1 = int(Mod.random(1 << gsrbits))\n", + "ga2.r2 = int(Mod.random(1 << gsrbits))" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "879e75a4", + "metadata": {}, + "outputs": [], + "source": [ + "test_3n_random_scalar_projected(ga1,10)" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "07b29e36", + "metadata": {}, + "outputs": [], + "source": [ + "test_3n_random_scalar_projected(ga2,300)" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "9ae7dd85", + "metadata": {}, + "outputs": [], + "source": [ + "test_3n_random_scalar_projected(ga2,300)" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "707b8b61", + "metadata": {}, + "outputs": [], + "source": [ + "order = params3n.order\n", + "ga1 = GSR_Add_1(mult)\n", + "ga1.s = Mod.random(order)\n", + "ga2 = GSR_Add_2(mult)\n", + "ga2.s = Mod.random(order)" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "4e217adf", + "metadata": {}, + "outputs": [], + "source": [ + "test_3n_random_scalar_projected(ga1,300)" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "b97290ac", + "metadata": {}, + "outputs": [], + "source": [ + "test_3n_random_scalar_projected(ga2,300)" + ] + }, + { + "cell_type": "markdown", + "id": "32da4f70", + "metadata": {}, + "source": [ + "## GSR + Mult" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "cd9fa456", + "metadata": {}, + "outputs": [], + "source": [ + "@public\n", + "class GSR_Mult_1(ScalarMultiplierCountermeasure):\n", + " r\"\"\"\n", + " GSR with Mult, option 1.\n", + " [ks^(-1)+rn][s]\n", + " \"\"\"\n", + "\n", + " rand_bits: int\n", + "\n", + " def __init__(self, mult: ScalarMultiplier, rand_bits_gsr: int = 32, rand_bits_mult: int = 32):\n", + " \"\"\"\n", + " :param mult: The multiplier to use.\n", + " :param rand_bits: How many random bits to sample.\n", + " \"\"\"\n", + " super().__init__(mult)\n", + " self.rand_bits_gsr = rand_bits_gsr\n", + " self.rand_bits_mult = rand_bits_mult\n", + " self.r = None\n", + " self.s = None\n", + " \n", + " def init(self, params: DomainParameters, point: Point):\n", + " self.params = params\n", + " self.point = point\n", + " self.mult.init(\n", + " self.params,\n", + " self.point,\n", + " bits=params.full_order.bit_length() + self.rand_bits_gsr,\n", + " )\n", + "\n", + " def multiply(self, scalar: int) -> Point:\n", + " if self.params is None or self.point is None:\n", + " raise ValueError(\"Not initialized.\")\n", + " with ScalarMultiplicationAction(self.point, self.params, scalar) as action:\n", + " order = self.params.order\n", + " r = Mod.random(1 << self.rand_bits_gsr) if self.r is None else self.r\n", + " s = Mod.random(1 << self.rand_bits_mult) if self.s is None else self.s\n", + " \n", + " S = self.mult.multiply(int(s))\n", + " self.mult.init(self.params, S)\n", + " \n", + " ks_inv = scalar * mod(int(s), order).inverse()\n", + " ks_inv_gsr = int(ks_inv) + int(r)*order\n", + " return action.exit(self.mult.multiply(int(ks_inv_gsr)))\n", + "\n", + "@public\n", + "class GSR_Mult_2(ScalarMultiplierCountermeasure):\n", + " r\"\"\"\n", + " GSR with Mult, option 2.\n", + " [ks^(-1)+r_1*n][s+r_2*n]\n", + " \"\"\"\n", + "\n", + " rand_bits: int\n", + "\n", + " def __init__(self, mult: ScalarMultiplier, rand_bits_gsr: int = 32, rand_bits_mult: int = 32):\n", + " \"\"\"\n", + " :param mult: The multiplier to use.\n", + " :param rand_bits: How many random bits to sample.\n", + " \"\"\"\n", + " super().__init__(mult)\n", + " self.rand_bits_gsr = rand_bits_gsr\n", + " self.rand_bits_mult = rand_bits_mult\n", + " self.s = None\n", + " self.r1 = None\n", + " self.r2 = None\n", + "\n", + " def multiply(self, scalar: int) -> Point:\n", + " if self.params is None or self.point is None:\n", + " raise ValueError(\"Not initialized.\")\n", + " with ScalarMultiplicationAction(self.point, self.params, scalar) as action:\n", + " order = self.params.order\n", + " r1 = Mod.random(1 << self.rand_bits_gsr) if self.r1 is None else self.r1\n", + " r2 = Mod.random(1 << self.rand_bits_gsr) if self.r2 is None else self.r2\n", + " s = Mod.random(1 << self.rand_bits_mult) if self.s is None else self.s\n", + " s_gsr = s+ r2*order \n", + " \n", + " S = self.mult.multiply(int(s_gsr))\n", + " self.mult.init(self.params, S)\n", + " \n", + " ks_inv = scalar * mod(int(s_gsr), order).inverse()\n", + " ks_inv_gsr = int(ks_inv) + int(r1)*order\n", + " return action.exit(self.mult.multiply(int(ks_inv_gsr)))\n", + " \n", + "\n", + "@public\n", + "class GSR_Mult_3(ScalarMultiplierCountermeasure):\n", + " r\"\"\"\n", + " GSR with Mult, option 2.\n", + " [ks^(-1)][s+r*n]\n", + " \"\"\"\n", + "\n", + " rand_bits: int\n", + "\n", + " def __init__(self, mult: ScalarMultiplier, rand_bits_gsr: int = 32, rand_bits_mult: int = 32):\n", + " \"\"\"\n", + " :param mult: The multiplier to use.\n", + " :param rand_bits: How many random bits to sample.\n", + " \"\"\"\n", + " super().__init__(mult)\n", + " self.rand_bits_gsr = rand_bits_gsr\n", + " self.rand_bits_mult = rand_bits_mult\n", + " self.r = None\n", + " self.s = None\n", + " \n", + " def init(self, params: DomainParameters, point: Point):\n", + " self.params = params\n", + " self.point = point\n", + " self.mult.init(\n", + " self.params,\n", + " self.point,\n", + " bits=params.full_order.bit_length() + self.rand_bits_gsr,\n", + " )\n", + "\n", + " def multiply(self, scalar: int) -> Point:\n", + " if self.params is None or self.point is None:\n", + " raise ValueError(\"Not initialized.\")\n", + " with ScalarMultiplicationAction(self.point, self.params, scalar) as action:\n", + " order = self.params.order\n", + " r = Mod.random(1 << self.rand_bits_gsr) if self.r is None else self.r\n", + " s = Mod.random(1 << self.rand_bits_mult) if self.s is None else self.s\n", + " s_gsr = s+ r*order \n", + " \n", + " S = self.mult.multiply(int(s_gsr))\n", + " self.mult.init(self.params, S)\n", + " \n", + " ks_inv = scalar * mod(int(s_gsr), order).inverse()\n", + " return action.exit(self.mult.multiply(int(ks_inv)))" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "567cfeb5", + "metadata": {}, + "outputs": [], + "source": [ + "gm1 = GSR_Mult_1(mult)\n", + "gm2 = GSR_Mult_2(mult)\n", + "gm3 = GSR_Mult_3(mult)" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "14b8e75a", + "metadata": {}, + "outputs": [], + "source": [ + "test_3n_random_scalar(gm1, 10)" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "978d91fe", + "metadata": {}, + "outputs": [], + "source": [ + "test_3n_random_scalar(gm2, 10)" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "4eff0e70", + "metadata": {}, + "outputs": [], + "source": [ + "test_3n_random_scalar(gm3, 10)" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "bbe3335a", + "metadata": {}, + "outputs": [], + "source": [ + "test_3n_random_scalar_projected(gm1,10)" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "d4810b30", + "metadata": {}, + "outputs": [], + "source": [ + "test_3n_random_scalar_projected(gm2,10)" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "0bc389aa", + "metadata": {}, + "outputs": [], + "source": [ + "test_3n_random_scalar_projected(gm3,10)" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "d495728b", + "metadata": {}, + "outputs": [], + "source": [ + "test_3n_fixed_scalar(gm1,10)" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "d6abc08b", + "metadata": {}, + "outputs": [], + "source": [ + "test_3n_fixed_scalar(gm2,10)" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "c9585053", + "metadata": {}, + "outputs": [], + "source": [ + "test_3n_fixed_scalar(gm3,10)" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "d204713a", + "metadata": {}, + "outputs": [], + "source": [ + "r = Mod.random(32)\n", + "gm1 = GSR_Mult_1(mult)\n", + "gm1.r = r\n", + "gm2 = GSR_Mult_2(mult)\n", + "gm2.r = r\n", + "gm3 = GSR_Mult_3(mult)\n", + "gm3.r = r" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "f588c3a6", + "metadata": {}, + "outputs": [], + "source": [ + "test_3n_random_scalar_projected(gm1,300)" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "5f75f678", + "metadata": {}, + "outputs": [], + "source": [ + "test_3n_random_scalar_projected(gm2,300)" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "ba0b5b0a", + "metadata": {}, + "outputs": [], + "source": [ + "test_3n_random_scalar_projected(gm3,300)" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "7cbf5e3a", + "metadata": {}, + "outputs": [], + "source": [ + "s = Mod.random(32)\n", + "gm1 = GSR_Mult_1(mult)\n", + "gm1.s = s\n", + "gm2 = GSR_Mult_2(mult)\n", + "gm2.s = s\n", + "gm3 = GSR_Mult_3(mult)\n", + "gm3.s = s" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "2d5e7a7c", + "metadata": {}, + "outputs": [], + "source": [ + "test_3n_random_scalar_projected(gm1,300)" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "08c1dd70", + "metadata": {}, + "outputs": [], + "source": [ + "test_3n_random_scalar_projected(gm2,300)" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "b96efcce", + "metadata": {}, + "outputs": [], + "source": [ + "test_3n_random_scalar_projected(gm3,300)" + ] + }, + { + "cell_type": "markdown", + "id": "856a3f86", + "metadata": {}, + "source": [ + "### GSR + Euclid" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "3a525ad2", + "metadata": {}, + "outputs": [], + "source": [ + "@public\n", + "class GSR_Eucl_1(ScalarMultiplierCountermeasure):\n", + " r\"\"\"\n", + " GSR with Eucl, option 1.\n", + " k+rn = k1+k2s\n", + " [k1]+[k2][s]\n", + " \"\"\"\n", + "\n", + " add: Optional[AdditionFormula]\n", + "\n", + " def __init__(self, mult: ScalarMultiplier, rand_bits_gsr: int = 32, add: Optional[AdditionFormula] = None):\n", + " \"\"\"\n", + " :param mult: The multiplier to use.\n", + " :param add: Addition formula to use, if None, the formula from the multiplier is used.\n", + " \"\"\"\n", + " super().__init__(mult)\n", + " self.add = add\n", + " self.rand_bits_gsr = rand_bits_gsr\n", + " self.r = None\n", + " self.s = None\n", + "\n", + " def init(self, params: DomainParameters, point: Point):\n", + " self.params = params\n", + " self.point = point\n", + " self.mult.init(\n", + " self.params,\n", + " self.point,\n", + " bits=params.full_order.bit_length() + self.rand_bits_gsr,\n", + " )\n", + " \n", + " def multiply(self, scalar: int) -> Point:\n", + " if self.params is None or self.point is None:\n", + " raise ValueError(\"Not initialized.\")\n", + " with ScalarMultiplicationAction(self.point, self.params, scalar) as action:\n", + " half_bits = self.params.order.bit_length() // 2\n", + " order = self.params.order\n", + " r = Mod.random(1 << self.rand_bits_gsr) if self.r is None else self.r\n", + " gsr = int(scalar)+int(r)*int(order)\n", + " s = Mod.random(1 << half_bits) if self.s is None else self.s\n", + " S = self.mult.multiply(int(s))\n", + " k1 = gsr % int(s)\n", + " k2 = gsr // int(s)\n", + " T = self.mult.multiply(k1)\n", + " self.mult.init(self.params, S)\n", + " R = self.mult.multiply(k2)\n", + " if self.add is None:\n", + " res = self.mult._add(R, T) # noqa: This is OK.\n", + " else:\n", + " res = self.add(\n", + " self.params.curve.prime, R, T, **self.params.curve.parameters\n", + " )[0]\n", + " return action.exit(res)\n", + " \n", + " \n", + "@public\n", + "class GSR_Eucl_2(ScalarMultiplierCountermeasure):\n", + " r\"\"\"\n", + " GSR with Eucl, option 2.\n", + " k = k1+k2s\n", + " [k1]+[k2][s+r*n]\n", + " \"\"\"\n", + "\n", + " add: Optional[AdditionFormula]\n", + "\n", + " def __init__(self, mult: ScalarMultiplier, rand_bits_gsr: int = 32, add: Optional[AdditionFormula] = None):\n", + " \"\"\"\n", + " :param mult: The multiplier to use.\n", + " :param add: Addition formula to use, if None, the formula from the multiplier is used.\n", + " \"\"\"\n", + " super().__init__(mult)\n", + " self.add = add\n", + " self.rand_bits_gsr = rand_bits_gsr\n", + " self.r = None\n", + " self.s = None\n", + " \n", + " def init(self, params: DomainParameters, point: Point):\n", + " self.params = params\n", + " self.point = point\n", + " self.mult.init(\n", + " self.params,\n", + " self.point,\n", + " bits=params.full_order.bit_length() + self.rand_bits_gsr,\n", + " )\n", + "\n", + " def multiply(self, scalar: int) -> Point:\n", + " if self.params is None or self.point is None:\n", + " raise ValueError(\"Not initialized.\")\n", + " with ScalarMultiplicationAction(self.point, self.params, scalar) as action:\n", + " half_bits = self.params.order.bit_length() // 2\n", + " order = self.params.order\n", + " r = Mod.random(1 << self.rand_bits_gsr) if self.r is None else self.r\n", + " s = Mod.random(1 << half_bits) if self.s is None else self.s\n", + " S = self.mult.multiply(int(s)+int(r)*order)\n", + " k1 = int(scalar) % int(s)\n", + " k2 = int(scalar) // int(s)\n", + " T = self.mult.multiply(k1)\n", + " self.mult.init(self.params, S)\n", + " R = self.mult.multiply(k2)\n", + " if self.add is None:\n", + " res = self.mult._add(R, T) # noqa: This is OK.\n", + " else:\n", + " res = self.add(\n", + " self.params.curve.prime, R, T, **self.params.curve.parameters\n", + " )[0]\n", + " return action.exit(res)\n", + " \n", + "@public\n", + "class GSR_Eucl_3(ScalarMultiplierCountermeasure):\n", + " r\"\"\"\n", + " GSR with Eucl, option 3.\n", + " k = k1+k2s\n", + " [k1+r1*n]+[k2+r2*n][s]\n", + " \"\"\"\n", + "\n", + " add: Optional[AdditionFormula]\n", + "\n", + " def __init__(self, mult: ScalarMultiplier, rand_bits_gsr: int = 32, add: Optional[AdditionFormula] = None):\n", + " \"\"\"\n", + " :param mult: The multiplier to use.\n", + " :param add: Addition formula to use, if None, the formula from the multiplier is used.\n", + " \"\"\"\n", + " super().__init__(mult)\n", + " self.add = add\n", + " self.rand_bits_gsr = rand_bits_gsr\n", + " self.r1 = None\n", + " self.r2 = None\n", + " self.s = None\n", + " \n", + " def init(self, params: DomainParameters, point: Point):\n", + " self.params = params\n", + " self.point = point\n", + " self.mult.init(\n", + " self.params,\n", + " self.point,\n", + " bits=params.full_order.bit_length() + self.rand_bits_gsr,\n", + " )\n", + "\n", + " def multiply(self, scalar: int) -> Point:\n", + " if self.params is None or self.point is None:\n", + " raise ValueError(\"Not initialized.\")\n", + " with ScalarMultiplicationAction(self.point, self.params, scalar) as action:\n", + " half_bits = self.params.order.bit_length() // 2\n", + " order = self.params.order\n", + " r1 = Mod.random(1 << self.rand_bits_gsr) if self.r1 is None else self.r1\n", + " r2 = Mod.random(1 << self.rand_bits_gsr) if self.r2 is None else self.r2\n", + " s = Mod.random(1 << half_bits) if self.s is None else self.s\n", + " S = self.mult.multiply(int(s))\n", + " k1 = int(scalar) % int(s)\n", + " k2 = int(scalar) // int(s)\n", + " T = self.mult.multiply(k1+int(r1)*order)\n", + " self.mult.init(self.params, S)\n", + " R = self.mult.multiply(k2+int(r2)*order)\n", + " if self.add is None:\n", + " res = self.mult._add(R, T) # noqa: This is OK.\n", + " else:\n", + " res = self.add(\n", + " self.params.curve.prime, R, T, **self.params.curve.parameters\n", + " )[0]\n", + " return action.exit(res)\n", + " \n", + "@public\n", + "class GSR_Eucl_4(ScalarMultiplierCountermeasure):\n", + " r\"\"\"\n", + " GSR with Eucl, option 4.\n", + " k = k1+k2s\n", + " [k1+r1*n]+[k2+r2*n][s+r3*n]\n", + " \"\"\"\n", + "\n", + " add: Optional[AdditionFormula]\n", + "\n", + " def __init__(self, mult: ScalarMultiplier, rand_bits_gsr: int = 32, add: Optional[AdditionFormula] = None):\n", + " \"\"\"\n", + " :param mult: The multiplier to use.\n", + " :param add: Addition formula to use, if None, the formula from the multiplier is used.\n", + " \"\"\"\n", + " super().__init__(mult)\n", + " self.add = add\n", + " self.rand_bits_gsr = rand_bits_gsr\n", + " self.r1 = None\n", + " self.r2 = None\n", + " self.r3 = None\n", + " self.s = None\n", + " \n", + " def init(self, params: DomainParameters, point: Point):\n", + " self.params = params\n", + " self.point = point\n", + " self.mult.init(\n", + " self.params,\n", + " self.point,\n", + " bits=params.full_order.bit_length() + self.rand_bits_gsr,\n", + " )\n", + "\n", + " def multiply(self, scalar: int) -> Point:\n", + " if self.params is None or self.point is None:\n", + " raise ValueError(\"Not initialized.\")\n", + " with ScalarMultiplicationAction(self.point, self.params, scalar) as action:\n", + " half_bits = self.params.order.bit_length() // 2\n", + " order = self.params.order\n", + " r1 = Mod.random(1 << self.rand_bits_gsr) if self.r1 is None else self.r1\n", + " r2 = Mod.random(1 << self.rand_bits_gsr) if self.r2 is None else self.r2\n", + " r3 = Mod.random(1 << self.rand_bits_gsr) if self.r3 is None else self.r3\n", + " s = Mod.random(1 << half_bits) if self.s is None else self.s\n", + " S = self.mult.multiply(int(s)+int(r3)*order)\n", + " k1 = int(scalar) % int(s)\n", + " k2 = int(scalar) // int(s)\n", + " T = self.mult.multiply(k1+int(r1)*order)\n", + " self.mult.init(self.params, S)\n", + " R = self.mult.multiply(k2+int(r2)*order)\n", + " if self.add is None:\n", + " res = self.mult._add(R, T) # noqa: This is OK.\n", + " else:\n", + " res = self.add(\n", + " self.params.curve.prime, R, T, **self.params.curve.parameters\n", + " )[0]\n", + " return action.exit(res)\n", + " \n" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "ac043c0e", + "metadata": {}, + "outputs": [], + "source": [ + "ge1 = GSR_Eucl_1(mult)\n", + "ge2 = GSR_Eucl_2(mult)\n", + "ge3 = GSR_Eucl_3(mult)\n", + "ge4 = GSR_Eucl_4(mult)" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "7089521c", + "metadata": {}, + "outputs": [], + "source": [ + "test_3n_random_scalar(ge1, 10)" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "9b0f74fc", + "metadata": {}, + "outputs": [], + "source": [ + "test_3n_random_scalar(ge2, 10)" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "e2482dbd", + "metadata": {}, + "outputs": [], + "source": [ + "test_3n_random_scalar(ge3, 10)" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "1182264d", + "metadata": {}, + "outputs": [], + "source": [ + "test_3n_random_scalar(ge4, 10)" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "83df90c7", + "metadata": {}, + "outputs": [], + "source": [ + "test_3n_random_scalar_projected(ge1,10)" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "c11fe8ac", + "metadata": {}, + "outputs": [], + "source": [ + "test_3n_random_scalar_projected(ge2,10)" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "e8c93af4", + "metadata": {}, + "outputs": [], + "source": [ + "test_3n_random_scalar_projected(ge3,1000)" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "b1e49379", + "metadata": {}, + "outputs": [], + "source": [ + "test_3n_random_scalar_projected(ge4,1000)" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "f8a19a27", + "metadata": {}, + "outputs": [], + "source": [ + "test_3n_fixed_scalar(ge1,1000)" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "53eab763", + "metadata": {}, + "outputs": [], + "source": [ + "test_3n_fixed_scalar(ge2,1000)" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "b3bf92f9", + "metadata": {}, + "outputs": [], + "source": [ + "test_3n_fixed_scalar(ge3,1000)" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "b630dac1", + "metadata": {}, + "outputs": [], + "source": [ + "test_3n_fixed_scalar(ge4,1000)" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "538e547e", + "metadata": {}, + "outputs": [], + "source": [ + "half_bits = params3n.order.bit_length() // 2\n", + "s = Mod.random(1 << half_bits)\n", + "ge1 = GSR_Eucl_1(mult)\n", + "ge1.s = s\n", + "ge2 = GSR_Eucl_2(mult)\n", + "ge2.s = s\n", + "ge3 = GSR_Eucl_3(mult)\n", + "ge3.s = s\n", + "ge4 = GSR_Eucl_4(mult)\n", + "ge4.s = s" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "1a513b67", + "metadata": {}, + "outputs": [], + "source": [ + "test_3n_random_scalar_projected(ge1,1000)" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "0bd86e62", + "metadata": {}, + "outputs": [], + "source": [ + "test_3n_random_scalar_projected(ge2,1000)" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "d0106770", + "metadata": {}, + "outputs": [], + "source": [ + "test_3n_random_scalar_projected(ge3,1000)" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "b54b176c", + "metadata": {}, + "outputs": [], + "source": [ + "test_3n_random_scalar_projected(ge4,1000)" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "d7af08bd", + "metadata": {}, + "outputs": [], + "source": [ + "bits = 32\n", + "r1 = Mod.random(1 << bits)\n", + "r2 = Mod.random(1 << bits)\n", + "r3 = Mod.random(1 << bits)\n", + "\n", + "ge1 = GSR_Eucl_1(mult)\n", + "ge1.r1 = r1\n", + "ge1.r2 = r2\n", + "ge1.r3 = r3\n", + "ge2 = GSR_Eucl_2(mult)\n", + "ge2.r1 = r1\n", + "ge2.r2 = r2\n", + "ge2.r3 = r3\n", + "ge3 = GSR_Eucl_3(mult)\n", + "ge3.r1 = r1\n", + "ge3.r2 = r2\n", + "ge3.r3 = r3\n", + "ge4 = GSR_Eucl_4(mult)\n", + "ge4.r1 = r1\n", + "ge4.r2 = r2\n", + "ge4.r3 = r3" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "2cbcfb89", + "metadata": {}, + "outputs": [], + "source": [ + "test_3n_random_scalar_projected(ge1,1000)" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "e0f2ba16", + "metadata": {}, + "outputs": [], + "source": [ + "test_3n_random_scalar_projected(ge2,1000)" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "9ddb9c53", + "metadata": {}, + "outputs": [], + "source": [ + "test_3n_random_scalar_projected(ge3,1000)" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "d0d3daed", + "metadata": {}, + "outputs": [], + "source": [ + "test_3n_random_scalar_projected(ge4,1000)" + ] + }, + { + "cell_type": "markdown", + "id": "a4d14a41", + "metadata": {}, + "source": [ + "### Add+Mul" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "cc2ea21f", + "metadata": {}, + "outputs": [], + "source": [ + "@public\n", + "class Add_Mul_1(ScalarMultiplierCountermeasure):\n", + " r\"\"\"\n", + " Add with Mul, option 1.\n", + " [(k-r)s1^(-1)][s1]+[rs2^(-1)][s2]\n", + " \"\"\"\n", + "\n", + " add: Optional[AdditionFormula]\n", + "\n", + " def __init__(self, mult: ScalarMultiplier,rand_bits_mul=32, add: Optional[AdditionFormula] = None):\n", + " \"\"\"\n", + " :param mult: The multiplier to use.\n", + " :param add: Addition formula to use, if None, the formula from the multiplier is used.\n", + " \"\"\"\n", + " super().__init__(mult)\n", + " self.add = add\n", + " self.rand_bits_mul = rand_bits_mul\n", + " self.r = None\n", + " self.s1 = None\n", + " self.s2 = None\n", + "\n", + " def multiply(self, scalar: int) -> Point:\n", + " if self.params is None or self.point is None:\n", + " raise ValueError(\"Not initialized.\")\n", + " with ScalarMultiplicationAction(self.point, self.params, scalar) as action:\n", + " order = self.params.order\n", + " r = Mod.random(order) if self.r is None else self.r\n", + " s1 = Mod.random(1 << self.rand_bits_mul) if self.s1 is None else self.s1\n", + " s2 = Mod.random(1 << self.rand_bits_mul) if self.s2 is None else self.s2\n", + " kr = scalar - r\n", + " \n", + " kr_inv = kr * mod(int(s1), order).inverse()\n", + " r_inv = r * mod(int(s2), order).inverse()\n", + " \n", + " R = self.mult.multiply(int(s1))\n", + " self.mult.init(self.params, R)\n", + " R = self.mult.multiply(int(kr_inv))\n", + " \n", + " self.mult.init(self.params, self.point)\n", + " S = self.mult.multiply(int(s2))\n", + " self.mult.init(self.params, S)\n", + " S = self.mult.multiply(int(r_inv))\n", + " if self.add is None:\n", + " res = self.mult._add(R, S) # noqa: This is OK.\n", + " else:\n", + " res = self.add(\n", + " self.params.curve.prime, R, S, **self.params.curve.parameters\n", + " )[0]\n", + " return action.exit(res)\n", + "\n", + "@public\n", + "class Add_Mul_2(ScalarMultiplierCountermeasure):\n", + " r\"\"\"\n", + " Add with Mul, option 2.\n", + " ([ks^(-1)-r]+[r])[s]\n", + " \"\"\"\n", + "\n", + " add: Optional[AdditionFormula]\n", + "\n", + " def __init__(self, mult: ScalarMultiplier,rand_bits_mul=32, add: Optional[AdditionFormula] = None):\n", + " \"\"\"\n", + " :param mult: The multiplier to use.\n", + " :param add: Addition formula to use, if None, the formula from the multiplier is used.\n", + " \"\"\"\n", + " super().__init__(mult)\n", + " self.add = add\n", + " self.rand_bits_mul = rand_bits_mul\n", + " self.r = None\n", + " self.s = None\n", + "\n", + " def multiply(self, scalar: int) -> Point:\n", + " if self.params is None or self.point is None:\n", + " raise ValueError(\"Not initialized.\")\n", + " with ScalarMultiplicationAction(self.point, self.params, scalar) as action:\n", + " order = self.params.order\n", + " r = Mod.random(order) if self.r is None else self.r\n", + " s = Mod.random(1 << self.rand_bits_mul) if self.s is None else self.s\n", + " \n", + " ks_inv = scalar * mod(int(s), order).inverse()\n", + " \n", + " S = self.mult.multiply(int(s))\n", + " self.mult.init(self.params, S)\n", + " \n", + " R = self.mult.multiply(int(ks_inv-r))\n", + " S = self.mult.multiply(int(r))\n", + "\n", + " if self.add is None:\n", + " res = self.mult._add(R, S) # noqa: This is OK.\n", + " else:\n", + " res = self.add(\n", + " self.params.curve.prime, R, S, **self.params.curve.parameters\n", + " )[0]\n", + " return action.exit(res)" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "626a183b", + "metadata": {}, + "outputs": [], + "source": [ + "am1 = Add_Mul_1(mult)\n", + "am2 = Add_Mul_2(mult)" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "f1cb0716", + "metadata": {}, + "outputs": [], + "source": [ + "test_3n_random_scalar(am1, 10)" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "a24caf02", + "metadata": {}, + "outputs": [], + "source": [ + "test_3n_random_scalar(am2, 1000)" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "64e2cc97", + "metadata": {}, + "outputs": [], + "source": [ + "test_3n_random_scalar_projected(am1, 1000)" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "b1b5c2d7", + "metadata": {}, + "outputs": [], + "source": [ + "test_3n_random_scalar_projected(am2, 1000)" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "c4ffd67c", + "metadata": {}, + "outputs": [], + "source": [ + "test_3n_fixed_scalar(am1,1000)" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "29337718", + "metadata": {}, + "outputs": [], + "source": [ + "test_3n_fixed_scalar(am2,1000)" + ] + }, + { + "cell_type": "markdown", + "id": "82876bb4", + "metadata": {}, + "source": [ + "### Add + Eucl" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "5ab887c5", + "metadata": {}, + "outputs": [], + "source": [ + " \n", + "@public\n", + "class Add_Eucl_1(ScalarMultiplierCountermeasure):\n", + " r\"\"\"\n", + " Add with Eucl, option 1.\n", + " k-r = k1+k2s1\n", + " r = l1+l2s2\n", + " [k1]+[k2][s1]+[l1]+[l2][s2]\n", + " \"\"\"\n", + "\n", + " add: Optional[AdditionFormula]\n", + "\n", + " def __init__(self, mult: ScalarMultiplier, add: Optional[AdditionFormula] = None):\n", + " \"\"\"\n", + " :param mult: The multiplier to use.\n", + " :param add: Addition formula to use, if None, the formula from the multiplier is used.\n", + " \"\"\"\n", + " super().__init__(mult)\n", + " self.add = add\n", + " self.r = None\n", + " self.s1 = None\n", + " self.s2 = None\n", + "\n", + " def multiply(self, scalar: int) -> Point:\n", + " if self.params is None or self.point is None:\n", + " raise ValueError(\"Not initialized.\")\n", + " with ScalarMultiplicationAction(self.point, self.params, scalar) as action:\n", + " half_bits = self.params.order.bit_length() // 2\n", + " order = self.params.order\n", + " r = Mod.random(order) if self.r is None else self.r\n", + " s1 = Mod.random(1 << half_bits) if self.s1 is None else self.s1\n", + " s2 = Mod.random(1 << half_bits) if self.s2 is None else self.s2\n", + " k_r = int(scalar-r)\n", + " k1 = k_r % int(s1)\n", + " k2 = k_r // int(s1)\n", + " \n", + " l1 = int(r) % int(s2)\n", + " l2 = int(r) // int(s2)\n", + " \n", + " \n", + " S1 = self.mult.multiply(int(s1))\n", + " S2 = self.mult.multiply(int(s2))\n", + " K1 = self.mult.multiply(int(k1))\n", + " L1 = self.mult.multiply(int(l1))\n", + " \n", + " self.mult.init(self.params, S1)\n", + " K2 = self.mult.multiply(int(k2))\n", + " self.mult.init(self.params, S2)\n", + " L2 = self.mult.multiply(int(l2))\n", + " \n", + " if self.add is None:\n", + " res = self.mult._add(K1, K2)\n", + " res = self.mult._add(res, L1)\n", + " res = self.mult._add(res, L2)\n", + " else:\n", + " res = self.add(\n", + " self.params.curve.prime, K1, K2, **self.params.curve.parameters\n", + " )[0]\n", + " res = self.add(\n", + " self.params.curve.prime, res, L1, **self.params.curve.parameters\n", + " )[0]\n", + " res = self.add(\n", + " self.params.curve.prime, res, L2, **self.params.curve.parameters\n", + " )[0]\n", + " return action.exit(res)\n", + " \n", + "\n", + " \n", + "@public\n", + "class Add_Eucl_2(ScalarMultiplierCountermeasure):\n", + " r\"\"\"\n", + " Add with Eucl, option 2.\n", + " k = k1+k2s\n", + " [k1-r1]+[r1]+([k2-r2]+[r2])[s]\n", + " \"\"\"\n", + "\n", + " add: Optional[AdditionFormula]\n", + "\n", + " def __init__(self, mult: ScalarMultiplier, add: Optional[AdditionFormula] = None):\n", + " \"\"\"\n", + " :param mult: The multiplier to use.\n", + " :param add: Addition formula to use, if None, the formula from the multiplier is used.\n", + " \"\"\"\n", + " super().__init__(mult)\n", + " self.add = add\n", + " self.r1 = None\n", + " self.r2 = None\n", + " self.s = None\n", + "\n", + " def multiply(self, scalar: int) -> Point:\n", + " if self.params is None or self.point is None:\n", + " raise ValueError(\"Not initialized.\")\n", + " with ScalarMultiplicationAction(self.point, self.params, scalar) as action:\n", + " half_bits = self.params.order.bit_length() // 2\n", + " order = self.params.order\n", + " r1 = Mod.random(order) if self.r1 is None else self.r1\n", + " r2 = Mod.random(order) if self.r2 is None else self.r2\n", + " s = Mod.random(1 << half_bits) if self.s is None else self.s\n", + " k1 = int(scalar) % int(s)\n", + " k2 = int(scalar) // int(s)\n", + " k1r1 = k1-r1\n", + " k2r2 = k2-r2\n", + " \n", + " \n", + " S = self.mult.multiply(int(s))\n", + " KR1 = self.mult.multiply(int(k1r1))\n", + " R1 = self.mult.multiply(int(r1))\n", + " \n", + " self.mult.init(self.params, S)\n", + " KR2 = self.mult.multiply(int(k2r2))\n", + " R2 = self.mult.multiply(int(r2))\n", + " \n", + " if self.add is None:\n", + " res = self.mult._add(KR1, R1)\n", + " res = self.mult._add(res, KR2)\n", + " res = self.mult._add(res, R2)\n", + " else:\n", + " res = self.add(\n", + " self.params.curve.prime, KR1, R1, **self.params.curve.parameters\n", + " )[0]\n", + " res = self.add(\n", + " self.params.curve.prime, res, KR2, **self.params.curve.parameters\n", + " )[0]\n", + " res = self.add(\n", + " self.params.curve.prime, res, R2, **self.params.curve.parameters\n", + " )[0]\n", + " return action.exit(res)\n", + " \n" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "e70576c6", + "metadata": {}, + "outputs": [], + "source": [ + "ae1 = Add_Eucl_1(mult)\n", + "ae2 = Add_Eucl_2(mult)\n" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "c2baaaef", + "metadata": {}, + "outputs": [], + "source": [ + "test_3n_random_scalar(ae1, 10)" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "8eae89c8", + "metadata": {}, + "outputs": [], + "source": [ + "test_3n_random_scalar(ae2, 1000)" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "e95c8c39", + "metadata": {}, + "outputs": [], + "source": [ + "test_3n_random_scalar_projected(ae1, 1000)" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "2d619d4f", + "metadata": {}, + "outputs": [], + "source": [ + "test_3n_random_scalar_projected(ae2, 1000)" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "a827e3fd", + "metadata": {}, + "outputs": [], + "source": [ + "test_3n_fixed_scalar(ae1,1000)" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "da2bcb55", + "metadata": {}, + "outputs": [], + "source": [ + "test_3n_fixed_scalar(ae2,1000)" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "3afaaa43", + "metadata": {}, + "outputs": [], + "source": [ + " \n", + "@public\n", + "class Mul_Eucl_1(ScalarMultiplierCountermeasure):\n", + " r\"\"\"\n", + " Mul with Eucl, option 1.\n", + " kr^(-1) = k1+k2s\n", + " ([k1]+[k2][s])[r]\n", + " \"\"\"\n", + "\n", + " add: Optional[AdditionFormula]\n", + "\n", + " def __init__(self, mult: ScalarMultiplier,rand_bits_mul=32, add: Optional[AdditionFormula] = None):\n", + " \"\"\"\n", + " :param mult: The multiplier to use.\n", + " :param add: Addition formula to use, if None, the formula from the multiplier is used.\n", + " \"\"\"\n", + " super().__init__(mult)\n", + " self.add = add\n", + " self.rand_bits_mul = rand_bits_mul\n", + " self.r = None\n", + " self.s = None\n", + "\n", + " def multiply(self, scalar: int) -> Point:\n", + " if self.params is None or self.point is None:\n", + " raise ValueError(\"Not initialized.\")\n", + " with ScalarMultiplicationAction(self.point, self.params, scalar) as action:\n", + " half_bits = self.params.order.bit_length() // 2\n", + " order = self.params.order\n", + " s = Mod.random(order) if self.s is None else self.s\n", + " r = Mod.random(1 << self.rand_bits_mul) if self.r is None else self.r\n", + " \n", + " kr_inv = scalar * mod(int(r), order).inverse()\n", + " \n", + " k1 = int(kr_inv) % int(s)\n", + " k2 = int(kr_inv) // int(s)\n", + " \n", + " R = self.mult.multiply(int(r))\n", + " self.mult.init(self.params, R)\n", + " \n", + " K1 = self.mult.multiply(int(k1))\n", + " \n", + " S = self.mult.multiply(int(s))\n", + " self.mult.init(self.params, S)\n", + " K2 = self.mult.multiply(int(k2))\n", + " \n", + " if self.add is None:\n", + " res = self.mult._add(K1, K2)\n", + " else:\n", + " res = self.add(\n", + " self.params.curve.prime, K1, K2, **self.params.curve.parameters\n", + " )[0]\n", + " return action.exit(res)\n", + " \n", + "\n", + " \n", + "@public\n", + "class Mul_Eucl_2(ScalarMultiplierCountermeasure):\n", + " r\"\"\"\n", + " Mul with Eucl, option 2.\n", + " [k1r1^(-1)][r1]+[k2r2^(-1)][r2][s]\n", + " \"\"\"\n", + "\n", + " add: Optional[AdditionFormula]\n", + "\n", + " def __init__(self, mult: ScalarMultiplier,rand_bits_mul=32, add: Optional[AdditionFormula] = None):\n", + " \"\"\"\n", + " :param mult: The multiplier to use.\n", + " :param add: Addition formula to use, if None, the formula from the multiplier is used.\n", + " \"\"\"\n", + " super().__init__(mult)\n", + " self.add = add\n", + " self.rand_bits_mul = rand_bits_mul\n", + " self.s = None\n", + " self.r1 = None\n", + " self.r2 = None\n", + "\n", + " def multiply(self, scalar: int) -> Point:\n", + " if self.params is None or self.point is None:\n", + " raise ValueError(\"Not initialized.\")\n", + " with ScalarMultiplicationAction(self.point, self.params, scalar) as action:\n", + " half_bits = self.params.order.bit_length() // 2\n", + " order = self.params.order\n", + " s = Mod.random(order) if self.s is None else self.s\n", + " \n", + " r1 = Mod.random(1 << self.rand_bits_mul) if self.r1 is None else self.r1\n", + " r2 = Mod.random(1 << self.rand_bits_mul) if self.r2 is None else self.r2\n", + " \n", + " k1 = int(scalar) % int(s)\n", + " k2 = int(scalar) // int(s)\n", + " \n", + " kr1_inv = k1 * mod(int(r1), order).inverse()\n", + " kr2_inv = k2 * mod(int(r2), order).inverse()\n", + " \n", + " R1 = self.mult.multiply(int(r1))\n", + " S = self.mult.multiply(int(s))\n", + " \n", + " self.mult.init(self.params, R1)\n", + " R1 = self.mult.multiply(int(kr1_inv))\n", + " \n", + " self.mult.init(self.params, S)\n", + " R2 = self.mult.multiply(int(r2))\n", + " \n", + " self.mult.init(self.params, R2)\n", + " R2 = self.mult.multiply(int(kr2_inv))\n", + " \n", + " \n", + " if self.add is None:\n", + " res = self.mult._add(R1, R2)\n", + " else:\n", + " res = self.add(\n", + " self.params.curve.prime, R1, R2, **self.params.curve.parameters\n", + " )[0]\n", + " return action.exit(res)\n", + " \n" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "39c6abd4", + "metadata": {}, + "outputs": [], + "source": [ + "me1 = Mul_Eucl_1(mult)\n", + "me2 = Mul_Eucl_2(mult)" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "dd85d5e2", + "metadata": {}, + "outputs": [], + "source": [ + "test_3n_random_scalar(me1, 10)" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "228ad9c3", + "metadata": {}, + "outputs": [], + "source": [ + "test_3n_random_scalar(me2, 1000)" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "3ff4c1e6", + "metadata": {}, + "outputs": [], + "source": [ + "test_3n_random_scalar_projected(me1, 1000)" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "e0b3fe67", + "metadata": {}, + "outputs": [], + "source": [ + "test_3n_random_scalar_projected(me2, 1000)" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "34ad9676", + "metadata": {}, + "outputs": [], + "source": [ + "test_3n_fixed_scalar(me1,1000)" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "b7f69ff0", + "metadata": {}, + "outputs": [], + "source": [ + "test_3n_fixed_scalar(me2,1000)" + ] + } + ], + "metadata": { + "kernelspec": { + "display_name": "env", + "language": "python", + "name": "env" + }, + "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.10.12" + } + }, + "nbformat": 4, + "nbformat_minor": 5 +} |