Python implementation of Linkable Ring Signatures over Elliptic curves

ec_lsag_test.py

# MIT License
#
# Copyright (C) 2014 Jesper Borgstrup
# -------------------------------------------------------------------
# Permission is hereby granted, free of charge, to any person
# obtaining a copy of this software and associated documentation
# files (the "Software"), to deal in the Software without restriction,
# including without limitation the rights to use, copy, modify, merge,
# publish, distribute, sublicense, and/or sell copies of the Software,
# and to permit persons to whom the Software is furnished to do so,
# subject to the following conditions:
# 
# The above copyright notice and this permission notice shall be
# included in all copies or substantial portions of the Software.
# 
# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
# EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
# OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
# NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
# HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
# WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
# OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
# DEALINGS IN THE SOFTWARE.

import hashlib
from pyelliptic.openssl import OpenSSL
from random import randint
import time

CURVE = "secp256k1"
KEY_COUNT = 10000
DEBUG = False
curve_p = 2**256 - 2**32 - 2**9 - 2**8 - 2**7 - 2**6 - 2**4 - 1

def sign(group, keys, signer_index, message="Hello message"):
    key_count = len( keys )

    # Set signer
    signer = keys[signer_index]
    privkey_signer = get_bignum( OpenSSL.EC_KEY_get0_private_key( signer ) )

    # Get EC variables for later use
    group = OpenSSL.EC_KEY_get0_group( signer )
    group_order = get_order( group )
    generator = OpenSSL.EC_GROUP_get0_generator( group )

    # Make room for c_i, s_i, z'_i, and z''_i variables
    cs = [0] * key_count
    ss = [0] * key_count
    z_s = [0] * key_count
    z__s = [0] * key_count

    # Retrieve all public keys and their coordinates
    public_keys = map( lambda key: OpenSSL.EC_KEY_get0_public_key( key ), keys )
    public_keys_coords = map( lambda result: get_point_coordinates( group, result ), public_keys )

    # Step 1
    keys_list_hash = H2( public_keys_coords )
    H = find_point_try_and_increment( group, keys_list_hash, curve_p )
    Y_tilde = multiply_point( group, H, by_dec=privkey_signer )

    # Step 2
    u = randint( 0, group_order )
    pi_plus_1 = (signer_index+1) % key_count
    cs[pi_plus_1] = H1( group, keys_list_hash, Y_tilde, message,
                        multiply_generator( group, by_dec=u ),
                        multiply_point( group, H, by_dec=u ) )

    # Step 3
    for i in range( signer_index+1, key_count ) + range( signer_index ):
        ss[i] = randint( 0, group_order )
        next_i = (i+1) % key_count
        z_s[i] = multiply_and_add_points( group, generator, ss[i], public_keys[i], cs[i] )
        z__s[i] = multiply_and_add_points( group, H, ss[i], Y_tilde, cs[i] )
        cs[next_i] = H1( group, keys_list_hash, Y_tilde, message, z_s[i], z__s[i] )

    # Step 4
    ss[signer_index] = ( u - privkey_signer * cs[signer_index] ) % group_order

    if DEBUG:
        dump_point( group, H, "SIGN H" )
        dump_point( group, Y_tilde, "SIGN Y_tilde")
        for i in range( len( cs ) ):
            print "SIGN  c_%d:   %d" % ( i, cs[i] )
            print "SIGN  s_%d:   %d" % ( i, ss[i] )
            if z_s[i] != 0:
                dump_point( group, z_s[i], "SIGN  Z_%d" % i )
            if z__s[i] != 0:
                dump_point( group, z__s[i], "SIGN Z__%d" % i )
            print "-----------------------------------------"

    return ( public_keys, 
             message, 
             cs[0], 
             ss, 
             Y_tilde
           )

def verify( group, public_keys, message, c_0, ss, Y_tilde ):
    public_keys_coords = map( lambda result: get_point_coordinates( group, result ), public_keys )
    generator = OpenSSL.EC_GROUP_get0_generator( group )

    n = len( public_keys )

    cs = [c_0] + [0] * ( n - 1 )
    z_s = [0] * n
    z__s = [0] * n

    # Step 1
    keys_list_hash = H2( public_keys_coords )
    H = find_point_try_and_increment( group, keys_list_hash, curve_p )
    for i in range( n ):
        z_s[i] = multiply_and_add_points( group, generator, ss[i], public_keys[i], cs[i] )
        z__s[i] = multiply_and_add_points( group, H, ss[i], Y_tilde, cs[i] )
        if i < n - 1:
            cs[i+1] = H1( group, keys_list_hash, Y_tilde, message, z_s[i], z__s[i] )

    H1_ver = H1( group, keys_list_hash, Y_tilde, message, z_s[n-1], z__s[n-1] )

    if DEBUG:
        dump_point( group, H, "VERIFY H" )
        for i in range( len( cs ) ):
            print "VERIFY  c_%d:   %d" % ( i, cs[i] )
            print "VERIFY  s_%d:   %d" % ( i, ss[i] )
            dump_point( group, z_s[i], "VERIFY  Z_%d" % i )
            dump_point( group, z__s[i], "VERIFY Z__%d" % i )
            print "-----------------------------------------"

        print "VERIFY H1_ver==c_0: (%d == %d)" % ( H1_ver, cs[0] )

    return cs[0] == H1_ver

