From efa1b87eead8fb2374568ec7252ac87230ca1a1c Mon Sep 17 00:00:00 2001
From: J08nY
Date: Mon, 21 Apr 2025 12:26:00 +0200
Subject: Add more docs to simulation notebook.

---
 analysis/countermeasures/simulation.ipynb | 66 ++++++++++++++++++++++++++++---
 1 file changed, 61 insertions(+), 5 deletions(-)

diff --git a/analysis/countermeasures/simulation.ipynb b/analysis/countermeasures/simulation.ipynb
index 4f4c601..db66832 100644
--- a/analysis/countermeasures/simulation.ipynb
+++ b/analysis/countermeasures/simulation.ipynb
@@ -2315,7 +2315,11 @@
    "id": "867fedf2-0d95-4012-b57c-f2e3dcf0826c",
    "metadata": {},
    "source": [
-    "## Composite test"
+    "## Composite test\n",
+    "\n",
+    "The composite test works by observing the implementation operating on a composite order curve. The order of the curve is correctly presented to the implementation, so this test is not applicable to targets that check primality of the curve order.\n",
+    "\n",
+    "This test is able to detect the presence of multiplicative splitting, due to errors arising from trying to invert the random mask modulo a composite order. Based on the inversion algorithm used, different behaviors may be present. Importantly, the other countermeasures do not error on composite order curves."
    ]
   },
   {
@@ -2328,6 +2332,14 @@
     "composite = load_params_ectester(io.BytesIO(b\"0xc7a3ef9fa4ea63b537eedefc6bd52c3f35dc45be933d44270a1536c2ff9b6543,0x395f3675858362cbe7ac0d3e85708750aa42428368ae6ab1fda0d2a56255039b,0x61ca87695d4f6147b35975326eeee1a77f93226487315cd2419b4a1fe23f32d1,0x56e9a905d29f0f512cf709522bdd43a862d4e32c46268eec2f4c3fd9a70cb9d6,0xaf77a4ef604d33e3cf6c2ecaaa2913a5c51660e40365832ab98488950f3c348e,0xc7a3ef9fa4ea63b537eedefc6bd52c40f5e8e3bfe0f6dd05ac513edbcaa3cc47,0x01\"), \"projective\")"
    ]
   },
+  {
+   "cell_type": "markdown",
+   "id": "9f8c9bb9-64f4-4154-b148-8050de4468fc",
+   "metadata": {},
+   "source": [
+    "The order is 11-times a big prime."
+   ]
+  },
   {
    "cell_type": "code",
    "execution_count": 104,
@@ -2355,6 +2367,14 @@
     "print(f\"n:\\t0x{composite.order:x}\")"
    ]
   },
+  {
+   "cell_type": "markdown",
+   "id": "f0338115-84f8-44ee-bbb6-67a678537c0e",
+   "metadata": {},
+   "source": [
+    "The test consists of repeatedly performing the operation (ECDH, keygen, ECDSA) and observing whether the implementation returns an error and checking the validity of the result if it returns a result."
+   ]
+  },
   {
    "cell_type": "code",
    "execution_count": 120,
@@ -2384,6 +2404,14 @@
     "    print(f\"{errors} errors, {wrong} wrong results\")"
    ]
   },
+  {
+   "cell_type": "markdown",
+   "id": "0ebd90c6-2022-4d50-aca0-416c444418bb",
+   "metadata": {},
+   "source": [
+    "Scalar multipliers without countermeasures have no issues computing over composite order curves."
+   ]
+  },
   {
    "cell_type": "code",
    "execution_count": 74,
@@ -2425,7 +2453,8 @@
    "id": "54c9ef0f-bc9e-47b9-a7e4-3821c2a2f93a",
    "metadata": {},
    "source": [
-    "### Group scalar randomization"
+    "### Group scalar randomization\n",
+    "GSR has no issues computing over composite order curves."
    ]
   },
   {
@@ -2451,7 +2480,8 @@
    "id": "fea32f4e-dca2-4a5c-bd93-6580183e2d02",
    "metadata": {},
    "source": [
-    "### Multiplicative splitting"
+    "### Multiplicative splitting\n",
+    "When multiplicative splitting is used, the implementation may detect the element as not invertible and raise an error, as can be seen below when the extended euclid algorithm is used."
    ]
   },
   {
@@ -2478,6 +2508,14 @@
     "test_composite(msplit, 100)"
    ]
   },
+  {
+   "cell_type": "markdown",
+   "id": "15a742dd-d615-4103-8782-f7f26559ec8f",
+   "metadata": {},
+   "source": [
+    "If we keep using the extended euclid algorithm but instead make the implementation ignore the errors and return the results, we get wrong results for masks that were not invertible."
+   ]
+  },
   {
    "cell_type": "code",
    "execution_count": 115,
@@ -2498,6 +2536,14 @@
     "    test_composite(msplit, 100)"
    ]
   },
+  {
+   "cell_type": "markdown",
+   "id": "2082a2a6-7ab3-469b-a7e5-71c9e2e465d4",
+   "metadata": {},
+   "source": [
+    "This also shows that all of the `Mod` implementations in pyecsca use extended euclid algorithm for the inversion."
+   ]
+  },
   {
    "cell_type": "code",
    "execution_count": 116,
@@ -2561,6 +2607,14 @@
     "    test_composite(msplit, 100)"
    ]
   },
+  {
+   "cell_type": "markdown",
+   "id": "141687e0-d688-4431-91ea-010a66b4bcfe",
+   "metadata": {},
+   "source": [
+    "If we switch to inversion via Fermat's little theorem, we see that we always get wrong results."
+   ]
+  },
   {
    "cell_type": "code",
    "execution_count": 119,
@@ -2596,7 +2650,8 @@
    "id": "189d4f2a-1f0c-473f-b9fe-988bf4fbe9f7",
    "metadata": {},
    "source": [
-    "### Additive splitting"
+    "### Additive splitting\n",
+    "Additive splitting has no issues computing over composite order curves."
    ]
   },
   {
@@ -2622,7 +2677,8 @@
    "id": "287b7945-c538-4b40-a65b-1081f68107ab",
    "metadata": {},
    "source": [
-    "### Euclidean splitting"
+    "### Euclidean splitting\n",
+    "Euclidean splitting has no issues computing over composite order curves."
    ]
   },
   {
-- 
cgit v1.2.3-70-g09d2