expand_libecc.py

#/*
# *  Copyright (C) 2017 - This file is part of libecc project
# *
# *  Authors:
# *      Ryad BENADJILA <ryadbenadjila@gmail.com>
# *      Arnaud EBALARD <arnaud.ebalard@ssi.gouv.fr>
# *      Jean-Pierre FLORI <jean-pierre.flori@ssi.gouv.fr>
# *
# *  Contributors:
# *      Nicolas VIVET <nicolas.vivet@ssi.gouv.fr>
# *      Karim KHALFALLAH <karim.khalfallah@ssi.gouv.fr>
# *
# *  This software is licensed under a dual BSD and GPL v2 license.
# *  See LICENSE file at the root folder of the project.
# */
#! /usr/bin/env python

import random, sys, re, math, os, getopt, glob, copy, hashlib, binascii, string, signal, base64

# External dependecy for SHA-3
# It is an independent module, since hashlib has no support
# for SHA-3 functions for now
import sha3

# Handle Python 2/3 issues
def is_python_2():
    if sys.version_info[0] < 3:
        return True
    else:
        return False

### Ctrl-C handler
def handler(signal, frame):
    print("\nSIGINT caught: exiting ...")
    exit(0)

# Helper to ask the user for something
def get_user_input(prompt):
    # Handle the Python 2/3 issue
    if is_python_2() == False:
        return input(prompt)
    else:
        return raw_input(prompt)

##########################################################
#### Math helpers
def egcd(b, n):
    x0, x1, y0, y1 = 1, 0, 0, 1
    while n != 0:
        q, b, n = b // n, n, b % n
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return  b, x0, y0

def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception("Error: modular inverse does not exist")
    else:
        return x % m

def compute_monty_coef(prime, pbitlen, wlen):
    """
    Compute montgomery coeff r, r^2 and mpinv. pbitlen is the size
    of p in bits. It is expected to be a multiple of word
    bit size.
    """
    r = (1 << int(pbitlen)) % prime
    r_square = (1 << (2 * int(pbitlen))) % prime
    mpinv = 2**wlen - (modinv(prime, 2**wlen))
    return r, r_square, mpinv

def compute_div_coef(prime, pbitlen, wlen):
    """
    Compute division coeffs p_normalized, p_shift and p_reciprocal.
    """
    tmp = prime
    cnt = 0
    while tmp != 0:
        tmp = tmp >> 1
        cnt += 1
    pshift = int(pbitlen - cnt)
    primenorm = prime << pshift
    B = 2**wlen
    prec = B**3 // ((primenorm >> int(pbitlen - 2*wlen)) + 1) - B
    return pshift, primenorm, prec

def is_probprime(n):
    # ensure n is odd
    if n % 2 == 0:
        return False
    # write n-1 as 2**s * d
    # repeatedly try to divide n-1 by 2
    s = 0
    d = n-1
    while True:
        quotient, remainder = divmod(d, 2)
        if remainder == 1:
            break
        s += 1
        d = quotient
    assert(2**s * d == n-1)
    # test the base a to see whether it is a witness for the compositeness of n
    def try_composite(a):
        if pow(a, d, n) == 1:
            return False
        for i in range(s):
            if pow(a, 2**i * d, n) == n-1:
                return False
        return True # n is definitely composite
    for i in range(5):
        a = random.randrange(2, n)
        if try_composite(a):
            return False
    return True # no base tested showed n as composite

