import operator
import numpy as np
import holoviews as hv
import tabulate
from tqdm.auto import tqdm, trange
from IPython.display import HTML, display
from functools import reduce
from pyecsca.ec.model import ShortWeierstrassModel
from pyecsca.ec.coordinates import AffineCoordinateModel
from pyecsca.ec.curve import EllipticCurve
from pyecsca.ec.params import DomainParameters
from pyecsca.ec.formula import FormulaAction
from pyecsca.ec.op import OpType
from pyecsca.ec.point import Point
from pyecsca.ec.mod import mod
from pyecsca.ec.mult import *
from pyecsca.ec.context import DefaultContext, local
from pyecsca.sca.re.rpa import MultipleContext
from pyecsca.sca.attack.leakage_model import HammingWeight
from pyecsca.sca.trace import Trace
from pyecsca.sca.trace.plot import plot_trace, plot_traces
hv.extension("bokeh")
model = ShortWeierstrassModel()
coordsaff = AffineCoordinateModel(model)
coords = model.coordinates["projective"]
add = coords.formulas["add-2007-bl"]
dbl = coords.formulas["dbl-2007-bl"]
neg = coords.formulas["neg"]
# A 64-bit prime order curve for testing things out
p = 0xc50de883f0e7b167
a = mod(0x4833d7aa73fa6694, p)
b = mod(0xa6c44a61c5323f6a, p)
gx = mod(0x5fd1f7d38d4f2333, p)
gy = mod(0x21f43957d7e20ceb, p)
n = 0xc50de885003b80eb
h = 1
infty = Point(coords, X=mod(0, p), Y=mod(1, p), Z=mod(0, p))
g = Point(coords, X=gx, Y=gy, Z=mod(1, p))
curve = EllipticCurve(model, coords, p, infty, dict(a=a,b=b))
params = DomainParameters(curve, g, n, h)
First select a bunch of multipliers. We will be trying to distinguish among these.
multipliers = [
LTRMultiplier(add, dbl, None, False, AccumulationOrder.PeqPR, True, True),
LTRMultiplier(add, dbl, None, True, AccumulationOrder.PeqPR, True, True),
RTLMultiplier(add, dbl, None, False, AccumulationOrder.PeqPR, True),
RTLMultiplier(add, dbl, None, True, AccumulationOrder.PeqPR, False),
SimpleLadderMultiplier(add, dbl, None, True, True),
BinaryNAFMultiplier(add, dbl, neg, None, ProcessingDirection.LTR, AccumulationOrder.PeqPR, True),
WindowNAFMultiplier(add, dbl, neg, 3, None, AccumulationOrder.PeqPR, True, True),
WindowNAFMultiplier(add, dbl, neg, 4, None, AccumulationOrder.PeqPR, True, True),
#WindowNAFMultiplier(add, dbl, neg, 4, None, AccumulationOrder.PeqPR, False, True),
SlidingWindowMultiplier(add, dbl, 3, None, ProcessingDirection.LTR, AccumulationOrder.PeqPR, True),
SlidingWindowMultiplier(add, dbl, 5, None, ProcessingDirection.LTR, AccumulationOrder.PeqPR, True),
FixedWindowLTRMultiplier(add, dbl, 4, None, AccumulationOrder.PeqPR, True),
FixedWindowLTRMultiplier(add, dbl, 5, None, AccumulationOrder.PeqPR, True),
FullPrecompMultiplier(add, dbl, None, True, ProcessingDirection.LTR, AccumulationOrder.PeqPR, True, True),
FullPrecompMultiplier(add, dbl, None, False, ProcessingDirection.LTR, AccumulationOrder.PeqPR, True, True),
#FullPrecompMultiplier(add, dbl, None, False, ProcessingDirection.RTL, AccumulationOrder.PeqPR, True, True),
BGMWMultiplier(add, dbl, 3, None, ProcessingDirection.LTR, AccumulationOrder.PeqPR, True),
BGMWMultiplier(add, dbl, 5, None, ProcessingDirection.LTR, AccumulationOrder.PeqPR, True),
CombMultiplier(add, dbl, 3, None, AccumulationOrder.PeqPR, True),
CombMultiplier(add, dbl, 5, None, AccumulationOrder.PeqPR, True)
]
Now choose a scalar and compute with it using all of the multipliers. Track the amounts of add and dbl formula applications during precomputation and the main scalar multiplication.
scalar = 0b1000000000000000000000000000000000000000000000000
scalar = 0b1111111111111111111111111111111111111111111111111
scalar = 0b1010101010101010101010101010101010101010101010101
scalar = 0b1111111111111111111111110000000000000000000000000
scalar = 123456789123456789
def count_formula_actions(ctx, formula):
actions = []
def callback(action):
if isinstance(action, FormulaAction) and action.formula == formula:
actions.append(action)
ctx.actions[0].walk(callback)
return len(actions)
def simulate_trace(ctx):
lm = HammingWeight()
trace = []
def callback(action):
if isinstance(action, FormulaAction):
for intermediate in action.op_results:
leak = lm(intermediate.value)
trace.append(leak)
trace.extend([0] * 20)
ctx.actions[0].walk(callback)
return Trace(np.array(trace))
traces = []
table = [["Multiplier", "Precomp add", "Precomp dbl", "Precomp total", "Multiply add", "Multiply dbl", "Multiply total", "Total"]]
for mult in multipliers:
with local(DefaultContext()) as ctx:
mult.init(params, g)
precomp_add = count_formula_actions(ctx, add)
precomp_dbl = count_formula_actions(ctx, dbl)
precomp_trace = simulate_trace(ctx)
with local(DefaultContext()) as ctx:
mult.multiply(scalar)
multiply_add = count_formula_actions(ctx, add)
multiply_dbl = count_formula_actions(ctx, dbl)
formula_count = precomp_add + precomp_dbl + multiply_add + multiply_dbl
multiply_trace = simulate_trace(ctx)
traces.append(multiply_trace)
table.append([mult, precomp_add, precomp_dbl, precomp_add + precomp_dbl, multiply_add, multiply_dbl, multiply_add + multiply_dbl, formula_count])
display(HTML(tabulate.tabulate(table, tablefmt="html", headers="firstrow")))
Now we can look at the distributions of the number of operations for random scalars.
scalars = [int(Mod.random(params.order)) for _ in range(100)]
counts = {}
for i, mult in enumerate(tqdm(multipliers)):
counts[mult] = []
for scalar in tqdm(scalars, leave=False):
mult.init(params, g)
with local(DefaultContext()) as ctx:
mult.multiply(int(scalar))
multiply_add = count_formula_actions(ctx, add)
multiply_dbl = count_formula_actions(ctx, dbl)
counts[mult].append(multiply_add + multiply_dbl)
count_max = max(map(max, counts.values()))
count_min = min(map(min, counts.values()))
grams = []
for i, item in enumerate(counts.items()):
mult, count = item
freqs, edges = np.histogram(count, range=(count_min, count_max), bins=50, density=True)
grams.append(hv.Histogram((edges, freqs), label=mult.__class__.__name__ + str(i)))
reduce(operator.mul, grams[1:], grams[0]).opts(hv.opts.Histogram(alpha=1)).opts(responsive=True, height=500, xlabel="Opertion count")
We can apply similar structural techniques to examine formulas.
adds = list(filter(lambda formula: formula.name.startswith("add"), coords.formulas.values()))
dbls = list(filter(lambda formula: formula.name.startswith("dbl"), coords.formulas.values()))
def op_string(formula):
ops = []
for op in formula.code:
if op.operator == OpType.Mult:
ops.append("m")
elif op.operator == OpType.Sqr:
ops.append("s")
elif op.operator == OpType.Add:
ops.append("+")
elif op.operator == OpType.Sub:
ops.append("-")
elif op.operator == OpType.Pow and op.right == 3:
ops.append("sm")
elif op.operator == OpType.Id:
pass
else:
print(op.operator, op.right)
return "".join(ops)
table = [["Formula", "count", "ops"]]
for add in adds:
ops = op_string(add)
table.append([add.name, len(ops), ops])
for dbl in dbls:
ops = op_string(dbl)
table.append([dbl.name, len(ops), ops])
display(HTML(tabulate.tabulate(table, tablefmt="html", headers="firstrow", colalign=("left", "center", "left"))))