<commit_before>#!/usr/bin/env python3

# Copyright (C) 2020 The btclib developers
#
# This file is part of btclib. It is subject to the license terms in the
# LICENSE file found in the top-level directory of this distribution.
#
# No part of btclib including this file, may be copied, modified, propagated,
# or distributed except according to the terms contained in the LICENSE file.

"""Elliptic curve point multiplication functions.

The implemented algorithms are:
    - Montgomery Ladder
    - Scalar multiplication on basis 3
    - Fixed window
    - Sliding window
    - w-ary non-adjacent form (wNAF)

References:
    - https://en.wikipedia.org/wiki/Elliptic_curve_point_multiplication
    - https://cryptojedi.org/peter/data/eccss-20130911b.pdf
    - https://ecc2017.cs.ru.nl/slides/ecc2017school-castryck.pdf

TODO:
    - Computational cost of the different multiplications
    - New alghoritms at the state-of-art:
        -https://hal.archives-ouvertes.fr/hal-00932199/document
        -https://iacr.org/workshops/ches/ches2006/presentations/Douglas%20Stebila.pdf
        -1-s2.0-S1071579704000395-main
    - Elegance in the code
    - Solve problem with wNAF and w=1
    - Multi_mult algorithm: why does it work?
"""


from typing import List

from .alias import INFJ, JacPoint
from .curvegroup import CurveGroup


def convert_number_to_base(i: int, base: int) -> List[int]:
    "Return the digits of an integer in the requested base."

    digits: List[int] = []
    while i or not digits:
        i, idx = divmod(i, base)
        digits.append(idx)
    return digits[::-1]


def mods(m: int, w: int) -> int:
    """Signed modulo function.

    FIXME:
    mods does NOT work for w=1. However the function in NOT really meant to be used for w=1
    For w=1 it always gives back -1 and enters an infinte loop
    """

    w2 = pow(2, w)
    M = m % w2
    return M - w2 if M >= (w2 / 2) else M


def _mult_mont_ladder(m: int, Q: JacPoint, ec: CurveGroup) -> JacPoint:
    """Scalar multiplication using 'Montgomery ladder' algorithm.

    This implementation uses
    'Montgomery ladder' algorithm,
    'left-to-right' binary decomposition of the m coefficient,
    Jacobian coordinates.

    The input point is assumed to be on curve and
    the m coefficient is assumed to have been reduced mod n
    if appropriate (e.g. cyclic groups of order n).
    """

    if m < 0:
        raise ValueError(f"negative m: {hex(m)}")

    R = INFJ  # initialize as infinity point
    for m in [int(i) for i in bin(m)[2:]]:  # goes through binary digits
        if m == 0:
            Q = ec._add_jac(R, Q)
            R = ec._double_jac(R)
        else:
            R = ec._add_jac(R, Q)
            Q = ec._double_jac(Q)
    return R


def _mult_base_3(m: int, Q: JacPoint, ec: CurveGroup) -> JacPoint:
    """Scalar multiplication using ternary decomposition of the scalar.

    This implementation uses
    'double & add' algorithm,
    'left-to-right' biternaryary decomposition of the m coefficient,
    Jacobian coordinates.

    TODO: make it constant-time.

    The input point is assumed to be on curve and
    the m coefficient is assumed to have been reduced mod n
    if appropriate (e.g. cyclic groups of order n).
    """

    if m < 0:
        raise ValueError(f"negative m: {hex(m)}")

    base = 3
    M = convert_number_to_base(m, base)

    T = [INFJ]
    for i in range(1, base):
        T.append(ec._add_jac(T[i - 1], Q))

    R = T[M[0]]
    for i in range(1, len(M)):
        R2 = ec._double_jac(R)
        R = ec._add_jac(R2, R)<commit_msg>made Montgomery Ladder constant time<commit_after>#!/usr/bin/env python3

# Copyright (C) 2020 The btclib developers
#
# This file is part of btclib. It is subject to the license terms in the
# LICENSE file found in the top-level directory of this distribution.
#
# No part of btclib including this file, may be copied, modified, propagated,
# or distributed except according to the terms contained in the LICENSE file.

