ecpp

#!/usr/bin/python3

# Author: Hubert Kario, Stefan Dordevic
# Released under Gnu GPL v2.1, see LICENSE file for details

from __future__ import print_function, division
import os
import errno
import sys
import getopt
import math
import six
try:
    import ConfigParser
except ImportError:
    import configparser as ConfigParser
try:
    import StringIO
except ImportError:
    import io as StringIO
import pkg_resources
from ecpp.verify import lucas_lehmer_riesel_test, pocklington_test, curve_test
from ecpp.convert import sha256_of_number
from ecpp.snfs_check import snfs_vulnerable

# xrange python3 compatibility
try:
    xrange
except NameError:
    xrange = range

# input files directory for primo tool
PRIMO_IN = 'in/'

# dict with params
PARAMS = {}


def par_set():
    """Paramater set/reset function"""
    PARAMS.update({'s': None, 'w': None, 'j': None, 't': None,
                   'a': None, 'b': None, 'q': None, 'r': None})


if six.PY2:
    def read_config(filename, resource):
        config = ConfigParser.RawConfigParser(allow_no_value=True)

        if resource:
            # on py2 config parser needs files but uncompressing them
            # to a tmp dir is slow, so do memory buffer instead
            config_buff = pkg_resources.resource_string("ecpp", filename)
            config_fp = StringIO.StringIO(config_buff)
            config.readfp(config_fp)
        else:
            with open(filename) as fp:
                config.readfp(fp)

        return config
else:
    def read_config(filename, resource):
        config = ConfigParser.RawConfigParser(allow_no_value=True)

        if resource:
            config_buff = pkg_resources.resource_string("ecpp", filename)
            config_buff = str(config_buff, "utf-8")
        else:
            with open(filename) as fp:
                config_buff = fp.read()
        config.read_string(config_buff)

        return config


# division function
def is_prime_64(n):
    """Check if number is a prime through trial division"""
    if n % 2 == 0:
        raise ValueError("not prime")
    for i in xrange(3, int(n**0.5)+1, 2):
        if n % i == 0:
            raise ValueError("not prime: " + str(n))


def is_prime_64_MR(n):
    """
    Check if 64 bit number is prime using Miller-Rabin algorithm.

    Since we are limiting the input space, we can select bases to which
    the primality needs to be checked to verify primality of the number.
    """
    if n % 2 == 0:
        raise ValueError("not prime")
    if n > 2**64 or n < 2:
        raise ValueError("parameter outside valid range")

    s = n - 1
    t = 0
    while s % 2 == 0:
        s, t = s // 2, t + 1

    # bases needed for verifying n <= 2**64
    for a in [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]:
        v = pow(a, s, n)
        if v == 1:
            continue
        i = 0
        while v != n - 1:
            if i == t - 1:
                return False
            else:
                v, i = pow(v, 2, n), i + 1
    return True


def candidate_finder(filename, resource):
    """Return the int number from certificates Candidate section.
       If file is malformed, file is not primality certificate, or version
       of primality certificate is unsupported 'None' will be returned"""
    config = read_config(filename, resource)
    v = config.get('PRIMO - Primality Certificate', 'Format')
    if v == "4":
        n = config.get('Candidate', 'N')
        n = int(n.replace("$", ""), 16)
        return n
    else:
        return


def create_in_file(directory, int_prime_moduli):
    """Create input file for primo tool"""
    file_name = sha256_of_number(int_prime_moduli)
    file_name = str(file_name + ".in")
    try:
        os.makedirs(directory)
    except OSError as e:
        if e.errno != errno.EEXIST:
            raise
    with open(directory + file_name, "w+") as f:
        f.write("[Candidate]\n")
        f.write("N={0}\n".format(int_prime_moduli))


