functional_ecc.py

# -*- coding: utf-8 -*-
"""Functional implementation of ECC multiplication and addition.
Addition and multiplication are the most fundamental elliptic curve operations.
"""
from collections import namedtuple
from sympy import mod_inverse


at_infinity = object()


domain_param = namedtuple("domain_param", "prime a b G_x G_y n")
domain_params = {
    "P-192": domain_param(
        prime=0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFFFFFFFFFFFF,
        b=0x64210519E59C80E70FA7E9AB72243049FEB8DEECC146B9B1,
        a=0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFFFFFFFFFFFC,
        G_x=0x188DA80EB03090F67CBF20EB43A18800F4FF0AFD82FF1012,
        G_y=0x07192B95FFC8DA78631011ED6B24CDD573F977A11E794811,
        n=0xFFFFFFFFFFFFFFFFFFFFFFFF99DEF836146BC9B1B4D22831,
    ),
    "P-224": domain_param(
        prime=0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF000000000000000000000001,
        a=0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFFFFFFFFFFFFFFFFFFFE,
        b=0xB4050A850C04B3ABF54132565044B0B7D7BFD8BA270B39432355FFB4,
        G_x=0xB70E0CBD6BB4BF7F321390B94A03C1D356C21122343280D6115C1D21,
        G_y=0xBD376388B5F723FB4C22DFE6CD4375A05A07476444D5819985007E34,
        n=0xFFFFFFFFFFFFFFFFFFFFFFFFFFFF16A2E0B8F03E13DD29455C5C2A3D,
    ),
    "P-256": domain_param(
        prime=0xFFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFF,
        a=0xFFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFC,
        b=0x5AC635D8AA3A93E7B3EBBD55769886BC651D06B0CC53B0F63BCE3C3E27D2604B,
        G_x=0x6B17D1F2E12C4247F8BCE6E563A440F277037D812DEB33A0F4A13945D898C296,
        G_y=0x4FE342E2FE1A7F9B8EE7EB4A7C0F9E162BCE33576B315ECECBB6406837BF51F5,
        n=0xFFFFFFFF00000000FFFFFFFFFFFFFFFFBCE6FAADA7179E84F3B9CAC2FC632551,
    ),
    "P-384": domain_param(
        prime=0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFFFF0000000000000000FFFFFFFF,
        a=0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFFFF0000000000000000FFFFFFFC,
        b=0xB3312FA7E23EE7E4988E056BE3F82D19181D9C6EFE8141120314088F5013875AC656398D8A2ED19D2A85C8EDD3EC2AEF,
        G_x=0xAA87CA22BE8B05378EB1C71EF320AD746E1D3B628BA79B9859F741E082542A385502F25DBF55296C3A545E3872760AB7,
        G_y=0x3617DE4A96262C6F5D9E98BF9292DC29F8F41DBD289A147CE9DA3113B5F0B8C00A60B1CE1D7E819D7A431D7C90EA0E5F,
        n=0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFC7634D81F4372DDF581A0DB248B0A77AECEC196ACCC52973,
    ),
    "P-521": domain_param(
        prime=2 ** 521 - 1,
        a=2 ** 521 - 4,
        b=0x0051953EB9618E1C9A1F929A21A0B68540EEA2DA725B99B315F3B8B489918EF109E156193951EC7E937B1652C0BD3BB1BF073573DF883D2C34F1EF451FD46B503F00,
        G_x=0xC6858E06B70404E9CD9E3ECB662395B4429C648139053FB521F828AF606B4D3DBAA14B5E77EFE75928FE1DC127A2FFA8DE3348B3C1856A429BF97E7E31C2E5BD66,
        G_y=0x11839296A789A3BC0045C8A5FB42C7D1BD998F54449579B446817AFBD17273E662C97EE72995EF42640C550B9013FAD0761353C7086A272C24088BE94769FD16650,
        n=0x01FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFA51868783BF2F966B7FCC0148F709A5D03BB5C9B8899C47AEBB6FB71E91386409,
    ),
}


def calculate_slope(x1, y1, x2, y2, prime, a):
    assert x1 == x1 % prime
    assert y1 == y1 % prime
    assert x2 == x2 % prime
    assert y2 == y2 % prime
    return (
        mod_inverse(2 * y1, prime) * (3 * x1 ** 2 + a) % prime
        if (x1, y1) == (x2, y2)
        else mod_inverse(x2 - x1, prime) * (y2 - y1) % prime
    )


def point_add(x1, y1, x2, y2, prime, a):
    """ Semantics of point at infinity is y coordinate is None"""

    if y1 is at_infinity:
        return x2, y2
    if y2 is at_infinity:
        return x1, y1
    if (x1, y1) == (x2, -1 * y2 % prime):
        return x1, at_infinity

    slope = calculate_slope(x1, y1, x2, y2, prime, a)
    x3 = (slope ** 2 - x1 - x2) % prime
    y3 = (slope * (x1 - x3) - y1) % prime
    return x3, y3


def point_multiply(x1, y1, multiplicant, prime, a):
    assert multiplicant >= 1
    x2, y2 = x1, y1

    # Skip first '1' digit and start double and add sequence
    for digit in bin(multiplicant)[3:]:
        x2, y2 = point_add(x2, y2, x2, y2, prime, a)
        if digit == "1":
            x2, y2 = point_add(x1, y1, x2, y2, prime, a)

    return x2, y2