def H2( input ):
    """
    Hash the input as a string and return the hash as an integer.
    """
    return int( hashlib.sha1( 'H2_salt%s'%(input)).hexdigest(), 16 )

def H1(group, keys, Y_tilde, message, P1, P2):
    """
    The H1 function that hashes a lot of variables
    and returns the hash as an integer.
    """
    P1_x, P1_y = get_point_coordinates( group, P1 )
    P2_x, P2_y = get_point_coordinates( group, P2 )
    str = "%s,%d,%s,%d,%d,%d,%d" % ( keys, Y_tilde, message,
                                     P1_x, P1_y, P2_x, P2_y)
    return int( hashlib.sha1( "H1_salt%s"%(str) ).hexdigest(), 16 )

def int2bin(i):
    """
    Takes an integer and returns a bitstring (big endian)
    representing the integer.
    """
    result = []
    while i:
        result.append(chr(i&0xFF))
        i >>= 8
    result.reverse()
    return ''.join(result)

def new_bignum(decval=None,binval=None):
    """
    Constructs a new BN object
    and fills it with the value given.
    """
    bn = OpenSSL.BN_new()
    if decval is not None:
        binval = int2bin( decval )
    if binval is not None:
        OpenSSL.BN_bin2bn( binval, len( binval ), bn )
    return bn

def get_order(group):
    """
    Returns the order of the elliptic curve group.
    """
    result = 0
    try:
        result_bn = OpenSSL.BN_new()
        OpenSSL.EC_GROUP_get_order(group, result_bn, None)
        result = get_bignum( result_bn )
    finally:
        OpenSSL.BN_free( result_bn )
    return result

def multiply_point(group, point, by_dec=None, by_bin=None):
    """
    Multiply an EC point by a scalar value
    and returns the multiplication result
    """
    bn = new_bignum( decval=by_dec, binval=by_bin )
    result = OpenSSL.EC_POINT_new( group )
    OpenSSL.EC_POINT_mul( group, result, 0, point, bn, 0 )
    OpenSSL.BN_free( bn )
    return result

def multiply_generator(group, by_dec=None, by_bin=None):
    """
    Multiply the EC group's generator point by a scalar value
    and returns the multiplication result
    """
    try:
        bn = new_bignum( decval=by_dec, binval=by_bin )
        result = OpenSSL.EC_POINT_new( group )
        OpenSSL.EC_POINT_mul( group, result, bn, 0, 0, 0 )
    finally:
        OpenSSL.BN_free( bn )
    return result

def multiply_and_add_points(group, P1, c1, P2, c2):
    """
    Shorthand function for returning c1*P1+c2*P2,
    where P1 and P2 are EC points and c1 and c2 are scalar values.
    """
    _P1 = multiply_point( group, P1, by_dec=c1 )
    _P2 = multiply_point( group, P2, by_dec=c2 )
    result = OpenSSL.EC_POINT_new( group )
    OpenSSL.EC_POINT_add( group, result, _P1, _P2, 0 )
    return result

def generate_key( curve ):
    """
    Generates an EC public/private key pair.
    """
    key = OpenSSL.EC_KEY_new_by_curve_name( curve )
    OpenSSL.EC_KEY_generate_key( key )
    return key

def get_bignum(bn):
    """
    Extracts and returns the value of a BN object.
    """
    binary = OpenSSL.malloc(0, OpenSSL.BN_num_bytes( bn ) )
    OpenSSL.BN_bn2bin( bn, binary )
    return int( binary.raw.encode('hex') or '0', 16 )

def get_point_coordinates(group, point):
    """
    Extracts the X and Y coordinates for an EC point,
    and returns these coordinates.
    """
    try:
        x = OpenSSL.BN_new()
        y = OpenSSL.BN_new()

        # Put X and Y coordinates of public key into x and y vars
        OpenSSL.EC_POINT_get_affine_coordinates_GFp( group, point, x, y, None )

        return get_bignum( x ), get_bignum( y )

    finally:
        OpenSSL.BN_free( x )
        OpenSSL.BN_free( y )