def verify(config):
    """Primality certificate verification"""
    sections = config.sections()

    # set paramiters
    par_set()

    # set combinations
    c_t1 = set(['s', 'w', 'j', 't'])
    c_t2 = set(['s', 'w', 'a', 'b', 't'])
    llr_t = set(['s', 'q'])
    bls_t = set(['s', 'b'])

    # prime candidate
    n = config.get('Candidate', 'N')
    n = int(n.replace("$", ""), 16)
    section = str(1)
    run = True
    while run:
        if section in sections:
            par_set()
            par_list = set([])
            options = config.options(section)
            for option in options:
                value = config.get(section, option)
                PARAMS[option] = int(value.replace("$", ""), 16)
                par_list.add(option)
            s = PARAMS['s']
            w = PARAMS['w']
            t = PARAMS['t']
            j = PARAMS['j']
            a = PARAMS['a']
            b = PARAMS['b']
            q = PARAMS['q']
            if c_t1 == par_list:
                n = curve_test(n, s, w, t, j=j)
            if c_t2 == par_list:
                n = curve_test(n, s, w, t, a, b)
            if llr_t == par_list:
                n = lucas_lehmer_riesel_test(n, s, q)
            if bls_t == par_list:
                n = pocklington_test(n, s, b)
            section = str(int(section) + 1)
            run = True
        else:
            run = False
    try:
        is_prime_64_MR(n)
    except KeyboardInterrupt:
        print(n)
        raise
    return True


def number_to_work_unit(number):
    """
    Try to estimate the amount of work needed to verify certificate of
    given number
    """
    bit_size = math.ceil(math.log(number, 2))
    # derived experimentally
    a = 3.522712
    b = 3.95577E-12
    return b * bit_size ** a


def correlate(moduli, certs=None, verify_opt=None, primo_opt=None):
    """Correlate between functionalities"""
    missing_cert_flag = False
    if certs is None:
        # use built-in
        dirs = ["certificates/" + i for i in
                pkg_resources.resource_listdir("ecpp", "certificates")
                if pkg_resources.resource_isdir("ecpp", "certificates/" + i)]
        cert_files = []
        for name in dirs:
            cert_files.extend(name + "/" + i for i in
                              pkg_resources.resource_listdir("ecpp", name)
                              if i.endswith('.out'))
        cert_dict = {}
        for cert in cert_files:
            cert_candidate = candidate_finder(cert, True)
            cert_dict[cert_candidate] = cert

    else:
        cert_files = []
        for path, _, files in os.walk(certs):
            for name in files:
                cert_files.append(os.path.join(path, name))
        cert_dict = {}
        for cert in cert_files:
            if cert.endswith('.out'):
                cert_candidate = candidate_finder(cert, False)
                cert_dict[cert_candidate] = cert

    sum_work = 0.0
    work_done = 0.0
    with open(str(moduli)) as f:
        inputfile = filter(None, (line.rstrip() for line in f))
        for line in inputfile:
            if line.startswith('#'):
                continue
            prime_moduli = int(line.split(" ")[6], 16)
            sum_work += number_to_work_unit(prime_moduli) * 2

    with open(str(moduli)) as f:
        inputfile = filter(None, (line.rstrip() for line in f))
        for count_line, line in enumerate(inputfile, 1):
            if line.startswith('#'):
                continue
            prime_moduli = (line.split(" ")[6])
            int_prime_moduli = int(prime_moduli, 16)
            sophie_prime_moduli = (int_prime_moduli - 1) // 2
            primes = []
            primes.append(int_prime_moduli)
            primes.append(sophie_prime_moduli)
            print_out = []
            for p in primes:
                if p in cert_dict:
                    if verify_opt:
                        print("Verifying... {0:5.2f}% done".format(
                              work_done / sum_work * 100), end="\r")
                        cert = read_config(cert_dict[p], certs is None)
                        if verify(cert):
                            print_out.append("cert: {0} - is a prime number"
                                             .format(cert_dict[p]))
                        else:
                            missing_cert_flag = True
                            print_out.append("cert: {0} - is NOT a prime number"
                                             .format(cert_dict[p]))
                        if p == int_prime_moduli:
                            if snfs_vulnerable(p):
                                print_out.append("IS vulnerable "
                                                 "to SNFS attacks"
                                                 .format(cert_dict[p]))
                                missing_cert_flag = True
                            else:
                                print_out.append("is not "
                                                 "vulnerable to SNFS attacks"
                                                 .format(cert_dict[p]))
                        work_done += number_to_work_unit(p)
                        print("Verifying... {0:5.2f}% done".format(
                              work_done / sum_work * 100), end="\r")
                    else:
                        print_out.append("cert: {0}".format(cert_dict[p]))
                else:
                    missing_cert_flag = True
                    if primo_opt:
                        print_out.append("creating input file for primo")
                        create_in_file(PRIMO_IN, p)
                    else:
                        print_out.append("cert: missing")
            print("[{0}] line {1}: {2}"
                  .format("-" if missing_cert_flag else "+",
                          count_line,
                          ", ".join(print_out)))
    return missing_cert_flag


