Update ZVP notebook with factor sets.

1 files changed, 73 insertions, 116 deletions

diff --git a/re/zvp.ipynb b/re/zvp.ipynb
index 1df4dbb..080753a 100644
--- a/re/zvp.ipynb
+++ b/re/zvp.ipynb
@@ -10,27 +10,34 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 1,
+   "execution_count": null,
    "id": "17a9e580-5f1e-45c9-8afd-fc35e833b0b0",
    "metadata": {},
    "outputs": [],
    "source": [
     "import sympy\n",
-    "from sympy import FF, sympify, symbols\n",
+    "from sympy import FF, sympify, symbols, Poly, Monomial\n",
+    "from collections import Counter\n",
+    "import tabulate\n",
+    "from IPython.display import HTML, display\n",
+    "from tqdm.notebook import tqdm\n",
     "\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.formula import FormulaAction\n",
     "from pyecsca.ec.point import Point\n",
-    "from pyecsca.ec.mod import Mod, SymbolicMod\n",
+    "from pyecsca.ec.mod import Mod\n",
     "from pyecsca.ec.context import DefaultContext, local\n",
-    "from pyecsca.misc.cfg import getconfig"
+    "from pyecsca.ec.mult import LTRMultiplier, AccumulationOrder\n",
+    "from pyecsca.misc.cfg import getconfig\n",
+    "from pyecsca.sca.re.zvp import unroll_formula, compute_factor_set, zvp_points"
    ]
   },
   {
    "cell_type": "code",
-   "execution_count": 2,
+   "execution_count": null,
    "id": "d8ea0c4d-86e1-46af-ac20-569e6ef5439d",
    "metadata": {},
    "outputs": [],
@@ -41,7 +48,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 3,
+   "execution_count": null,
    "id": "8de124f1-9498-4e55-8b7f-1bd291ccf3fe",
    "metadata": {},
    "outputs": [],
@@ -73,147 +80,97 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 25,
-   "id": "e91d81b6-a3ce-4b1f-8ace-3e55e0d6fadf",
+   "execution_count": null,
+   "id": "7bb4b36e-9efc-4a4b-a8c5-aad74c0db374",
    "metadata": {},
    "outputs": [],
    "source": [
-    "# add\n",
-    "# TODO: this is wrooooong, needs to have X1 and X2...\n",
-    "P1 = Point(coords, **{str(var): SymbolicMod(symbols(var + \"1\"), p) for var in coords.variables})\n",
-    "P2 = Point(coords, **{str(var): SymbolicMod(symbols(var + \"2\"), p) for var in coords.variables})\n",
-    "parameters = {str(var): SymbolicMod(var, p) for var in symbols(model.parameter_names)}\n",
-    "with local(DefaultContext()) as ctx:\n",
-    "    res = add(p, P1, P2, **parameters)[0]"
+    "adds = list(filter(lambda formula: formula.name.startswith(\"add\"), coords.formulas.values()))"
    ]
   },
   {
    "cell_type": "code",
-   "execution_count": 20,
-   "id": "7f4c7416-49a9-4fe5-a1ff-38f2cb6c5815",
+   "execution_count": null,
+   "id": "3be76ec7-775e-465b-8528-713374b95344",
    "metadata": {},
-   "outputs": [
-    {
-     "data": {
-      "text/latex": [
-       "$\\displaystyle 2 Z_{1} Z_{2} \\left(Y_{1} Z_{2} + Y_{2} Z_{1}\\right) \\left(Z_{1}^{2} Z_{2}^{2} \\left(Y_{1} Z_{2} + Y_{2} Z_{1}\\right)^{4} + \\left(X_{1} Z_{2} + X_{2} Z_{1}\\right)^{2} - \\left(X_{1} Z_{2} + X_{2} Z_{1} + Z_{1} Z_{2} \\left(Y_{1} Z_{2} + Y_{2} Z_{1}\\right)^{2}\\right)^{2} + 2 \\left(- X_{1} X_{2} Z_{1} Z_{2} + Z_{1}^{2} Z_{2}^{2} a + \\left(X_{1} Z_{2} + X_{2} Z_{1}\\right)^{2}\\right)^{2}\\right)$"
-      ],
-      "text/plain": [
-       "2*Z1*Z2*(Y1*Z2 + Y2*Z1)*(Z1**2*Z2**2*(Y1*Z2 + Y2*Z1)**4 + (X1*Z2 + X2*Z1)**2 - (X1*Z2 + X2*Z1 + Z1*Z2*(Y1*Z2 + Y2*Z1)**2)**2 + 2*(-X1*X2*Z1*Z2 + Z1**2*Z2**2*a + (X1*Z2 + X2*Z1)**2)**2)"
-      ]
-     },
-     "execution_count": 20,
-     "metadata": {},
-     "output_type": "execute_result"
-    }
-   ],
+   "outputs": [],
    "source": [
-    "res.X.x"
+    "gens = None\n",
+    "factor_sets = {}\n",
+    "for add in adds:\n",
+    "    factor_set = compute_factor_set(add, affine=True)\n",
+    "    factor_sets[add.name] = factor_set"
    ]
   },
   {
    "cell_type": "code",
-   "execution_count": 21,
-   "id": "89a34db8-81d2-4741-ae0a-5268b46d0974",
+   "execution_count": null,
+   "id": "354be601-f3d4-41d9-ac95-e3d146bf7859",
    "metadata": {},
-   "outputs": [
-    {
-     "data": {
-      "text/latex": [
-       "$\\displaystyle - 2 Z_{1}^{2} Z_{2}^{2} \\left(Y_{1} Z_{2} + Y_{2} Z_{1}\\right)^{4} + \\left(- X_{1} X_{2} Z_{1} Z_{2} + Z_{1}^{2} Z_{2}^{2} a + \\left(X_{1} Z_{2} + X_{2} Z_{1}\\right)^{2}\\right) \\left(- 3 Z_{1}^{2} Z_{2}^{2} \\left(Y_{1} Z_{2} + Y_{2} Z_{1}\\right)^{4} - 3 \\left(X_{1} Z_{2} + X_{2} Z_{1}\\right)^{2} + 3 \\left(X_{1} Z_{2} + X_{2} Z_{1} + Z_{1} Z_{2} \\left(Y_{1} Z_{2} + Y_{2} Z_{1}\\right)^{2}\\right)^{2} - 4 \\left(- X_{1} X_{2} Z_{1} Z_{2} + Z_{1}^{2} Z_{2}^{2} a + \\left(X_{1} Z_{2} + X_{2} Z_{1}\\right)^{2}\\right)^{2}\\right)$"
-      ],
-      "text/plain": [
-       "-2*Z1**2*Z2**2*(Y1*Z2 + Y2*Z1)**4 + (-X1*X2*Z1*Z2 + Z1**2*Z2**2*a + (X1*Z2 + X2*Z1)**2)*(-3*Z1**2*Z2**2*(Y1*Z2 + Y2*Z1)**4 - 3*(X1*Z2 + X2*Z1)**2 + 3*(X1*Z2 + X2*Z1 + Z1*Z2*(Y1*Z2 + Y2*Z1)**2)**2 - 4*(-X1*X2*Z1*Z2 + Z1**2*Z2**2*a + (X1*Z2 + X2*Z1)**2)**2)"
-      ]
-     },
-     "execution_count": 21,
-     "metadata": {},
-     "output_type": "execute_result"
-    }
-   ],
+   "outputs": [],
    "source": [
-    "res.Y.x"
+    "c = Counter()\n",
+    "for factor_set in factor_sets.values():\n",
+    "    for poly in factor_set:\n",
+    "        c[poly] += 1\n",
+    "print(c)"
    ]
   },
   {
    "cell_type": "code",
-   "execution_count": 22,
-   "id": "8d3db4ac-95fb-4483-a572-265744461daf",
+   "execution_count": null,
+   "id": "e65c4ab0-a9fa-479b-b109-67968fd67c1c",
    "metadata": {},
-   "outputs": [
-    {
-     "data": {
-      "text/latex": [
-       "$\\displaystyle 4 Z_{1}^{3} Z_{2}^{3} \\left(Y_{1} Z_{2} + Y_{2} Z_{1}\\right)^{3}$"
-      ],
-      "text/plain": [
-       "4*Z1**3*Z2**3*(Y1*Z2 + Y2*Z1)**3"
-      ]
-     },
-     "execution_count": 22,
-     "metadata": {},
-     "output_type": "execute_result"
-    }
-   ],
+   "outputs": [],
    "source": [
-    "res.Z.x"
+    "def simulated_oracle(scalar, affine_point):\n",
+    "    real_coords = model.coordinates[\"projective\"]\n",
+    "    real_add = real_coords.formulas[\"add-2007-bl\"]\n",
+    "    real_dbl = real_coords.formulas[\"dbl-2007-bl\"]\n",
+    "    real_mult = LTRMultiplier(real_add, real_dbl, None, False, AccumulationOrder.PeqPR, True, True)\n",
+    "    point = affine_point.to_model(params.curve.coordinate_model, params.curve)\n",
+    "    with local(DefaultContext()) as ctx:\n",
+    "        real_mult.init(params, point)\n",
+    "        real_mult.multiply(scalar)\n",
+    "\n",
+    "    trace = []\n",
+    "\n",
+    "    def callback(action):\n",
+    "        if isinstance(action, FormulaAction):\n",
+    "            for intermediate in action.op_results:\n",
+    "                trace.append(intermediate.value)\n",
+    "    ctx.actions.walk(callback)\n",
+    "    return any(int(value) == 0 for value in trace)"
    ]
   },
   {
    "cell_type": "code",
-   "execution_count": 24,
-   "id": "645ca07a-8d47-446d-93ca-eab4de26dfff",
+   "execution_count": null,
+   "id": "ae203ed4-cbdb-4b27-8f0a-0a74340d8e22",
    "metadata": {},
-   "outputs": [
-    {
-     "name": "stdout",
-     "output_type": "stream",
-     "text": [
-      "U1 = X1*Z2 \t X1*Z2\n",
-      "U2 = X2*Z1 \t X2*Z1\n",
-      "S1 = Y1*Z2 \t Y1*Z2\n",
-      "S2 = Y2*Z1 \t Y2*Z1\n",
-      "ZZ = Z1*Z2 \t Z1*Z2\n",
-      "T = U1+U2 \t X1*Z2 + X2*Z1\n",
-      "TT = T \t (X1*Z2 + X2*Z1)**2\n",
-      "M = S1+S2 \t Y1*Z2 + Y2*Z1\n",
-      "t0 = ZZ \t Z1**2*Z2**2\n",
-      "t1 = a*t0 \t Z1**2*Z2**2*a\n",
-      "t2 = U1*U2 \t X1*X2*Z1*Z2\n",
-      "t3 = TT-t2 \t -X1*X2*Z1*Z2 + (X1*Z2 + X2*Z1)**2\n",
-      "R = t3+t1 \t -X1*X2*Z1*Z2 + Z1**2*Z2**2*a + (X1*Z2 + X2*Z1)**2\n",
-      "F = ZZ*M \t Z1*Z2*(Y1*Z2 + Y2*Z1)\n",
-      "L = M*F \t Z1*Z2*(Y1*Z2 + Y2*Z1)**2\n",
-      "LL = L \t Z1**2*Z2**2*(Y1*Z2 + Y2*Z1)**4\n",
-      "t4 = T+L \t X1*Z2 + X2*Z1 + Z1*Z2*(Y1*Z2 + Y2*Z1)**2\n",
-      "t5 = t4 \t (X1*Z2 + X2*Z1 + Z1*Z2*(Y1*Z2 + Y2*Z1)**2)**2\n",
-      "t6 = t5-TT \t -(X1*Z2 + X2*Z1)**2 + (X1*Z2 + X2*Z1 + Z1*Z2*(Y1*Z2 + Y2*Z1)**2)**2\n",
-      "G = t6-LL \t -Z1**2*Z2**2*(Y1*Z2 + Y2*Z1)**4 - (X1*Z2 + X2*Z1)**2 + (X1*Z2 + X2*Z1 + Z1*Z2*(Y1*Z2 + Y2*Z1)**2)**2\n",
-      "t7 = R \t (-X1*X2*Z1*Z2 + Z1**2*Z2**2*a + (X1*Z2 + X2*Z1)**2)**2\n",
-      "t8 = 2*t7 \t 2*(-X1*X2*Z1*Z2 + Z1**2*Z2**2*a + (X1*Z2 + X2*Z1)**2)**2\n",
-      "W = t8-G \t Z1**2*Z2**2*(Y1*Z2 + Y2*Z1)**4 + (X1*Z2 + X2*Z1)**2 - (X1*Z2 + X2*Z1 + Z1*Z2*(Y1*Z2 + Y2*Z1)**2)**2 + 2*(-X1*X2*Z1*Z2 + Z1**2*Z2**2*a + (X1*Z2 + X2*Z1)**2)**2\n",
-      "t9 = F*W \t Z1*Z2*(Y1*Z2 + Y2*Z1)*(Z1**2*Z2**2*(Y1*Z2 + Y2*Z1)**4 + (X1*Z2 + X2*Z1)**2 - (X1*Z2 + X2*Z1 + Z1*Z2*(Y1*Z2 + Y2*Z1)**2)**2 + 2*(-X1*X2*Z1*Z2 + Z1**2*Z2**2*a + (X1*Z2 + X2*Z1)**2)**2)\n",
-      "X3 = 2*t9 \t 2*Z1*Z2*(Y1*Z2 + Y2*Z1)*(Z1**2*Z2**2*(Y1*Z2 + Y2*Z1)**4 + (X1*Z2 + X2*Z1)**2 - (X1*Z2 + X2*Z1 + Z1*Z2*(Y1*Z2 + Y2*Z1)**2)**2 + 2*(-X1*X2*Z1*Z2 + Z1**2*Z2**2*a + (X1*Z2 + X2*Z1)**2)**2)\n",
-      "t10 = 2*W \t 2*Z1**2*Z2**2*(Y1*Z2 + Y2*Z1)**4 + 2*(X1*Z2 + X2*Z1)**2 - 2*(X1*Z2 + X2*Z1 + Z1*Z2*(Y1*Z2 + Y2*Z1)**2)**2 + 4*(-X1*X2*Z1*Z2 + Z1**2*Z2**2*a + (X1*Z2 + X2*Z1)**2)**2\n",
-      "t11 = G-t10 \t -3*Z1**2*Z2**2*(Y1*Z2 + Y2*Z1)**4 - 3*(X1*Z2 + X2*Z1)**2 + 3*(X1*Z2 + X2*Z1 + Z1*Z2*(Y1*Z2 + Y2*Z1)**2)**2 - 4*(-X1*X2*Z1*Z2 + Z1**2*Z2**2*a + (X1*Z2 + X2*Z1)**2)**2\n",
-      "t12 = 2*LL \t 2*Z1**2*Z2**2*(Y1*Z2 + Y2*Z1)**4\n",
-      "t13 = R*t11 \t (-X1*X2*Z1*Z2 + Z1**2*Z2**2*a + (X1*Z2 + X2*Z1)**2)*(-3*Z1**2*Z2**2*(Y1*Z2 + Y2*Z1)**4 - 3*(X1*Z2 + X2*Z1)**2 + 3*(X1*Z2 + X2*Z1 + Z1*Z2*(Y1*Z2 + Y2*Z1)**2)**2 - 4*(-X1*X2*Z1*Z2 + Z1**2*Z2**2*a + (X1*Z2 + X2*Z1)**2)**2)\n",
-      "Y3 = t13-t12 \t -2*Z1**2*Z2**2*(Y1*Z2 + Y2*Z1)**4 + (-X1*X2*Z1*Z2 + Z1**2*Z2**2*a + (X1*Z2 + X2*Z1)**2)*(-3*Z1**2*Z2**2*(Y1*Z2 + Y2*Z1)**4 - 3*(X1*Z2 + X2*Z1)**2 + 3*(X1*Z2 + X2*Z1 + Z1*Z2*(Y1*Z2 + Y2*Z1)**2)**2 - 4*(-X1*X2*Z1*Z2 + Z1**2*Z2**2*a + (X1*Z2 + X2*Z1)**2)**2)\n",
-      "t14 = F \t Z1**2*Z2**2*(Y1*Z2 + Y2*Z1)**2\n",
-      "t15 = F*t14 \t Z1**3*Z2**3*(Y1*Z2 + Y2*Z1)**3\n",
-      "Z3 = 4*t15 \t 4*Z1**3*Z2**3*(Y1*Z2 + Y2*Z1)**3\n"
-     ]
-    }
-   ],
+   "outputs": [],
    "source": [
-    "for op_result in ctx.actions.get_by_index([0])[0].op_results:\n",
-    "    print(repr(op_result), \"\\t\", op_result.value.x)"
+    "table = [[\"Formula\", \"Polynomial\", \"k\", \"Oracle output\"]]\n",
+    "\n",
+    "big_scalar = 7  # -> dbl(1) = 2, add(1, 2) = 3, dbl(3) = 6, add(1, 6) = 7\n",
+    "small_scalars = [2,6]\n",
+    "for formula_name, factor_set in tqdm(factor_sets.items()):\n",
+    "    for poly in tqdm(factor_set):\n",
+    "        for small_scalar in small_scalars:\n",
+    "            pts = zvp_points(poly, curve, small_scalar, n)\n",
+    "            if pts:\n",
+    "                outputs = []\n",
+    "                for point in pts:\n",
+    "                    #print(formula_name, poly, small_scalar, simulated_oracle(big_scalar, point))\n",
+    "                    outputs.append(simulated_oracle(big_scalar, point))\n",
+    "                table.append([formula_name, poly, small_scalar, outputs])\n",
+    "display(HTML(tabulate.tabulate(table, tablefmt=\"html\", headers=\"firstrow\")))"
    ]
   },
   {
    "cell_type": "code",
    "execution_count": null,
-   "id": "08e17876-331a-445a-8fbc-1990a0b5f69d",
+   "id": "d0ef1628-3d87-40be-95a0-3045bb1ee4aa",
    "metadata": {},
    "outputs": [],
    "source": []
@@ -235,7 +192,7 @@
    "name": "python",
    "nbconvert_exporter": "python",
    "pygments_lexer": "ipython3",
-   "version": "3.11.3"
+   "version": "3.11.5"
   }
  },
  "nbformat": 4,