def modular_sqrt(a, p):
    """ Find a quadratic residue (mod p) of 'a'. p
        must be an odd prime.

        Solve the congruence of the form:
            x^2 = a (mod p)
        And returns x. Note that p - x is also a root.

        0 is returned is no square root exists for
        these a and p.

        The Tonelli-Shanks algorithm is used (except
        for some simple cases in which the solution
        is known from an identity). This algorithm
        runs in polynomial time (unless the
        generalized Riemann hypothesis is false).

        Originally taken from
        http://eli.thegreenplace.net/2009/03/07/computing-modular-square-roots-in-python/
    """
    # Simple cases
    #
    if legendre_symbol(a, p) != 1:
        return 0
    elif a == 0:
        return 0
    elif p == 2:
        return p
    elif p % 4 == 3:
        return pow(a, (p + 1) / 4, p)

    # Partition p-1 to s * 2^e for an odd s (i.e.
    # reduce all the powers of 2 from p-1)
    #
    s = p - 1
    e = 0
    while s % 2 == 0:
        s /= 2
        e += 1

    # Find some 'n' with a legendre symbol n|p = -1.
    # Shouldn't take long.
    #
    n = 2
    while legendre_symbol(n, p) != -1:
        n += 1

    # Here be dragons!
    # Read the paper "Square roots from 1; 24, 51,
    # 10 to Dan Shanks" by Ezra Brown for more
    # information
    #

    # x is a guess of the square root that gets better
    # with each iteration.
    # b is the "fudge factor" - by how much we're off
    # with the guess. The invariant x^2 = ab (mod p)
    # is maintained throughout the loop.
    # g is used for successive powers of n to update
    # both a and b
    # r is the exponent - decreases with each update
    #
    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
        for m in xrange(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


def legendre_symbol(a, p):
    """ Compute the Legendre symbol a|p using
        Euler's criterion. p is a prime, a is
        relatively prime to p (if p divides
        a, then a|p = 0)

        Returns 1 if a has a square root modulo
        p, -1 otherwise.

        Originally taken from
        http://eli.thegreenplace.net/2009/03/07/computing-modular-square-roots-in-python/
    """
    ls = pow(a, (p - 1) / 2, p)
    return -1 if ls == p - 1 else ls

def find_point_try_and_increment(group, x, p):
    found = False
    x -= 1
    while not found:
        x += 1
        y_sq = x**3 + 7
        y = modular_sqrt( y_sq, p )
        if y != 0:
            result = OpenSSL.EC_POINT_new( group )
            x_bn = new_bignum( x )
            y_bn = new_bignum( y )
            OpenSSL.EC_POINT_set_affine_coordinates_GFp( group, result, x_bn, y_bn, None )
            return result

def dump_bignum(bn, prefix=""):
    """
    Prints the value of a BN object with an optional prefix.
    """
    print "%s: %d" % ( prefix, get_bignum( bn ) )

def dump_point(group, result, prefix=""):
    """
    Prints the coordinates of an EC point with an optional prefix.
    """
    x, y = get_point_coordinates( group, result )
    print "%s X: %d\n%s Y: %d" % ( prefix, x, prefix, y )

def dump_key(key):
    """
    Prints the private and public keys of an EC key with an optional prefix.
    """
    group = OpenSSL.EC_KEY_get0_group( key )
    pubkey = OpenSSL.EC_KEY_get0_public_key( key )
    privkey = OpenSSL.EC_KEY_get0_private_key( key )

    dump_bignum( privkey, "Private key" )
    dump_point( group, pubkey, "Public key" )

def get_signature_size( signature ):
    public_keys, message, c_0, ss, Y_tilde = signature
    # Each public key is 64 bytes (32 bytes per coordinate)
    size = 64 * len( public_keys )
    size += len( int2bin( c_0 ) )
    size += sum( map( lambda s: len( int2bin( s ) ), ss ) )
    # Y_tilde is also a point, which again requires 64 bytes
    size += 64
    return size

def run_test( group, keys, signer_index ):
    signature = sign( group, keys, signer_index )
    assert verify( group, *signature )
    return get_signature_size( signature )

def run_multiple_tests( group, keys, signer_index=0, tests=1 ):
    t_start = time.time()
    size = sum( map( lambda _: run_test( group, keys, signer_index), range( tests ) ) )
    t_end = time.time()
    t = t_end - t_start
    print "Signing and verifying %d messages with %d keys took %.3f seconds (%.3f s/msg, %.3f ms/msg/key)" \
                % ( tests, len( keys ), t, t / tests, 1000 * t / tests / len( keys ) )
    print "The %d signatures were %d bytes in total (%.3f b/test, %.3f b/test/key)" % ( tests, size, float(size) / tests, float(size) / tests / len(keys) )
    return ( len( keys ), tests, t, size )

if __name__ == "__main__":
    curve = OpenSSL.get_curve( CURVE )
    group = OpenSSL.EC_GROUP_new_by_curve_name( curve )

    # Generate private/public key pairs
    print "Generating %d key pairs..." % KEY_COUNT
    t = time.time()
    key_gen_time = keys = map( lambda _: generate_key( curve ), range( KEY_COUNT ) )
    print "Generating %d key pairs took %.3f seconds" % ( KEY_COUNT, time.time() - t )

    results = []

    for i in [ 2, 3, 5, 10, 20, 30, 50, 100, 200, 300, 500, 1000, 2000, 3000, 5000, 10000]:
        results.append( run_multiple_tests( group, keys[0:i], tests=10 ) )

    print repr( results )

openssl.py

#  Copyright (C) 2011 Yann GUIBET <yannguibet@gmail.com>
#  See LICENSE for details.
#
#  Software slightly changed by Jonathan Warren <bitmessage at-symbol jonwarren.org>
#
#  Additional changes by Jesper Borgstrup <jesper at-symbol borgstrup.dk>:
#  * Added EC_GROUP_get0_generator, EC_GROUP_get_order,
#          EC_GROUP_new_by_curve_name and EC_POINT_add.

import sys
import ctypes

OpenSSL = None


class CipherName:
    def __init__(self, name, pointer, blocksize):
        self._name = name
        self._pointer = pointer
        self._blocksize = blocksize

    def __str__(self):
        return "Cipher : " + self._name + " | Blocksize : " + str(self._blocksize) + " | Fonction pointer : " + str(self._pointer)

    def get_pointer(self):
        return self._pointer()

    def get_name(self):
        return self._name

    def get_blocksize(self):
        return self._blocksize


class _OpenSSL:
    """
    Wrapper for OpenSSL using ctypes
    """
    def __init__(self, library):
        """
        Build the wrapper
        """
        self._lib = ctypes.CDLL(library)

        self.pointer = ctypes.pointer
        self.c_int = ctypes.c_int
        self.byref = ctypes.byref
        self.create_string_buffer = ctypes.create_string_buffer

        self.BN_new = self._lib.BN_new
        self.BN_new.restype = ctypes.c_void_p
        self.BN_new.argtypes = []

        self.BN_free = self._lib.BN_free
        self.BN_free.restype = None
        self.BN_free.argtypes = [ctypes.c_void_p]

        self.BN_num_bits = self._lib.BN_num_bits
        self.BN_num_bits.restype = ctypes.c_int
        self.BN_num_bits.argtypes = [ctypes.c_void_p]

        self.BN_bn2bin = self._lib.BN_bn2bin
        self.BN_bn2bin.restype = ctypes.c_int
        self.BN_bn2bin.argtypes = [ctypes.c_void_p, ctypes.c_void_p]

        self.BN_bin2bn = self._lib.BN_bin2bn
        self.BN_bin2bn.restype = ctypes.c_void_p
        self.BN_bin2bn.argtypes = [ctypes.c_void_p, ctypes.c_int,
                                   ctypes.c_void_p]

        self.EC_GROUP_get0_generator = self._lib.EC_GROUP_get0_generator
        self.EC_GROUP_get0_generator.restype = ctypes.c_int
        self.EC_GROUP_get0_generator.argtypes = [ctypes.c_void_p]

        self.EC_GROUP_get_order = self._lib.EC_GROUP_get_order
        self.EC_GROUP_get_order.restype = ctypes.c_int
        self.EC_GROUP_get_order.argtypes = [ctypes.c_void_p, ctypes.c_void_p,
                                            ctypes.c_void_p]

        self.EC_GROUP_new_by_curve_name = self._lib.EC_GROUP_new_by_curve_name
        self.EC_GROUP_new_by_curve_name.restype = ctypes.c_void_p
        self.EC_GROUP_new_by_curve_name.argtypes = [ctypes.c_int]

        self.EC_KEY_free = self._lib.EC_KEY_free
        self.EC_KEY_free.restype = None
        self.EC_KEY_free.argtypes = [ctypes.c_void_p]

        self.EC_KEY_new_by_curve_name = self._lib.EC_KEY_new_by_curve_name
        self.EC_KEY_new_by_curve_name.restype = ctypes.c_void_p
        self.EC_KEY_new_by_curve_name.argtypes = [ctypes.c_int]

        self.EC_KEY_generate_key = self._lib.EC_KEY_generate_key
        self.EC_KEY_generate_key.restype = ctypes.c_int
        self.EC_KEY_generate_key.argtypes = [ctypes.c_void_p]

        self.EC_KEY_check_key = self._lib.EC_KEY_check_key
        self.EC_KEY_check_key.restype = ctypes.c_int
        self.EC_KEY_check_key.argtypes = [ctypes.c_void_p]

        self.EC_KEY_get0_private_key = self._lib.EC_KEY_get0_private_key
        self.EC_KEY_get0_private_key.restype = ctypes.c_void_p
        self.EC_KEY_get0_private_key.argtypes = [ctypes.c_void_p]

        self.EC_KEY_get0_public_key = self._lib.EC_KEY_get0_public_key
        self.EC_KEY_get0_public_key.restype = ctypes.c_void_p
        self.EC_KEY_get0_public_key.argtypes = [ctypes.c_void_p]

        self.EC_KEY_get0_group = self._lib.EC_KEY_get0_group
        self.EC_KEY_get0_group.restype = ctypes.c_void_p
        self.EC_KEY_get0_group.argtypes = [ctypes.c_void_p]

        self.EC_POINT_get_affine_coordinates_GFp = self._lib.EC_POINT_get_affine_coordinates_GFp
        self.EC_POINT_get_affine_coordinates_GFp.restype = ctypes.c_int
        self.EC_POINT_get_affine_coordinates_GFp.argtypes = [ctypes.c_void_p, ctypes.c_void_p, ctypes.c_void_p, ctypes.c_void_p, ctypes.c_void_p]

        self.EC_KEY_set_private_key = self._lib.EC_KEY_set_private_key
        self.EC_KEY_set_private_key.restype = ctypes.c_int
        self.EC_KEY_set_private_key.argtypes = [ctypes.c_void_p,
                                                ctypes.c_void_p]

        self.EC_KEY_set_public_key = self._lib.EC_KEY_set_public_key
        self.EC_KEY_set_public_key.restype = ctypes.c_int
        self.EC_KEY_set_public_key.argtypes = [ctypes.c_void_p,
                                               ctypes.c_void_p]

        self.EC_KEY_set_group = self._lib.EC_KEY_set_group
        self.EC_KEY_set_group.restype = ctypes.c_int
        self.EC_KEY_set_group.argtypes = [ctypes.c_void_p, ctypes.c_void_p]

        self.EC_POINT_set_affine_coordinates_GFp = self._lib.EC_POINT_set_affine_coordinates_GFp
        self.EC_POINT_set_affine_coordinates_GFp.restype = ctypes.c_int
        self.EC_POINT_set_affine_coordinates_GFp.argtypes = [ctypes.c_void_p, ctypes.c_void_p, ctypes.c_void_p, ctypes.c_void_p, ctypes.c_void_p]

        self.EC_POINT_new = self._lib.EC_POINT_new
        self.EC_POINT_new.restype = ctypes.c_void_p
        self.EC_POINT_new.argtypes = [ctypes.c_void_p]

        self.EC_POINT_free = self._lib.EC_POINT_free
        self.EC_POINT_free.restype = None
        self.EC_POINT_free.argtypes = [ctypes.c_void_p]

        self.BN_CTX_free = self._lib.BN_CTX_free
        self.BN_CTX_free.restype = None
        self.BN_CTX_free.argtypes = [ctypes.c_void_p]

        self.EC_POINT_mul = self._lib.EC_POINT_mul
        self.EC_POINT_mul.restype = None
        self.EC_POINT_mul.argtypes = [ctypes.c_void_p, ctypes.c_void_p, ctypes.c_void_p, ctypes.c_void_p, ctypes.c_void_p]

        self.EC_POINT_add = self._lib.EC_POINT_add
        self.EC_POINT_add.resType = None
        self.EC_POINT_add.argtypes = [ctypes.c_void_p, ctypes.c_void_p, ctypes.c_void_p, ctypes.c_void_p, ctypes.c_void_p]

        self.EC_KEY_set_private_key = self._lib.EC_KEY_set_private_key
        self.EC_KEY_set_private_key.restype = ctypes.c_int
        self.EC_KEY_set_private_key.argtypes = [ctypes.c_void_p,
                                                ctypes.c_void_p]

        self.ECDH_OpenSSL = self._lib.ECDH_OpenSSL
        self._lib.ECDH_OpenSSL.restype = ctypes.c_void_p
        self._lib.ECDH_OpenSSL.argtypes = []

        self.BN_CTX_new = self._lib.BN_CTX_new
        self._lib.BN_CTX_new.restype = ctypes.c_void_p
        self._lib.BN_CTX_new.argtypes = []

        self.ECDH_set_method = self._lib.ECDH_set_method
        self._lib.ECDH_set_method.restype = ctypes.c_int
        self._lib.ECDH_set_method.argtypes = [ctypes.c_void_p, ctypes.c_void_p]

        self.ECDH_compute_key = self._lib.ECDH_compute_key
        self.ECDH_compute_key.restype = ctypes.c_int
        self.ECDH_compute_key.argtypes = [ctypes.c_void_p,
                                          ctypes.c_int, ctypes.c_void_p, ctypes.c_void_p]

        self.EVP_CipherInit_ex = self._lib.EVP_CipherInit_ex
        self.EVP_CipherInit_ex.restype = ctypes.c_int
        self.EVP_CipherInit_ex.argtypes = [ctypes.c_void_p,
                                           ctypes.c_void_p, ctypes.c_void_p]

        self.EVP_CIPHER_CTX_new = self._lib.EVP_CIPHER_CTX_new
        self.EVP_CIPHER_CTX_new.restype = ctypes.c_void_p
        self.EVP_CIPHER_CTX_new.argtypes = []

        # Cipher
        self.EVP_aes_128_cfb128 = self._lib.EVP_aes_128_cfb128
        self.EVP_aes_128_cfb128.restype = ctypes.c_void_p
        self.EVP_aes_128_cfb128.argtypes = []

        self.EVP_aes_256_cfb128 = self._lib.EVP_aes_256_cfb128
        self.EVP_aes_256_cfb128.restype = ctypes.c_void_p
        self.EVP_aes_256_cfb128.argtypes = []

        self.EVP_aes_128_cbc = self._lib.EVP_aes_128_cbc
        self.EVP_aes_128_cbc.restype = ctypes.c_void_p
        self.EVP_aes_128_cbc.argtypes = []

        self.EVP_aes_256_cbc = self._lib.EVP_aes_256_cbc
        self.EVP_aes_256_cbc.restype = ctypes.c_void_p
        self.EVP_aes_256_cbc.argtypes = []

        #self.EVP_aes_128_ctr = self._lib.EVP_aes_128_ctr
        #self.EVP_aes_128_ctr.restype = ctypes.c_void_p
        #self.EVP_aes_128_ctr.argtypes = []

        #self.EVP_aes_256_ctr = self._lib.EVP_aes_256_ctr
        #self.EVP_aes_256_ctr.restype = ctypes.c_void_p
        #self.EVP_aes_256_ctr.argtypes = []

        self.EVP_aes_128_ofb = self._lib.EVP_aes_128_ofb
        self.EVP_aes_128_ofb.restype = ctypes.c_void_p
        self.EVP_aes_128_ofb.argtypes = []

        self.EVP_aes_256_ofb = self._lib.EVP_aes_256_ofb
        self.EVP_aes_256_ofb.restype = ctypes.c_void_p
        self.EVP_aes_256_ofb.argtypes = []

        self.EVP_bf_cbc = self._lib.EVP_bf_cbc
        self.EVP_bf_cbc.restype = ctypes.c_void_p
        self.EVP_bf_cbc.argtypes = []

        self.EVP_bf_cfb64 = self._lib.EVP_bf_cfb64
        self.EVP_bf_cfb64.restype = ctypes.c_void_p
        self.EVP_bf_cfb64.argtypes = []

        self.EVP_rc4 = self._lib.EVP_rc4
        self.EVP_rc4.restype = ctypes.c_void_p
        self.EVP_rc4.argtypes = []

        self.EVP_CIPHER_CTX_cleanup = self._lib.EVP_CIPHER_CTX_cleanup
        self.EVP_CIPHER_CTX_cleanup.restype = ctypes.c_int
        self.EVP_CIPHER_CTX_cleanup.argtypes = [ctypes.c_void_p]

        self.EVP_CIPHER_CTX_free = self._lib.EVP_CIPHER_CTX_free
        self.EVP_CIPHER_CTX_free.restype = None
        self.EVP_CIPHER_CTX_free.argtypes = [ctypes.c_void_p]

        self.EVP_CipherUpdate = self._lib.EVP_CipherUpdate
        self.EVP_CipherUpdate.restype = ctypes.c_int
        self.EVP_CipherUpdate.argtypes = [ctypes.c_void_p,
                                          ctypes.c_void_p, ctypes.c_void_p, ctypes.c_void_p, ctypes.c_int]

        self.EVP_CipherFinal_ex = self._lib.EVP_CipherFinal_ex
        self.EVP_CipherFinal_ex.restype = ctypes.c_int
        self.EVP_CipherFinal_ex.argtypes = [ctypes.c_void_p,
                                            ctypes.c_void_p, ctypes.c_void_p]

        self.EVP_DigestInit = self._lib.EVP_DigestInit
        self.EVP_DigestInit.restype = ctypes.c_int
        self._lib.EVP_DigestInit.argtypes = [ctypes.c_void_p, ctypes.c_void_p]

        self.EVP_DigestUpdate = self._lib.EVP_DigestUpdate
        self.EVP_DigestUpdate.restype = ctypes.c_int
        self.EVP_DigestUpdate.argtypes = [ctypes.c_void_p,
                                          ctypes.c_void_p, ctypes.c_int]

        self.EVP_DigestFinal = self._lib.EVP_DigestFinal
        self.EVP_DigestFinal.restype = ctypes.c_int
        self.EVP_DigestFinal.argtypes = [ctypes.c_void_p,
                                         ctypes.c_void_p, ctypes.c_void_p]

        self.EVP_ecdsa = self._lib.EVP_ecdsa
        self._lib.EVP_ecdsa.restype = ctypes.c_void_p
        self._lib.EVP_ecdsa.argtypes = []

        self.ECDSA_sign = self._lib.ECDSA_sign
        self.ECDSA_sign.restype = ctypes.c_int
        self.ECDSA_sign.argtypes = [ctypes.c_int, ctypes.c_void_p,
                                    ctypes.c_int, ctypes.c_void_p, ctypes.c_void_p, ctypes.c_void_p]

        self.ECDSA_verify = self._lib.ECDSA_verify
        self.ECDSA_verify.restype = ctypes.c_int
        self.ECDSA_verify.argtypes = [ctypes.c_int, ctypes.c_void_p,
                                      ctypes.c_int, ctypes.c_void_p, ctypes.c_int, ctypes.c_void_p]

        self.EVP_MD_CTX_create = self._lib.EVP_MD_CTX_create
        self.EVP_MD_CTX_create.restype = ctypes.c_void_p
        self.EVP_MD_CTX_create.argtypes = []

        self.EVP_MD_CTX_init = self._lib.EVP_MD_CTX_init
        self.EVP_MD_CTX_init.restype = None
        self.EVP_MD_CTX_init.argtypes = [ctypes.c_void_p]

        self.EVP_MD_CTX_destroy = self._lib.EVP_MD_CTX_destroy
        self.EVP_MD_CTX_destroy.restype = None
        self.EVP_MD_CTX_destroy.argtypes = [ctypes.c_void_p]

        self.RAND_bytes = self._lib.RAND_bytes
        self.RAND_bytes.restype = ctypes.c_int
        self.RAND_bytes.argtypes = [ctypes.c_void_p, ctypes.c_int]


        self.EVP_sha256 = self._lib.EVP_sha256
        self.EVP_sha256.restype = ctypes.c_void_p
        self.EVP_sha256.argtypes = []

        self.i2o_ECPublicKey = self._lib.i2o_ECPublicKey
        self.i2o_ECPublicKey.restype = ctypes.c_void_p
        self.i2o_ECPublicKey.argtypes = [ctypes.c_void_p, ctypes.c_void_p]

        self.EVP_sha512 = self._lib.EVP_sha512
        self.EVP_sha512.restype = ctypes.c_void_p
        self.EVP_sha512.argtypes = []

        self.HMAC = self._lib.HMAC
        self.HMAC.restype = ctypes.c_void_p
        self.HMAC.argtypes = [ctypes.c_void_p, ctypes.c_void_p, ctypes.c_int,
                              ctypes.c_void_p, ctypes.c_int, ctypes.c_void_p, ctypes.c_void_p]

        try:
            self.PKCS5_PBKDF2_HMAC = self._lib.PKCS5_PBKDF2_HMAC
        except:
            # The above is not compatible with all versions of OSX.
            self.PKCS5_PBKDF2_HMAC = self._lib.PKCS5_PBKDF2_HMAC_SHA1
            
        self.PKCS5_PBKDF2_HMAC.restype = ctypes.c_int
        self.PKCS5_PBKDF2_HMAC.argtypes = [ctypes.c_void_p, ctypes.c_int,
                                           ctypes.c_void_p, ctypes.c_int,
                                           ctypes.c_int, ctypes.c_void_p,
                                           ctypes.c_int, ctypes.c_void_p]

        self._set_ciphers()
        self._set_curves()

    def _set_ciphers(self):
        self.cipher_algo = {
            'aes-128-cbc': CipherName('aes-128-cbc', self.EVP_aes_128_cbc, 16),
            'aes-256-cbc': CipherName('aes-256-cbc', self.EVP_aes_256_cbc, 16),
            'aes-128-cfb': CipherName('aes-128-cfb', self.EVP_aes_128_cfb128, 16),
            'aes-256-cfb': CipherName('aes-256-cfb', self.EVP_aes_256_cfb128, 16),
            'aes-128-ofb': CipherName('aes-128-ofb', self._lib.EVP_aes_128_ofb, 16),
            'aes-256-ofb': CipherName('aes-256-ofb', self._lib.EVP_aes_256_ofb, 16),
            #'aes-128-ctr': CipherName('aes-128-ctr', self._lib.EVP_aes_128_ctr, 16),
            #'aes-256-ctr': CipherName('aes-256-ctr', self._lib.EVP_aes_256_ctr, 16),
            'bf-cfb': CipherName('bf-cfb', self.EVP_bf_cfb64, 8),
            'bf-cbc': CipherName('bf-cbc', self.EVP_bf_cbc, 8),
            'rc4': CipherName('rc4', self.EVP_rc4, 128), # 128 is the initialisation size not block size
        }

    def _set_curves(self):
        self.curves = {
            'secp112r1': 704,
            'secp112r2': 705,
            'secp128r1': 706,
            'secp128r2': 707,
            'secp160k1': 708,
            'secp160r1': 709,
            'secp160r2': 710,
            'secp192k1': 711,
            'secp224k1': 712,
            'secp224r1': 713,
            'secp256k1': 714,
            'secp384r1': 715,
            'secp521r1': 716,
            'sect113r1': 717,
            'sect113r2': 718,
            'sect131r1': 719,
            'sect131r2': 720,
            'sect163k1': 721,
            'sect163r1': 722,
            'sect163r2': 723,
            'sect193r1': 724,
            'sect193r2': 725,
            'sect233k1': 726,
            'sect233r1': 727,
            'sect239k1': 728,
            'sect283k1': 729,
            'sect283r1': 730,
            'sect409k1': 731,
            'sect409r1': 732,
            'sect571k1': 733,
            'sect571r1': 734,
        }

    def BN_num_bytes(self, x):
        """
        returns the length of a BN (OpenSSl API)
        """
        return int((self.BN_num_bits(x) + 7) / 8)

    def get_cipher(self, name):
        """
        returns the OpenSSL cipher instance
        """
        if name not in self.cipher_algo:
            raise Exception("Unknown cipher")
        return self.cipher_algo[name]

    def get_curve(self, name):
        """
        returns the id of a elliptic curve
        """
        if name not in self.curves:
            raise Exception("Unknown curve")
        return self.curves[name]

    def get_curve_by_id(self, id):
        """
        returns the name of a elliptic curve with his id
        """
        res = None
        for i in self.curves:
            if self.curves[i] == id:
                res = i
                break
        if res is None:
            raise Exception("Unknown curve")
        return res

    def rand(self, size):
        """
        OpenSSL random function
        """
        buffer = self.malloc(0, size)
        # This pyelliptic library, by default, didn't check the return value of RAND_bytes. It is 
        # evidently possible that it returned an error and not-actually-random data. However, in
        # tests on various operating systems, while generating hundreds of gigabytes of random 
        # strings of various sizes I could not get an error to occur. Also Bitcoin doesn't check
        # the return value of RAND_bytes either. 
        # Fixed in Bitmessage version 0.4.2 (in source code on 2013-10-13)
        while self.RAND_bytes(buffer, size) != 1:
            import time
            time.sleep(1)
        return buffer.raw

    def malloc(self, data, size):
        """
        returns a create_string_buffer (ctypes)
        """
        buffer = None
        if data != 0:
            if sys.version_info.major == 3 and isinstance(data, type('')):
                data = data.encode()
            buffer = self.create_string_buffer(data, size)
        else:
            buffer = self.create_string_buffer(size)
        return buffer

try:
    OpenSSL = _OpenSSL('libcrypto.so')
except:
    try:
        OpenSSL = _OpenSSL('libeay32.dll')
    except:
        try:
            OpenSSL = _OpenSSL('libcrypto.dylib')
        except:
            try:
                # try homebrew installation
                OpenSSL = _OpenSSL('/usr/local/opt/openssl/lib/libcrypto.dylib')
            except:
                try:
                  # Load it from an Bitmessage.app on OSX
                  OpenSSL = _OpenSSL('./../Frameworks/libcrypto.dylib')
                except:
                  try:
                      from os import path
                      lib_path = path.join(sys._MEIPASS, "libeay32.dll")
                      OpenSSL = _OpenSSL(lib_path)
                  except:
                      if 'linux' in sys.platform or 'darwin' in sys.platform or 'freebsd' in sys.platform:
                          try:
                              from ctypes.util import find_library
                              OpenSSL = _OpenSSL(find_library('ssl'))
                          except Exception, err:
                              sys.stderr.write('(On Linux) Couldn\'t find and load the OpenSSL library. You must install it. If you believe that you already have it installed, this exception information might be of use:\n')
                              from ctypes.util import find_library
                              OpenSSL = _OpenSSL(find_library('ssl'))
                      else:
                          raise Exception("Couldn't find and load the OpenSSL library. You must install it.")

results.csv

113 z_s[i] = multiply_and_add_points( group, generator, ss[i], public_keys[i], cs[i] ) always cause segment fault ,it seems "generator" cause problems