def snfs_vulnerable_file(path):
    """Check if the prime in Primo certificate is vulnerable to SNFS."""
    config = read_config(path, False)

    n = config.get('Candidate', 'N')
    n = int(n.replace("$", ""), 16)

    return snfs_vulnerable(n)


def usage():
    """Usage"""
    print("usage: eccp [-h] [-m arg | -i arg | --snfs arg] [-c arg] [-p] [-v] \n")
    print("arguments:\n")
    print("-m, --moduli         specify moduli file")
    print("-c, --certs          specify certificates dir")
    print("-p, --primo-out      create primo input file if certificates not found")
    print("-v, --verify         verify found primality certificates")
    print("-i, --in             verify given primality certificate\n")
    print("--snfs               verify if the prime in certificate is vulnerable")
    print("                     to Special Number Field Sieve")
    print("-h, --help           show help message\n")


def main():
    """Main function"""
    moduli = None
    certs = None
    verify_opt = False
    primo_opt = False
    input_file = None
    snfs_file = None

    try:
        opts, args = getopt.getopt(sys.argv[1:], 'm:c:pvi:h', ['moduli=', \
                                    'certs=', 'primo-out', \
                                    'verify', 'in=', 'help', 'snfs='])
    except getopt.GetoptError:
        print("[!] parsing of arguments failed\n")
        usage()
        sys.exit(2)

    for opt, arg in opts:
        if opt in ('-h', '--help'):
            usage()
            sys.exit(2)
        elif opt in ('-m', '--moduli'):
            moduli = arg
        elif opt in ('-c', '--certs'):
            certs = arg
        elif opt in ('-p', '--primo-out'):
            primo_opt = True
        elif opt in ('-v', '--verify'):
            verify_opt = True
        elif opt in ('-i', '--in'):
            input_file = arg
        elif opt == "--snfs":
            snfs_file = arg
        else:
            usage()
            sys.exit(2)

    if not moduli and not input_file and not snfs_file:
        print("[!] moduli and certificate file not specified\n")
        usage()
        sys.exit(2)

    if sum(bool(i) for i in (input_file, moduli, snfs_file)) != 1:
        print("[!] only certificate or moduli must be specified\n")
        usage()
        sys.exit(2)

    if input_file:
        ret = 0
        cert = read_config(input_file, False)
        if verify(cert):
            print("certificate is a prime number")
        else:
            print("certificate is not a prime number")
            ret = 1
        if snfs_vulnerable_file(input_file):
            print("prime in certificate is vulnerable to SNFS")
            ret = 1
        else:
            print("prime in certificate is not vulnerable to SNFS")
        if ret:
            sys.exit(1)
    elif snfs_file:
        if snfs_vulnerable_file(snfs_file):
            print("prime in {0} is vulnerable to SNFS".format(snfs_file))
            sys.exit(1)
        else:
            print("prime in {0} is not vulnerable to SNFS".format(snfs_file))
    else:
        status = correlate(moduli, certs, verify_opt, primo_opt)
        if status:
            print("[!] primes without primality certificates found")
            sys.exit(1)


if __name__ == "__main__":
    main()