aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--Makefile5
-rw-r--r--pyecsca/ec/divpoly.py263
-rw-r--r--pyecsca/sca/attack/leakage_model.py2
-rw-r--r--pyecsca/sca/re/zvp.py197
-rw-r--r--pyecsca/sca/stacked_traces/combine.py4
-rw-r--r--pyecsca/sca/stacked_traces/stacked_traces.py2
-rw-r--r--test/ec/test_divpoly.py169
-rw-r--r--test/sca/test_zvp.py137
8 files changed, 455 insertions, 324 deletions
diff --git a/Makefile b/Makefile
index 1ae4371..bf60189 100644
--- a/Makefile
+++ b/Makefile
@@ -1,10 +1,11 @@
EC_TESTS = ec.test_context ec.test_configuration ec.test_curve ec.test_formula \
ec.test_params ec.test_key_agreement ec.test_key_generation ec.test_mod ec.test_model \
-ec.test_mult ec.test_naf ec.test_op ec.test_point ec.test_signature ec.test_transformations ec.test_regress
+ec.test_mult ec.test_naf ec.test_op ec.test_point ec.test_signature ec.test_transformations ec.test_regress \
+ec.test_divpoly
SCA_TESTS = sca.test_align sca.test_combine sca.test_edit sca.test_filter sca.test_match sca.test_process \
sca.test_sampling sca.test_target sca.test_test sca.test_trace sca.test_traceset sca.test_plot sca.test_rpa \
-sca.test_stacked_combine sca.test_leakage_models
+sca.test_zvp sca.test_stacked_combine sca.test_leakage_models
TESTS = ${EC_TESTS} ${SCA_TESTS}
diff --git a/pyecsca/ec/divpoly.py b/pyecsca/ec/divpoly.py
new file mode 100644
index 0000000..2f2b635
--- /dev/null
+++ b/pyecsca/ec/divpoly.py
@@ -0,0 +1,263 @@
+from typing import Tuple, Dict, Union, Set, Mapping
+
+from sympy import symbols, FF, Poly
+import networkx as nx
+
+from .curve import EllipticCurve
+from .mod import Mod
+from .model import ShortWeierstrassModel
+
+
+def values(*ns: int) -> Mapping[int, Tuple[int, ...]]:
+ done: Set[int] = set()
+ vals = {}
+ todo: Set[int] = set()
+ todo.update(ns)
+ while todo:
+ val = todo.pop()
+ if val in done:
+ continue
+ new: Tuple[int, ...] = ()
+ if val == -2:
+ new = (-1,)
+ elif val == -1:
+ pass
+ elif val < 0:
+ raise ValueError(f"bad {val}")
+ elif val in (0, 1, 2, 3):
+ pass
+ elif val == 4:
+ new = (-2, 3)
+ elif val % 2 == 0:
+ m = (val - 2) // 2
+ new = (m + 1, m + 3, m, m - 1, m + 2)
+ else:
+ m = (val - 1) // 2
+ if m % 2 == 0:
+ new = (-2, m + 2, m, m - 1, m + 1)
+ else:
+ new = (m + 2, m, -2, m - 1, m + 1)
+ if new:
+ todo.update(new)
+ vals[val] = new
+ done.add(val)
+ return vals
+
+
+def dep_graph(*ns: int):
+ g = nx.DiGraph()
+ vals = values(*ns)
+ for k, v in vals.items():
+ if v:
+ for e in v:
+ g.add_edge(k, e)
+ else:
+ g.add_node(k)
+ return g, vals
+
+
+def dep_map(*ns: int):
+ g, vals = dep_graph(*ns)
+ current: Set[int] = set()
+ ls = []
+ for vert in nx.lexicographical_topological_sort(g, key=lambda v: -sum(g[v].keys())):
+ if vert in current:
+ current.remove(vert)
+ ls.append((vert, set(current)))
+ current.update(vals[vert])
+ ls.reverse()
+ return ls, vals
+
+
+def a_invariants(curve: EllipticCurve) -> Tuple[Mod, ...]:
+ """
+ Compute the a-invariants of the curve.
+
+ :param curve: The elliptic curve (only ShortWeierstrass model).
+ :return: A tuple of 5 a-invariants (a1, a2, a3, a4, a6).
+ """
+ if isinstance(curve.model, ShortWeierstrassModel):
+ a1 = Mod(0, curve.prime)
+ a2 = Mod(0, curve.prime)
+ a3 = Mod(0, curve.prime)
+ a4 = curve.parameters["a"]
+ a6 = curve.parameters["b"]
+ return a1, a2, a3, a4, a6
+ else:
+ raise NotImplementedError
+
+
+def b_invariants(curve: EllipticCurve) -> Tuple[Mod, ...]:
+ """
+ Compute the b-invariants of the curve.
+
+ :param curve: The elliptic curve (only ShortWeierstrass model).
+ :return: A tuple of 4 b-invariants (b2, b4, b6, b8).
+ """
+ if isinstance(curve.model, ShortWeierstrassModel):
+ a1, a2, a3, a4, a6 = a_invariants(curve)
+ return (a1 * a1 + 4 * a2,
+ a1 * a3 + 2 * a4,
+ a3 ** 2 + 4 * a6,
+ a1 ** 2 * a6 + 4 * a2 * a6 - a1 * a3 * a4 + a2 * a3 ** 2 - a4 ** 2)
+ else:
+ raise NotImplementedError
+
+
+def divpoly0(curve: EllipticCurve, *ns: int) -> Mapping[int, Poly]:
+ """
+ Basically sagemath's division_polynomial_0 but more clever memory management.
+
+ As sagemath says:
+
+ Return the `n^{th}` torsion (division) polynomial, without
+ the 2-torsion factor if `n` is even, as a polynomial in `x`.
+
+ These are the polynomials `g_n` defined in [MT1991]_, but with
+ the sign flipped for even `n`, so that the leading coefficient is
+ always positive.
+
+ :param curve: The elliptic curve.
+ :param ns: The values to compute the polynomial for.
+ :return:
+ """
+ xs = symbols("x")
+
+ K = FF(curve.prime)
+ Kx = lambda r: Poly(r, xs, domain=K) # noqa
+
+ x = Kx(xs)
+
+ b2, b4, b6, b8 = map(lambda b: Kx(int(b)), b_invariants(curve))
+ ls, vals = dep_map(*ns)
+
+ mem: Dict[int, Poly] = {}
+ for i, keep in ls:
+ if i == -2:
+ val = mem[-1] ** 2
+ elif i == -1:
+ val = Kx(4) * x ** 3 + b2 * x ** 2 + Kx(2) * b4 * x + b6
+ elif i == 0:
+ val = Kx(0)
+ elif i < 0:
+ raise ValueError("n must be a positive integer (or -1 or -2)")
+ elif i == 1 or i == 2:
+ val = Kx(1)
+ elif i == 3:
+ val = Kx(3) * x ** 4 + b2 * x ** 3 + Kx(3) * b4 * x ** 2 + Kx(3) * b6 * x + b8
+ elif i == 4:
+ val = -mem[-2] + (Kx(6) * x ** 2 + b2 * x + b4) * mem[3]
+ elif i % 2 == 0:
+ m = (i - 2) // 2
+ val = mem[m + 1] * (mem[m + 3] * mem[m] ** 2 - mem[m - 1] * mem[m + 2] ** 2)
+ else:
+ m = (i - 1) // 2
+ if m % 2 == 0:
+ val = mem[-2] * mem[m + 2] * mem[m] ** 3 - mem[m - 1] * mem[m + 1] ** 3
+ else:
+ val = mem[m + 2] * mem[m] ** 3 - mem[-2] * mem[m - 1] * mem[m + 1] ** 3
+ for dl in set(mem.keys()).difference(keep).difference(ns):
+ del mem[dl]
+ mem[i] = val
+
+ return mem
+
+
+def divpoly(curve: EllipticCurve, n: int, two_torsion_multiplicity: int = 2) -> Poly:
+ """
+ Compute the n-th division polynomial.
+
+ :param curve:
+ :param n:
+ :param two_torsion_multiplicity:
+ :return:
+ """
+ f: Poly = divpoly0(curve, n)[n]
+ a1, a2, a3, a4, a6 = a_invariants(curve)
+ xs, ys = symbols("x y")
+ x = Poly(xs, xs, domain=f.domain)
+ y = Poly(ys, ys, domain=f.domain)
+
+ if two_torsion_multiplicity == 0:
+ return f
+ elif two_torsion_multiplicity == 1:
+ if n % 2 == 0:
+ Kxy = lambda r: Poly(r, xs, ys, domain=f.domain) # noqa
+ return Kxy(f) * (Kxy(2) * y + Kxy(a1) * x + Kxy(a3))
+ else:
+ return f
+ elif two_torsion_multiplicity == 2:
+ if n % 2 == 0:
+ return f * divpoly0(curve, -1)[-1]
+ else:
+ return f
+
+
+def mult_by_n(curve: EllipticCurve, n: int) -> Tuple[Tuple[Poly, Poly], Tuple[Poly, Poly]]:
+ """
+ Compute the multiplication-by-n map on an elliptic curve.
+
+ :param curve: Curve to compute on.
+ :param n: Scalar.
+ :return:
+ """
+ xs, ys = symbols("x y")
+ K = FF(curve.prime)
+ x = Poly(xs, xs, domain=K)
+ y = Poly(ys, ys, domain=K)
+ Kxy = lambda r: Poly(r, xs, ys, domain=K) # noqa
+
+ if n == 1:
+ return x
+
+ a1, a2, a3, a4, a6 = a_invariants(curve)
+
+ polys = divpoly0(curve, -2, -1, n - 1, n, n + 1, n + 2)
+ mx_denom = polys[n] ** 2
+ if n % 2 == 0:
+ mx_num = x * polys[-1] * polys[n] ** 2 - polys[n - 1] * polys[n + 1]
+ mx_denom *= polys[-1]
+ else:
+ mx_num = x * polys[n] ** 2 - polys[-1] * polys[n - 1] * polys[n + 1]
+
+ # Alternative that makes the denominator monic by dividing the
+ # numerator by the leading coefficient. Sage does this
+ # simplification when asking for multiplication_by_m with the
+ # x-only=True, as then the poly is an univariate object.
+ # lc = K(mx_denom.LC())
+ # mx = (mx_num.quo(lc), mx_denom.monic())
+ mx = (mx_num, mx_denom)
+
+ # The following lines compute
+ # my = ((2*y+a1*x+a3)*mx.derivative(x)/m - a1*mx-a3)/2
+ # just as sage does, but using sympy and step-by-step
+ # tracking the numerator and denominator of the fraction.
+
+ # mx.derivative()
+ mxd_num = mx[1] * mx[0].diff() - mx[0] * mx[1].diff()
+ mxd_denom = mx[1] ** 2
+
+ # mx.derivative()/m
+ mxd_dn_num = mxd_num
+ mxd_dn_denom = mxd_denom * Kxy(n)
+
+ # (2*y+a1*x+a3)*mx.derivative(x)/m
+ mxd_full_num = mxd_dn_num * (Kxy(2) * y + Kxy(a1) * x + Kxy(a3))
+ mxd_full_denom = mxd_dn_denom
+
+ # a1*mx
+ a1mx_num = (Kxy(a1) * mx[0]).quo(Kxy(2))
+ a1mx_denom = mx[1] # noqa
+
+ # a3
+ a3_num = Kxy(a3) * mx[1]
+ a3_denom = mx[1] # noqa
+
+ # The mx.derivative part has a different denominator, basically mx[1]^2 * m
+ # so the rest needs to be multiplied by this factor when subtracitng.
+ mxd_fact = mx[1] * n
+
+ my_num = (mxd_full_num - a1mx_num * mxd_fact - a3_num * mxd_fact)
+ my_denom = mxd_full_denom * Kxy(2)
+ my = (my_num, my_denom)
+ return mx, my
diff --git a/pyecsca/sca/attack/leakage_model.py b/pyecsca/sca/attack/leakage_model.py
index 937ec65..f9adcff 100644
--- a/pyecsca/sca/attack/leakage_model.py
+++ b/pyecsca/sca/attack/leakage_model.py
@@ -5,7 +5,7 @@ from typing import Literal, ClassVar
from numpy.random import default_rng
from public import public
-from pyecsca.sca import Trace
+from ...sca.trace import Trace
if sys.version_info[0] < 3 or sys.version_info[0] == 3 and sys.version_info[1] < 10:
def hw(i):
diff --git a/pyecsca/sca/re/zvp.py b/pyecsca/sca/re/zvp.py
index 836c18e..22f6f79 100644
--- a/pyecsca/sca/re/zvp.py
+++ b/pyecsca/sca/re/zvp.py
@@ -4,21 +4,25 @@ Provides functionality inspired by the Zero-value point attack.
Zero-Value Point Attacks on Elliptic Curve Cryptosystem, Toru Akishita & Tsuyoshi Takagi , ISC '03
`<https://doi.org/10.1007/10958513_17>`_
"""
-from typing import Tuple, Dict, Union, Set
+from typing import List
-from sympy import symbols, FF, Poly
-import networkx as nx
+from sympy import symbols
-from pyecsca.ec.context import DefaultContext, local
-from pyecsca.ec.curve import EllipticCurve
-from pyecsca.ec.formula import Formula
-from pyecsca.ec.mod import SymbolicMod, Mod
-from pyecsca.ec.model import ShortWeierstrassModel
-from pyecsca.ec.point import Point
-from pyecsca.misc.cfg import TemporaryConfig
+from ...ec.context import DefaultContext, local
+from ...ec.formula import Formula
+from ...ec.mod import SymbolicMod
+from ...ec.point import Point
+from ...misc.cfg import TemporaryConfig
-def unroll_formula(formula: Formula, prime: int):
+def unroll_formula(formula: Formula, prime: int) -> List[SymbolicMod]:
+ """
+ Unroll a given formula symbolically to obtain symbolic expressions for its intermediate values.
+
+ :param formula: Formula to unroll.
+ :param prime: Field to unroll over.
+ :return: List of symbolic intermediate values.
+ """
inputs = [Point(formula.coordinate_model,
**{var: SymbolicMod(symbols(var + str(i)), prime) for var in formula.coordinate_model.variables})
for i in
@@ -28,174 +32,3 @@ def unroll_formula(formula: Formula, prime: int):
cfg.ec.mod_implementation = "symbolic"
formula(prime, *inputs, **params)
return [op_result.value for op_result in ctx.actions.get_by_index([0])[0].op_results]
-
-
-def values(*ns: int):
- done: Set[int] = set()
- vals = {}
- todo: Set[int] = set()
- todo.update(ns)
- while todo:
- val = todo.pop()
- if val in done:
- continue
- new: Tuple[int, ...] = ()
- if val == -2:
- new = (-1,)
- elif val == -1:
- pass
- elif val <= 0:
- raise ValueError(f"bad {val}")
- elif val == 1 or val == 2 or val == 3:
- pass
- elif val == 4:
- new = (-2, 3)
- elif val % 2 == 0:
- m = (val - 2) // 2
- new = (m + 1, m + 3, m, m - 1, m + 2)
- else:
- m = (val - 1) // 2
- if m % 2 == 0:
- new = (-2, m + 2, m, m - 1, m + 1)
- else:
- new = (m + 2, m, -2, m - 1, m + 1)
- if new:
- todo.update(new)
- vals[val] = new
- done.add(val)
- return vals
-
-
-def dep_graph(*ns: int):
- g = nx.DiGraph()
- vals = values(*ns)
- for k, v in vals.items():
- if v:
- for e in v:
- g.add_edge(k, e)
- else:
- g.add_node(k)
- return g, vals
-
-
-def dep_map(*ns: int):
- g, vals = dep_graph(*ns)
- current: Set[int] = set()
- ls = []
- for vert in nx.lexicographical_topological_sort(g, key=lambda v: -sum(g[v].keys())):
- if vert in current:
- current.remove(vert)
- ls.append((vert, set(current)))
- current.update(vals[vert])
- ls.reverse()
- return ls, vals
-
-
-def a_invariants(curve: EllipticCurve) -> Tuple[Mod, ...]:
- if isinstance(curve.model, ShortWeierstrassModel):
- a1 = Mod(0, curve.prime)
- a2 = Mod(0, curve.prime)
- a3 = Mod(0, curve.prime)
- a4 = curve.parameters["a"]
- a6 = curve.parameters["b"]
- return a1, a2, a3, a4, a6
- else:
- raise NotImplementedError
-
-
-def b_invariants(curve: EllipticCurve) -> Tuple[Mod, ...]:
- if isinstance(curve.model, ShortWeierstrassModel):
- a1, a2, a3, a4, a6 = a_invariants(curve)
- return (a1 * a1 + 4 * a2,
- a1 * a3 + 2 * a4,
- a3 ** 2 + 4 * a6,
- a1 ** 2 * a6 + 4 * a2 * a6 - a1 * a3 * a4 + a2 * a3 ** 2 - a4 ** 2)
- else:
- raise NotImplementedError
-
-
-def divpoly0(curve: EllipticCurve, *ns: int) -> Union[Poly, Tuple[Poly, ...]]:
- # Basically sagemath's division_polynomial_0 but more clever memory management
- # and dependency computation.
- xs = symbols("x")
-
- K = FF(curve.prime)
- Kx = lambda r: Poly(r, xs, domain=K)
-
- x = Kx(xs)
-
- b2, b4, b6, b8 = map(lambda b: Kx(int(b)), b_invariants(curve))
- ls, vals = dep_map(*ns)
-
- mem: Dict[int, Poly] = {}
- for i, keep in ls:
- if i == -2:
- val = mem[-1] ** 2
- elif i == -1:
- val = Kx(4) * x ** 3 + b2 * x ** 2 + Kx(2) * b4 * x + b6
- elif i <= 0:
- raise ValueError("n must be a positive integer (or -1 or -2)")
- elif i == 1 or i == 2:
- val = Kx(1)
- elif i == 3:
- val = Kx(3) * x ** 4 + b2 * x ** 3 + Kx(3) * b4 * x ** 2 + Kx(3) * b6 * x + b8
- elif i == 4:
- val = -mem[-2] + (Kx(6) * x ** 2 + b2 * x + b4) * mem[3]
- elif i % 2 == 0:
- m = (i - 2) // 2
- val = mem[m + 1] * (mem[m + 3] * mem[m] ** 2 - mem[m - 1] * mem[m + 2] ** 2)
- else:
- m = (i - 1) // 2
- if m % 2 == 0:
- val = mem[-2] * mem[m + 2] * mem[m] ** 3 - mem[m - 1] * mem[m + 1] ** 3
- else:
- val = mem[m + 2] * mem[m] ** 3 - mem[-2] * mem[m - 1] * mem[m + 1] ** 3
- for dl in set(mem.keys()).difference(keep).difference(ns):
- del mem[dl]
- mem[i] = val
-
- if len(ns) == 1:
- return mem[ns[0]]
- else:
- return tuple(mem[n] for n in ns)
-
-
-def divpoly(curve: EllipticCurve, n: int, two_torsion_multiplicity: int = 2) -> Poly:
- f: Poly = divpoly0(curve, n)
- a1, a2, a3, a4, a6 = a_invariants(curve)
- xs, ys = symbols("x y")
- x = Poly(xs, xs, domain=f.domain)
- y = Poly(ys, ys, domain=f.domain)
-
- if two_torsion_multiplicity == 0:
- return f
- elif two_torsion_multiplicity == 1:
- if n % 2 == 0:
- Kxy = lambda r: Poly(r, xs, ys, domain=f.domain)
- return Kxy(f) * (Kxy(2) * y + Kxy(a1) * x + Kxy(a3))
- else:
- return f
- elif two_torsion_multiplicity == 2:
- if n % 2 == 0:
- return f * divpoly0(curve, -1)
- else:
- return f
-
-
-def mult_by_n(curve: EllipticCurve, n: int) -> Tuple[Poly, Poly]:
- xs = symbols("x")
- K = FF(curve.prime)
- x = Poly(xs, xs, domain=K)
-
- if n == 1:
- return x
-
- polys = divpoly0(curve, -2, -1, n - 1, n, n + 1)
- denom = polys[3] ** 2
- if n % 2 == 0:
- num = x * polys[1] * polys[3] ** 2 - polys[2] * polys[4]
- denom *= polys[1]
- else:
- num = x * polys[3] ** 2 - polys[1] * polys[2] * polys[4]
- lc = K(denom.LC())
- return num.quo(lc), denom.monic()
diff --git a/pyecsca/sca/stacked_traces/combine.py b/pyecsca/sca/stacked_traces/combine.py
index 5849150..cbdfe04 100644
--- a/pyecsca/sca/stacked_traces/combine.py
+++ b/pyecsca/sca/stacked_traces/combine.py
@@ -8,8 +8,8 @@ from math import sqrt
from public import public
from typing import Callable, Union, Tuple, cast
-from pyecsca.sca.trace.trace import CombinedTrace
-from pyecsca.sca.stacked_traces import StackedTraces
+from ...sca.trace.trace import CombinedTrace
+from ...sca.stacked_traces import StackedTraces
TPB = Union[int, Tuple[int, ...]]
CudaCTX = Tuple[
diff --git a/pyecsca/sca/stacked_traces/stacked_traces.py b/pyecsca/sca/stacked_traces/stacked_traces.py
index 09169bd..f2c67fc 100644
--- a/pyecsca/sca/stacked_traces/stacked_traces.py
+++ b/pyecsca/sca/stacked_traces/stacked_traces.py
@@ -4,7 +4,7 @@ import numpy as np
from public import public
from typing import Any, Mapping, Sequence
-from pyecsca.sca.trace_set.base import TraceSet
+from ...sca.trace_set.base import TraceSet
@public
diff --git a/test/ec/test_divpoly.py b/test/ec/test_divpoly.py
new file mode 100644
index 0000000..7cda6f6
--- /dev/null
+++ b/test/ec/test_divpoly.py
@@ -0,0 +1,169 @@
+from unittest import TestCase
+
+from sympy import FF
+from pyecsca.ec.divpoly import a_invariants, b_invariants, divpoly0, divpoly, mult_by_n
+from pyecsca.ec.model import ShortWeierstrassModel
+from pyecsca.ec.params import get_params
+
+
+class DivpolyTests(TestCase):
+ def setUp(self):
+ self.secp128r1 = get_params("secg", "secp128r1", "projective")
+ self.model = ShortWeierstrassModel()
+ self.coords = self.model.coordinates["projective"]
+ self.add = self.coords.formulas["add-2007-bl"]
+ self.dbl = self.coords.formulas["dbl-2007-bl"]
+ self.neg = self.coords.formulas["neg"]
+
+ def test_ainvs(self):
+ ainvs = a_invariants(self.secp128r1.curve)
+ self.assertSequenceEqual(ainvs, (0,
+ 0,
+ 0,
+ 340282366762482138434845932244680310780,
+ 308990863222245658030922601041482374867))
+
+ def test_binvs(self):
+ binvs = b_invariants(self.secp128r1.curve)
+ self.assertSequenceEqual(binvs, (0,
+ 340282366762482138434845932244680310777,
+ 215116352601536216819152607431888567119,
+ 340282366762482138434845932244680310774))
+
+ def test_divpoly0(self):
+ # Data from sagemath
+ coeffs = [11,
+ 0,
+ 340282366762482138434845932244680302401,
+ 211962053797180672439257756222135086642,
+ 340282366762482138434845932244678441564,
+ 115415922367823003571854983213102698477,
+ 152803211743444076787231275062278784385,
+ 68540219804769369063918923691867278088,
+ 43207172520353703997069627419519708522,
+ 83208285732019037267730920881743782729,
+ 93286967763556583502947234289842152563,
+ 324950611928652823046744874201355360259,
+ 244242343224213805514200367379671854852,
+ 307096814154284337284845014037169929735,
+ 180946781765592277412990188457219828893,
+ 301253861469456022084288029442105687698,
+ 58053323975526190296189278379252064657,
+ 224437885189054146208302696540070489578,
+ 281987318191429654256483850017931541622,
+ 21449216018131966691124843738286677726,
+ 10958264881628724646042625283328121348,
+ 104868338562600481545003572552335444641,
+ 127205813185570107009206143413997395181,
+ 116865717360861207318274706645935808417,
+ 281460458922812844939222119784601506753,
+ 336607098463310980140968249747513775735,
+ 304486486784143285234063826161805094682,
+ 194935097339732797131694429642153881938,
+ 193523171473792085604518744912658246509,
+ 204844449336357293979832621297234119270,
+ 244481753281744913785581086721299830802,
+ 46816299473081369405217767361380254657,
+ 303070923752707405164354702252828590781,
+ 222516549119176621389776816552836322766,
+ 292006660232236762950883960515487362063,
+ 53617127992846936725441702182362940200,
+ 242498306026562585655027965022211017540,
+ 25039963304689451659955607939868533124,
+ 328580435950647191774558154445103295305,
+ 24226614081978788956695324769468902511,
+ 147945052666123617872720080832548744564,
+ 287190187011075399698210761813202261601,
+ 117131681517270554750959286838283723521,
+ 35018410385280384289320020556813474742,
+ 83939964512240352730304831725346032711,
+ 147219996946006689656600631222993527180,
+ 280430477096741745234510250577626566690,
+ 32753113267385981127807026368593329576,
+ 105134319561523011785486683031223863934,
+ 206456116679151691099661865534540095270,
+ 116180470443213022739312068090342951131,
+ 245850120846480965440408943459023315919,
+ 45805943896736805301879725516256422457,
+ 226777421435695229777151315574975350291,
+ 283680841707610526659029980964566557627,
+ 53168487339451866167506032177471934158,
+ 69212302225932892622760219621519562036,
+ 183916411340675637978873336955593385541,
+ 119478537598919956688656337369481692789,
+ 234767298887335988751880131162396819780,
+ 218412162101425422347176804186940045781]
+
+ K = FF(self.secp128r1.curve.prime)
+ poly = divpoly0(self.secp128r1.curve, 11)[11]
+ computed = list(map(K, poly.all_coeffs()))
+ self.assertListEqual(coeffs, computed)
+
+ def test_divpoly(self):
+ # Data from sagemath
+ K = FF(self.secp128r1.curve.prime)
+ coeffs_0 = {
+ (0,): K(16020440675387382717114730680672549016),
+ (1,): K(269851015321770885610377847857290470365),
+ (2,): K(340282366762482138434845932244680310693),
+ (3,): K(109469325440469337582450480850803806492),
+ (4,): K(340282366762482138434845932244680310753),
+ (6,): K(2)
+ }
+ self.assertDictEqual(divpoly(self.secp128r1.curve, 4, 0).as_dict(), coeffs_0)
+ coeffs_1 = {
+ (6, 1): K(4),
+ (4, 1): K(340282366762482138434845932244680310723),
+ (3, 1): K(218938650880938675164900961701607612984),
+ (2, 1): K(340282366762482138434845932244680310603),
+ (1, 1): K(199419663881059632785909763469900629947),
+ (0, 1): K(32040881350774765434229461361345098032)
+ }
+ self.assertDictEqual(divpoly(self.secp128r1.curve, 4, 1).as_dict(), coeffs_1)
+ coeffs_2 = {
+ (9,): K(8),
+ (7,): K(340282366762482138434845932244680310639),
+ (6,): K(187545273439985507098415273777631738640),
+ (4,): K(117928913205007755574446043156465405646),
+ (3,): K(244159722710157842132157548160645018307),
+ (2,): K(200234655086793134086408617236124137371),
+ (1,): K(51914434605509249526780779992574428819),
+ (0,): K(60581150995923875019702403440670701629)
+ }
+ self.assertDictEqual(divpoly(self.secp128r1.curve, 4, 2).as_dict(), coeffs_2)
+
+ def test_mult_by_n(self):
+ # Data from sagemath
+ K = FF(self.secp128r1.curve.prime)
+ coeffs_mx_num = [1,
+ 0,
+ 6,
+ 250332028321891843231386649625583487328,
+ 9]
+ coeffs_mx_denom = [4,
+ 0,
+ 340282366762482138434845932244680310771,
+ 215116352601536216819152607431888567119]
+ coeffs_my_num = {
+ (6, 1): K(8),
+ (4, 1): K(340282366762482138434845932244680310663),
+ (3, 1): K(97594934999395211894955991158534915185),
+ (2, 1): K(340282366762482138434845932244680310423),
+ (1, 1): K(58556960999637127136973594695120949111),
+ (0, 1): K(64081762701549530868458922722690196064)
+ }
+ coeffs_my_denom = {
+ (6, 0): K(64),
+ (4, 0): K(340282366762482138434845932244680310399),
+ (3, 0): K(78075947999516169515964792926827932148),
+ (2, 0): K(576),
+ (1, 0): K(106054522763933629886951553464196514339),
+ (0, 0): K(276200604060932607566387009521990114935)
+ }
+ mx, my = mult_by_n(self.secp128r1.curve, 2)
+ mx_num, mx_denom = mx
+ self.assertListEqual(coeffs_mx_num, list(map(K, mx_num.all_coeffs())))
+ self.assertListEqual(coeffs_mx_denom, list(map(K, mx_denom.all_coeffs())))
+ my_num, my_denom = my
+ self.assertDictEqual(my_num.as_dict(), coeffs_my_num)
+ self.assertDictEqual(my_denom.as_dict(), coeffs_my_denom)
diff --git a/test/sca/test_zvp.py b/test/sca/test_zvp.py
index de86edf..837fb08 100644
--- a/test/sca/test_zvp.py
+++ b/test/sca/test_zvp.py
@@ -1,9 +1,8 @@
from unittest import TestCase
-from sympy import FF
from pyecsca.ec.model import ShortWeierstrassModel
from pyecsca.ec.params import get_params
-from pyecsca.sca.re.zvp import unroll_formula, divpoly0, a_invariants, b_invariants, divpoly, mult_by_n
+from pyecsca.sca.re.zvp import unroll_formula
class ZVPTests(TestCase):
@@ -22,137 +21,3 @@ class ZVPTests(TestCase):
self.assertIsNotNone(results)
results = unroll_formula(self.neg, 11)
self.assertIsNotNone(results)
-
- def test_ainvs(self):
- ainvs = a_invariants(self.secp128r1.curve)
- self.assertSequenceEqual(ainvs, (0,
- 0,
- 0,
- 340282366762482138434845932244680310780,
- 308990863222245658030922601041482374867))
-
- def test_binvs(self):
- binvs = b_invariants(self.secp128r1.curve)
- self.assertSequenceEqual(binvs, (0,
- 340282366762482138434845932244680310777,
- 215116352601536216819152607431888567119,
- 340282366762482138434845932244680310774))
-
- def test_divpoly0(self):
- # Data from sagemath
- coeffs = [11,
- 0,
- 340282366762482138434845932244680302401,
- 211962053797180672439257756222135086642,
- 340282366762482138434845932244678441564,
- 115415922367823003571854983213102698477,
- 152803211743444076787231275062278784385,
- 68540219804769369063918923691867278088,
- 43207172520353703997069627419519708522,
- 83208285732019037267730920881743782729,
- 93286967763556583502947234289842152563,
- 324950611928652823046744874201355360259,
- 244242343224213805514200367379671854852,
- 307096814154284337284845014037169929735,
- 180946781765592277412990188457219828893,
- 301253861469456022084288029442105687698,
- 58053323975526190296189278379252064657,
- 224437885189054146208302696540070489578,
- 281987318191429654256483850017931541622,
- 21449216018131966691124843738286677726,
- 10958264881628724646042625283328121348,
- 104868338562600481545003572552335444641,
- 127205813185570107009206143413997395181,
- 116865717360861207318274706645935808417,
- 281460458922812844939222119784601506753,
- 336607098463310980140968249747513775735,
- 304486486784143285234063826161805094682,
- 194935097339732797131694429642153881938,
- 193523171473792085604518744912658246509,
- 204844449336357293979832621297234119270,
- 244481753281744913785581086721299830802,
- 46816299473081369405217767361380254657,
- 303070923752707405164354702252828590781,
- 222516549119176621389776816552836322766,
- 292006660232236762950883960515487362063,
- 53617127992846936725441702182362940200,
- 242498306026562585655027965022211017540,
- 25039963304689451659955607939868533124,
- 328580435950647191774558154445103295305,
- 24226614081978788956695324769468902511,
- 147945052666123617872720080832548744564,
- 287190187011075399698210761813202261601,
- 117131681517270554750959286838283723521,
- 35018410385280384289320020556813474742,
- 83939964512240352730304831725346032711,
- 147219996946006689656600631222993527180,
- 280430477096741745234510250577626566690,
- 32753113267385981127807026368593329576,
- 105134319561523011785486683031223863934,
- 206456116679151691099661865534540095270,
- 116180470443213022739312068090342951131,
- 245850120846480965440408943459023315919,
- 45805943896736805301879725516256422457,
- 226777421435695229777151315574975350291,
- 283680841707610526659029980964566557627,
- 53168487339451866167506032177471934158,
- 69212302225932892622760219621519562036,
- 183916411340675637978873336955593385541,
- 119478537598919956688656337369481692789,
- 234767298887335988751880131162396819780,
- 218412162101425422347176804186940045781]
-
- K = FF(self.secp128r1.curve.prime)
- poly = divpoly0(self.secp128r1.curve, 11)
- computed = list(map(K, poly.all_coeffs()))
- self.assertListEqual(coeffs, computed)
-
- def test_divpoly(self):
- # Data from sagemath
- K = FF(self.secp128r1.curve.prime)
- coeffs_0 = {
- (0,): K(16020440675387382717114730680672549016),
- (1,): K(269851015321770885610377847857290470365),
- (2,): K(340282366762482138434845932244680310693),
- (3,): K(109469325440469337582450480850803806492),
- (4,): K(340282366762482138434845932244680310753),
- (6,): K(2)
- }
- self.assertDictEqual(divpoly(self.secp128r1.curve, 4, 0).as_dict(), coeffs_0)
- coeffs_1 = {
- (6, 1): K(4),
- (4, 1): K(340282366762482138434845932244680310723),
- (3, 1): K(218938650880938675164900961701607612984),
- (2, 1): K(340282366762482138434845932244680310603),
- (1, 1): K(199419663881059632785909763469900629947),
- (0, 1): K(32040881350774765434229461361345098032)
- }
- self.assertDictEqual(divpoly(self.secp128r1.curve, 4, 1).as_dict(), coeffs_1)
- coeffs_2 = {
- (9,): K(8),
- (7,): K(340282366762482138434845932244680310639),
- (6,): K(187545273439985507098415273777631738640),
- (4,): K(117928913205007755574446043156465405646),
- (3,): K(244159722710157842132157548160645018307),
- (2,): K(200234655086793134086408617236124137371),
- (1,): K(51914434605509249526780779992574428819),
- (0,): K(60581150995923875019702403440670701629)
- }
- self.assertDictEqual(divpoly(self.secp128r1.curve, 4, 2).as_dict(), coeffs_2)
-
- def test_mult_by_n(self):
- # Data from sagemath
- coeffs_num = [85070591690620534608711483061170077696,
- 0,
- 170141183381241069217422966122340155393,
- 62583007080472960807846662406395871832,
- 85070591690620534608711483061170077698]
- coeffs_denom = [1,
- 0,
- 340282366762482138434845932244680310780,
- 308990863222245658030922601041482374867]
-
- num, denom = mult_by_n(self.secp128r1.curve, 2)
- K = FF(self.secp128r1.curve.prime)
- self.assertListEqual(coeffs_num, list(map(K, num.all_coeffs())))
- self.assertListEqual(coeffs_denom, list(map(K, denom.all_coeffs())))
generated by cgit v1.2.3-70-g09d2 (git 2.51.2) at 2025-11-08 14:29:20 +0000