def legendre_symbol(a, p):
    ls = pow(a, (p - 1) // 2, p)
    return -1 if ls == p - 1 else ls

# Tonelli-Shanks algorithm to find square roots
# over prime fields
def mod_sqrt(a, p):
    # Simple cases
    if legendre_symbol(a, p) != 1:
        # No square residue
        return None
    elif a == 0:
        return 0
    elif p == 2:
        return a
    elif p % 4 == 3:
        return pow(a, (p + 1) // 4, p)
    s = p - 1
    e = 0
    while s % 2 == 0:
        s = s // 2
        e += 1
    n = 2
    while legendre_symbol(n, p) != -1:
        n += 1
    x = pow(a, (s + 1) // 2, p)
    b = pow(a, s, p)
    g = pow(n, s, p)
    r = e
    while True:
        t = b
        m = 0
        if is_python_2():
            for m in xrange(r):
                if t == 1:
                    break
                t = pow(t, 2, p)
        else:
            for m in range(r):
                if t == 1:
                    break
                t = pow(t, 2, p)
        if m == 0:
            return x
        gs = pow(g, 2 ** (r - m - 1), p)
        g = (gs * gs) % p
        x = (x * gs) % p
        b = (b * g) % p
        r = m

##########################################################
### Math elliptic curves basic blocks

# WARNING: these blocks are only here for testing purpose and
# are not intended to be used in a security oriented library!
# This explains the usage of naive affine coordinates fomulas
class Curve(object):
    def __init__(self, a, b, prime, order, cofactor, gx, gy, npoints, name, oid):
        self.a = a
        self.b = b
        self.p = prime
        self.q = order
        self.c = cofactor
        self.gx = gx
        self.gy = gy
        self.n = npoints
        self.name = name
        self.oid = oid
    # Equality testing
    def __eq__(self, other):
        return self.__dict__ == other.__dict__
    # Deep copy is implemented using the ~X operator
    def __invert__(self):
        return copy.deepcopy(self)


class Point(object):
    # Affine coordinates (x, y), infinity point is (None, None)
    def __init__(self, curve, x, y):
        self.curve = curve
        if x != None:
            self.x = (x % curve.p)
        else:
            self.x = None
        if y != None:
            self.y = (y % curve.p)
        else:
            self.y = None
        # Check that the point is indeed on the curve
        if (x != None):
            if (pow(y, 2, curve.p) != ((pow(x, 3, curve.p) + (curve.a * x) + curve.b ) % curve.p)):
                raise Exception("Error: point is not on curve!")
    # Addition
    def __add__(self, Q):
        x1 = self.x
        y1 = self.y
        x2 = Q.x
        y2 = Q.y
        curve = self.curve
        # Check that we are on the same curve
        if Q.curve != curve:
            raise Exception("Point add error: two point don't have the same curve")
        # If Q is infinity point, return ourself
        if Q.x == None:
            return self
        # If we are the infinity point return Q
        if self.x == None:
            return Q
        # Infinity point or Doubling
        if (x1 == x2):
            if (((y1 + y2) % curve.p) == 0):
                # Return infinity point
                return Point(self.curve, None, None)
            else:
                # Doubling
                L = ((3*pow(x1, 2, curve.p) + curve.a) * modinv(2*y1, curve.p)) % curve.p
        # Addition
        else:
            L = ((y2 - y1) * modinv((x2 - x1) % curve.p, curve.p)) % curve.p
        resx = (pow(L, 2, curve.p) - x1 - x2) % curve.p
        resy = ((L * (x1 - resx)) - y1) % curve.p
        # Return the point
        return Point(self.curve, resx, resy)
    # Negation
    def __neg__(self):
        if (self.x == None):
            return self
        else:
            return Point(self.curve, self.x, -self.y)
    # Subtraction
    def __sub__(self, other):
        return self + (-other)
    # Scalar mul
    def __rmul__(self, scalar):
        # Implement simple double and add algorithm
        P = self
        Q = Point(P.curve, None, None)
        for i in range(getbitlen(scalar), 0, -1):
            Q = Q + Q
            if (scalar >> (i-1)) & 0x1 == 0x1:
                Q = Q + P
        return Q
    # Equality testing
    def __eq__(self, other):
        return self.__dict__ == other.__dict__
    # Deep copy is implemented using the ~X operator
    def __invert__(self):
        return copy.deepcopy(self)

##########################################################
### Private and public keys structures
class PrivKey(object):
    def __init__(self, curve, x):
        self.curve = curve
        self.x = x

class PubKey(object):
    def __init__(self, curve, Y):
        # Sanity check
        if Y.curve != curve:
            raise Exception("Error: curve and point curve differ in public key!")
        self.curve = curve
        self.Y = Y

class KeyPair(object):
    def __init__(self, pubkey, privkey):
        self.pubkey = pubkey
        self.privkey = privkey


def fromprivkey(privkey, is_eckcdsa=False):
    curve = privkey.curve
    q = curve.q
    gx = curve.gx
    gy = curve.gy
    G = Point(curve, gx, gy)
    if is_eckcdsa == False:
        return PubKey(curve, privkey.x * G)
    else:
        return PubKey(curve, modinv(privkey.x, q) * G)

def genKeyPair(curve, is_eckcdsa=False):
    p = curve.p
    q = curve.q
    gx = curve.gx
    gy = curve.gy
    G = Point(curve, gx, gy)
    OK = False
    while OK == False:
        x = getrandomint(q)
        if x == 0:
            continue
        OK = True
    privkey = PrivKey(curve, x)
    pubkey = fromprivkey(privkey, is_eckcdsa)
    return KeyPair(pubkey, privkey)

##########################################################
### Signature algorithms helpers
def getrandomint(modulo):
    return random.randrange(0, modulo+1)

def getbitlen(bint):
    """
    Returns the number of bits encoding an integer
    """
    if bint == None:
        return 0
    if bint == 0:
        # Zero is encoded on one bit
        return 1
    else:
        return int(bint).bit_length()

def getbytelen(bint):
    """
    Returns the number of bytes encoding an integer
    """
    bitsize = getbitlen(bint)
    bytesize = int(bitsize // 8)
    if bitsize % 8 != 0:
        bytesize += 1
    return bytesize

def stringtoint(bitstring):
    acc = 0
    size = len(bitstring)
    for i in range(0, size):
        acc = acc + (ord(bitstring[i]) * (2**(8*(size - 1 - i))))
    return acc

def inttostring(a):
    size = int(getbytelen(a))
    outstr = ""
    for i in range(0, size):
        outstr = outstr + chr((a >> (8*(size - 1 - i))) & 0xFF)
    return outstr

def expand(bitstring, bitlen, direction):
    bytelen = int(math.ceil(bitlen / 8.))
    if len(bitstring) >= bytelen:
        return bitstring
    else:
        if direction == "LEFT":
            return ((bytelen-len(bitstring))*"\x00") + bitstring
        elif direction == "RIGHT":
            return bitstring + ((bytelen-len(bitstring))*"\x00")
        else:
            raise Exception("Error: unknown direction "+direction+" in expand")

def truncate(bitstring, bitlen, keep):
    """
    Takes a bit string and truncates it to keep the left
    most or the right most bits
    """
    strbitlen = 8*len(bitstring)
    # Check if truncation is needed
    if strbitlen > bitlen:
        if keep == "LEFT":
            return expand(inttostring(stringtoint(bitstring) >> int(strbitlen - bitlen)), bitlen, "LEFT")
        elif keep == "RIGHT":
            mask = (2**bitlen)-1
            return expand(inttostring(stringtoint(bitstring) & mask), bitlen, "LEFT")
        else:
            raise Exception("Error: unknown direction "+keep+" in truncate")
    else:
        # No need to truncate!
        return bitstring

##########################################################
### Hash algorithms
def sha224(message):
    ctx = hashlib.sha224()
    if(is_python_2() == True):
        ctx.update(message)
        digest = ctx.digest()
    else:
        ctx.update(message.encode('latin-1'))
        digest = ctx.digest().decode('latin-1')
    return (digest, ctx.digest_size, ctx.block_size)

def sha256(message):
    ctx = hashlib.sha256()
    if(is_python_2() == True):
        ctx.update(message)
        digest = ctx.digest()
    else:
        ctx.update(message.encode('latin-1'))
        digest = ctx.digest().decode('latin-1')
    return (digest, ctx.digest_size, ctx.block_size)

def sha384(message):
    ctx = hashlib.sha384()
    if(is_python_2() == True):
        ctx.update(message)
        digest = ctx.digest()
    else:
        ctx.update(message.encode('latin-1'))
        digest = ctx.digest().decode('latin-1')
    return (digest, ctx.digest_size, ctx.block_size)

def sha512(message):
    ctx = hashlib.sha512()
    if(is_python_2() == True):
        ctx.update(message)
        digest = ctx.digest()
    else:
        ctx.update(message.encode('latin-1'))
        digest = ctx.digest().decode('latin-1')
    return (digest, ctx.digest_size, ctx.block_size)

def sha3_224(message):
    ctx = sha3.Sha3_ctx(224)
    if(is_python_2() == True):
        ctx.update(message)
        digest = ctx.digest()
    else:
        ctx.update(message.encode('latin-1'))
        digest = ctx.digest().decode('latin-1')
    return (digest, ctx.digest_size, ctx.block_size)

def sha3_256(message):
    ctx = sha3.Sha3_ctx(256)
    if(is_python_2() == True):
        ctx.update(message)
        digest = ctx.digest()
    else:
        ctx.update(message.encode('latin-1'))
        digest = ctx.digest().decode('latin-1')
    return (digest, ctx.digest_size, ctx.block_size)

def sha3_384(message):
    ctx = sha3.Sha3_ctx(384)
    if(is_python_2() == True):
        ctx.update(message)
        digest = ctx.digest()
    else:
        ctx.update(message.encode('latin-1'))
        digest = ctx.digest().decode('latin-1')
    return (digest, ctx.digest_size, ctx.block_size)

def sha3_512(message):
    ctx = sha3.Sha3_ctx(512)
    if(is_python_2() == True):
        ctx.update(message)
        digest = ctx.digest()
    else:
        ctx.update(message.encode('latin-1'))
        digest = ctx.digest().decode('latin-1')
    return (digest, ctx.digest_size, ctx.block_size)

##########################################################
### Signature algorithms

# *| IUF  - ECDSA signature
# *|
# *|  UF  1. Compute h = H(m)
# *|   F  2. If |h| > bitlen(q), set h to bitlen(q)
# *|         leftmost (most significant) bits of h
# *|   F  3. e = OS2I(h) mod q
# *|   F  4. Get a random value k in ]0,q[
# *|   F  5. Compute W = (W_x,W_y) = kG
# *|   F  6. Compute r = W_x mod q
# *|   F  7. If r is 0, restart the process at step 4.
# *|   F  8. If e == rx, restart the process at step 4.
# *|   F  9. Compute s = k^-1 * (xr + e) mod q
# *|   F 10. If s is 0, restart the process at step 4.
# *|   F 11. Return (r,s)
def ecdsa_sign(hashfunc, keypair, message, k=None):
    privkey = keypair.privkey
    # Get important parameters from the curve
    p = privkey.curve.p
    q = privkey.curve.q
    gx = privkey.curve.gx
    gy = privkey.curve.gy
    G = Point(privkey.curve, gx, gy)
    q_limit_len = getbitlen(q)
    # Compute the hash
    (h, _, _) = hashfunc(message)
    # Truncate hash value
    h = truncate(h, q_limit_len, "LEFT")
    # Convert the hash value to an int
    e = stringtoint(h) % q
    OK = False
    while OK == False:
        if k == None:
            k = getrandomint(q)
        if k == 0:
            continue
        W = k * G
        r = W.x % q
        if r == 0:
            continue
        if e == r * privkey.x:
            continue
        s = (modinv(k, q) * ((privkey.x * r) + e)) % q
        if s == 0:
            continue
        OK = True
    return ((expand(inttostring(r), 8*getbytelen(q), "LEFT") + expand(inttostring(s), 8*getbytelen(q), "LEFT")), k)

# *| IUF  - ECDSA verification
# *|
# *| I    1. Reject the signature if r or s is 0.
# *|  UF  2. Compute h = H(m)
# *|   F  3. If |h| > bitlen(q), set h to bitlen(q)
# *|         leftmost (most significant) bits of h
# *|   F  4. Compute e = OS2I(h) mod q
# *|   F  5. Compute u = (s^-1)e mod q
# *|   F  6. Compute v = (s^-1)r mod q
# *|   F  7. Compute W' = uG + vY
# *|   F  8. If W' is the point at infinity, reject the signature.
# *|   F  9. Compute r' = W'_x mod q
# *|   F 10. Accept the signature if and only if r equals r'
def ecdsa_verify(hashfunc, keypair, message, sig):
    pubkey = keypair.pubkey
    # Get important parameters from the curve
    p = pubkey.curve.p
    q = pubkey.curve.q
    gx = pubkey.curve.gx
    gy = pubkey.curve.gy
    q_limit_len = getbitlen(q)
    G = Point(pubkey.curve, gx, gy)
    # Extract r and s
    if len(sig) != 2*getbytelen(q):
        raise Exception("ECDSA verify: bad signature length!")
    r = stringtoint(sig[0:int(len(sig)/2)])
    s = stringtoint(sig[int(len(sig)/2):])
    if r == 0 or s == 0:
        return False
    # Compute the hash
    (h, _, _) = hashfunc(message)
    # Truncate hash value
    h = truncate(h, q_limit_len, "LEFT")
    # Convert the hash value to an int
    e = stringtoint(h) % q
    u = (modinv(s, q) * e) % q
    v = (modinv(s, q) * r) % q
    W_ = (u * G) + (v * pubkey.Y)
    if W_.x == None:
        return False
    r_ = W_.x % q
    if r == r_:
        return True
    else:
        return False

def eckcdsa_genKeyPair(curve):
    return genKeyPair(curve, True)

# *| IUF  - ECKCDSA signature
# *|
# *| IUF  1. Compute h = H(z||m)
# *|   F  2. If hsize > bitlen(q), set h to bitlen(q)
# *|         rightmost (less significant) bits of h.
# *|   F  3. Get a random value k in ]0,q[
# *|   F  4. Compute W = (W_x,W_y) = kG
# *|   F  5. Compute r = h(FE2OS(W_x)).
# *|   F  6. If hsize > bitlen(q), set r to bitlen(q)
# *|         rightmost (less significant) bits of r.
# *|   F  7. Compute e = OS2I(r XOR h) mod q
# *|   F  8. Compute s = x(k - e) mod q
# *|   F  9. if s == 0, restart at step 3.
# *|   F 10. return (r,s)
def eckcdsa_sign(hashfunc, keypair, message, k=None):
    privkey = keypair.privkey
    # Get important parameters from the curve
    p = privkey.curve.p
    q = privkey.curve.q
    gx = privkey.curve.gx
    gy = privkey.curve.gy
    G = Point(privkey.curve, gx, gy)
    q_limit_len = getbitlen(q)
    # Compute the certificate data
    (_, _, hblocksize) = hashfunc("")
    z = expand(inttostring(keypair.pubkey.Y.x), 8*getbytelen(p), "LEFT")
    z = z + expand(inttostring(keypair.pubkey.Y.y), 8*getbytelen(p), "LEFT")
    if len(z) > hblocksize:
        # Truncate
        z = truncate(z, 8*hblocksize, "LEFT")
    else:
        # Expand
        z = expand(z, 8*hblocksize, "RIGHT")
    # Compute the hash
    (h, _, _) = hashfunc(z + message)
    # Truncate hash value
    h = truncate(h, q_limit_len, "RIGHT")
    OK = False
    while OK == False:
        if k == None:
            k = getrandomint(q)
        if k == 0:
            continue
        W = k * G
        (r, _, _) = hashfunc(expand(inttostring(W.x), 8*getbytelen(p), "LEFT"))
        r = truncate(r, q_limit_len, "RIGHT")
        e = (stringtoint(r) ^ stringtoint(h)) % q
        s = (privkey.x * (k - e)) % q
        if s == 0:
            continue
        OK = True
    return (r + expand(inttostring(s), 8*getbytelen(q), "LEFT"), k)

# *| IUF - ECKCDSA verification
# *|
# *| I   1. Check the length of r:
# *|         - if hsize > bitlen(q), r must be of
# *|           length bitlen(q)
# *|         - if hsize <= bitlen(q), r must be of
# *|           length hsize
# *| I   2. Check that s is in ]0,q[
# *| IUF 3. Compute h = H(z||m)
# *|   F 4. If hsize > bitlen(q), set h to bitlen(q)
# *|        rightmost (less significant) bits of h.
# *|   F 5. Compute e = OS2I(r XOR h) mod q
# *|   F 6. Compute W' = sY + eG, where Y is the public key
# *|   F 7. Compute r' = h(FE2OS(W'x))
# *|   F 8. If hsize > bitlen(q), set r' to bitlen(q)
# *|        rightmost (less significant) bits of r'.
# *|   F 9. Check if r == r'
def eckcdsa_verify(hashfunc, keypair, message, sig):
    pubkey = keypair.pubkey
    # Get important parameters from the curve
    p = pubkey.curve.p
    q = pubkey.curve.q
    gx = pubkey.curve.gx
    gy = pubkey.curve.gy
    G = Point(pubkey.curve, gx, gy)
    q_limit_len = getbitlen(q)
    (_, hsize, hblocksize) = hashfunc("")
    # Extract r and s
    if (8*hsize) > q_limit_len:
        r_len = int(math.ceil(q_limit_len / 8.))
    else:
        r_len = hsize
    r = stringtoint(sig[0:int(r_len)])
    s = stringtoint(sig[int(r_len):])
    if (s >= q) or (s < 0):
        return False
    # Compute the certificate data
    z = expand(inttostring(keypair.pubkey.Y.x), 8*getbytelen(p), "LEFT")
    z = z + expand(inttostring(keypair.pubkey.Y.y), 8*getbytelen(p), "LEFT")
    if len(z) > hblocksize:
        # Truncate
        z = truncate(z, 8*hblocksize, "LEFT")
    else:
        # Expand
        z = expand(z, 8*hblocksize, "RIGHT")
    # Compute the hash
    (h, _, _) = hashfunc(z + message)
    # Truncate hash value
    h = truncate(h, q_limit_len, "RIGHT")
    e = (r ^ stringtoint(h)) % q
    W_ = (s * pubkey.Y) + (e * G)
    (h, _, _) = hashfunc(expand(inttostring(W_.x), 8*getbytelen(p), "LEFT"))
    r_ = truncate(h, q_limit_len, "RIGHT")
    if stringtoint(r_) == r:
        return True
    else:
        return False

# *| IUF - ECFSDSA signature
# *|
# *| I   1. Get a random value k in ]0,q[
# *| I   2. Compute W = (W_x,W_y) = kG
# *| I   3. Compute r = FE2OS(W_x)||FE2OS(W_y)
# *| I   4. If r is an all zero string, restart the process at step 1.
# *| IUF 5. Compute h = H(r||m)
# *|   F 6. Compute e = OS2I(h) mod q
# *|   F 7. Compute s = (k + ex) mod q
# *|   F 8. If s is 0, restart the process at step 1 (see c. below)
# *|   F 9. Return (r,s)
def ecfsdsa_sign(hashfunc, keypair, message, k=None):
    privkey = keypair.privkey
    # Get important parameters from the curve
    p = privkey.curve.p
    q = privkey.curve.q
    gx = privkey.curve.gx
    gy = privkey.curve.gy
    G = Point(privkey.curve, gx, gy)
    OK = False
    while OK == False:
        if k == None:
            k = getrandomint(q)
        if k == 0:
            continue
        W = k * G
        r = expand(inttostring(W.x), 8*getbytelen(p), "LEFT") + expand(inttostring(W.y), 8*getbytelen(p), "LEFT")
        if stringtoint(r) == 0:
            continue
        (h, _, _) = hashfunc(r + message)
        e = stringtoint(h) % q
        s = (k + e * privkey.x) % q
        if s == 0:
            continue
        OK = True
    return (r + expand(inttostring(s), 8*getbytelen(q), "LEFT"), k)


# *| IUF - ECFSDSA verification
# *|
# *| I   1. Reject the signature if r is not a valid point on the curve.
# *| I   2. Reject the signature if s is not in ]0,q[
# *| IUF 3. Compute h = H(r||m)
# *|   F 4. Convert h to an integer and then compute e = -h mod q
# *|   F 5. compute W' = sG + eY, where Y is the public key
# *|   F 6. Compute r' = FE2OS(W'_x)||FE2OS(W'_y)
# *|   F 7. Accept the signature if and only if r equals r'
def ecfsdsa_verify(hashfunc, keypair, message, sig):
    pubkey = keypair.pubkey
    # Get important parameters from the curve
    p = pubkey.curve.p
    q = pubkey.curve.q
    gx = pubkey.curve.gx
    gy = pubkey.curve.gy
    G = Point(pubkey.curve, gx, gy)
    # Extract coordinates from r and s from signature
    if len(sig) != (2*getbytelen(p)) + getbytelen(q):
        raise Exception("ECFSDSA verify: bad signature length!")
    wx = sig[:int(getbytelen(p))]
    wy = sig[int(getbytelen(p)):int(2*getbytelen(p))]
    r = wx + wy
    s = stringtoint(sig[int(2*getbytelen(p)):int((2*getbytelen(p))+getbytelen(q))])
    # Check r is on the curve
    W = Point(pubkey.curve, stringtoint(wx), stringtoint(wy))
    # Check s is in ]0,q[
    if s == 0 or s > q:
        raise Exception("ECFSDSA verify: s not in ]0,q[")
    (h, _, _) = hashfunc(r + message)
    e = (-stringtoint(h)) % q
    W_ = s * G + e * pubkey.Y
    r_ = expand(inttostring(W_.x), 8*getbytelen(p), "LEFT") + expand(inttostring(W_.y), 8*getbytelen(p), "LEFT")
    if r == r_:
        return True
    else:
        return False


# NOTE: ISO/IEC 14888-3 standard seems to diverge from the existing implementations
# of ECRDSA when treating the message hash, and from the examples of certificates provided
# in RFC 7091 and draft-deremin-rfc4491-bis. While in ISO/IEC 14888-3 it is explicitely asked
# to proceed with the hash of the message as big endian, the RFCs derived from the Russian
# standard expect the hash value to be treated as little endian when importing it as an integer
# (this discrepancy is exhibited and confirmed by test vectors present in ISO/IEC 14888-3, and
# by X.509 certificates present in the RFCs). This seems (to be confirmed) to be a discrepancy of
# ISO/IEC 14888-3 algorithm description that must be fixed there.
#
# In order to be conservative, libecc uses the Russian standard behavior as expected to be in line with
# other implemetations, but keeps the ISO/IEC 14888-3 behavior if forced/asked by the user using
# the USE_ISO14888_3_ECRDSA toggle. This allows to keep backward compatibility with previous versions of the
# library if needed.

# *| IUF - ECRDSA signature
# *|
# *|  UF  1. Compute h = H(m)
# *|   F  2. Get a random value k in ]0,q[
# *|   F  3. Compute W = (W_x,W_y) = kG
# *|   F  4. Compute r = W_x mod q
# *|   F  5. If r is 0, restart the process at step 2.
# *|   F  6. Compute e = OS2I(h) mod q. If e is 0, set e to 1.
# *|         NOTE: here, ISO/IEC 14888-3 and RFCs differ in the way e treated.
# *|         e = OS2I(h) for ISO/IEC 14888-3, or e = OS2I(reversed(h)) when endianness of h
# *|         is reversed for RFCs.
# *|   F  7. Compute s = (rx + ke) mod q
# *|   F  8. If s is 0, restart the process at step 2.
# *|   F 11. Return (r,s)
def ecrdsa_sign(hashfunc, keypair, message, k=None, use_iso14888_divergence=False):
    privkey = keypair.privkey
    # Get important parameters from the curve
    p = privkey.curve.p
    q = privkey.curve.q
    gx = privkey.curve.gx
    gy = privkey.curve.gy
    G = Point(privkey.curve, gx, gy)
    (h, _, _) = hashfunc(message)
    if use_iso14888_divergence == False:
        # Reverse the endianness for Russian standard RFC ECRDSA (contrary to ISO/IEC 14888-3 case)
        h = h[::-1]
    OK = False
    while OK == False:
        if k == None:
            k = getrandomint(q)
        if k == 0:
            continue
        W = k * G
        r = W.x % q
        if r == 0:
            continue
        e = stringtoint(h) % q
        if e == 0:
            e = 1
        s = ((r * privkey.x) + (k * e)) % q
        if s == 0:
            continue
        OK = True
    return (expand(inttostring(r), 8*getbytelen(q), "LEFT") + expand(inttostring(s), 8*getbytelen(q), "LEFT"), k)

# *| IUF - ECRDSA verification
# *|
# *|  UF 1. Check that r and s are both in ]0,q[
# *|   F 2. Compute h = H(m)
# *|   F 3. Compute e = OS2I(h)^-1 mod q
# *|         NOTE: here, ISO/IEC 14888-3 and RFCs differ in the way e treated.
# *|         e = OS2I(h) for ISO/IEC 14888-3, or e = OS2I(reversed(h)) when endianness of h
# *|         is reversed for RFCs.
# *|   F 4. Compute u = es mod q
# *|   F 4. Compute v = -er mod q
# *|   F 5. Compute W' = uG + vY = (W'_x, W'_y)
# *|   F 6. Let's now compute r' = W'_x mod q
# *|   F 7. Check r and r' are the same
def ecrdsa_verify(hashfunc, keypair, message, sig, use_iso14888_divergence=False):
    pubkey = keypair.pubkey
    # Get important parameters from the curve
    p = pubkey.curve.p
    q = pubkey.curve.q
    gx = pubkey.curve.gx
    gy = pubkey.curve.gy
    G = Point(pubkey.curve, gx, gy)
    # Extract coordinates from r and s from signature
    if len(sig) != 2*getbytelen(q):
        raise Exception("ECRDSA verify: bad signature length!")
    r = stringtoint(sig[:int(getbytelen(q))])
    s = stringtoint(sig[int(getbytelen(q)):int(2*getbytelen(q))])
    if r == 0 or r > q:
        raise Exception("ECRDSA verify: r not in ]0,q[")
    if s == 0 or s > q:
        raise Exception("ECRDSA verify: s not in ]0,q[")
    (h, _, _) = hashfunc(message)
    if use_iso14888_divergence == False:
        # Reverse the endianness for Russian standard RFC ECRDSA (contrary to ISO/IEC 14888-3 case)
        h = h[::-1]
    e = modinv(stringtoint(h) % q, q)
    u = (e * s) % q
    v = (-e * r) % q
    W_ = u * G + v * pubkey.Y
    r_ = W_.x % q
    if r == r_:
        return True
    else:
        return False


# *| IUF - ECGDSA signature
# *|
# *|  UF 1. Compute h = H(m). If |h| > bitlen(q), set h to bitlen(q)
# *|         leftmost (most significant) bits of h
# *|   F 2. Convert e = - OS2I(h) mod q
# *|   F 3. Get a random value k in ]0,q[
# *|   F 4. Compute W = (W_x,W_y) = kG
# *|   F 5. Compute r = W_x mod q
# *|   F 6. If r is 0, restart the process at step 4.
# *|   F 7. Compute s = x(kr + e) mod q
# *|   F 8. If s is 0, restart the process at step 4.
# *|   F 9. Return (r,s)
def ecgdsa_sign(hashfunc, keypair, message, k=None):
    privkey = keypair.privkey
    # Get important parameters from the curve
    p = privkey.curve.p
    q = privkey.curve.q
    gx = privkey.curve.gx
    gy = privkey.curve.gy
    G = Point(privkey.curve, gx, gy)
    (h, _, _) = hashfunc(message)
    q_limit_len = getbitlen(q)
    # Truncate hash value
    h = truncate(h, q_limit_len, "LEFT")
    e = (-stringtoint(h)) % q
    OK = False
    while OK == False:
        if k == None:
            k = getrandomint(q)
        if k == 0:
            continue
        W = k * G
        r = W.x % q
        if r == 0:
            continue
        s = (privkey.x * ((k * r) + e)) % q
        if s == 0:
            continue
        OK = True
    return (expand(inttostring(r), 8*getbytelen(q), "LEFT") + expand(inttostring(s), 8*getbytelen(q), "LEFT"), k)

# *| IUF - ECGDSA verification
# *|
# *| I   1. Reject the signature if r or s is 0.
# *|  UF 2. Compute h = H(m). If |h| > bitlen(q), set h to bitlen(q)
# *|         leftmost (most significant) bits of h
# *|   F 3. Compute e = OS2I(h) mod q
# *|   F 4. Compute u = ((r^-1)e mod q)
# *|   F 5. Compute v = ((r^-1)s mod q)
# *|   F 6. Compute W' = uG + vY
# *|   F 7. Compute r' = W'_x mod q
# *|   F 8. Accept the signature if and only if r equals r'
def ecgdsa_verify(hashfunc, keypair, message, sig):
    pubkey = keypair.pubkey
    # Get important parameters from the curve
    p = pubkey.curve.p
    q = pubkey.curve.q
    gx = pubkey.curve.gx
    gy = pubkey.curve.gy
    G = Point(pubkey.curve, gx, gy)
    # Extract coordinates from r and s from signature
    if len(sig) != 2*getbytelen(q):
        raise Exception("ECGDSA verify: bad signature length!")
    r = stringtoint(sig[:int(getbytelen(q))])
    s = stringtoint(sig[int(getbytelen(q)):int(2*getbytelen(q))])
    if r == 0 or r > q:
        raise Exception("ECGDSA verify: r not in ]0,q[")
    if s == 0 or s > q:
        raise Exception("ECGDSA verify: s not in ]0,q[")
    (h, _, _) = hashfunc(message)
    q_limit_len = getbitlen(q)
    # Truncate hash value
    h = truncate(h, q_limit_len, "LEFT")
    e = stringtoint(h) % q
    r_inv = modinv(r, q)
    u = (r_inv * e) % q
    v = (r_inv * s) % q
    W_ = u * G + v * pubkey.Y
    r_ = W_.x % q
    if r == r_:
        return True
    else:
        return False

# *| IUF - ECSDSA/ECOSDSA signature
# *|
# *| I   1. Get a random value k in ]0, q[
# *| I   2. Compute W = kG = (Wx, Wy)
# *| IUF 3. Compute r = H(Wx [|| Wy] || m)
# *|        - In the normal version (ECSDSA), r = h(Wx || Wy || m).
# *|        - In the optimized version (ECOSDSA), r = h(Wx || m).
# *|   F 4. Compute e = OS2I(r) mod q
# *|   F 5. if e == 0, restart at step 1.
# *|   F 6. Compute s = (k + ex) mod q.
# *|   F 7. if s == 0, restart at step 1.
# *|   F 8. Return (r, s)
def ecsdsa_common_sign(hashfunc, keypair, message, optimized, k=None):
    privkey = keypair.privkey
    # Get important parameters from the curve
    p = privkey.curve.p
    q = privkey.curve.q
    gx = privkey.curve.gx
    gy = privkey.curve.gy
    G = Point(privkey.curve, gx, gy)
    OK = False
    while OK == False:
        if k == None:
            k = getrandomint(q)
        if k == 0:
            continue
        W = k * G
        if optimized == False:
            (r, _, _) = hashfunc(expand(inttostring(W.x), 8*getbytelen(p), "LEFT") + expand(inttostring(W.y), 8*getbytelen(p), "LEFT") + message)
        else:
            (r, _, _) = hashfunc(expand(inttostring(W.x), 8*getbytelen(p), "LEFT") + message)
        e = stringtoint(r) % q
        if e == 0:
            continue
        s = (k + (e * privkey.x)) % q
        if s == 0:
            continue
        OK = True
    return (r + expand(inttostring(s), 8*getbytelen(q), "LEFT"), k)

def ecsdsa_sign(hashfunc, keypair, message, k=None):
    return ecsdsa_common_sign(hashfunc, keypair, message, False, k)

def ecosdsa_sign(hashfunc, keypair, message, k=None):
    return ecsdsa_common_sign(hashfunc, keypair, message, True, k)

# *| IUF - ECSDSA/ECOSDSA verification
# *|
# *| I   1. if s is not in ]0,q[, reject the signature.x
# *| I   2. Compute e = -r mod q
# *| I   3. If e == 0, reject the signature.
# *| I   4. Compute W' = sG + eY
# *| IUF 5. Compute r' = H(W'x [|| W'y] || m)
# *|        - In the normal version (ECSDSA), r = h(W'x || W'y || m).
# *|        - In the optimized version (ECOSDSA), r = h(W'x || m).
# *|   F 6. Accept the signature if and only if r and r' are the same
def ecsdsa_common_verify(hashfunc, keypair, message, sig, optimized):
    pubkey = keypair.pubkey
    # Get important parameters from the curve
    p = pubkey.curve.p
    q = pubkey.curve.q
    gx = pubkey.curve.gx
    gy = pubkey.curve.gy
    G = Point(pubkey.curve, gx, gy)
    (_, hlen, _) = hashfunc("")
    # Extract coordinates from r and s from signature
    if len(sig) != hlen + getbytelen(q):
        raise Exception("EC[O]SDSA verify: bad signature length!")
    r = stringtoint(sig[:int(hlen)])
    s = stringtoint(sig[int(hlen):int(hlen+getbytelen(q))])
    if s == 0 or s > q:
        raise Exception("EC[O]DSA verify: s not in ]0,q[")
    e = (-r) % q
    if e == 0:
        raise Exception("EC[O]DSA verify: e is null")
    W_ = s * G + e * pubkey.Y
    if optimized == False:
        (r_, _, _) = hashfunc(expand(inttostring(W_.x), 8*getbytelen(p), "LEFT") + expand(inttostring(W_.y), 8*getbytelen(p), "LEFT") + message)
    else:
        (r_, _, _) = hashfunc(expand(inttostring(W_.x), 8*getbytelen(p), "LEFT") + message)
    if sig[:int(hlen)] == r_:
        return True
    else:
        return False

def ecsdsa_verify(hashfunc, keypair, message, sig):
    return ecsdsa_common_verify(hashfunc, keypair, message, sig, False)

def ecosdsa_verify(hashfunc, keypair, message, sig):
    return ecsdsa_common_verify(hashfunc, keypair, message, sig, True)


##########################################################
### Generate self-tests for all the algorithms

all_hash_funcs = [ (sha224, "SHA224"), (sha256, "SHA256"), (sha384, "SHA384"), (sha512, "SHA512"), (sha3_224, "SHA3_224"), (sha3_256, "SHA3_256"), (sha3_384, "SHA3_384"), (sha3_512, "SHA3_512") ]

all_sig_algs = [ (ecdsa_sign, ecdsa_verify, genKeyPair, "ECDSA"),
         (eckcdsa_sign, eckcdsa_verify, eckcdsa_genKeyPair, "ECKCDSA"),
         (ecfsdsa_sign, ecfsdsa_verify, genKeyPair, "ECFSDSA"),
         (ecrdsa_sign, ecrdsa_verify, genKeyPair, "ECRDSA"),
         (ecgdsa_sign, ecgdsa_verify, eckcdsa_genKeyPair, "ECGDSA"),
         (ecsdsa_sign, ecsdsa_verify, genKeyPair, "ECSDSA"),
         (ecosdsa_sign, ecosdsa_verify, genKeyPair, "ECOSDSA"), ]


curr_test = 0
def pretty_print_curr_test(num_test, total_gen_tests):
    num_decimal = int(math.log10(total_gen_tests))+1
    format_buf = "%0"+str(num_decimal)+"d/%0"+str(num_decimal)+"d"
    sys.stdout.write('\b'*((2*num_decimal)+1))
    sys.stdout.flush()
    sys.stdout.write(format_buf % (num_test, total_gen_tests))
    if num_test == total_gen_tests:
        print("")
    return

def gen_self_test(curve, hashfunc, sig_alg_sign, sig_alg_verify, sig_alg_genkeypair, num, hashfunc_name, sig_alg_name, total_gen_tests):
    global curr_test
    curr_test = curr_test + 1
    if num != 0:
        pretty_print_curr_test(curr_test, total_gen_tests)
    output_list = []
    for test_num in range(0, num):
        out_vectors = ""
        # Generate a random key pair
        keypair = sig_alg_genkeypair(curve)
        # Generate a random message with a random size
        size = getrandomint(256)
        if is_python_2():
            message = ''.join([random.choice(string.ascii_letters + string.digits) for n in xrange(size)])
        else:
            message = ''.join([random.choice(string.ascii_letters + string.digits) for n in range(size)])
        test_name = sig_alg_name + "_" + hashfunc_name + "_" + curve.name.upper() + "_" + str(test_num)
        # Sign the message
        (sig, k) = sig_alg_sign(hashfunc, keypair, message)
        # Check that everything is OK with a verify
        if sig_alg_verify(hashfunc, keypair, message, sig) != True:
            raise Exception("Error during self test generation: sig verify failed! "+test_name+ "   /  msg="+message+"   /   sig="+binascii.hexlify(sig)+"    /    k="+hex(k)+"   /   privkey.x="+hex(keypair.privkey.x))
        if sig_alg_name == "ECRDSA":
            out_vectors += "#ifndef USE_ISO14888_3_ECRDSA\n"
        # Now generate the test vector
        out_vectors += "#ifdef WITH_HASH_"+hashfunc_name.upper()+"\n"
        out_vectors += "#ifdef WITH_CURVE_"+curve.name.upper()+"\n"
        out_vectors += "#ifdef WITH_SIG_"+sig_alg_name.upper()+"\n"
        out_vectors += "/* "+test_name+" known test vectors */\n"
        out_vectors += "static int "+test_name+"_test_vectors_get_random(nn_t out, nn_src_t q)\n{\n"
        # k_buf MUST be exported padded to the length of q
        out_vectors += "\tconst u8 k_buf[] = "+bigint_to_C_array(k, getbytelen(curve.q))
        out_vectors += "\tint ret, cmp;\n\tret = nn_init_from_buf(out, k_buf, sizeof(k_buf)); EG(ret, err);\n\tret = nn_cmp(out, q, &cmp); EG(ret, err);\n\tret = (cmp >= 0) ? -1 : 0;\nerr:\n\treturn ret;\n}\n"
        out_vectors += "static const u8 "+test_name+"_test_vectors_priv_key[] = \n"+bigint_to_C_array(keypair.privkey.x, getbytelen(keypair.privkey.x))
        out_vectors += "static const u8 "+test_name+"_test_vectors_expected_sig[] = \n"+bigint_to_C_array(stringtoint(sig), len(sig))
        out_vectors += "static const ec_test_case "+test_name+"_test_case = {\n"
        out_vectors += "\t.name = \""+test_name+"\",\n"
        out_vectors += "\t.ec_str_p = &"+curve.name+"_str_params,\n"
        out_vectors += "\t.priv_key = "+test_name+"_test_vectors_priv_key,\n"
        out_vectors += "\t.priv_key_len = sizeof("+test_name+"_test_vectors_priv_key),\n"
        out_vectors += "\t.nn_random = "+test_name+"_test_vectors_get_random,\n"
        out_vectors += "\t.hash_type = "+hashfunc_name+",\n"
        out_vectors += "\t.msg = \""+message+"\",\n"
        out_vectors += "\t.msglen = "+str(len(message))+",\n"
        out_vectors += "\t.sig_type = "+sig_alg_name+",\n"
        out_vectors += "\t.exp_sig = "+test_name+"_test_vectors_expected_sig,\n"
        out_vectors += "\t.exp_siglen = sizeof("+test_name+"_test_vectors_expected_sig),\n};\n"
        out_vectors += "#endif /* WITH_HASH_"+hashfunc_name+" */\n"
        out_vectors += "#endif /* WITH_CURVE_"+curve.name+" */\n"
        out_vectors += "#endif /* WITH_SIG_"+sig_alg_name+" */\n"
        if sig_alg_name == "ECRDSA":
            out_vectors += "#endif /* !USE_ISO14888_3_ECRDSA */\n"
        out_name = ""
        if sig_alg_name == "ECRDSA":
            out_name += "#ifndef USE_ISO14888_3_ECRDSA"+"/* For "+test_name+" */\n"
        out_name += "#ifdef WITH_HASH_"+hashfunc_name.upper()+"/* For "+test_name+" */\n"
        out_name += "#ifdef WITH_CURVE_"+curve.name.upper()+"/* For "+test_name+" */\n"
        out_name += "#ifdef WITH_SIG_"+sig_alg_name.upper()+"/* For "+test_name+" */\n"
        out_name += "\t&"+test_name+"_test_case,\n"
        out_name += "#endif /* WITH_HASH_"+hashfunc_name+" for "+test_name+" */\n"
        out_name += "#endif /* WITH_CURVE_"+curve.name+" for "+test_name+" */\n"
        out_name += "#endif /* WITH_SIG_"+sig_alg_name+" for "+test_name+" */"
        if sig_alg_name == "ECRDSA":
            out_name += "\n#endif /* !USE_ISO14888_3_ECRDSA */"+"/* For "+test_name+" */"
        output_list.append((out_name, out_vectors))
        # In the specific case of ECRDSA, we also generate an ISO/IEC compatible test vector
        if sig_alg_name == "ECRDSA":
            out_vectors = ""
            (sig, k) = sig_alg_sign(hashfunc, keypair, message, use_iso14888_divergence=True)
            # Check that everything is OK with a verify
            if sig_alg_verify(hashfunc, keypair, message, sig, use_iso14888_divergence=True) != True:
                raise Exception("Error during self test generation: sig verify failed! "+test_name+ "   /  msg="+message+"   /   sig="+binascii.hexlify(sig)+"    /    k="+hex(k)+"   /   privkey.x="+hex(keypair.privkey.x))
            out_vectors += "#ifdef USE_ISO14888_3_ECRDSA\n"
            # Now generate the test vector
            out_vectors += "#ifdef WITH_HASH_"+hashfunc_name.upper()+"\n"
            out_vectors += "#ifdef WITH_CURVE_"+curve.name.upper()+"\n"
            out_vectors += "#ifdef WITH_SIG_"+sig_alg_name.upper()+"\n"
            out_vectors += "/* "+test_name+" known test vectors */\n"
            out_vectors += "static int "+test_name+"_test_vectors_get_random(nn_t out, nn_src_t q)\n{\n"
            # k_buf MUST be exported padded to the length of q
            out_vectors += "\tconst u8 k_buf[] = "+bigint_to_C_array(k, getbytelen(curve.q))
            out_vectors += "\tint ret, cmp;\n\tret = nn_init_from_buf(out, k_buf, sizeof(k_buf)); EG(ret, err);\n\tret = nn_cmp(out, q, &cmp); EG(ret, err);\n\tret = (cmp >= 0) ? -1 : 0;\nerr:\n\treturn ret;\n}\n"
            out_vectors += "static const u8 "+test_name+"_test_vectors_priv_key[] = \n"+bigint_to_C_array(keypair.privkey.x, getbytelen(keypair.privkey.x))
            out_vectors += "static const u8 "+test_name+"_test_vectors_expected_sig[] = \n"+bigint_to_C_array(stringtoint(sig), len(sig))
            out_vectors += "static const ec_test_case "+test_name+"_test_case = {\n"
            out_vectors += "\t.name = \""+test_name+"\",\n"
            out_vectors += "\t.ec_str_p = &"+curve.name+"_str_params,\n"
            out_vectors += "\t.priv_key = "+test_name+"_test_vectors_priv_key,\n"
            out_vectors += "\t.priv_key_len = sizeof("+test_name+"_test_vectors_priv_key),\n"
            out_vectors += "\t.nn_random = "+test_name+"_test_vectors_get_random,\n"
            out_vectors += "\t.hash_type = "+hashfunc_name+",\n"
            out_vectors += "\t.msg = \""+message+"\",\n"
            out_vectors += "\t.msglen = "+str(len(message))+",\n"
            out_vectors += "\t.sig_type = "+sig_alg_name+",\n"
            out_vectors += "\t.exp_sig = "+test_name+"_test_vectors_expected_sig,\n"
            out_vectors += "\t.exp_siglen = sizeof("+test_name+"_test_vectors_expected_sig),\n};\n"
            out_vectors += "#endif /* WITH_HASH_"+hashfunc_name+" */\n"
            out_vectors += "#endif /* WITH_CURVE_"+curve.name+" */\n"
            out_vectors += "#endif /* WITH_SIG_"+sig_alg_name+" */\n"
            out_vectors += "#endif /* USE_ISO14888_3_ECRDSA */\n"
            out_name = ""
            out_name += "#ifdef USE_ISO14888_3_ECRDSA"+"/* For "+test_name+" */\n"
            out_name += "#ifdef WITH_HASH_"+hashfunc_name.upper()+"/* For "+test_name+" */\n"
            out_name += "#ifdef WITH_CURVE_"+curve.name.upper()+"/* For "+test_name+" */\n"
            out_name += "#ifdef WITH_SIG_"+sig_alg_name.upper()+"/* For "+test_name+" */\n"
            out_name += "\t&"+test_name+"_test_case,\n"
            out_name += "#endif /* WITH_HASH_"+hashfunc_name+" for "+test_name+" */\n"
            out_name += "#endif /* WITH_CURVE_"+curve.name+" for "+test_name+" */\n"
            out_name += "#endif /* WITH_SIG_"+sig_alg_name+" for "+test_name+" */\n"
            out_name += "#endif /* USE_ISO14888_3_ECRDSA */"+"/* For "+test_name+" */"
            output_list.append((out_name, out_vectors))

    return output_list

def gen_self_tests(curve, num):
    global curr_test
    curr_test = 0
    total_gen_tests = len(all_hash_funcs) * len(all_sig_algs)
    vectors = [[ gen_self_test(curve, hashf, sign, verify, genkp, num, hash_name, sig_alg_name, total_gen_tests)
               for (hashf, hash_name) in all_hash_funcs ] for (sign, verify, genkp, sig_alg_name) in all_sig_algs ]
    return vectors

##########################################################
### ASN.1 stuff
def parse_DER_extract_size(derbuf):
    # Extract the size
    if ord(derbuf[0]) & 0x80 != 0:
        encoding_len_bytes = ord(derbuf[0]) & ~0x80
        # Skip
        base = 1
    else:
        encoding_len_bytes = 1
        base = 0
    if len(derbuf) < encoding_len_bytes+1:
        return (False, 0, 0)
    else:
        length = stringtoint(derbuf[base:base+encoding_len_bytes])
        if len(derbuf) < length+encoding_len_bytes:
            return (False, 0, 0)
        else:
            return (True, encoding_len_bytes+base, length)

def extract_DER_object(derbuf, object_tag):
    # Check type
    if ord(derbuf[0]) != object_tag:
        # Not the type we expect ...
        return (False, 0, "")
    else:
        derbuf = derbuf[1:]
        # Extract the size
        (check, encoding_len, size) = parse_DER_extract_size(derbuf)
        if check == False:
            return (False, 0, "")
        else:
            if len(derbuf) < encoding_len + size:
                return (False, 0, "")
            else:
                return (True, size+encoding_len+1, derbuf[encoding_len:encoding_len+size])

def extract_DER_sequence(derbuf):
    return extract_DER_object(derbuf, 0x30)

def extract_DER_integer(derbuf):
    return extract_DER_object(derbuf, 0x02)

def extract_DER_octetstring(derbuf):
    return extract_DER_object(derbuf, 0x04)

def extract_DER_bitstring(derbuf):
    return extract_DER_object(derbuf, 0x03)

def extract_DER_oid(derbuf):
    return extract_DER_object(derbuf, 0x06)

# See ECParameters sequence in RFC 3279
def parse_DER_ECParameters(derbuf):
    # XXX: this is a very ugly way of extracting the information
    # regarding an EC curve, but since the ASN.1 structure is quite
    # "static", this might be sufficient without embedding a full
    # ASN.1 parser ...
    # Default return (a, b, prime, order, cofactor, gx, gy)
    default_ret = (0, 0, 0, 0, 0, 0, 0)
    # Get ECParameters wrapping sequence
    (check, size_ECParameters, ECParameters) = extract_DER_sequence(derbuf)
    if check == False:
        return (False, default_ret)
    # Get integer
    (check, size_ECPVer, ECPVer) = extract_DER_integer(ECParameters)
    if check == False:
        return (False, default_ret)
    # Get sequence
    (check, size_FieldID, FieldID) = extract_DER_sequence(ECParameters[size_ECPVer:])
    if check == False:
        return (False, default_ret)
    # Get OID
    (check, size_Oid, Oid) = extract_DER_oid(FieldID)
    if check == False:
        return (False, default_ret)
    # Does the OID correspond to a prime field?
    if(Oid != "\x2A\x86\x48\xCE\x3D\x01\x01"):
        print("DER parse error: only prime fields are supported ...")
        return (False, default_ret)
    # Get prime p of prime field
    (check, size_P, P) = extract_DER_integer(FieldID[size_Oid:])
    if check == False:
        return (False, default_ret)
    # Get curve (sequence)
    (check, size_Curve, Curve) = extract_DER_sequence(ECParameters[size_ECPVer+size_FieldID:])
    if check == False:
        return (False, default_ret)
    # Get A in curve
    (check, size_A, A) = extract_DER_octetstring(Curve)
    if check == False:
        return (False, default_ret)
    # Get B in curve
    (check, size_B, B) = extract_DER_octetstring(Curve[size_A:])
    if check == False:
        return (False, default_ret)
    # Get ECPoint
    (check, size_ECPoint, ECPoint) = extract_DER_octetstring(ECParameters[size_ECPVer+size_FieldID+size_Curve:])
    if check == False:
        return (False, default_ret)
    # Get Order
    (check, size_Order, Order) = extract_DER_integer(ECParameters[size_ECPVer+size_FieldID+size_Curve+size_ECPoint:])
    if check == False:
        return (False, default_ret)
    # Get Cofactor
    (check, size_Cofactor, Cofactor) = extract_DER_integer(ECParameters[size_ECPVer+size_FieldID+size_Curve+size_ECPoint+size_Order:])
    if check == False:
        return (False, default_ret)
    # If we end up here, everything is OK, we can extract all our elements
    prime = stringtoint(P)
    a = stringtoint(A)
    b = stringtoint(B)
    order = stringtoint(Order)
    cofactor = stringtoint(Cofactor)
    # Extract Gx and Gy, see X9.62-1998
    if len(ECPoint) < 1:
        return (False, default_ret)
    ECPoint_type = ord(ECPoint[0])
    if (ECPoint_type == 0x04) or (ECPoint_type == 0x06) or (ECPoint_type == 0x07):
        # Uncompressed and hybrid points
        if len(ECPoint[1:]) % 2 != 0:
            return (False, default_ret)
        ECPoint = ECPoint[1:]
        gx = stringtoint(ECPoint[:int(len(ECPoint)/2)])
        gy = stringtoint(ECPoint[int(len(ECPoint)/2):])
    elif (ECPoint_type == 0x02) or (ECPoint_type == 0x03):
        # Compressed point: uncompress it, see X9.62-1998 section 4.2.1
        ECPoint = ECPoint[1:]
        gx = stringtoint(ECPoint)
        alpha = (pow(gx, 3, prime) + (a * gx) + b) % prime
        beta = mod_sqrt(alpha, prime)
        if (beta == None) or ((beta == 0) and (alpha != 0)):
            return (False, 0)
        if (beta & 0x1) == (ECPoint_type & 0x1):
            gy = beta
        else:
            gy = prime - beta
    else:
        print("DER parse error: hybrid points are unsupported!")
        return (False, default_ret)
    return (True, (a, b, prime, order, cofactor, gx, gy))

##########################################################
### Text and format helpers
def bigint_to_C_array(bint, size):
    """
    Format a python big int to a C hex array
    """
    hexstr = format(int(bint), 'x')
    # Left pad to the size!
    hexstr = ("0"*int((2*size)-len(hexstr)))+hexstr
    hexstr = ("0"*(len(hexstr) % 2))+hexstr
    out_str = "{\n"
    for i in range(0, len(hexstr) - 1, 2):
        if (i%16 == 0):
            if(i!=0):
                out_str += "\n"
            out_str += "\t"
        out_str += "0x"+hexstr[i:i+2]+", "
    out_str += "\n};\n"
    return out_str

def check_in_file(fname, pat):
    # See if the pattern is in the file.
    with open(fname) as f:
        if not any(re.search(pat, line) for line in f):
            return False # pattern does not occur in file so we are done.
        else:
            return True

def num_patterns_in_file(fname, pat):
    num_pat = 0
    with open(fname) as f:
        for line in f:
            if re.search(pat, line):
                num_pat = num_pat+1
    return num_pat

def file_replace_pattern(fname, pat, s_after):
    # first, see if the pattern is even in the file.
    with open(fname) as f:
        if not any(re.search(pat, line) for line in f):
            return # pattern does not occur in file so we are done.

    # pattern is in the file, so perform replace operation.
    with open(fname) as f:
        out_fname = fname + ".tmp"
        out = open(out_fname, "w")
        for line in f:
            out.write(re.sub(pat, s_after, line))
        out.close()
        os.rename(out_fname, fname)

def file_remove_pattern(fname, pat):
    # first, see if the pattern is even in the file.
    with open(fname) as f:
        if not any(re.search(pat, line) for line in f):
            return # pattern does not occur in file so we are done.

    # pattern is in the file, so perform remove operation.
    with open(fname) as f:
        out_fname = fname + ".tmp"
        out = open(out_fname, "w")
        for line in f:
            if not re.search(pat, line):
                out.write(line)
        out.close()

    if os.path.exists(fname):
        remove_file(fname)
    os.rename(out_fname, fname)

def remove_file(fname):
    # Remove file
    os.remove(fname)

def remove_files_pattern(fpattern):
    [remove_file(x) for x in glob.glob(fpattern)]

def buffer_remove_pattern(buff, pat):
    if is_python_2() == False:
        buff = buff.decode('latin-1')
    if re.search(pat, buff) == None:
        return (False, buff) # pattern does not occur in file so we are done.
    # Remove the pattern
    buff = re.sub(pat, "", buff)
    return (True, buff)

def is_base64(s):
    s = ''.join([s.strip() for s in s.split("\n")])
    try:
        enc = base64.b64encode(base64.b64decode(s)).strip()
        return enc == s
    except TypeError:
        return False

### Curve helpers
def export_curve_int(curvename, intname, bigint, size):
    if bigint == None:
        out  = "static const u8 "+curvename+"_"+intname+"[] = {\n\t0x00,\n};\n"
        out += "TO_EC_STR_PARAM_FIXED_SIZE("+curvename+"_"+intname+", 0);\n\n"
    else:
        out  = "static const u8 "+curvename+"_"+intname+"[] = "+bigint_to_C_array(bigint, size)+"\n"
        out += "TO_EC_STR_PARAM("+curvename+"_"+intname+");\n\n"
    return out

def export_curve_string(curvename, stringname, stringvalue):
    out  = "static const u8 "+curvename+"_"+stringname+"[] = \""+stringvalue+"\";\n"
    out += "TO_EC_STR_PARAM("+curvename+"_"+stringname+");\n\n"
    return out

def export_curve_struct(curvename, paramname, paramnamestr):
    return "\t."+paramname+" = &"+curvename+"_"+paramnamestr+"_str_param, \n"

def curve_params(name, prime, pbitlen, a, b, gx, gy, order, cofactor, oid, alpha_montgomery, gamma_montgomery, alpha_edwards):
    """
    Take as input some elliptic curve parameters and generate the
    C parameters in a string
    """
    bytesize = int(pbitlen / 8)
    if pbitlen % 8 != 0:
        bytesize += 1
    # Compute the rounded word size for each word size
    if bytesize % 8 != 0:
        wordsbitsize64 = 8*((int(bytesize/8)+1)*8)
    else:
        wordsbitsize64 = 8*bytesize
    if bytesize % 4 != 0:
        wordsbitsize32 = 8*((int(bytesize/4)+1)*4)
    else:
        wordsbitsize32 = 8*bytesize
    if bytesize % 2 != 0:
        wordsbitsize16 = 8*((int(bytesize/2)+1)*2)
    else:
        wordsbitsize16 = 8*bytesize
    # Compute some parameters
    (r64, r_square64, mpinv64) = compute_monty_coef(prime, wordsbitsize64, 64)
    (r32, r_square32, mpinv32) = compute_monty_coef(prime, wordsbitsize32, 32)
    (r16, r_square16, mpinv16) = compute_monty_coef(prime, wordsbitsize16, 16)
    # Compute p_reciprocal for each word size
    (pshift64, primenorm64, p_reciprocal64) = compute_div_coef(prime, wordsbitsize64, 64)
    (pshift32, primenorm32, p_reciprocal32) = compute_div_coef(prime, wordsbitsize32, 32)
    (pshift16, primenorm16, p_reciprocal16) = compute_div_coef(prime, wordsbitsize16, 16)
    # Compute the number of points on the curve
    npoints = order * cofactor

    # Now output the parameters
    ec_params_string =  "#include \"../../lib_ecc_config.h\"\n"
    ec_params_string += "#ifdef WITH_CURVE_"+name.upper()+"\n\n"
    ec_params_string += "#ifndef __EC_PARAMS_"+name.upper()+"_H__\n"
    ec_params_string += "#define __EC_PARAMS_"+name.upper()+"_H__\n"
    ec_params_string += "#include \"../known/ec_params_external.h\"\n"
    ec_params_string += export_curve_int(name, "p", prime, bytesize)

    ec_params_string += "#define CURVE_"+name.upper()+"_P_BITLEN "+str(pbitlen)+"\n"
    ec_params_string += export_curve_int(name, "p_bitlen", pbitlen, getbytelen(pbitlen))

    ec_params_string += "#if (WORD_BYTES == 8)     /* 64-bit words */\n"
    ec_params_string += export_curve_int(name, "r", r64, getbytelen(r64))
    ec_params_string += export_curve_int(name, "r_square", r_square64, getbytelen(r_square64))
    ec_params_string += export_curve_int(name, "mpinv", mpinv64, getbytelen(mpinv64))
    ec_params_string += export_curve_int(name, "p_shift", pshift64, getbytelen(pshift64))
    ec_params_string += export_curve_int(name, "p_normalized", primenorm64, getbytelen(primenorm64))
    ec_params_string += export_curve_int(name, "p_reciprocal", p_reciprocal64, getbytelen(p_reciprocal64))
    ec_params_string += "#elif (WORD_BYTES == 4)   /* 32-bit words */\n"
    ec_params_string += export_curve_int(name, "r", r32, getbytelen(r32))
    ec_params_string += export_curve_int(name, "r_square", r_square32, getbytelen(r_square32))
    ec_params_string += export_curve_int(name, "mpinv", mpinv32, getbytelen(mpinv32))
    ec_params_string += export_curve_int(name, "p_shift", pshift32, getbytelen(pshift32))
    ec_params_string += export_curve_int(name, "p_normalized", primenorm32, getbytelen(primenorm32))
    ec_params_string += export_curve_int(name, "p_reciprocal", p_reciprocal32, getbytelen(p_reciprocal32))
    ec_params_string += "#elif (WORD_BYTES == 2)   /* 16-bit words */\n"
    ec_params_string += export_curve_int(name, "r", r16, getbytelen(r16))
    ec_params_string += export_curve_int(name, "r_square", r_square16, getbytelen(r_square16))
    ec_params_string += export_curve_int(name, "mpinv", mpinv16, getbytelen(mpinv16))
    ec_params_string += export_curve_int(name, "p_shift", pshift16, getbytelen(pshift16))
    ec_params_string += export_curve_int(name, "p_normalized", primenorm16, getbytelen(primenorm16))
    ec_params_string += export_curve_int(name, "p_reciprocal", p_reciprocal16, getbytelen(p_reciprocal16))
    ec_params_string += "#else                     /* unknown word size */\n"
    ec_params_string += "#error \"Unsupported word size\"\n"
    ec_params_string += "#endif\n\n"

    ec_params_string += export_curve_int(name, "a", a, bytesize)
    ec_params_string += export_curve_int(name, "b", b, bytesize)

    curve_order_bitlen = getbitlen(npoints)
    ec_params_string += "#define CURVE_"+name.upper()+"_CURVE_ORDER_BITLEN "+str(curve_order_bitlen)+"\n"
    ec_params_string += export_curve_int(name, "curve_order", npoints, getbytelen(npoints))

    ec_params_string += export_curve_int(name, "gx", gx, bytesize)
    ec_params_string += export_curve_int(name, "gy", gy, bytesize)
    ec_params_string += export_curve_int(name, "gz", 0x01, bytesize)

    qbitlen = getbitlen(order)

    ec_params_string += export_curve_int(name, "gen_order", order, getbytelen(order))
    ec_params_string += "#define CURVE_"+name.upper()+"_Q_BITLEN "+str(qbitlen)+"\n"
    ec_params_string += export_curve_int(name, "gen_order_bitlen", qbitlen, getbytelen(qbitlen))

    ec_params_string += export_curve_int(name, "cofactor", cofactor, getbytelen(cofactor))

    ec_params_string += export_curve_int(name, "alpha_montgomery", alpha_montgomery, getbytelen(alpha_montgomery))
    ec_params_string += export_curve_int(name, "gamma_montgomery", gamma_montgomery, getbytelen(gamma_montgomery))
    ec_params_string += export_curve_int(name, "alpha_edwards", alpha_edwards, getbytelen(alpha_edwards))

    ec_params_string += export_curve_string(name, "name", name.upper());

    if oid == None:
        oid = ""
    ec_params_string += export_curve_string(name, "oid", oid);

    ec_params_string += "static const ec_str_params "+name+"_str_params = {\n"+\
    export_curve_struct(name, "p", "p") +\
    export_curve_struct(name, "p_bitlen", "p_bitlen") +\
    export_curve_struct(name, "r", "r") +\
    export_curve_struct(name, "r_square", "r_square") +\
    export_curve_struct(name, "mpinv", "mpinv") +\
    export_curve_struct(name, "p_shift", "p_shift") +\
    export_curve_struct(name, "p_normalized", "p_normalized") +\
    export_curve_struct(name, "p_reciprocal", "p_reciprocal") +\
    export_curve_struct(name, "a", "a") +\
    export_curve_struct(name, "b", "b") +\
    export_curve_struct(name, "curve_order", "curve_order") +\
    export_curve_struct(name, "gx", "gx") +\
    export_curve_struct(name, "gy", "gy") +\
    export_curve_struct(name, "gz", "gz") +\
    export_curve_struct(name, "gen_order", "gen_order") +\
    export_curve_struct(name, "gen_order_bitlen", "gen_order_bitlen") +\
    export_curve_struct(name, "cofactor", "cofactor") +\
    export_curve_struct(name, "alpha_montgomery", "alpha_montgomery") +\
    export_curve_struct(name, "gamma_montgomery", "gamma_montgomery") +\
    export_curve_struct(name, "alpha_edwards", "alpha_edwards") +\
    export_curve_struct(name, "oid", "oid") +\
    export_curve_struct(name, "name", "name")
    ec_params_string += "};\n\n"

    ec_params_string += "/*\n"+\
    " * Compute max bit length of all curves for p and q\n"+\
    " */\n"+\
    "#ifndef CURVES_MAX_P_BIT_LEN\n"+\
    "#define CURVES_MAX_P_BIT_LEN    0\n"+\
    "#endif\n"+\
    "#if (CURVES_MAX_P_BIT_LEN < CURVE_"+name.upper()+"_P_BITLEN)\n"+\
    "#undef CURVES_MAX_P_BIT_LEN\n"+\
    "#define CURVES_MAX_P_BIT_LEN CURVE_"+name.upper()+"_P_BITLEN\n"+\
    "#endif\n"+\
    "#ifndef CURVES_MAX_Q_BIT_LEN\n"+\
    "#define CURVES_MAX_Q_BIT_LEN    0\n"+\
    "#endif\n"+\
    "#if (CURVES_MAX_Q_BIT_LEN < CURVE_"+name.upper()+"_Q_BITLEN)\n"+\
    "#undef CURVES_MAX_Q_BIT_LEN\n"+\
    "#define CURVES_MAX_Q_BIT_LEN CURVE_"+name.upper()+"_Q_BITLEN\n"+\
    "#endif\n"+\
    "#ifndef CURVES_MAX_CURVE_ORDER_BIT_LEN\n"+\
    "#define CURVES_MAX_CURVE_ORDER_BIT_LEN    0\n"+\
    "#endif\n"+\
    "#if (CURVES_MAX_CURVE_ORDER_BIT_LEN < CURVE_"+name.upper()+"_CURVE_ORDER_BITLEN)\n"+\
    "#undef CURVES_MAX_CURVE_ORDER_BIT_LEN\n"+\
    "#define CURVES_MAX_CURVE_ORDER_BIT_LEN CURVE_"+name.upper()+"_CURVE_ORDER_BITLEN\n"+\
    "#endif\n\n"

    ec_params_string += "/*\n"+\
    " * Compute and adapt max name and oid length\n"+\
    " */\n"+\
    "#ifndef MAX_CURVE_OID_LEN\n"+\
    "#define MAX_CURVE_OID_LEN 0\n"+\
    "#endif\n"+\
    "#ifndef MAX_CURVE_NAME_LEN\n"+\
    "#define MAX_CURVE_NAME_LEN 0\n"+\
    "#endif\n"+\
    "#if (MAX_CURVE_OID_LEN < "+str(len(oid)+1)+")\n"+\
    "#undef MAX_CURVE_OID_LEN\n"+\
    "#define MAX_CURVE_OID_LEN "+str(len(oid)+1)+"\n"+\
    "#endif\n"+\
    "#if (MAX_CURVE_NAME_LEN < "+str(len(name.upper())+1)+")\n"+\
    "#undef MAX_CURVE_NAME_LEN\n"+\
    "#define MAX_CURVE_NAME_LEN "+str(len(name.upper())+1)+"\n"+\
    "#endif\n\n"

    ec_params_string += "#endif /* __EC_PARAMS_"+name.upper()+"_H__ */\n\n"+"#endif /* WITH_CURVE_"+name.upper()+" */\n"

    return ec_params_string

def usage():
    print("This script is intented to *statically* expand the ECC library with user defined curves.")
    print("By statically we mean that the source code of libecc is expanded with new curves parameters through")
    print("automatic code generation filling place holders in the existing code base of the library. Though the")
    print("choice of static code generation versus dynamic curves import (such as what OpenSSL does) might be")
    print("argued, this choice has been driven by simplicity and security design decisions: we want libecc to have")
    print("all its parameters (such as memory consumption) set at compile time and statically adapted to the curves.")
    print("Since libecc only supports curves over prime fields, the script can only add this kind of curves.")
    print("This script implements elliptic curves and ISO signature algorithms from scratch over Python's multi-precision")
    print("big numbers library. Addition and doubling over curves use naive formulas. Please DO NOT use the functions of this")
    print("script for production code: they are not securely implemented and are very inefficient. Their only purpose is to expand")
    print("libecc and produce test vectors.")
    print("")
    print("In order to add a curve, there are two ways:")
    print("Adding a user defined curve with explicit parameters:")
    print("-----------------------------------------------------")
    print(sys.argv[0]+" --name=\"YOURCURVENAME\" --prime=... --order=... --a=... --b=... --gx=... --gy=... --cofactor=... --oid=THEOID")
    print("\t> name: name of the curve in the form of a string")
    print("\t> prime: prime number representing the curve prime field")
    print("\t> order: prime number representing the generator order")
    print("\t> cofactor: cofactor of the curve")
    print("\t> a: 'a' coefficient of the short Weierstrass equation of the curve")
    print("\t> b: 'b' coefficient of the short Weierstrass equation of the curve")
    print("\t> gx: x coordinate of the generator G")
    print("\t> gy: y coordinate of the generator G")
    print("\t> oid: optional OID of the curve")
    print("  Notes:")
    print("  ******")
    print("\t1) These elements are verified to indeed satisfy the curve equation.")
    print("\t2) All the numbers can be given either in decimal or hexadecimal format with a prepending '0x'.")
    print("\t3) The script automatically generates all the necessary files for the curve to be included in the library." )
    print("\tYou will find the new curve definition in the usual 'lib_ecc_config.h' file (one can activate it or not at compile time).")
    print("")
    print("Adding a user defined curve through RFC3279 ASN.1 parameters:")
    print("-------------------------------------------------------------")
    print(sys.argv[0]+" --name=\"YOURCURVENAME\" --ECfile=... --oid=THEOID")
    print("\t> ECfile: the DER or PEM encoded file containing the curve parameters (see RFC3279)")
    print("  Notes:")
    print("\tCurve parameters encoded in DER or PEM format can be generated with tools like OpenSSL (among others). As an illustrative example,")
    print("\tone can list all the supported curves under OpenSSL with:")
    print("\t  $ openssl ecparam -list_curves")
    print("\tOnly the listed so called \"prime\" curves are supported. Then, one can extract an explicit curve representation in ASN.1")
    print("\tas defined in RFC3279, for example for BRAINPOOLP320R1:")
    print("\t  $ openssl ecparam -param_enc explicit -outform DER -name brainpoolP320r1 -out brainpoolP320r1.der")
    print("")
    print("Removing user defined curves:")
    print("-----------------------------")
    print("\t*All the user defined curves can be removed with the --remove-all toggle.")
    print("\t*A specific named user define curve can be removed with the --remove toggle: in this case the --name option is used to ")
    print("\tlocate which named curve must be deleted.")
    print("")
    print("Test vectors:")
    print("-------------")
    print("\tTest vectors can be automatically generated and added to the library self tests when providing the --add-test-vectors=X toggle.")
    print("\tIn this case, X test vectors will be generated for *each* (curve, sign algorithm, hash algorithm) 3-uplet (beware of combinatorial")
    print("\tissues when X is big!). These tests are transparently added and compiled with the self tests.")
    return

def get_int(instring):
    if len(instring) == 0:
        return 0
    if len(instring) >= 2:
        if instring[:2] == "0x":
            return int(instring, 16)
    return int(instring)

def parse_cmd_line(args):
    """
    Get elliptic curve parameters from command line
    """
    name = oid = prime = a = b = gx = gy = g = order = cofactor = ECfile = remove = remove_all = add_test_vectors = None
    alpha_montgomery = gamma_montgomery = alpha_edwards = None
    try:
        opts, args = getopt.getopt(sys.argv[1:], ":h", ["help", "remove", "remove-all", "name=", "prime=", "a=", "b=", "generator=", "gx=", "gy=", "order=", "cofactor=", "alpha_montgomery=","gamma_montgomery=", "alpha_edwards=", "ECfile=", "oid=", "add-test-vectors="])
    except getopt.GetoptError as err:
        # print help information and exit:
        print(err) # will print something like "option -a not recognized"
        usage()
        return False
    for o, arg in opts:
        if o in ("-h", "--help"):
            usage()
            return True
        elif o in ("--name"):
            name = arg
            # Prepend the custom string before name to avoid any collision
            name = "user_defined_"+name
            # Replace any unwanted name char
            name = re.sub("\-", "_", name)
        elif o in ("--oid="):
            oid = arg
        elif o in ("--prime"):
            prime = get_int(arg.replace(' ', ''))
        elif o in ("--a"):
            a = get_int(arg.replace(' ', ''))
        elif o in ("--b"):
            b = get_int(arg.replace(' ', ''))
        elif o in ("--gx"):
            gx = get_int(arg.replace(' ', ''))
        elif o in ("--gy"):
            gy = get_int(arg.replace(' ', ''))
        elif o in ("--generator"):
            g = arg.replace(' ', '')
        elif o in ("--order"):
            order = get_int(arg.replace(' ', ''))
        elif o in ("--cofactor"):
            cofactor = get_int(arg.replace(' ', ''))
        elif o in ("--alpha_montgomery"):
            alpha_montgomery = get_int(arg.replace(' ', ''))
        elif o in ("--gamma_montgomery"):
            gamma_montgomery = get_int(arg.replace(' ', ''))
        elif o in ("--alpha_edwards"):
            alpha_edwards = get_int(arg.replace(' ', ''))
        elif o in ("--remove"):
            remove = True
        elif o in ("--remove-all"):
            remove_all = True
        elif o in ("--add-test-vectors"):
            add_test_vectors = get_int(arg.replace(' ', ''))
        elif o in ("--ECfile"):
            ECfile = arg
        else:
            print("unhandled option")
            usage()
            return False

    # File paths
    script_path = os.path.abspath(os.path.dirname(sys.argv[0])) + "/"
    ec_params_path = script_path + "../src/curves/user_defined/"
    curves_list_path = script_path + "../src/curves/"
    lib_ecc_types_path = script_path + "../src/"
    lib_ecc_config_path = script_path + "../src/"
    ec_self_tests_path = script_path + "../src/tests/"

    # If remove is True, we have been asked to remove already existing user defined curves
    if remove == True:
        if name == None:
            print("--remove option expects a curve name provided with --name")
            return False
        asked = ""
        while asked != "y" and asked != "n":
            asked = get_user_input("You asked to remove everything related to user defined "+name.replace("user_defined_", "")+" curve. Enter y to confirm, n to cancel [y/n]. ")
        if asked == "n":
            print("NOT removing curve "+name.replace("user_defined_", "")+" (cancelled).")
            return True
        # Remove any user defined stuff with given name
        print("Removing user defined curve "+name.replace("user_defined_", "")+" ...")
        if name == None:
            print("Error: you must provide a curve name with --remove")
            return False
        file_remove_pattern(curves_list_path + "curves_list.h", ".*"+name+".*")
        file_remove_pattern(curves_list_path + "curves_list.h", ".*"+name.upper()+".*")
        file_remove_pattern(lib_ecc_types_path + "lib_ecc_types.h", ".*"+name.upper()+".*")
        file_remove_pattern(lib_ecc_config_path + "lib_ecc_config.h", ".*"+name.upper()+".*")
        file_remove_pattern(ec_self_tests_path + "ec_self_tests_core.h", ".*"+name+".*")
        file_remove_pattern(ec_self_tests_path + "ec_self_tests_core.h", ".*"+name.upper()+".*")
        try:
            remove_file(ec_params_path + "ec_params_"+name+".h")
        except:
            print("Error: curve name "+name+" does not seem to be present in the sources!")
            return False
        try:
            remove_file(ec_self_tests_path + "ec_self_tests_core_"+name+".h")
        except:
            print("Warning: curve name "+name+" self tests do not seem to be present ...")
            return True
        return True
    if remove_all == True:
        asked = ""
        while asked != "y" and asked != "n":
            asked = get_user_input("You asked to remove everything related to ALL user defined curves. Enter y to confirm, n to cancel [y/n]. ")
        if asked == "n":
            print("NOT removing user defined curves (cancelled).")
            return True
        # Remove any user defined stuff with given name
        print("Removing ALL user defined curves ...")
        # Remove any user defined stuff (whatever name)
        file_remove_pattern(curves_list_path + "curves_list.h", ".*user_defined.*")
        file_remove_pattern(curves_list_path + "curves_list.h", ".*USER_DEFINED.*")
        file_remove_pattern(lib_ecc_types_path + "lib_ecc_types.h", ".*USER_DEFINED.*")
        file_remove_pattern(lib_ecc_config_path + "lib_ecc_config.h", ".*USER_DEFINED.*")
        file_remove_pattern(ec_self_tests_path + "ec_self_tests_core.h", ".*USER_DEFINED.*")
        file_remove_pattern(ec_self_tests_path + "ec_self_tests_core.h", ".*user_defined.*")
        remove_files_pattern(ec_params_path + "ec_params_user_defined_*.h")
        remove_files_pattern(ec_self_tests_path + "ec_self_tests_core_user_defined_*.h")
        return True

    # If a g is provided, split it in two gx and gy
    if g != None:
        if (len(g)/2)%2 == 0:
            gx = get_int(g[:len(g)/2])
            gy = get_int(g[len(g)/2:])
        else:
            # This is probably a generator encapsulated in a bit string
            if g[0:2] != "04":
                print("Error: provided generator g is not conforming!")
                return False
            else:
                g = g[2:]
                gx = get_int(g[:len(g)/2])
                gy = get_int(g[len(g)/2:])
    if ECfile != None:
        # ASN.1 DER input incompatible with other options
        if (prime != None) or (a != None) or (b != None) or (gx != None) or (gy != None) or (order != None) or (cofactor != None):
            print("Error: option ECfile incompatible with explicit (prime, a, b, gx, gy, order, cofactor) options!")
            return False
        # We need at least a name
        if (name == None):
            print("Error: option ECfile needs a curve name!")
            return False
        # Open the file
        try:
            buf = open(ECfile, 'rb').read()
        except:
            print("Error: cannot open ECfile file "+ECfile)
            return False
        # Check if we have a PEM or a DER file
        (check, derbuf) = buffer_remove_pattern(buf, "-----.*-----")
        if (check == True):
            # This a PEM file, proceed with base64 decoding
            if(is_base64(derbuf) == False):
                print("Error: error when decoding ECfile file "+ECfile+" (seems to be PEM, but failed to decode)")
                return False
            derbuf = base64.b64decode(derbuf)
        (check, (a, b, prime, order, cofactor, gx, gy)) = parse_DER_ECParameters(derbuf)
        if (check == False):
            print("Error: error when parsing ECfile file "+ECfile+" (malformed or unsupported ASN.1)")
            return False

    else:
        if (prime == None) or (a == None) or (b == None) or (gx == None) or (gy == None) or (order == None) or (cofactor == None) or (name == None):
            err_string = (prime == None)*"prime "+(a == None)*"a "+(b == None)*"b "+(gx == None)*"gx "+(gy == None)*"gy "+(order == None)*"order "+(cofactor == None)*"cofactor "+(name == None)*"name "
            print("Error: missing "+err_string+" in explicit curve definition (name, prime, a, b, gx, gy, order, cofactor)!")
            print("See the help with -h or --help")
            return False

    # Some sanity checks here
    # Check that prime is indeed a prime
    if is_probprime(prime) == False:
        print("Error: given prime is *NOT* prime!")
        return False
    if is_probprime(order) == False:
        print("Error: given order is *NOT* prime!")
        return False
    if (a > prime) or (b > prime) or (gx > prime) or (gy > prime):
        err_string = (a > prime)*"a "+(b > prime)*"b "+(gx > prime)*"gx "+(gy > prime)*"gy "
        print("Error: "+err_string+"is > prime")
        return False
    # Check that the provided generator is on the curve
    if pow(gy, 2, prime) != ((pow(gx, 3, prime) + (a*gx) + b) % prime):
        print("Error: the given parameters (prime, a, b, gx, gy) do not verify the elliptic curve equation!")
        return False

    # Check Montgomery and Edwards transfer coefficients
    if ((alpha_montgomery != None) and (gamma_montgomery == None)) or ((alpha_montgomery == None) and (gamma_montgomery != None)):
        print("Error: alpha_montgomery and gamma_montgomery must be both defined if used!")
        return False
    if (alpha_edwards != None):
        if (alpha_montgomery == None) or (gamma_montgomery == None):
            print("Error: alpha_edwards needs alpha_montgomery and gamma_montgomery to be both defined if used!")
            return False

    # Now that we have our parameters, call the function to get bitlen
    pbitlen = getbitlen(prime)
    ec_params = curve_params(name, prime, pbitlen, a, b, gx, gy, order, cofactor, oid, alpha_montgomery, gamma_montgomery, alpha_edwards)
    # Check if there is a name collision somewhere
    if os.path.exists(ec_params_path + "ec_params_"+name+".h") == True :
        print("Error: file %s already exists!" % (ec_params_path + "ec_params_"+name+".h"))
        return False
    if (check_in_file(curves_list_path + "curves_list.h", "ec_params_"+name+"_str_params") == True) or (check_in_file(curves_list_path + "curves_list.h", "WITH_CURVE_"+name.upper()+"\n") == True) or (check_in_file(lib_ecc_types_path + "lib_ecc_types.h", "WITH_CURVE_"+name.upper()+"\n") == True):
        print("Error: name %s already exists in files" % ("ec_params_"+name))
        return False
    # Create a new file with the parameters
    if not os.path.exists(ec_params_path):
        # Create the "user_defined" folder if it does not exist
        os.mkdir(ec_params_path)
    f = open(ec_params_path + "ec_params_"+name+".h", 'w')
    f.write(ec_params)
    f.close()
    # Include the file in curves_list.h
    magic = "ADD curves header here"
    magic_re = "\/\* "+magic+" \*\/"
    magic_back = "/* "+magic+" */"
    file_replace_pattern(curves_list_path + "curves_list.h", magic_re, "#include \"user_defined/ec_params_"+name+".h\"\n"+magic_back)
    # Add the curve mapping
    magic = "ADD curves mapping here"
    magic_re = "\/\* "+magic+" \*\/"
    magic_back = "/* "+magic+" */"
    file_replace_pattern(curves_list_path + "curves_list.h", magic_re, "#ifdef WITH_CURVE_"+name.upper()+"\n\t{ .type = "+name.upper()+", .params = &"+name+"_str_params },\n#endif /* WITH_CURVE_"+name.upper()+" */\n"+magic_back)
    # Add the new curve type in the enum
    # First we get the number of already defined curves so that we increment the enum counter
    num_with_curve = num_patterns_in_file(lib_ecc_types_path + "lib_ecc_types.h", "#ifdef WITH_CURVE_")
    magic = "ADD curves type here"
    magic_re = "\/\* "+magic+" \*\/"
    magic_back = "/* "+magic+" */"
    file_replace_pattern(lib_ecc_types_path + "lib_ecc_types.h", magic_re, "#ifdef WITH_CURVE_"+name.upper()+"\n\t"+name.upper()+" = "+str(num_with_curve+1)+",\n#endif /* WITH_CURVE_"+name.upper()+" */\n"+magic_back)
    # Add the new curve define in the config
    magic = "ADD curves define here"
    magic_re = "\/\* "+magic+" \*\/"
    magic_back = "/* "+magic+" */"
    file_replace_pattern(lib_ecc_config_path + "lib_ecc_config.h", magic_re, "#define WITH_CURVE_"+name.upper()+"\n"+magic_back)

    # Do we need to add some test vectors?
    if add_test_vectors != None:
        print("Test vectors generation asked: this can take some time! Please wait ...")
        # Create curve
        c = Curve(a, b, prime, order, cofactor, gx, gy, cofactor * order, name, oid)
        # Generate key pair for the algorithm
        vectors = gen_self_tests(c, add_test_vectors)
        # Iterate through all the tests
        f = open(ec_self_tests_path + "ec_self_tests_core_"+name+".h", 'w')
        for l in vectors:
            for v in l:
                for case in v:
                    (case_name, case_vector) = case
                    # Add the new test case
                    magic = "ADD curve test case here"
                    magic_re = "\/\* "+magic+" \*\/"
                    magic_back = "/* "+magic+" */"
                    file_replace_pattern(ec_self_tests_path + "ec_self_tests_core.h", magic_re, case_name+"\n"+magic_back)
                    # Create/Increment the header file
                    f.write(case_vector)
        f.close()
        # Add the new test cases header
        magic = "ADD curve test vectors header here"
        magic_re = "\/\* "+magic+" \*\/"
        magic_back = "/* "+magic+" */"
        file_replace_pattern(ec_self_tests_path + "ec_self_tests_core.h", magic_re, "#include \"ec_self_tests_core_"+name+".h\"\n"+magic_back)
    return True


#### Main
if __name__ == "__main__":
    signal.signal(signal.SIGINT, handler)
    parse_cmd_line(sys.argv[1:])