sextic_search.sage

# Copyright (c) 2022-2023 Toposware, Inc.
#
# Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
# http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
# <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
# option. This file may not be copied, modified, or distributed
# except according to those terms.

"""
This module aims at finding curves defined over sextic extensions of prime fields.
"""

import sys
from multiprocessing import cpu_count, Pool
from traceback import print_exc

from utils import POLLARD_RHO_SECURITY, POLLARD_RHO_TWIST_SECURITY, EMBEDDING_DEGREE_SECURITY
from utils import find_irreducible_poly, find_sparse_irreducible_poly, poly_weight
from utils import generic_curve_security, sextic_extension_specific_security, generic_twist_security_ignore_embedding_degree
from util_hashtocurve import OptimizedSSWU

if sys.version_info[0] == 2:
    range = xrange


def find_curve(extension, max_cofactor, small_order, sswu_string, wid=0, processes=1):
    r"""Yield curve constructed over a prime field extension.

    INPUT:

    - ``extension`` -- the field seen as a direct extension
    - ``max_cofactor`` -- the maximum cofactor for the curve order
    - ``small_order`` -- boolean indicating whether to look for small orders (252-255 bits).
            Overrides `max_cofactor` if set to `True`.
    - ``sswu_string`` -- the string to be used when generating the subgroup basepoint with SSWU hash-to-curve
    - ``wid`` -- current job id (default 0)
    - ``processes`` -- number of concurrent jobs (default 1)

    OUTPUT:

    - ``extension`` -- the field extension
    - ``E`` -- the curve definition
    - ``g`` -- a generator of the large prime order subgroup
    - ``prime_order`` -- the prime order of the large subgroup generated by g
    - ``cofactor`` -- the cofactor of the curve
    - ``coeff_a`` -- the a coefficient of the curve in short Weierstrass form (always 1)
    - ``coeff_b`` -- the b coefficient of the curve in short Weierstrass form
    - ``rho_sec`` -- the Pollard-Rho security of the curve
    - ``k`` -- the embedding degree of the curve
    - ``twist_rho_sec`` -- the Pollard-Rho security of the twist

    """

    a = extension.gen()
    for i in range(wid + 395, 1000000000, processes):
        sys.stdout.write(".")
        sys.stdout.flush()

        coeff_a = 1
        coeff_b = a + i

        E = EllipticCurve(extension, [coeff_a, coeff_b])

        n = E.count_points()
        prime_order = list(ecm.factor(n))[-1]
        cofactor = n // prime_order
        if small_order:
            if prime_order.nbits() < 252 or prime_order.nbits() > 255:
                continue
        elif cofactor > max_cofactor:
            continue

        sys.stdout.write("o")
        sys.stdout.flush()

        # We generate a point on the curve with the SSWU hash-to-curve algorithm.
        # If the point is not in the prime-order subgroup, we multiply it by the cofactor.
        curve_sswu = OptimizedSSWU(extension, coeff_a, coeff_b)
        bin = BinaryStrings()
        sswu_bin_encoding = bin.encoding("Cheetah - Pedersen")
        sswu_int = extension(int(str(sswu_bin_encoding), 2))
        g_ped = curve_sswu.map_to_curve(sswu_int)

        if prime_order * g_ped != E(0, 1, 0):
            g_ped = cofactor * g_ped

        bin = BinaryStrings()
        sswu_bin_encoding = bin.encoding(sswu_string)
        sswu_int = extension(int(str(sswu_bin_encoding), 2))
        g = curve_sswu.map_to_curve(sswu_int)

        if prime_order * g != E(0, 1, 0):
            g = cofactor * g

        (rho_sec, k) = generic_curve_security(
            extension.cardinality(), n, prime_order)

        if k.nbits() < EMBEDDING_DEGREE_SECURITY:
            continue

        sys.stdout.write("+")
        sys.stdout.flush()

        if rho_sec < POLLARD_RHO_SECURITY:
            continue

        sys.stdout.write("~")
        sys.stdout.flush()

        extension_sec = sextic_extension_specific_security(
            E, coeff_a, coeff_b, extension, n)
        if not extension_sec:
            continue

        # Factorization for calculating the embedding degree can be extremely slow
        # hence this check must be performed separately on potential candidates
        # outputted by the search algorithm.
        twist_rho_sec = generic_twist_security_ignore_embedding_degree(
            extension.cardinality(), n)

        if twist_rho_sec < POLLARD_RHO_TWIST_SECURITY:
            continue

        yield (extension, E, g, g_ped, prime_order, cofactor, coeff_a, coeff_b, rho_sec, k, twist_rho_sec)


