2 files changed, 207 insertions, 1 deletions

diff --git a/analysis/scalarmults/bruteforce.ipynb b/analysis/scalarmults/bruteforce.ipynb
new file mode 100644
index 0000000..b0f6b5b
--- /dev/null
+++ b/analysis/scalarmults/bruteforce.ipynb
@@ -0,0 +1,206 @@
+{
+ "cells": [
+  {
+   "cell_type": "code",
+   "execution_count": null,
+   "id": "25781c57-7d4f-486c-bb2a-976145e62320",
+   "metadata": {},
+   "outputs": [],
+   "source": [
+    "import io\n",
+    "from hashlib import sha1\n",
+    "from tqdm.auto import tqdm, trange\n",
+    "\n",
+    "from pyecsca.ec.params import DomainParameters, get_params, load_params_ectester\n",
+    "from pyecsca.ec.mult import LTRMultiplier\n",
+    "from pyecsca.ec.mod import mod, Mod\n",
+    "from pyecsca.ec.point import Point\n",
+    "from pyecsca.ec.model import ShortWeierstrassModel\n",
+    "from pyecsca.ec.coordinates import AffineCoordinateModel\n",
+    "from pyecsca.ec.key_agreement import ECDH as ECDHBase\n",
+    "from pyecsca.misc.utils import TaskExecutor"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": null,
+   "id": "d156e478-740b-428c-9700-0087a87a6442",
+   "metadata": {},
+   "outputs": [],
+   "source": [
+    "params = load_params_ectester(io.BytesIO(b\"0xa9fa3419aca88bade2cba14e317816c79d52481d463dc9bcb12c37f45aa3b4e1,0x2ea3bfe6659f8e035735349b91fbfa2baf0cf8e640315f0fe03c1136813dec99,0x2b07c518e04b02158651e3dbbef7720015dd496bf15af02f8439f8e1503b8370,0x16a1e99de6f5ac372c1565a232f9bd3fc602c70d8edb6a30e604f391750ad7ee,0x2e311109d9f55a54977e288bf19a7411353e80b2d4c08c4f80a87105889d4a05,0xa9fa3419aca88bade2cba14e317816c6828910c6ce04fcd2a2e857d66aa4d6d3,0x01\"), \"projective\")"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": null,
+   "id": "c46c4fae-ae24-4518-b3b7-c788e689d2b6",
+   "metadata": {},
+   "outputs": [],
+   "source": [
+    "model = ShortWeierstrassModel()\n",
+    "coords = model.coordinates[\"projective\"]\n",
+    "affine = AffineCoordinateModel(model)\n",
+    "add = coords.formulas[\"add-2015-rcb\"]\n",
+    "dbl = coords.formulas[\"dbl-2015-rcb\"]\n",
+    "mult = LTRMultiplier(add, dbl)"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": null,
+   "id": "678439db-36ee-4ede-af95-aa6d39f4ec6a",
+   "metadata": {},
+   "outputs": [],
+   "source": [
+    "priv = 0x2bc345cc91f6b17ca180beb2b5de274e1a384e9dc2f40de02eae4141a91f39d5\n",
+    "pub = Point(affine,\n",
+    "            x=mod(0x90fb04b1af19e8e20396ac052f260a9fb5f736b97e3cd4af08fe81a1e75dac6d, params.curve.prime),\n",
+    "            y=mod(0x2302bcf700d3d5899f04d0c7441f5017c9758bfafd6ce15dbe36fb4eea76baec, params.curve.prime))\n",
+    "secret = bytes.fromhex(\"72f7a06b7d934a9370e66f37e3745c206589d205\")"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": null,
+   "id": "30bf4a1d-dd5b-4437-b9d8-8f0ecc49beda",
+   "metadata": {},
+   "outputs": [],
+   "source": [
+    "base = params.curve.affine_multiply(pub, priv)\n",
+    "pub92 = params.curve.affine_multiply(pub, 92)"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": null,
+   "id": "3a83ad43-b556-4d13-ad02-0d3b05884d62",
+   "metadata": {},
+   "outputs": [],
+   "source": [
+    "class ECDH(ECDHBase):\n",
+    "    def __init__(self, params: DomainParameters, pubkey: Point, privkey: Mod,\n",
+    "                 base: Point, i: int, pub92: Point):\n",
+    "        self.hash_algo = sha1\n",
+    "        self.params = params\n",
+    "        self.pubkey = pubkey\n",
+    "        self.privkey = privkey\n",
+    "        self.base = base\n",
+    "        self.i = i\n",
+    "        self.pub92 = pub92\n",
+    "        self.point = params.curve.affine_add(base, params.curve.affine_multiply(pub92, i))\n",
+    "\n",
+    "    def advance(self, by: int = 1):\n",
+    "        if by == 1:\n",
+    "            self.point = params.curve.affine_add(self.point, pub92)\n",
+    "        else:\n",
+    "            multiple = params.curve.affine_multiply(pub92, by)\n",
+    "            self.point = params.curve.affine_add(self.point, multiple)\n",
+    "        self.i += by\n",
+    "    \n",
+    "    def perform_raw(self) -> Point:\n",
+    "        return self.point"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": null,
+   "id": "bb96993e-6ed7-44fb-a86c-851abc10c239",
+   "metadata": {},
+   "outputs": [],
+   "source": [
+    "def split_ranges(bound, splits):\n",
+    "    \"\"\"\n",
+    "    Splits the range [0, bound) into `splits` equally sized ranges.\n",
+    "\n",
+    "    Returns:\n",
+    "        List of (start, end) tuples, where each tuple represents a range [start, end)\n",
+    "    \"\"\"\n",
+    "    ranges = []\n",
+    "    chunk_size = bound // splits\n",
+    "    remainder = bound % splits\n",
+    "    start = 0\n",
+    "    for i in range(splits):\n",
+    "        end = start + chunk_size + (1 if i < remainder else 0)\n",
+    "        ranges.append((start, end))\n",
+    "        start = end\n",
+    "    return ranges"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": null,
+   "id": "e5097396-0f77-45e7-94cb-8175f9d50001",
+   "metadata": {},
+   "outputs": [],
+   "source": [
+    "def process_split(split, params, pub, priv, base, pub92, secret):\n",
+    "    start, end = split\n",
+    "    e = ECDH(params, pub, mod(priv, params.order), base, start, pub92)\n",
+    "    for i in range(*split):\n",
+    "        out = e.perform()\n",
+    "        if out == secret:\n",
+    "            break\n",
+    "        e.advance()\n",
+    "    else:\n",
+    "        return None\n",
+    "    return e.i"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": null,
+   "id": "a0cd1c61-2669-4444-bef6-bb74a11eb2a1",
+   "metadata": {},
+   "outputs": [],
+   "source": [
+    "num_workers = 10\n",
+    "splits = 10000\n",
+    "bound = 2**32\n",
+    "with TaskExecutor(max_workers=num_workers) as pool:\n",
+    "    for split in tqdm(split_ranges(bound, splits), desc=\"Submitting.\"):\n",
+    "        pool.submit_task(split,\n",
+    "                         process_split,\n",
+    "                         split, params, pub, priv, base, pub92, secret)\n",
+    "    for split, future in tqdm(pool.as_completed(), desc=\"Computing secrets.\", total=len(pool.tasks)):\n",
+    "        if error := future.exception():\n",
+    "            print(\"Error!\", error)\n",
+    "            continue\n",
+    "        res = future.result()\n",
+    "        if res is not None:\n",
+    "            print(split)\n",
+    "            print(f\"Found {rest}\")\n",
+    "            break"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": null,
+   "id": "0108cb80-e307-415d-9c94-095197fd9054",
+   "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.13.5"
+  }
+ },
+ "nbformat": 4,
+ "nbformat_minor": 5
+}
diff --git a/analysis/scalarmults/simulate.ipynb b/analysis/scalarmults/simulate.ipynb
index 47a8c73..93d016a 100644
--- a/analysis/scalarmults/simulate.ipynb
+++ b/analysis/scalarmults/simulate.ipynb
@@ -256,7 +256,7 @@
    "name": "python",
    "nbconvert_exporter": "python",
    "pygments_lexer": "ipython3",
-   "version": "3.12.3"
+   "version": "3.13.5"
   }
  },
  "nbformat": 4,