Add EPA-RE notebook.

1 files changed, 154 insertions, 54 deletions

diff --git a/re/epa.ipynb b/re/epa.ipynb
index 2ed690b..67e7973 100644
--- a/re/epa.ipynb
+++ b/re/epa.ipynb
@@ -15,124 +15,224 @@
    "metadata": {},
    "outputs": [],
    "source": [
+    "import io\n",
+    "import tabulate\n",
+    "from itertools import product\n",
+    "from IPython.display import HTML, display\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.mod import Mod, miller_rabin\n",
+    "from pyecsca.ec.params import DomainParameters, load_params_ectester\n",
+    "from pyecsca.ec.mod import Mod, miller_rabin, gcd\n",
     "from pyecsca.ec.point import Point\n",
     "from pyecsca.ec.error import NonInvertibleError\n",
-    "from pyecsca.ec.mult import LTRMultiplier"
+    "from pyecsca.ec.mult import LTRMultiplier\n",
+    "from pyecsca.sca.re.rpa import MultipleContext\n",
+    "from pyecsca.ec.context import local\n",
+    "from pyecsca.ec.error import UnsatisfiedAssumptionError"
    ]
   },
   {
    "cell_type": "code",
    "execution_count": null,
-   "id": "6e92cdd8-9040-4c6d-9700-f992d09195ee",
+   "id": "9506f889-75cf-4b27-8535-e71cb8d5301e",
    "metadata": {},
    "outputs": [],
    "source": [
-    "model = ShortWeierstrassModel()\n",
-    "coords = model.coordinates[\"projective\"]\n",
-    "add = coords.formulas[\"add-2007-bl\"]\n",
-    "dbl = coords.formulas[\"dbl-2007-bl\"]\n",
-    "neg = coords.formulas[\"neg\"]\n",
-    "\n",
-    "p = 0xdb49063db56b7783fa01dd62077c5a88dfa28009  # such that phi(p)/p ~ 0.5\n",
-    "a = Mod(0xaee572fdd4790bcd4729bb3b612b52a573df46e9, p)\n",
-    "b = Mod(0xdab9e68366a593ca1df9cb2f20890a578729d6ef, p)\n",
-    "\n",
-    "n = 0x34a9fbe62b272f930b2e5027780a32300feb0dd8f\n",
-    "h = 1\n",
-    "gx = Mod(0xd4a3aaf43bdb25be7c308b69ae54f639e6e32e8c, p)\n",
-    "gy = Mod(0x7b6c82140bb427ac6e2a64507f60775949b2c8ce, p)\n",
-    "\n",
-    "g = Point(coords, X=gx, Y=gy, Z=Mod(1, p))\n",
-    "infty = Point(coords, X=Mod(0, p), Y=Mod(1, p), Z=Mod(0, p))\n",
-    "\n",
-    "curve = EllipticCurve(model, coords, p, infty, dict(a=a, b=b))\n",
-    "params = DomainParameters(curve, g, n, h)\n",
-    "print(miller_rabin(p))\n",
-    "print(curve.is_on_curve(g))"
+    "curves = [\n",
+    "    # phi(p)/p =\n",
+    "    # 0.8286039438617044\n",
+    "    \"dfb2da5e1b7bd7bb098cb975966293ed,d9c4372806e8131b18d0036e8f832749,bcae41be8e808acdc04bb769dead91e2,0e2f983c0f852bef381f567448f0d488,1599bba77ed1cb8dec41555098958492,10fcabd48fffc71e6300d44acc236157d,0001\",\n",
+    "    # 0.633325621696952\n",
+    "    \"cca6f6718a06cad7094962b2a35f067d,67aa9464eb493fbb7b509d29381b9a9d,cafc69aa517b654a6a608644996cc8d1,4c092beb06cc00751eec39675f680cb8,82800378a47dd6f26ff6a50f69e4c4e6,18a22d20b6de3ff6bdc49329c21163f77,0001\",\n",
+    "    # 0.8508806646440022 \n",
+    "    \"b3755d654bad73114e4191e9f5f36af9,9fe4f88cfbacba71f4b767ace8580c74,4610526fdcfbd69aed453ac2ee6efeef,542d8e0bbafe40dae36f25cbc350add6,68a65f5a5dc304bfd0d8fe963c250206,118a34a1ea295e78b3a3c960b6f680ee1,0001\",\n",
+    "    # 0.9845701775215489    \n",
+    "    \"de1406450d5d7e91d81907956019c0c1,5fbe46b9f1086011e18f5d823c6110ce,a859c36ceeadb39c7a978f7b1b0563ee,1cba89c3f099c29401ecf3fe1806e822,345d7282a0114070be91f95fe3db1faa,0fcd24d24e57a40547814b6766b9ea735,0001\",\n",
+    "    # 0.9547100843537808\n",
+    "    \"f1a8a441b6d0e9600e33ccf16f9b8291,b3f55185bd6a63528e3d560c6a7b729a,c2fee2d65350e870eda0ac5e2b96b810,29b3e793822fad03a3c2ebca3cf62c12,b937d5389b6c5d0212d0f53e26843092,1153442389f9e1da8dd130bc93c6ef42b,0001\",\n",
+    "    # 0.7214369438844093\n",
+    "    \"a4dfa4b6b065c40b45980474266c9fbb,2c3486e725755b44a7c119473c5b9c64,329078ab070fc18edc6ce53047e00a39,9f6209be91b66943d9e8e0b61c4aae4e,05271c9ac628351b9add9e1be69a9fa4,0cef2e52ffe86ebc6dd323912ac7d9a87,0001\",\n",
+    "    # 0.4716485170445178 (160-bit)\n",
+    "    \"db49063db56b7783fa01dd62077c5a88dfa28009,aee572fdd4790bcd4729bb3b612b52a573df46e9,dab9e68366a593ca1df9cb2f20890a578729d6ef,d4a3aaf43bdb25be7c308b69ae54f639e6e32e8c,7b6c82140bb427ac6e2a64507f60775949b2c8ce,34a9fbe62b272f930b2e5027780a32300feb0dd8f,0001\"\n",
+    "]"
    ]
   },
   {
    "cell_type": "code",
    "execution_count": null,
-   "id": "ffce5b71-3029-4219-a45a-1c8d78748fee",
+   "id": "6e92cdd8-9040-4c6d-9700-f992d09195ee",
    "metadata": {},
    "outputs": [],
    "source": [
-    "mult = LTRMultiplier(add, dbl, None, False, True, True)\n",
-    "mult.init(params, g)\n",
-    "non = 0\n",
-    "for _ in range(1000):\n",
-    "    scalar = int(Mod.random(n*5))\n",
-    "    \n",
-    "    res = mult.multiply(scalar)\n",
-    "    #print(res)\n",
-    "    try:\n",
-    "        res.Z.inverse()\n",
-    "        print(\"yay\", scalar, res)\n",
-    "        break\n",
-    "    except NonInvertibleError as e:\n",
-    "        non += 1\n",
-    "print(non)"
+    "model = ShortWeierstrassModel()\n",
+    "affine = AffineCoordinateModel(model)\n",
+    "which = \"projective\"\n",
+    "coords = model.coordinates[which]\n",
+    "\n",
+    "params = load_params_ectester(io.BytesIO(curves[3].encode()), which)\n",
+    "curve = params.curve\n",
+    "g = params.generator\n",
+    "n = params.order"
    ]
   },
   {
    "cell_type": "code",
    "execution_count": null,
-   "id": "7611348f-ac20-402f-8791-6f4eb6d681af",
+   "id": "703da72a-1c41-41a9-886d-453da1160932",
    "metadata": {},
    "outputs": [],
    "source": [
-    "b.inverse()"
+    "adds = list(filter(lambda formula: formula.name.startswith(\"add\"), coords.formulas.values()))\n",
+    "dbls = list(filter(lambda formula: formula.name.startswith(\"dbl\"), coords.formulas.values()))\n",
+    "formula_pairs = list(product(adds, dbls))"
    ]
   },
   {
    "cell_type": "code",
    "execution_count": null,
-   "id": "4108fce0-28a9-4c28-a8d4-6051b86ce534",
-   "metadata": {},
+   "id": "ffce5b71-3029-4219-a45a-1c8d78748fee",
+   "metadata": {
+    "scrolled": true
+   },
    "outputs": [],
    "source": [
-    "b"
+    "scalars = [int(Mod.random(n)) for _ in range(200)]\n",
+    "\n",
+    "table = [[\"Pair\", \"scalars with trivial gcd\", \"scalars with all multiples with trivial gcds\", \"scalars with invertible final zs\", \"scalars with all multiples's zs invertible\"]]\n",
+    "pair_table = [[None for _ in dbls] for _ in adds]\n",
+    "for pair in formula_pairs:\n",
+    "    mult = LTRMultiplier(*pair, None, False, True, True)\n",
+    "    mult.init(params, g)\n",
+    "    inv = 0\n",
+    "    gcds = 0\n",
+    "    fgcds = 0\n",
+    "    zs = 0\n",
+    "    for scalar in scalars:\n",
+    "        if gcd(scalar, n) == 1:\n",
+    "            gcds += 1\n",
+    "        with local(MultipleContext()) as ctx:\n",
+    "            res = mult.multiply(scalar)\n",
+    "        if all(map(lambda x: gcd(x, n) == 1, ctx.points.values())):\n",
+    "            fgcds += 1\n",
+    "        if all(map(lambda x: gcd(int(x.Z), n) == 1, ctx.points.keys())):\n",
+    "            zs += 1\n",
+    "    \n",
+    "        try:\n",
+    "            res.Z.inverse()\n",
+    "            inv += 1\n",
+    "        except NonInvertibleError as e:\n",
+    "            pass\n",
+    "    #print(\"---\")\n",
+    "    #print(pair[0].name, pair[1].name)\n",
+    "    #print(gcds, \"\\tscalars with trivial gcd\")\n",
+    "    #print(fgcds, \"\\tscalars with all multiples with trivial gcds\")\n",
+    "    #print(inv, \"\\tscalars with invertible final zs\")\n",
+    "    #print(zs, \"\\tscalars with all multiples's zs invertible\")\n",
+    "    pair_table[adds.index(pair[0])][dbls.index(pair[1])] = inv\n",
+    "    table.append([f\"{pair[0].name}, {pair[1].name}\", gcds, fgcds, inv, zs])\n",
+    "for pl, add in zip(pair_table, adds):\n",
+    "    pl.insert(0, add.name)\n",
+    "pair_table.insert(0, [None] + [dbl.name for dbl in dbls])\n",
+    "display(HTML(tabulate.tabulate(table, tablefmt=\"html\", headers=\"firstrow\")))\n",
+    "display(HTML(tabulate.tabulate(pair_table, tablefmt=\"html\", headers=\"firstrow\")))"
    ]
   },
   {
    "cell_type": "code",
    "execution_count": null,
-   "id": "ba9e5177-ca8f-488d-af4c-f3261e6563ef",
+   "id": "f47c0743-a6cf-408a-8c6e-dca6732278e2",
    "metadata": {},
    "outputs": [],
    "source": [
-    "dbl(p, g, a=a, b=b)"
+    "def simulate_epa_oracle(affine_params, affine_point, scalar):\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, True, True)\n",
+    "    params = affine_params.to_coords(real_coords)\n",
+    "    point = affine_point.to_model(real_coords, params.curve)\n",
+    "    real_mult.init(params, point)\n",
+    "    res = real_mult.multiply(scalar)\n",
+    "    try:\n",
+    "        res.to_affine()\n",
+    "        return True\n",
+    "    except NonInvertibleError as e:\n",
+    "        return False\n",
+    "\n",
+    "def epa_distinguish(oracle, mult_factory):\n",
+    "    affine_params = load_params_ectester(io.BytesIO(curves[3].encode()), \"affine\")\n",
+    "    model = affine_params.curve.model\n",
+    "    scalars = [int(Mod.random(affine_params.order)) for _ in range(100)]\n",
+    "    responses = [oracle(affine_params,  affine_params.generator, scalar) for scalar in scalars]\n",
+    "    candidates = set()\n",
+    "    print(\"Got responses\")\n",
+    "    total = 0\n",
+    "    for coords in model.coordinates.values():\n",
+    "        adds = list(filter(lambda formula: formula.name.startswith(\"add\"), coords.formulas.values()))\n",
+    "        dbls = list(filter(lambda formula: formula.name.startswith(\"dbl\"), coords.formulas.values()))\n",
+    "        formula_pairs = list(product(adds, dbls))\n",
+    "        total += len(formula_pairs)\n",
+    "        try:\n",
+    "            params = affine_params.to_coords(coords)\n",
+    "        except UnsatisfiedAssumptionError:\n",
+    "            print(f\"Skipping {coords.name}, does not fit\")\n",
+    "            continue\n",
+    "\n",
+    "        for pair in formula_pairs:\n",
+    "            mult = mult_factory(*pair)\n",
+    "            mult.init(params, params.generator)\n",
+    "            abort = False\n",
+    "            print(f\"Trying {coords.name} {pair[0].name} {pair[1].name}\", end=\"\") \n",
+    "            for scalar, target in zip(scalars, responses):\n",
+    "                res = mult.multiply(scalar)\n",
+    "                try:\n",
+    "                    res.to_affine()\n",
+    "                    if not target:\n",
+    "                        # not this one\n",
+    "                        abort = True\n",
+    "                        break\n",
+    "                except NonInvertibleError as e:\n",
+    "                    if target:\n",
+    "                        # not this one\n",
+    "                        abort = True\n",
+    "                        break\n",
+    "            if abort:\n",
+    "                print(\" not\")\n",
+    "                continue\n",
+    "            else:\n",
+    "                print(\" candidate\")\n",
+    "                candidates.add((coords.name, pair[0].name, pair[1].name))\n",
+    "    print(f\"Got {len(candidates)} out of {total} total\")\n",
+    "    return candidates\n",
+    "                "
    ]
   },
   {
    "cell_type": "code",
    "execution_count": null,
-   "id": "9b42e209-5185-4121-b756-7f8c3374da5c",
+   "id": "d2c26c45-a66a-4472-830e-b22010a967e5",
    "metadata": {},
    "outputs": [],
    "source": [
-    "Mod(753921130225168876277183530034689476795287082245, p).inverse()"
+    "c = epa_distinguish(simulate_epa_oracle, lambda add,dbl:LTRMultiplier(add, dbl, None, False, True, True))"
    ]
   },
   {
    "cell_type": "code",
    "execution_count": null,
-   "id": "dff4a049-2cad-40d8-9c49-98dcd9f93231",
+   "id": "dd3e076c-cd52-47e1-beb0-2cb59812dacc",
    "metadata": {},
    "outputs": [],
    "source": [
-    "curve.affine_random()"
+    "c"
    ]
   },
   {
    "cell_type": "code",
    "execution_count": null,
-   "id": "4ebc3535-737f-4ed6-8df5-d0629795ce8f",
+   "id": "aa548870-4236-42d8-a4a6-b6b8082b87bb",
    "metadata": {},
    "outputs": [],
    "source": []