<jupyter_start><jupyter_text>Example of a Refined Power Analysis attack on a double-and-add algorithm<jupyter_code>from pyecsca.ec.params import get_params
from pyecsca.ec.model import ShortWeierstrassModel
from pyecsca.ec.mult import LTRMultiplier
from pyecsca.ec.context import DefaultContext, local
from pyecsca.ec.point import Point
from pyecsca.ec.mod import Mod
# Setup the secp256r1 curve and some complete formulas and a double-and-add left-to-right multiplier
params = get_params("secg", "secp256r1", "projective")
p = params.curve.prime
g = params.generator.to_affine()
coords = params.curve.coordinate_model
add_formula = coords.formulas["add-2016-rcb"]
dbl_formula = coords.formulas["dbl-2016-rcb"]
neg_formula = coords.formulas["neg"]
mult = LTRMultiplier(add=add_formula, dbl=dbl_formula, complete=True)
# Pick a "random" scalar and compute the public key
scalar = 123456789123456789123456789123456789123456789123456789 % params.order
pubkey = params.curve.affine_multiply(params.generator.to_affine(), scalar)
# A point with a zero-coordinate (of large order)
rpa_p0 = Point(coords, X=Mod(0, p),
                       Y=Mod(69528327468847610065686496900697922508397251637412376320436699849860351814667, p),
                       Z=Mod(1, p))

# Multiply the RPA point above with the inverse of `c` to obtain a point which when multiplied by `c` leads
# to the RPA point.
def rpa_c(c) -> Point:
    """Compute [c^-1]P_O."""
    return params.curve.affine_multiply(rpa_p0.to_affine(),
                                        int(Mod(c, params.order).inverse())).to_model(coords, params.curve)

def query(pt: Point) -> bool:
    """Query the implementation and observe the RPA side-channel,
       i.e. whether a zero occured in some output of a formula."""
    with local(DefaultContext()) as ctx:
        mult.init(params, pt)
        mult.multiply(scalar)
    smult, subtree = ctx.actions.get_by_index([0])
    for formula_action in subtree:
        if formula_action.output_points[0].X == Mod(0, p):
            return True
    return False

def try_guess(guess) -> bool:
    """Test if we have the right private key."""
    return params.curve.affine_multiply(g, guess) == pubkey
# The attack itself, recovered scalar is in the `recovered` variable
recovered = 1
while True:
    """RPA attack for left-to-right double-and-add always"""
    p1guess = rpa_c(recovered + 1)
    if query(p1guess):
        recovered = (recovered + 1)
    print(bin(recovered))
    if try_guess(recovered):
        break
    recovered = recovered * 2
print(recovered == scalar)<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.10445468509984639, 'fraction_numerical': 0.06182795698924731, 'mean_word_length': 3.851024208566108, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 8, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '1', 'dir': 'jupyter-structured-clean-dedup', 'id': '405902', 'license': 'MIT', 'n_tokens_mistral': 966, 'n_tokens_neox': 848, 'n_words': 230, 'path': 'rpa/rpa_example.ipynb', 'repo_name': 'crocs-muni/formula-for-disaster', 'size': '2604'}