"""Elliptic curve point multiplication functions.

The implemented algorithms are:
    - Montgomery Ladder
    - Scalar multiplication on basis 3
    - Fixed window
    - Sliding window
    - w-ary non-adjacent form (wNAF)

References:
    - https://en.wikipedia.org/wiki/Elliptic_curve_point_multiplication
    - https://cryptojedi.org/peter/data/eccss-20130911b.pdf
    - https://ecc2017.cs.ru.nl/slides/ecc2017school-castryck.pdf

TODO:
    - Computational cost of the different multiplications
    - New alghoritms at the state-of-art:
        -https://hal.archives-ouvertes.fr/hal-00932199/document
        -https://iacr.org/workshops/ches/ches2006/presentations/Douglas%20Stebila.pdf
        -1-s2.0-S1071579704000395-main
    - Elegance in the code
    - Solve problem with wNAF and w=1
    - Multi_mult algorithm: why does it work?
"""


from typing import List

from .alias import INFJ, JacPoint
from .curvegroup import CurveGroup


def convert_number_to_base(i: int, base: int) -> List[int]:
    "Return the digits of an integer in the requested base."

    digits: List[int] = []
    while i or not digits:
        i, idx = divmod(i, base)
        digits.append(idx)
    return digits[::-1]


def mods(m: int, w: int) -> int:
    """Signed modulo function.

    FIXME:
    mods does NOT work for w=1. However the function in NOT really meant to be used for w=1
    For w=1 it always gives back -1 and enters an infinte loop
    """

    w2 = pow(2, w)
    M = m % w2
    return M - w2 if M >= (w2 / 2) else M


def _mult_mont_ladder(m: int, Q: JacPoint, ec: CurveGroup) -> JacPoint:
    """Scalar multiplication using 'Montgomery ladder' algorithm.

    This implementation uses
    'Montgomery ladder' algorithm,
    'left-to-right' binary decomposition of the m coefficient,
    Jacobian coordinates.

    It is constant-time and resistant to the FLUSH+RELOAD attack,
    as it prevents branch prediction avoiding any if.

    The input point is assumed to be on curve and
    the m coefficient is assumed to have been reduced mod n
    if appropriate (e.g. cyclic groups of order n).
    """

    if m < 0:
        raise ValueError(f"negative m: {hex(m)}")

    # R[0] is the running result, R[1] = R[0] + Q is an ancillary variable
    R = [INFJ, Q]
    for i in [int(i) for i in bin(m)[2:]]:
        R[not i] = ec._add_jac(R[i], R[not i])
        R[i] = ec._double_jac(R[i])
    return R[0]


def _mult_base_3(m: int, Q: JacPoint, ec: CurveGroup) -> JacPoint:
    """Scalar multiplication using ternary decomposition of the scalar.

    This implementation uses
    'double & add' algorithm,
    'left-to-right' biternaryary decomposition of the m coefficient,
    Jacobian coordinates.

    TODO: make it constant-time.

    The input point is assumed to be on curve and
    the m coefficient is assumed to have been reduced mod n
    if appropriate (e.g. cyclic groups of order n).
    """

    if m < 0:
        raise ValueError(f"negative m: {hex(m)}")

    base = 3
    M = convert_number_to_base(m, base)

    T = [INFJ]
    for i in range(1, base):
        T.append(ec._add_jac(T[i - 1], Q))

    R = T[M[0]]
    for i in range(1, len(M)):
        R2 = ec._double_jac(R)
        R = ec._add_jac(R2, R)
{'fraction_non_alphanumeric': 0.09818333102204965, 'fraction_numerical': 0.022327000416031063, 'mean_word_length': 2.7464935064935063, 'pattern_counts': {'":': 0, '<': 7, '<?xml version=': 0, '>': 13, 'https://': 10, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '1161237', 'n_tokens_mistral': 2492, 'n_tokens_neox': 2310, 'n_words': 840}