diff options
Diffstat (limited to 'epare/countermeasures.ipynb')
| -rw-r--r-- | epare/countermeasures.ipynb | 41 |
1 files changed, 22 insertions, 19 deletions
diff --git a/epare/countermeasures.ipynb b/epare/countermeasures.ipynb index b4371ce..3d931d2 100644 --- a/epare/countermeasures.ipynb +++ b/epare/countermeasures.ipynb @@ -1248,21 +1248,24 @@ "source": [ "### Multiplicative splitting\n", "In multiplicative splitting the situation is a bit more complicated. Doing the same computation, where the target thinks the curve order is $n+92$ leads to:\n", - "$$ P = [k r^{-1} \\mod (n+92)][r \\mod n]G $$\n", + "$$ P = [k r^{-1}\\pmod{n+92}][r \\mod n]G $$\n", "\n", "Since the curve is composite order we can easily compute the dlog $d$ of P to G, we get:\n", - "$$ d = k r r^{-1} = k + s (n + 92) $$\n", + "$$ d = (k r^{-1})\\pmod{n+92}\\: r = k + t (n + 92) $$\n", "\n", - "However, the dlog is computed $\\mod n$ so we really get: $ d = k + s 92$. We extract the $s$ out of this.\n", - "Note that $s$ will have roughly the same size as the mask $r$, so at this point we have recovered the mask size.\n", - "However, $s$ is always smaller than $r$, sometimes also in bitsize.\n", + "However, the dlog is computed $\\mod n$ so we really get: $ d = k + t 92$. We extract the $t$ out of this.\n", + "Note that $t$ will have roughly the same size as the mask $r$, since at the left side we have $(k r^{-1})_{\\mod (n+92)}$\n", + "of size $n$ and $r$ of size of the mask and on the right size we have $t n$ that dominates.\n", + "Thus at this point we have recovered the mask size.\n", + "However, $t$ is always smaller than $r$, sometimes also in bitsize.\n", "\n", "Now that we have $s$ we can go back to the original equation and get:\n", - "$$ k r r^{-1} = k + s (n + 92) $$\n", + "$$ (k r^{-1})\\pmod{n+92}\\: r = k + t (n + 92) $$\n", "\n", - "We can then factor this value and look for divisors that are larger than $s$ but smaller than the mask length\n", - "that we recovered before. There may be multiple candidates here and we don't know how to distinguoish between\n", - "them. However, sometimes there is only one candidate, which is equal to the true mask value $r$." + "We can then factor this value, lets call it $full$, and look for divisors that are larger than $t$ but smaller than the mask length\n", + "that we recovered before. There may be multiple candidates here and we don't know how to distinguish between\n", + "them. It holds for all of the candidates $c$ that the rest of the value $full$ is equal to the inverse of $c \\mod (n+92)$.\n", + "However, sometimes there is only one candidate, which is equal to the true mask value $r$." ] }, { @@ -1343,7 +1346,7 @@ "tries = 1000\n", "\n", "blens = [None for _ in range(tries)]\n", - "ss = [None for _ in range(tries)]\n", + "ts = [None for _ in range(tries)]\n", "\n", "results = []\n", "rs = []\n", @@ -1369,8 +1372,8 @@ " \n", " for i, future in tqdm(pool.as_completed(), desc=\"Computing dlogs\", total=len(pool.tasks)):\n", " dlog = future.result()\n", - " s = int((dlog - key) / 92)\n", - " ss[i] = s\n", + " t = int((dlog - key) / 92)\n", + " ts[i] = t\n", " blens[i] = s.bit_length()\n", "\n", "mask_len = max(blens)\n", @@ -1402,15 +1405,15 @@ "num_workers = 25\n", "\n", "with TaskExecutor(max_workers=num_workers) as pool:\n", - " for s in ss:\n", - " full = s * (real_n + 92) + key\n", - " pool.submit_task(s,\n", + " for t in ts:\n", + " full = t * (real_n + 92) + key\n", + " pool.submit_task(t,\n", " pari_factor,\n", " full)\n", " facts = [None for _ in ss]\n", - " for s, future in tqdm(pool.as_completed(), desc=\"Factoring\", total=len(ss)):\n", + " for t, future in tqdm(pool.as_completed(), desc=\"Factoring\", total=len(ts)):\n", " result = future.result()\n", - " facts[ss.index(s)] = result" + " facts[ts.index(t)] = result" ] }, { @@ -1535,12 +1538,12 @@ ], "source": [ "candidate_amounts = []\n", - "for s, blen, r, (primes, powers), result in zip(ss, blens, rs, facts, results):\n", + "for t, blen, r, (primes, powers), result in zip(ts, blens, rs, facts, results):\n", " #print(primes, powers)\n", " #print(s, blen, r, r.bit_length())\n", " candidates = set()\n", " for divisor in divisors(primes, powers):\n", - " if blen <= divisor.bit_length() <= mask_len and divisor > s:\n", + " if blen <= divisor.bit_length() <= mask_len and divisor > t:\n", " candidates.add(divisor)\n", " #print(f\"Candidates: {len(candidates)}, {r in candidates}\")\n", " candidate_amounts.append(len(candidates))\n", |