{ "cells": [ { "cell_type": "markdown", "id": "65d4a44b-b1f1-4a24-aed3-a7f12eb263a2", "metadata": {}, "source": [ "# Simulation of countermeasure combinations\n", "\n", "This notebook contains simulation of combinations of countermeasures and their behavior under our tests:\n", " - [GSR + Add](#GSR-+-Add)\n", " - [GSR + Mul](#GSR-+-Mul)\n", " - [GSR + Euclid](#GSR-+-Euclid)\n", " - [Add + Mul](#Add-+-Mul)\n", " - [Add + Euclid](#Add-+-Euclid)\n", " - [Mul + Euclid](#Mul-+-Euclid)" ] }, { "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 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 pyecsca.ec.countermeasures import *\n", "from public import public\n", "from abc import ABC, abstractmethod\n", "from typing import Optional\n", "# %matplotlib ipympl\n", "import secrets" ] }, { "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))\n", "\n", "\n", "def test_composite(countermeasure, samples):\n", " G = composite.generator\n", " Gaff = G.to_affine()\n", " correct = 0\n", " errors = 0\n", " wrong = 0\n", " for _ in range(samples):\n", " k = random.randrange(0, composite.full_order)\n", " countermeasure.init(composite, G)\n", " try:\n", " res = countermeasure.multiply(k)\n", " res_aff = composite.curve.affine_multiply(Gaff, k)\n", " \n", " if res.equals_scaled(res_aff.to_model(composite.curve.coordinate_model, composite.curve)):\n", " correct += 1\n", " else:\n", " wrong += 1\n", " except Exception as e:\n", " errors += 1\n", " print(f\"{errors} errors, {wrong} wrong results\")\n", "\n", "\n", "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": "4084e4ca-e375-4c3e-8ba9-37387a7ab8f9", "metadata": {}, "source": [ "Let's initialize some useful objects first." ] }, { "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", "\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": "markdown", "id": "0366cb95-f70d-42ec-91d5-4681a86b40e1", "metadata": {}, "source": [ "In the 3n test the target is given domain parameters of order $3n$ but claimed order $n$. The target is then given a point of order $3n$ for scalar multiplication and the results are observed." ] }, { "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": "code", "execution_count": null, "id": "76c61ded-55b4-46fd-b0cc-cbdc80f82775", "metadata": {}, "outputs": [], "source": [ "paramsk10 = get_params(\"secg\", \"secp256r1\", \"projective\")" ] }, { "cell_type": "code", "execution_count": null, "id": "17eddcbb-bc16-416d-bab1-b8826fd8db14", "metadata": {}, "outputs": [], "source": [ "composite = load_params_ectester(io.BytesIO(b\"0xc7a3ef9fa4ea63b537eedefc6bd52c3f35dc45be933d44270a1536c2ff9b6543,0x395f3675858362cbe7ac0d3e85708750aa42428368ae6ab1fda0d2a56255039b,0x61ca87695d4f6147b35975326eeee1a77f93226487315cd2419b4a1fe23f32d1,0x56e9a905d29f0f512cf709522bdd43a862d4e32c46268eec2f4c3fd9a70cb9d6,0xaf77a4ef604d33e3cf6c2ecaaa2913a5c51660e40365832ab98488950f3c348e,0xc7a3ef9fa4ea63b537eedefc6bd52c40f5e8e3bfe0f6dd05ac513edbcaa3cc47,0x01\"), \"projective\")\n", "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": "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: int = None\n", " self.s: int = 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", " s = int(Mod.random(order)) if self.s is None else self.s\n", " gsr_scalar = scalar + r * order\n", " m1 = self.mult.multiply(gsr_scalar-s)\n", " m2 = self.mult.multiply(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: int = None\n", " self.r2: int = None\n", " self.s: int = 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 = int(Mod.random(order)) if self.s is None else self.s\n", " add_scalar = int(mod(scalar,order) - mod(s,order))\n", " \n", " m1 = self.mult.multiply(add_scalar+r1*order)\n", " m2 = self.mult.multiply(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, 1000)" ] }, { "cell_type": "code", "execution_count": null, "id": "d3441ab5", "metadata": {}, "outputs": [], "source": [ "test_3n_random_scalar(ga2, 1000)" ] }, { "cell_type": "code", "execution_count": null, "id": "c93eb468", "metadata": {}, "outputs": [], "source": [ "test_3n_random_scalar_projected(ga1,1000)" ] }, { "cell_type": "code", "execution_count": null, "id": "b9a181a2", "metadata": {}, "outputs": [], "source": [ "test_3n_random_scalar_projected(ga2, 1000)" ] }, { "cell_type": "code", "execution_count": null, "id": "4c81fbba", "metadata": {}, "outputs": [], "source": [ "test_3n_fixed_scalar(ga1,1000)" ] }, { "cell_type": "code", "execution_count": null, "id": "f6a635ad", "metadata": {}, "outputs": [], "source": [ "test_3n_fixed_scalar(ga2, 1000)" ] }, { "cell_type": "code", "execution_count": null, "id": "6d959ee5-754a-46c4-94c0-7d57b1e2fbc1", "metadata": {}, "outputs": [], "source": [ "test_composite(ga1, 1000)" ] }, { "cell_type": "code", "execution_count": null, "id": "59761622-5d10-4a9d-8eab-4158b2c986e6", "metadata": {}, "outputs": [], "source": [ "test_composite(ga2, 1000)" ] }, { "cell_type": "code", "execution_count": null, "id": "be2fdd7c-81fe-4a56-af7a-1696e20e7902", "metadata": {}, "outputs": [], "source": [ "test_k10(ga1, 100, k_range = range(8,11))" ] }, { "cell_type": "code", "execution_count": null, "id": "a3e4d77f-770b-49f5-b919-a0866755e89d", "metadata": {}, "outputs": [], "source": [ "test_k10(ga2, 100, k_range = range(8,11))" ] }, { "cell_type": "markdown", "id": "79218e51-8b00-495f-ac03-8f6c7a19aaa4", "metadata": {}, "source": [ "#### Experiments with fixed masks" ] }, { "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,10)" ] }, { "cell_type": "code", "execution_count": null, "id": "9ae7dd85", "metadata": {}, "outputs": [], "source": [ "test_3n_random_scalar_projected(ga2,10)" ] }, { "cell_type": "code", "execution_count": null, "id": "707b8b61", "metadata": {}, "outputs": [], "source": [ "order = params3n.order\n", "ga1 = GSR_Add_1(mult)\n", "ga1.s = int(Mod.random(order))\n", "ga2 = GSR_Add_2(mult)\n", "ga2.s = int(Mod.random(order))" ] }, { "cell_type": "code", "execution_count": null, "id": "4e217adf", "metadata": {}, "outputs": [], "source": [ "test_3n_random_scalar_projected(ga1,10)" ] }, { "cell_type": "code", "execution_count": null, "id": "b97290ac", "metadata": {}, "outputs": [], "source": [ "test_3n_random_scalar_projected(ga2,10)" ] }, { "cell_type": "markdown", "id": "32da4f70", "metadata": {}, "source": [ "### GSR + Mul" ] }, { "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: int = None\n", " self.s: int = 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 = int(Mod.random(1 << self.rand_bits_gsr)) if self.r is None else self.r\n", " s = int(Mod.random(1 << self.rand_bits_mult)) if self.s is None else self.s\n", " \n", " S = self.mult.multiply(s)\n", " self.mult.init(self.params, S)\n", " \n", " ks_inv = scalar * mod(s, order).inverse()\n", " ks_inv_gsr = int(ks_inv) + r*order\n", " return action.exit(self.mult.multiply(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: int = None\n", " self.r1: int = None\n", " self.r2: int = 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 = int(Mod.random(1 << self.rand_bits_gsr)) if self.r1 is None else self.r1\n", " r2 = int(Mod.random(1 << self.rand_bits_gsr)) if self.r2 is None else self.r2\n", " s = int(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(s_gsr)\n", " self.mult.init(self.params, S)\n", " \n", " ks_inv = scalar * mod(s, order).inverse()\n", " ks_inv_gsr = int(ks_inv) + r1*order\n", " return action.exit(self.mult.multiply(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: int = None\n", " self.s: int = 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 = int(Mod.random(1 << self.rand_bits_gsr)) if self.r is None else self.r\n", " s = int(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(s_gsr)\n", " self.mult.init(self.params, S)\n", " \n", " ks_inv = scalar * mod(s, 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, 1000)" ] }, { "cell_type": "code", "execution_count": null, "id": "978d91fe", "metadata": {}, "outputs": [], "source": [ "test_3n_random_scalar(gm2, 1000)" ] }, { "cell_type": "code", "execution_count": null, "id": "4eff0e70", "metadata": {}, "outputs": [], "source": [ "test_3n_random_scalar(gm3, 1000)" ] }, { "cell_type": "code", "execution_count": null, "id": "bbe3335a", "metadata": {}, "outputs": [], "source": [ "test_3n_random_scalar_projected(gm1,1000)" ] }, { "cell_type": "code", "execution_count": null, "id": "d4810b30", "metadata": {}, "outputs": [], "source": [ "test_3n_random_scalar_projected(gm2,1000)" ] }, { "cell_type": "code", "execution_count": null, "id": "0bc389aa", "metadata": {}, "outputs": [], "source": [ "test_3n_random_scalar_projected(gm3,1000)" ] }, { "cell_type": "code", "execution_count": null, "id": "d495728b", "metadata": {}, "outputs": [], "source": [ "test_3n_fixed_scalar(gm1,1000)" ] }, { "cell_type": "code", "execution_count": null, "id": "d6abc08b", "metadata": {}, "outputs": [], "source": [ "test_3n_fixed_scalar(gm2,1000)" ] }, { "cell_type": "code", "execution_count": null, "id": "c9585053", "metadata": {}, "outputs": [], "source": [ "test_3n_fixed_scalar(gm3,1000)" ] }, { "cell_type": "code", "execution_count": null, "id": "d6636e68-2218-4bfd-b280-5c864d6da8c0", "metadata": {}, "outputs": [], "source": [ "test_k10(gm1, 100, k_range = range(8,11))" ] }, { "cell_type": "code", "execution_count": null, "id": "2e88c407-f041-4653-9f32-70a3fc2fa0b0", "metadata": {}, "outputs": [], "source": [ "test_k10(gm2, 100, k_range = range(8,11))" ] }, { "cell_type": "code", "execution_count": null, "id": "929539c0-93c8-49e0-806a-216d4d083c53", "metadata": {}, "outputs": [], "source": [ "test_k10(gm3, 100, k_range = range(8,11))" ] }, { "cell_type": "code", "execution_count": null, "id": "1205ddd6-14a8-406a-9c86-b00b14248882", "metadata": {}, "outputs": [], "source": [ "test_composite(gm1, 1000)" ] }, { "cell_type": "code", "execution_count": null, "id": "9aa2c845-f81a-4993-8c66-498008348874", "metadata": {}, "outputs": [], "source": [ "test_composite(gm2, 1000)" ] }, { "cell_type": "code", "execution_count": null, "id": "6d1a9dac-f579-430e-9a15-8ee8d9e41ca8", "metadata": {}, "outputs": [], "source": [ "test_composite(gm3, 1000)" ] }, { "cell_type": "markdown", "id": "101280dd-3c14-4906-a63c-e5c0e753452a", "metadata": {}, "source": [ "#### Experiments with fixed masks" ] }, { "cell_type": "code", "execution_count": null, "id": "d204713a", "metadata": {}, "outputs": [], "source": [ "r = int(Mod.random(1 << 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,10)" ] }, { "cell_type": "code", "execution_count": null, "id": "5f75f678", "metadata": {}, "outputs": [], "source": [ "test_3n_random_scalar_projected(gm2,10)" ] }, { "cell_type": "code", "execution_count": null, "id": "ba0b5b0a", "metadata": {}, "outputs": [], "source": [ "test_3n_random_scalar_projected(gm3,10)" ] }, { "cell_type": "code", "execution_count": null, "id": "7cbf5e3a", "metadata": {}, "outputs": [], "source": [ "s = int(Mod.random(1 << 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,10)" ] }, { "cell_type": "code", "execution_count": null, "id": "08c1dd70", "metadata": {}, "outputs": [], "source": [ "test_3n_random_scalar_projected(gm2,10)" ] }, { "cell_type": "code", "execution_count": null, "id": "b96efcce", "metadata": {}, "outputs": [], "source": [ "test_3n_random_scalar_projected(gm3,10)" ] }, { "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: int = None\n", " self.s: int = 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", " \n", " order = self.params.order\n", " r = int(Mod.random(1 << self.rand_bits_gsr)) if self.r is None else self.r\n", " gsr = scalar+r*order\n", " half_bits = gsr.bit_length() // 2\n", " s = int(Mod.random(1 << half_bits)) if self.s is None else self.s\n", " S = self.mult.multiply(s)\n", " k1 = gsr % s\n", " k2 = gsr // 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: int = None\n", " self.s: int = 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 = int(Mod.random(1 << self.rand_bits_gsr)) if self.r is None else self.r\n", " s = int(Mod.random(1 << half_bits)) if self.s is None else self.s\n", " S = self.mult.multiply(s+r*order)\n", " k1 = scalar % s\n", " k2 = scalar // 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: int = None\n", " self.r2: int = None\n", " self.s: int = 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 = int(Mod.random(1 << self.rand_bits_gsr)) if self.r1 is None else self.r1\n", " r2 = int(Mod.random(1 << self.rand_bits_gsr)) if self.r2 is None else self.r2\n", " s = int(Mod.random(1 << half_bits)) if self.s is None else self.s\n", " S = self.mult.multiply(s)\n", " k1 = scalar % s\n", " k2 = scalar // s\n", " T = self.mult.multiply(k1+r1*order)\n", " self.mult.init(self.params, S)\n", " R = self.mult.multiply(k2+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: int = None\n", " self.r2: int = None\n", " self.r3: int = None\n", " self.s: int = 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 = int(Mod.random(1 << self.rand_bits_gsr)) if self.r1 is None else self.r1\n", " r2 = int(Mod.random(1 << self.rand_bits_gsr)) if self.r2 is None else self.r2\n", " r3 = int(Mod.random(1 << self.rand_bits_gsr)) if self.r3 is None else self.r3\n", " s = int(Mod.random(1 << half_bits)) if self.s is None else self.s\n", " S = self.mult.multiply(s+r3*order)\n", " k1 = scalar % s\n", " k2 = scalar // s\n", " T = self.mult.multiply(k1+r1*order)\n", " self.mult.init(self.params, S)\n", " R = self.mult.multiply(k2+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)" ] }, { "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, 1000)" ] }, { "cell_type": "code", "execution_count": null, "id": "9b0f74fc", "metadata": {}, "outputs": [], "source": [ "test_3n_random_scalar(ge2, 1000)" ] }, { "cell_type": "code", "execution_count": null, "id": "e2482dbd", "metadata": {}, "outputs": [], "source": [ "test_3n_random_scalar(ge3, 1000)" ] }, { "cell_type": "code", "execution_count": null, "id": "351c0dbd-e659-4cb4-8af9-d532ff03237e", "metadata": {}, "outputs": [], "source": [ "test_3n_random_scalar(ge4, 1000)" ] }, { "cell_type": "code", "execution_count": null, "id": "83df90c7", "metadata": {}, "outputs": [], "source": [ "test_3n_random_scalar_projected(ge1,1000)" ] }, { "cell_type": "code", "execution_count": null, "id": "c11fe8ac", "metadata": {}, "outputs": [], "source": [ "test_3n_random_scalar_projected(ge2,1000)" ] }, { "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": "62a1b4c3-6fd8-4a89-979f-66041566d67d", "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": "cf65daf5-ae32-4973-b41b-e86f621eba0f", "metadata": {}, "outputs": [], "source": [ "test_3n_fixed_scalar(ge4,1000)" ] }, { "cell_type": "code", "execution_count": null, "id": "167d3839-22df-40b7-80ff-7a11cd5b915d", "metadata": {}, "outputs": [], "source": [ "test_composite(ge1, 1000)" ] }, { "cell_type": "code", "execution_count": null, "id": "84f59798-27b6-45a7-b14d-8cf820aac83f", "metadata": {}, "outputs": [], "source": [ "test_composite(ge2, 1000)" ] }, { "cell_type": "code", "execution_count": null, "id": "c60e0075-215b-489c-a6b3-945079dc7e3b", "metadata": {}, "outputs": [], "source": [ "test_composite(ge3, 1000)" ] }, { "cell_type": "code", "execution_count": null, "id": "82a8d754-47a4-4864-a36f-24144c6858d9", "metadata": {}, "outputs": [], "source": [ "test_composite(ge4, 1000)" ] }, { "cell_type": "code", "execution_count": null, "id": "1c3a77e2-b577-4570-830c-285bc19c235c", "metadata": {}, "outputs": [], "source": [ "test_k10(ge1, 100, k_range = range(8,11))" ] }, { "cell_type": "code", "execution_count": null, "id": "dc7b7967-fdda-48cd-b136-c0f6a970aedb", "metadata": {}, "outputs": [], "source": [ "test_k10(ge2, 100, k_range = range(8,11))" ] }, { "cell_type": "code", "execution_count": null, "id": "0e2696f1-1266-480b-9831-d90c01f384a0", "metadata": {}, "outputs": [], "source": [ "test_k10(ge3, 100, k_range = range(8,11))" ] }, { "cell_type": "code", "execution_count": null, "id": "7e1cd225-004a-4c56-8f7d-d149e42a65d9", "metadata": {}, "outputs": [], "source": [ "test_k10(ge4, 100, k_range = range(8,11))" ] }, { "cell_type": "markdown", "id": "27776d8b-ba29-4cef-8f6d-dce78b515030", "metadata": {}, "source": [ "#### Experiments with fixed masks" ] }, { "cell_type": "code", "execution_count": null, "id": "538e547e", "metadata": {}, "outputs": [], "source": [ "half_bits = params3n.order.bit_length() // 2\n", "s = int(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" ] }, { "cell_type": "code", "execution_count": null, "id": "1a513b67", "metadata": {}, "outputs": [], "source": [ "test_3n_random_scalar_projected(ge1,10)" ] }, { "cell_type": "code", "execution_count": null, "id": "0bd86e62", "metadata": {}, "outputs": [], "source": [ "test_3n_random_scalar_projected(ge2,10)" ] }, { "cell_type": "code", "execution_count": null, "id": "d0106770", "metadata": {}, "outputs": [], "source": [ "test_3n_random_scalar_projected(ge3,10)" ] }, { "cell_type": "code", "execution_count": null, "id": "d7af08bd", "metadata": {}, "outputs": [], "source": [ "bits = 32\n", "r1 = int(Mod.random(1 << bits))\n", "r2 = int(Mod.random(1 << bits))\n", "r3 = int(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" ] }, { "cell_type": "code", "execution_count": null, "id": "2cbcfb89", "metadata": {}, "outputs": [], "source": [ "test_3n_random_scalar_projected(ge1,10)" ] }, { "cell_type": "code", "execution_count": null, "id": "e0f2ba16", "metadata": {}, "outputs": [], "source": [ "test_3n_random_scalar_projected(ge2,10)" ] }, { "cell_type": "code", "execution_count": null, "id": "9ddb9c53", "metadata": {}, "outputs": [], "source": [ "test_3n_random_scalar_projected(ge3,10)" ] }, { "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: int = None\n", " self.s1: int = None\n", " self.s2: int = 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 = int(Mod.random(order)) if self.r is None else self.r\n", " s1 = int(Mod.random(1 << self.rand_bits_mul)) if self.s1 is None else self.s1\n", " s2 = int(Mod.random(1 << self.rand_bits_mul)) if self.s2 is None else self.s2\n", " kr = int(mod(scalar,order) - mod(r,order))\n", " \n", " kr_inv = int(kr * mod(s1, order).inverse())\n", " r_inv = int(r * mod(s2, order).inverse())\n", " \n", " R = self.mult.multiply(s1)\n", " self.mult.init(self.params, R)\n", " R = self.mult.multiply(kr_inv)\n", " \n", " self.mult.init(self.params, self.point)\n", " S = self.mult.multiply(s2)\n", " self.mult.init(self.params, S)\n", " S = self.mult.multiply(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)\n", "\n" ] }, { "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, 1000)" ] }, { "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": "code", "execution_count": null, "id": "d9029c1b-b166-4106-97e5-92319def0ab5", "metadata": {}, "outputs": [], "source": [ "test_composite(am1, 1000)" ] }, { "cell_type": "code", "execution_count": null, "id": "d4c0f1dd-ebf3-4e54-97b0-4e2594a6f8f1", "metadata": {}, "outputs": [], "source": [ "test_composite(am2, 1000)" ] }, { "cell_type": "code", "execution_count": null, "id": "0fe42ac2-3776-4bf7-8562-7d0748259738", "metadata": {}, "outputs": [], "source": [ "test_k10(am1, 100, k_range = range(8,11))" ] }, { "cell_type": "code", "execution_count": null, "id": "a2913fe4-83f8-4d30-84d1-c56008274931", "metadata": {}, "outputs": [], "source": [ "test_k10(am2, 100, k_range = range(8,11))" ] }, { "cell_type": "markdown", "id": "82876bb4", "metadata": {}, "source": [ "### Add + Euclid" ] }, { "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: int = None\n", " self.s1: int = None\n", " self.s2: int = 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 = int(Mod.random(order)) if self.r is None else self.r\n", " s1 = int(Mod.random(1 << half_bits)) if self.s1 is None else self.s1\n", " s2 = int(Mod.random(1 << half_bits)) if self.s2 is None else self.s2\n", " k_r = int(mod(scalar,order)-mod(r,order))\n", " k1 = k_r % s1\n", " k2 = k_r // s1\n", " \n", " l1 = r % s2\n", " l2 = r // s2\n", " \n", " \n", " S1 = self.mult.multiply(s1)\n", " S2 = self.mult.multiply(s2)\n", " K1 = self.mult.multiply(k1)\n", " L1 = self.mult.multiply(l1)\n", " \n", " self.mult.init(self.params, S1)\n", " K2 = self.mult.multiply(k2)\n", " self.mult.init(self.params, S2)\n", " L2 = self.mult.multiply(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: int = None\n", " self.r2: int = None\n", " self.s: int = 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 = int(Mod.random(order)) if self.r1 is None else self.r1\n", " r2 = int(Mod.random(order)) if self.r2 is None else self.r2\n", " s = int(Mod.random(1 << half_bits)) if self.s is None else self.s\n", " k1 = scalar % s\n", " k2 = scalar // s\n", " k1r1 = int(mod(k1,order)-mod(r1,order))\n", " k2r2 = int(mod(k2,order)-mod(r2,order))\n", " \n", " \n", " S = self.mult.multiply(s)\n", " KR1 = self.mult.multiply(k1r1)\n", " R1 = self.mult.multiply(r1)\n", " \n", " self.mult.init(self.params, S)\n", " KR2 = self.mult.multiply(k2r2)\n", " R2 = self.mult.multiply(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)" ] }, { "cell_type": "code", "execution_count": null, "id": "c2baaaef", "metadata": {}, "outputs": [], "source": [ "test_3n_random_scalar(ae1, 1000)" ] }, { "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": "adf2e610-fb35-45a5-aa20-d793b69d1ca4", "metadata": {}, "outputs": [], "source": [ "test_composite(ae1, 1000)" ] }, { "cell_type": "code", "execution_count": null, "id": "a8adab56-1cc1-4174-98ce-858a2a90def8", "metadata": {}, "outputs": [], "source": [ "test_composite(ae2, 1000)" ] }, { "cell_type": "code", "execution_count": null, "id": "f617263d-8d49-4dc0-9645-bb5388f0ef03", "metadata": {}, "outputs": [], "source": [ "test_k10(ae1, 100, k_range = range(8,11))" ] }, { "cell_type": "code", "execution_count": null, "id": "64af0ce4-e827-4b76-9372-b90b61fe5464", "metadata": {}, "outputs": [], "source": [ "test_k10(ae2, 100, k_range = range(8,11))" ] }, { "cell_type": "markdown", "id": "68dd0555-e536-4c55-814a-b13e8d8e8349", "metadata": {}, "source": [ "### Mul + Euclid" ] }, { "cell_type": "code", "execution_count": null, "id": "3afaaa43", "metadata": {}, "outputs": [], "source": [ "@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: int = None\n", " self.s: int = 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 = int(Mod.random(order)) if self.s is None else self.s\n", " r = int(Mod.random(1 << self.rand_bits_mul)) if self.r is None else self.r\n", " \n", " kr_inv = int(scalar * mod(int(r), order).inverse())\n", " \n", " k1 = kr_inv % s\n", " k2 = kr_inv // s\n", " \n", " R = self.mult.multiply(r)\n", " self.mult.init(self.params, R)\n", " \n", " K1 = self.mult.multiply(k1)\n", " \n", " S = self.mult.multiply(s)\n", " self.mult.init(self.params, S)\n", " K2 = self.mult.multiply(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: int = None\n", " self.r1: int = None\n", " self.r2: int = 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 = int(Mod.random(order)) if self.s is None else self.s\n", " \n", " r1 = int(Mod.random(1 << self.rand_bits_mul)) if self.r1 is None else self.r1\n", " r2 = int(Mod.random(1 << self.rand_bits_mul)) if self.r2 is None else self.r2\n", " \n", " k1 = scalar % s\n", " k2 = scalar // s\n", " \n", " kr1_inv = int(k1 * mod(int(r1), order).inverse())\n", " kr2_inv = int(k2 * mod(int(r2), order).inverse())\n", " \n", " R1 = self.mult.multiply(r1)\n", " S = self.mult.multiply(s)\n", " \n", " self.mult.init(self.params, R1)\n", " R1 = self.mult.multiply(kr1_inv)\n", " \n", " self.mult.init(self.params, S)\n", " R2 = self.mult.multiply(r2)\n", " \n", " self.mult.init(self.params, R2)\n", " R2 = self.mult.multiply(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, 1000)" ] }, { "cell_type": "code", "execution_count": null, "id": "228ad9c3", "metadata": {}, "outputs": [], "source": [ "test_3n_random_scalar(me2, 1000)" ] }, { "cell_type": "code", "execution_count": null, "id": "51edb972-54e0-4c2f-b3f4-45c29ba7d898", "metadata": {}, "outputs": [], "source": [ "test_3n_random_scalar(me3, 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)" ] }, { "cell_type": "code", "execution_count": null, "id": "270569f6-4a24-4752-b06a-887ccd823447", "metadata": {}, "outputs": [], "source": [ "test_composite(me1, 1000)" ] }, { "cell_type": "code", "execution_count": null, "id": "d59db17a-32c4-4aa2-8ff1-7991c2e1c9a9", "metadata": {}, "outputs": [], "source": [ "test_composite(me2, 1000)" ] }, { "cell_type": "code", "execution_count": null, "id": "268034b3-974f-480a-955f-bc32263c878a", "metadata": {}, "outputs": [], "source": [ "test_k10(me1, 100, k_range = range(8,11))" ] }, { "cell_type": "code", "execution_count": null, "id": "fe20f1a6-df47-4727-a997-333b64a2b03f", "metadata": {}, "outputs": [], "source": [ "test_k10(me2, 100, k_range = range(8,11))" ] } ], "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.13.5" } }, "nbformat": 4, "nbformat_minor": 5 }