Cleanup and document more ZVP stuff.

1 files changed, 42 insertions, 6 deletions

diff --git a/re/zvp.ipynb b/re/zvp.ipynb
index 3835be1..072b0aa 100644
--- a/re/zvp.ipynb
+++ b/re/zvp.ipynb
@@ -42,7 +42,7 @@
     "from pyecsca.ec.mult import LTRMultiplier, AccumulationOrder\n",
     "from pyecsca.misc.cfg import getconfig\n",
     "from pyecsca.ec.error import NonInvertibleError, UnsatisfiedAssumptionError\n",
-    "from pyecsca.sca.re.zvp import unroll_formula, compute_factor_set, zvp_points, addition_chain, precomp_zvp_points"
+    "from pyecsca.sca.re.zvp import unroll_formula, compute_factor_set, zvp_points, addition_chain"
    ]
   },
   {
@@ -190,7 +190,7 @@
     "    \"\"\"[{\"field\":{\"p\":\"0xb3c2beca75d66de3\"},\"a\":\"0x0000000000000000\",\"b\":\"0x46069225826b51aa\",\"order\":\"0xb3c2bec95881b695\",\"subgroups\":[{\"x\":\"0x81500c226efa0d5a\",\"y\":\"0x674e09d296452eee\",\"order\":\"0xb3c2bec95881b695\",\"cofactor\":\"0x1\",\"points\":[{\"x\":\"0x81500c226efa0d5a\",\"y\":\"0x674e09d296452eee\",\"order\":\"0xb3c2bec95881b695\"}]}]}]\"\"\",\n",
     "    \"\"\"[{\"field\":{\"p\":\"0xd6097c1ce207aae7\"},\"a\":\"0x0000000000000000\",\"b\":\"0x7adaab54e7dfd564\",\"order\":\"0xd6097c1b407eb413\",\"subgroups\":[{\"x\":\"0x151da8fb1f83201e\",\"y\":\"0x8bfeb90ec1177a91\",\"order\":\"0xd6097c1b407eb413\",\"cofactor\":\"0x1\",\"points\":[{\"x\":\"0x151da8fb1f83201e\",\"y\":\"0x8bfeb90ec1177a91\",\"order\":\"0xd6097c1b407eb413\"}]}]}]\"\"\",\n",
     "    \"\"\"[{\"field\":{\"p\":\"0x97a3e2d617a2309d\"},\"a\":\"0x0000000000000000\",\"b\":\"0x7f311cba46652247\",\"order\":\"0x97a3e2d712ffd715\",\"subgroups\":[{\"x\":\"0x46d725812af15870\",\"y\":\"0x727f88365dbd0e80\",\"order\":\"0x97a3e2d712ffd715\",\"cofactor\":\"0x1\",\"points\":[{\"x\":\"0x46d725812af15870\",\"y\":\"0x727f88365dbd0e80\",\"order\":\"0x97a3e2d712ffd715\"}]}]}]\"\"\",\n",
-    "    \"\"\"[{\"field\":{\"p\":\"0xd43c9a4cd686a599\"},\"a\":\"0x0000000000000000\",\"b\":\"0xc795a256566ee407\",\"order\":\"0xd43c9a4cb750f1a5\",\"subgroups\":[{\"x\":\"0x4f1fcb572419ce5c\",\"y\":\"0x5f54d643e16732e4\",\"order\":\"0xd43c9a4cb750f1a5\",\"cofactor\":\"0x1\",\"points\":[{\"x\":\"0x4f1fcb572419ce5c\",\"y\":\"0x5f54d643e16732e4\",\"order\":\"0xd43c9a4cb750f1a5\"}]}]}]\"\"\",\n",
+    "    \"\"\"[{\"field\":{\"p\":\"0xd8d7f39f545a5da7\"},\"a\":\"0x0000000000000000\",\"b\":\"0x09097ddcd4be8d55\",\"order\":\"0xd8d7f3a0c4115b4b\",\"subgroups\":[{\"x\":\"0xc5c771a9827a3251\",\"y\":\"0x64bf52041ac05b23\",\"order\":\"0xd8d7f3a0c4115b4b\",\"cofactor\":\"0x1\",\"points\":[{\"x\":\"0xc5c771a9827a3251\",\"y\":\"0x64bf52041ac05b23\",\"order\":\"0xd8d7f3a0c4115b4b\"}]}]}]\"\"\",\n",
     "    \"\"\"[{\"field\":{\"p\":\"0x847de883ab4fbf4d\"},\"a\":\"0x0000000000000000\",\"b\":\"0x09866366b3b45c2d\",\"order\":\"0x847de8837e6d4477\",\"subgroups\":[{\"x\":\"0x62fd7b4bc7c9acb4\",\"y\":\"0x2d0942774607106b\",\"order\":\"0x847de8837e6d4477\",\"cofactor\":\"0x1\",\"points\":[{\"x\":\"0x62fd7b4bc7c9acb4\",\"y\":\"0x2d0942774607106b\",\"order\":\"0x847de8837e6d4477\"}]}]}]\"\"\",\n",
     "    \"\"\"[{\"field\":{\"p\":\"0xf0d617c3c47b7c77\"},\"a\":\"0x0000000000000000\",\"b\":\"0xd856b3dcb95764a2\",\"order\":\"0xf0d617c5512cec85\",\"subgroups\":[{\"x\":\"0xeaf9b352a3daac45\",\"y\":\"0x4e4e557f9fc3febc\",\"order\":\"0xf0d617c5512cec85\",\"cofactor\":\"0x1\",\"points\":[{\"x\":\"0xeaf9b352a3daac45\",\"y\":\"0x4e4e557f9fc3febc\",\"order\":\"0xf0d617c5512cec85\"}]}]}]\"\"\",\n",
     "    \"\"\"[{\"field\":{\"p\":\"0xce920b656c80b373\"},\"a\":\"0x0000000000000000\",\"b\":\"0xb4a07dfae71ddc62\",\"order\":\"0xce920b65eee38015\",\"subgroups\":[{\"x\":\"0x7895c02b3c5205b5\",\"y\":\"0x2926be6446b98d62\",\"order\":\"0xce920b65eee38015\",\"cofactor\":\"0x1\",\"points\":[{\"x\":\"0x7895c02b3c5205b5\",\"y\":\"0x2926be6446b98d62\",\"order\":\"0xce920b65eee38015\"}]}]}]\"\"\",\n",
@@ -264,6 +264,7 @@
     "    for formula_group, formula_class in zip(formula_groups, formula_classes):\n",
     "        for formula in formula_group:\n",
     "            fset = compute_factor_set(formula, filter_nonhomo=False)\n",
+    "            # Fix the factor set polynomials for the case of doubling.\n",
     "            if formula_class == DoublingFormula:\n",
     "                new_fset = set()\n",
     "                for poly in fset:\n",
@@ -279,6 +280,8 @@
     "\n",
     "polynomials = {}\n",
     "for coord_name, coords in model.coordinates.items():\n",
+    "    coord_adds = 0\n",
+    "    coord_dbls = 0\n",
     "    for chain, affine_params in zip(chains, curves):\n",
     "        try:\n",
     "            params = affine_params.to_coords(coords)\n",
@@ -296,7 +299,10 @@
     "        polynomials[params] = {\n",
     "            \"add\": add_polynomials,\n",
     "            \"dbl\": dbl_polynomials\n",
-    "        }"
+    "        }\n",
+    "        coord_adds += len(add_polynomials)\n",
+    "        coord_dbls += len(dbl_polynomials)\n",
+    "    print(f\"Got {coord_adds} add polys and {coord_dbls} dbl polys for {coord_name}\")"
    ]
   },
   {
@@ -310,7 +316,7 @@
     "bound = 100\n",
     "\n",
     "all_points = set()\n",
-    "with ProcessPoolExecutor(max_workers=10) as pool:\n",
+    "with ProcessPoolExecutor(max_workers=20) as pool:\n",
     "    futures = []\n",
     "    args = []\n",
     "    for coord_name, coords in model.coordinates.items():\n",
@@ -387,6 +393,7 @@
     "            except UnsatisfiedAssumptionError:\n",
     "                continue\n",
     "        trace = []\n",
+    "        \n",
     "        def callback(action):\n",
     "            if isinstance(action, FormulaAction):\n",
     "                for intermediate in action.op_results:\n",
@@ -562,6 +569,14 @@
    ]
   },
   {
+   "cell_type": "markdown",
+   "id": "e1d50275-2917-4882-be29-28c67e58f23a",
+   "metadata": {},
+   "source": [
+    "Build two trees, one with the filtered factor sets and one with unfilitered factor sets (with non-homogenous polynomials present)."
+   ]
+  },
+  {
    "cell_type": "code",
    "execution_count": null,
    "id": "94f611c9-4570-4674-b1f3-902d06962bfa",
@@ -597,6 +612,16 @@
    ]
   },
   {
+   "cell_type": "markdown",
+   "id": "a60a099e-cb8f-4e9f-9b94-591957908d55",
+   "metadata": {},
+   "source": [
+    "As we can see, our technique is able to distinguish formulas better than the filtered factor sets, but not better than unfiltered factor sets.\n",
+    "\n",
+    "We can further analyze where unused possibilities of distinguishing remain but expanding the tree using the distinguishing map built out of factor sets."
+   ]
+  },
+  {
    "cell_type": "code",
    "execution_count": null,
    "id": "366ba814-c8ae-4567-8e26-27130f9dbfc9",
@@ -618,16 +643,27 @@
    ]
   },
   {
+   "cell_type": "markdown",
+   "id": "dc60901f-694b-47f3-b607-ef04646f41b9",
+   "metadata": {},
+   "source": [
+    "The tree improves its distinguishing abilities, however, upon closer analysis, the polynomials that it uses to further split the configurations never actually have solutions on the curves with the assumed properties (e.g. `a = 0`)."
+   ]
+  },
+  {
    "cell_type": "code",
    "execution_count": null,
    "id": "b78f99d6-46b9-44bb-b9b4-5df7fc4fa990",
-   "metadata": {},
+   "metadata": {
+    "scrolled": true
+   },
    "outputs": [],
    "source": [
     "p = set()\n",
     "for node in PreOrderIter(expanded.root):\n",
     "    if isinstance(node.dmap_input, Poly):\n",
     "        print(node.dmap_input, [len(child.cfgs) for child in node.children])\n",
+    "        print(\"\\t\", \"\\n\\t\".join(\", \".join(f\"({cfg[0]} {cfg[1]})\" for cfg in child.cfgs) for child in node.children))\n",
     "        p.add(node.dmap_input)\n",
     "print(\"---\")\n",
     "for pp in p:\n",
@@ -640,7 +676,7 @@
   {
    "cell_type": "code",
    "execution_count": null,
-   "id": "4fcc5071-72d7-45b3-a854-8d0a087bc3aa",
+   "id": "d327e346-9c82-4e50-9357-ba66b3c511ed",
    "metadata": {},
    "outputs": [],
    "source": []