def print_curve(prime, extension_degree, max_cofactor, small_order, sswu_string, wid=0, processes=1):
    r"""Print parameters of curves defined over a prime field extension

    INPUT:

    - ``prime`` -- the base prime defining Fp
    - ``extension_degree`` -- the targeted extension degree, defining Fp^n on which the curves will be constructed
    - ``max_cofactor`` -- the maximum cofactor for the curve order
    - ``small_order`` -- boolean indicating whether to look for small orders (252-255 bits).
            Overrides `max_cofactor` if set to `True`.
    - ``sswu_string`` -- the string to be used when generating the subgroup basepoint with SSWU hash-to-curve
    - ``wid`` -- current job id (default 0)
    - ``processes`` -- number of concurrent jobs (default 1)

    """

    Fp = GF(prime)
    if wid == 0:
        info = f"\n{Fp}.\n"
    Fpx = Fp['x']
    poly = find_sparse_irreducible_poly(Fpx, extension_degree, use_root=True)
    if poly == 0:
        poly_list = find_irreducible_poly(
            Fpx, extension_degree, output_all=True)
        if poly_list == []:
            poly_list = find_irreducible_poly(
                Fpx, extension_degree, use_root=True, output_all=True)
        if poly_list == []:
            raise ValueError(
                'Could not find an irreducible polynomial with specified parameters.')
        poly_list.sort(key=lambda e: poly_weight(e, prime))
        poly = poly_list[0]  # extract the polynomial from the list
    Fp = Fp.extension(poly, "u")
    if wid == 0:
        info += f"Modulus: {poly}.\n"

    if wid == 0:
        if small_order:
            info += f"Looking for curves with 252-255-bit prime order.\n"
        elif max_cofactor != 1:
            info += f"Looking for curves with max cofactor: {max_cofactor}.\n"
        else:
            info += f"Looking for prime-order curves.\n"
        print(info)

    for (extension, E, g, g_ped, order, cofactor, _coeff_a, coeff_b, rho_security, embedding_degree, twist_rho_security) in find_curve(Fp, max_cofactor, small_order, sswu_string, wid, processes):
        output = "\n\n\n"
        output += f"E(GF(({extension.base_ring().order().factor()})^{extension.degree()})) : y^2 = x^3 + x + {coeff_b}\n"
        output += f"E generator point (from SSWU on '{sswu_string}'): {g}\n"
        output += f"E generator point (from SSWU on 'Cheetah - Pedersen'): {g_ped}\n"
        output += f"Curve prime order: {order} ({order.nbits()} bits)\n"
        output += f"Curve cofactor: {cofactor}"
        if cofactor > 4:
            output += f" ( = {cofactor % 4} % 4 )"
        output += f"\nCurve security (Pollard-Rho): {'%.2f'%(rho_security)}\n"
        output += f"Curve embedding degree: {embedding_degree} (>2^{embedding_degree.nbits()-1}) \n"
        output += f"Twist security (Pollard-Rho): {'%.2f'%(twist_rho_security)}\n"
        # checked in find_curve
        output += f"Curve resistant to cover and decomposition attacks: True\n\n"
        print(output)
    return

########################################################################


def main():
    """Main function"""
    args = sys.argv[1:]
    processes = 1 if "--sequential" in args else cpu_count()
    small_order = "--small-order" in args
    help = "--help" in args
    args = [arg for arg in args if not arg.startswith("--")]

    if help:
        print("""
Cmd: sage sextic_search.sage [--sequential] [--small-order] <prime> <max_cofactor> <sswu_string>

Args:
    --sequential        Uses only one process
    --small-order       Looks for curves with 252-255-bit prime order (overrides cofactor)
    <prime>             A prime number, default 2^64 - 2^32 + 1
    <max_cofactor>      Maximum cofactor of the curve, default 1 (prime order curve)
    <sswu_string>       The string to be passed to the SSWU map to curve algorithm
""")
        return

    prime = int(args[0]) if len(
        args) > 0 else 2**64 - 2**32 + 1
    extension_degree = 6
    max_cofactor = int(args[1]) if len(args) > 1 else 1
    sswu_string = str(args[3]) if len(args) > 3 else "Cheetah"

    if processes == 1:
        print_curve(prime, extension_degree,
                    max_cofactor, small_order, sswu_string)
    else:
        print(f"Using {processes} processes.")
        pool = Pool(processes=processes)

        try:
            for wid in range(processes):
                pool.apply_async(
                    worker, (prime, extension_degree, max_cofactor, small_order, sswu_string, wid, processes))

            while True:
                sleep(1000)
        except (KeyboardInterrupt, SystemExit):
            pass
        finally:
            pool.terminate()


def worker(*args):
    res = []
    try:
        res = real_worker(*args)
    except (KeyboardInterrupt, SystemExit):
        pass
    except:
        print_exc()
    finally:
        return res


def real_worker(*args):
    return print_curve(*args)


main()