Add RPA-RE notebook.

1 files changed, 234 insertions, 0 deletions

diff --git a/re/rpa.ipynb b/re/rpa.ipynb
new file mode 100644
index 0000000..316a68b
--- /dev/null
+++ b/re/rpa.ipynb
@@ -0,0 +1,234 @@
+{
+ "cells": [
+  {
+   "cell_type": "markdown",
+   "id": "66c30004-cd2c-4d34-9999-f33f9e6fd5e9",
+   "metadata": {},
+   "source": [
+    "# RPA-based reverse-engineering"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": null,
+   "id": "11a5f41d-1471-49c3-ba7c-ac87470a31d0",
+   "metadata": {},
+   "outputs": [],
+   "source": [
+    "from collections import Counter\n",
+    "\n",
+    "from pyecsca.ec.key_generation import KeyGeneration\n",
+    "from pyecsca.ec.key_agreement import ECDH_SHA1\n",
+    "from pyecsca.ec.model import ShortWeierstrassModel\n",
+    "from pyecsca.ec.coordinates import AffineCoordinateModel\n",
+    "from pyecsca.ec.curve import EllipticCurve\n",
+    "from pyecsca.ec.params import DomainParameters\n",
+    "from pyecsca.ec.point import Point\n",
+    "from pyecsca.ec.mod import Mod\n",
+    "from pyecsca.ec.mult import *\n",
+    "from pyecsca.ec.context import DefaultContext, local\n",
+    "from pyecsca.sca.re.rpa import MultipleContext, rpa_distinguish"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": null,
+   "id": "194fff59-1c4b-473a-9ffc-99b256aecc24",
+   "metadata": {},
+   "outputs": [],
+   "source": [
+    "model = ShortWeierstrassModel()\n",
+    "coordsaff = AffineCoordinateModel(model)\n",
+    "coords = model.coordinates[\"projective\"]\n",
+    "add = coords.formulas[\"add-2007-bl\"]  # The formulas are irrelevant for this method\n",
+    "dbl = coords.formulas[\"dbl-2007-bl\"]\n",
+    "neg = coords.formulas[\"neg\"]\n",
+    "\n",
+    "# A 64-bit prime order curve for testing things out\n",
+    "p = 0xc50de883f0e7b167\n",
+    "a = Mod(0x4833d7aa73fa6694, p)\n",
+    "b = Mod(0xa6c44a61c5323f6a, p)\n",
+    "gx = Mod(0x5fd1f7d38d4f2333, p)\n",
+    "gy = Mod(0x21f43957d7e20ceb, p)\n",
+    "n = 0xc50de885003b80eb\n",
+    "h = 1\n",
+    "\n",
+    "# A (0, y) RPA point on the above curve, in affine coords.\n",
+    "P0_aff = Point(coordsaff, x=Mod(0, p), y=Mod(0x1742befa24cd8a0d, p))\n",
+    "\n",
+    "infty = Point(coords, X=Mod(0, p), Y=Mod(1, p), Z=Mod(0, p))\n",
+    "g = Point(coords, X=gx, Y=gy, Z=Mod(1, p))\n",
+    "\n",
+    "curve = EllipticCurve(model, coords, p, infty, dict(a=a,b=b))\n",
+    "params = DomainParameters(curve, g, n, h)"
+   ]
+  },
+  {
+   "cell_type": "markdown",
+   "id": "29fb8683-bcad-4a3e-869b-95f0e4b7bde3",
+   "metadata": {},
+   "source": [
+    "First select a bunch of multipliers. We will be trying to distinguish among these."
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": null,
+   "id": "febb198f-4370-4abd-8edc-17c5c1da8d0f",
+   "metadata": {},
+   "outputs": [],
+   "source": [
+    "multipliers = []\n",
+    "multipliers.append(LTRMultiplier(add, dbl, None, False, True, True))\n",
+    "multipliers.append(LTRMultiplier(add, dbl, None, True, True, True))\n",
+    "multipliers.append(RTLMultiplier(add, dbl, None, False, True))\n",
+    "multipliers.append(RTLMultiplier(add, dbl, None, True, True))\n",
+    "multipliers.append(SimpleLadderMultiplier(add, dbl, None, True, True))\n",
+    "multipliers.append(BinaryNAFMultiplier(add, dbl, neg, None, True))\n",
+    "multipliers.append(WindowNAFMultiplier(add, dbl, neg, 3, None, True))\n",
+    "multipliers.append(WindowNAFMultiplier(add, dbl, neg, 4, None, True))"
+   ]
+  },
+  {
+   "cell_type": "markdown",
+   "id": "bea70d56-1359-423b-9273-fae5877f6400",
+   "metadata": {},
+   "source": [
+    "Then select a random scalar and simulate computation using all of the multipliers, track the multiples, print the projective and affine results."
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": null,
+   "id": "44e7e2e9-e0ad-4c8d-8605-af68f73d73e2",
+   "metadata": {},
+   "outputs": [],
+   "source": [
+    "scalar = 0b1000000000000000000000000000000000000000000000000\n",
+    "scalar = 0b1111111111111111111111111111111111111111111111111\n",
+    "scalar = 0b1010101010101010101010101010101010101010101010101\n",
+    "scalar = 0b1111111111111111111111110000000000000000000000000\n",
+    "scalar = 123456789123456789\n",
+    "# multiples is a mapping from a multiple (integer) to a set of scalar multipliers that compute said multiple when doing [scalar]\n",
+    "multiples = {}\n",
+    "\n",
+    "for mult in multipliers:\n",
+    "    print(repr(mult))\n",
+    "    with local(MultipleContext()) as ctx:\n",
+    "        mult.init(params, g)\n",
+    "        res = mult.multiply(scalar)\n",
+    "    print(res, res.to_affine())\n",
+    "    for m in ctx.points.values():\n",
+    "        s = multiples.setdefault(m, set())\n",
+    "        s.add(mult)\n",
+    "    print()\n"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": null,
+   "id": "a7fb8a3f-7938-493b-88dc-582ba4d8959d",
+   "metadata": {},
+   "outputs": [],
+   "source": [
+    "# Pick a multiple \"k\", invert it mod n, and do [k^-1]P0 to obtain a point P0_target,\n",
+    "# such that, [k]P0_target = P0 and P0 has a zero coordinate.\n",
+    "k = 23547513796\n",
+    "kinv = Mod(k, n).inverse()\n",
+    "P0_target = curve.affine_multiply(P0_aff, int(kinv)).to_model(coords, curve)\n",
+    "\n",
+    "print(\"Original P0\", P0_aff)\n",
+    "print(\"P0_target  \", P0_target.to_affine())\n",
+    "print(\"Verify P0  \", curve.affine_multiply(P0_target.to_affine(), k))"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": null,
+   "id": "8113cb3f-dc06-4cb7-955c-11cedb4fbdd7",
+   "metadata": {},
+   "outputs": [],
+   "source": [
+    "# Now go over the multipliers with P0_target and the original scalar as input.\n",
+    "# Then look whether a zero coordinate point was computed.\n",
+    "# Also look at whether the multiple \"k\" was computed. These two should be the same.\n",
+    "\n",
+    "for mult in multipliers:\n",
+    "    print(mult.__class__.__name__)\n",
+    "    with local(MultipleContext()) as ctx:\n",
+    "        mult.init(params, P0_target)\n",
+    "        res = mult.multiply(scalar)\n",
+    "    print(\"\\tzero present     \", any(map(lambda P: P.X == 0, ctx.points.keys())))\n",
+    "    print(\"\\tmultiple computed\", k in ctx.points.values())\n",
+    "    print()"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": null,
+   "id": "67d7705c-6a41-47d9-ad1e-23ea549aaf00",
+   "metadata": {},
+   "outputs": [],
+   "source": [
+    "# Now lets look at the relation of multiples to multipliers\n",
+    "for multiple, mults in multiples.items():\n",
+    "    print(multiple, [mult.__class__.__name__ for mult in mults])"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": null,
+   "id": "9bb61ac5-d837-4287-a5de-a9a63c346acf",
+   "metadata": {},
+   "outputs": [],
+   "source": [
+    "def simulated_oracle(scalar, affine_point):\n",
+    "    real_mult = BinaryNAFMultiplier(add, dbl, neg, None, True)\n",
+    "    point = affine_point.to_model(params.curve.coordinate_model, params.curve)\n",
+    "    with local(MultipleContext()) as ctx:\n",
+    "        real_mult.init(params, point)\n",
+    "        real_mult.multiply(scalar)\n",
+    "    return any(map(lambda P: P.X == 0 or P.Y == 0, ctx.points.keys()))"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": null,
+   "id": "265eb13a-6028-4fde-9c3f-cc23768ba63e",
+   "metadata": {},
+   "outputs": [],
+   "source": [
+    "rpa_distinguish(params, multipliers, simulated_oracle)"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": null,
+   "id": "96bec03e-5397-440b-9e8c-81ba5253921b",
+   "metadata": {},
+   "outputs": [],
+   "source": []
+  }
+ ],
+ "metadata": {
+  "kernelspec": {
+   "display_name": "Python 3 (ipykernel)",
+   "language": "python",
+   "name": "python3"
+  },
+  "language_info": {
+   "codemirror_mode": {
+    "name": "ipython",
+    "version": 3
+   },
+   "file_extension": ".py",
+   "mimetype": "text/x-python",
+   "name": "python",
+   "nbconvert_exporter": "python",
+   "pygments_lexer": "ipython3",
+   "version": "3.11.3"
+  }
+ },
+ "nbformat": 4,
+ "nbformat_minor": 5
+}