Bitcoin Forum
December 03, 2016, 02:45:00 AM *
News: To be able to use the next phase of the beta forum software, please ensure that your email address is correct/functional.
 
   Home   Help Search Donate Login Register  
Pages: [1]
  Print  
Author Topic: ECDSA in python  (Read 5960 times)
etotheipi
Legendary
*
expert
Offline Offline

Activity: 1428


Core Armory Developer


View Profile WWW
July 12, 2011, 03:12:57 PM
 #1

As I work on developing my python backend for a BTC client, and finding it difficult to find a decent ECDSA implementation in python that would be sufficient for my purposes.  I have looked at the following:

M2Crypto -- looks like it's the best implementation in general, but I can't get the binary strings of the keys and signatures out of it.  I can only save them to PEM files. 
python-nss -- doesn't look to be cross-platform
pycrypto -- doesn't have ECDSA
python-ecdsa(*) -- temporary winner! -- https://github.com/warner/python-ecdsa

There's a lot of good info on cryptography packages, here:  http://mikeivanov.com/pc/python-crypto.pdf

M2Crypto would be my first choice, but  as far as I can tell, there's no way to get the binary keys directly from the library.  You can generate a key, generate signatures, and save things to PEM files, but no access to the keys themselves.  I am not fond of writing the keys to HDD and then reverse-engineering the PEM file format to get the key out.  Maybe if you could write it to a RAM file... but still seems like a hack.  (maybe someone has experience with this?)

python-ecdsa seems to be the best choice, as it doesn't appear to have any limitations, or any non-standard dependencies beyond it's own files, and should work on any platform.  It looks slow, but I'm not convinced that's a problem unless you're going to verify the entire block-chain.

Anyone know of any other python library, or technique for getting python to do the DSA signing/verification needed for Bitcoin? 

Founder and CEO of Armory Technologies, Inc.
Armory Bitcoin Wallet: Bringing cold storage to the average user!
Only use Armory software signed by the Armory Offline Signing Key (0x98832223)

Please donate to the Armory project by clicking here!    (or donate directly via 1QBDLYTDFHHZAABYSKGKPWKLSXZWCCJQBX -- yes, it's a real address!)
1480733100
Hero Member
*
Offline Offline

Posts: 1480733100

View Profile Personal Message (Offline)

Ignore
1480733100
Reply with quote  #2

1480733100
Report to moderator
1480733100
Hero Member
*
Offline Offline

Posts: 1480733100

View Profile Personal Message (Offline)

Ignore
1480733100
Reply with quote  #2

1480733100
Report to moderator
The forum strives to allow free discussion of any ideas. All policies are built around this principle. This doesn't mean you can post garbage, though: posts should actually contain ideas, and these ideas should be argued reasonably.
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
Ukigo
Hero Member
*****
Offline Offline

Activity: 924


View Profile
July 12, 2011, 03:46:36 PM
 #2

http://forum.bitcoin.org/index.php?topic=23241.0

Learn some russian or talk to Lis or read the code  Smiley

Also :
http://forum.bitcoin.org/index.php?topic=27179.0

add. search through the forum.
Cheers.

"...Enemies are everywhere ! Angka is all rage ! Be a good soldiers, blow everything... " <-- Pol Pot (C)
etotheipi
Legendary
*
expert
Offline Offline

Activity: 1428


Core Armory Developer


View Profile WWW
July 12, 2011, 04:31:32 PM
 #3

Wow, that is exactly what I was looking for!  Everything you need in a single, dependency-less python file!  I will surely donate to Lis!

P.S. - I did a search for "python ecdsa" in the forum search bar.  I only got 3 hits (probably 4 now, with this post).  I guess I needed to dig a little deeper.

-Eto

Founder and CEO of Armory Technologies, Inc.
Armory Bitcoin Wallet: Bringing cold storage to the average user!
Only use Armory software signed by the Armory Offline Signing Key (0x98832223)

Please donate to the Armory project by clicking here!    (or donate directly via 1QBDLYTDFHHZAABYSKGKPWKLSXZWCCJQBX -- yes, it's a real address!)
Ukigo
Hero Member
*****
Offline Offline

Activity: 924


View Profile
July 12, 2011, 05:10:35 PM
 #4

Search for Spesmilo, maybe there u will find some more useful stuff.

"...Enemies are everywhere ! Angka is all rage ! Be a good soldiers, blow everything... " <-- Pol Pot (C)
etotheipi
Legendary
*
expert
Offline Offline

Activity: 1428


Core Armory Developer


View Profile WWW
July 13, 2011, 12:38:02 AM
 #5

Okay, so the ECDSA library by Lis is fantastic, except I'm missing one critical piece of the puzzle -- I cannot for my life figure out how signatures are encoded.  A signature consists of two integers, (r,s), DER-encoded.  I'm digging through the very-dry DER encoding document, and I can't figure it out.  Most people use an SSL library for DER encoding/decoding, but I am trying not to have such dependencies in my client.

Is anyone familiar enough with the DER encoding to know how to break apart a binary signature into the two integers r and s?


Founder and CEO of Armory Technologies, Inc.
Armory Bitcoin Wallet: Bringing cold storage to the average user!
Only use Armory software signed by the Armory Offline Signing Key (0x98832223)

Please donate to the Armory project by clicking here!    (or donate directly via 1QBDLYTDFHHZAABYSKGKPWKLSXZWCCJQBX -- yes, it's a real address!)
etotheipi
Legendary
*
expert
Offline Offline

Activity: 1428


Core Armory Developer


View Profile WWW
July 13, 2011, 01:44:44 PM
 #6

Update:  After enough hex-diving and specification documents, I figured out how they are encoded.  I'm sure it would be irresponsible to blindly decode a DER chunk without checking byte codes/flags, but I imagine this will never change in Bitcoin, so I am foregoing a proper DER library.

Byte Listing:
--------------
1:  \x30
2:  1-byte length of DER-encoded (r,s) pair (assume 68)

3:  \x02
4:  1-byte length of r-value  (assume 32)
5-36:  integer value of r

37:  \x02
38:  1-byte length of s-value (assume 32)
39-70: integer value of s

71:  \x01
--------------

The values of r and s aren't always 32 bits so you still need to read all the length bytes.  The \x30 and \x02 bytes are bit strings of flags related to DER encoding scheme.

Founder and CEO of Armory Technologies, Inc.
Armory Bitcoin Wallet: Bringing cold storage to the average user!
Only use Armory software signed by the Armory Offline Signing Key (0x98832223)

Please donate to the Armory project by clicking here!    (or donate directly via 1QBDLYTDFHHZAABYSKGKPWKLSXZWCCJQBX -- yes, it's a real address!)
titeuf_87
Member
**
Offline Offline

Activity: 112


View Profile
July 13, 2011, 04:11:47 PM
 #7

This thread contains some sample code for M2Crypto and in a later post a code sample about how DER encoding works.

Hope this helps!

15kfBM3TQ4PGzL7cKncU3su2pH7ZJmiLtr
Joric
Member
**
Offline Offline

Activity: 67


View Profile
July 13, 2011, 10:04:11 PM
 #8

I've spend some time to get i2d_ECPrivateKey/i2o_ECPublicKey exports working (see https://github.com/joric/pywallet)
Relevant code (it uses only ctypes):
Code:
# Had to import i2d_ECPrivateKey/i2o_ECPublicKey from dynamic libs.
# Looks like PyCrypto/M2Crypto/pyOpenSSL modules do not support them.

dlls = list()
if 'win' in sys.platform:
    for d in ('libeay32.dll', 'libssl32.dll', 'ssleay32.dll'):
        try:
            dlls.append( cdll.LoadLibrary(d) )
        except:
            pass
else:
    dlls.append( cdll.LoadLibrary('libssl.so') )
           
class BIGNUM_Struct (Structure):
    _fields_ = [("d",c_void_p),("top",c_int),("dmax",c_int),("neg",c_int),("flags",c_int)]
               
class BN_CTX_Struct (Structure):
    _fields_ = [ ("_", c_byte) ]

BIGNUM = POINTER( BIGNUM_Struct )
BN_CTX = POINTER( BN_CTX_Struct )

def load_func( name, args, returns = c_int):
    d = sys.modules[ __name__ ].__dict__
    f = None
   
    for dll in dlls:
        try:
            f = getattr(dll, name)
            f.argtypes = args
            f.restype  = returns
            d[ name ] = f
            return
        except:
            pass
    raise ImportError('Unable to load required functions from SSL dlls')
   
load_func( 'BN_new', [], BIGNUM )
load_func( 'BN_CTX_new', [], BN_CTX )
load_func( 'BN_CTX_free', [BN_CTX], None   )
load_func( 'BN_num_bits', [BIGNUM], c_int )
load_func( 'BN_bn2bin',  [BIGNUM, c_char_p] )
load_func( 'BN_bin2bn',  [c_char_p, c_int, BIGNUM], BIGNUM )
load_func( 'EC_KEY_new_by_curve_name', [c_int], c_void_p )
load_func( 'EC_KEY_get0_group', [c_void_p], c_void_p)
load_func( 'EC_KEY_get0_private_key', [c_void_p], BIGNUM)
load_func( 'EC_POINT_new', [c_void_p], c_void_p)
load_func( 'EC_POINT_free', [c_void_p])
load_func( 'EC_POINT_mul', [c_void_p, c_void_p, BIGNUM, c_void_p, BIGNUM, BN_CTX], c_int)
load_func( 'EC_KEY_set_private_key', [c_void_p, BIGNUM], c_void_p)
load_func( 'EC_KEY_set_public_key', [c_void_p, c_void_p], c_void_p)
load_func( 'i2d_ECPrivateKey', [ c_void_p, POINTER(POINTER(c_char))], c_int )
load_func( 'i2o_ECPublicKey', [ c_void_p, POINTER(POINTER(c_char))], c_int )

def BN_num_bytes(a):
    return ((BN_num_bits(a)+7)/8)

NID_secp256k1 = 714

pkey = 0

def EC_KEY_regenerate_key(eckey, priv_key):
group = EC_KEY_get0_group(eckey)
ctx = BN_CTX_new()
pub_key = EC_POINT_new(group)
EC_POINT_mul(group, pub_key, priv_key, None, None, ctx)
EC_KEY_set_private_key(eckey, priv_key)
EC_KEY_set_public_key(eckey, pub_key)
EC_POINT_free(pub_key)
BN_CTX_free(ctx)

def GetSecret(pkey):
bn = EC_KEY_get0_private_key(pkey)
nSize = BN_num_bytes(bn)
b = create_string_buffer(nSize)
BN_bn2bin(bn, b)
return b.raw

def GetPrivKey(pkey):
nSize = i2d_ECPrivateKey(pkey, None)
p = create_string_buffer(nSize)
  i2d_ECPrivateKey(pkey, byref(cast(p, POINTER(c_char))))
return p.raw

def GetPubKey(pkey):
nSize = i2o_ECPublicKey(pkey, None)
p = create_string_buffer(nSize)
i2o_ECPublicKey(pkey, byref(cast(p, POINTER(c_char))))
return p.raw

def Hash(data):
s1 = hashlib.sha256()
s1.update(data)
h1 = s1.digest()
s2 = hashlib.sha256()
s2.update(h1)
h2 = s2.digest()
return h2

def EncodeBase58Check(vchIn):
hash = Hash(vchIn)
return b58encode(vchIn + hash[0:4])

def DecodeBase58Check(psz):
vchRet = b58decode(psz, None)
key = vchRet[0:-4]
csum = vchRet[-4:]
hash = Hash(key)
cs32 = hash[0:4]
if cs32 != csum:
return None
else:
return key

def SecretToASecret(privkey):
vchSecret = privkey[9:9+32]
# add 1-byte version number
vchIn = "\x80" + vchSecret
return EncodeBase58Check(vchIn)

def ASecretToSecret(key):
vch = DecodeBase58Check(key)
if vch:
return vch[1:]
else:
return False

def importprivkey(db, key):
vchSecret = ASecretToSecret(key)

if not vchSecret:
return False

pkey = EC_KEY_new_by_curve_name(NID_secp256k1)
bn = BN_bin2bn(vchSecret, 32, BN_new())
EC_KEY_regenerate_key(pkey, bn)

secret = GetSecret(pkey)
private_key = GetPrivKey(pkey)
public_key = GetPubKey(pkey)
addr = public_key_to_bc_address(public_key)

print "Address: %s" % addr
print "Privkey: %s" % SecretToASecret(private_key)

update_wallet(db, 'key', { 'public_key' : public_key, 'private_key' : private_key })
update_wallet(db, 'name', { 'hash' : addr, 'name' : '' })

return True

1JoricCBkW8C5m7QUZMwoRz9rBCM6ZSy96
TierNolan
Legendary
*
Offline Offline

Activity: 1036


View Profile
July 13, 2011, 10:25:59 PM
 #9

Update:  After enough hex-diving and specification documents, I figured out how they are encoded.  I'm sure it would be irresponsible to blindly decode a DER chunk without checking byte codes/flags, but I imagine this will never change in Bitcoin, so I am foregoing a proper DER library.

Byte Listing:
--------------
1:  \x30
2:  1-byte length of DER-encoded (r,s) pair (assume 68)

3:  \x02
4:  1-byte length of r-value  (assume 32)
5-36:  integer value of r

37:  \x02
38:  1-byte length of s-value (assume 32)
39-70: integer value of s

71:  \x01
--------------

The values of r and s aren't always 32 bits so you still need to read all the length bytes.  The \x30 and \x02 bytes are bit strings of flags related to DER encoding scheme.

R and S are 33 bytes if it would cause a negative number.

02_20_8000.....

is a 32 byte integer with the MSB = 1.  This is negative, so they change it to

02_21_008000.....

This is a 33 byte integer, but with leading zeros, so it is considered positive.

1LxbG5cKXzTwZg9mjL3gaRE835uNQEteWF
Joric
Member
**
Offline Offline

Activity: 67


View Profile
July 24, 2011, 03:11:16 AM
 #10

Made some investigations about 279-byte DER key.

There is an embedded DER encoder/decoder in the python-ecdsa library (https://github.com/warner/python-ecdsa).

Example i2d_ECPrivateKey output (from http://bitcointools.appspot.com):

Address: 1AJ3vE2NNYW2Jzv3fLwyjKF1LYbZ65Ez64
Private key: 5JMhGPWc3pkdgPd9jqVZkRtEp3QB3Ze8ihv62TmmvzABmkNzBHw

i2d_ECPrivateKey:
Code:
30820113020101042047510706d76bc74a5d57bdcffc68c9bbbc2d496bef87c9
1de7f616129ac62b5fa081a53081a2020101302c06072a8648ce3d0101022100
fffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f3006040100040107044104
79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f817984
83ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b802
2100fffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141020101a
144034200046211d9b7836892c8eef49c4d0cad7797815eff95108e1d30745c0
3577596c9c00d2cb1ab27c7f95c28771278f89b7ff40da49fe9b4ee834a3f6a88
324db837d8

Javascript ASN1 decoder (http://lapo.it/asn1js/) decodes it to:

Code:
SEQUENCE(4 elem)
    INTEGER1
    OCTET STRING(32 byte) A0DC65FFCA799873CBEA0AC274015B9526505DAA..
    [0]    (1)
        SEQUENCE(6 elem)
            INTEGER 1
            SEQUENCE(2 elem)
                OBJECT IDENTIFIER 1.2.840.10045.1.1
                INTEGER (256 bit)
        SEQUENCE(2 elem)
            OCTET STRING(1 byte) 00
            OCTET STRING(1 byte) 07
        OCTET STRING(65 byte) 0479BE667EF9DCBBAC55A06295CE870B07029BFC..
        INTEGER(256 bit)
        INTEGER1
    [1]    (1)
    BIT STRING(520 bit)

I wrote python-ecdsa SigningKey method that generates the same output as i2d_ECPrivateKey (279 bytes):

Code:
def i2d(self):

    _p = self.curve.curve.p()
    _r = self.curve.generator.order() # self.curve.order
    _Gx = self.curve.generator.x()
    _Gy = self.curve.generator.y()

    oid2 = (1, 2, 840, 10045, 1, 1) # ecdsa-with-SHA1 + id-prime-Field
    encoded_oid2 = der.encode_oid(*oid2)

    encoded_gxgy = "\x04" + ("%64x" % _Gx).decode('hex') + ("%64x" % _Gy).decode('hex')

    param_sequence = der.encode_sequence (
        der.encode_integer(1),
            der.encode_sequence (
            encoded_oid2,
            der.encode_integer(_p),
        ),
        der.encode_sequence (
            der.encode_octet_string("\x00"),
            der.encode_octet_string("\x07"),
        ),
        der.encode_octet_string(encoded_gxgy),
        der.encode_integer(_r),
        der.encode_integer(1),
    );

    encoded_vk = "\x00\x04" + self.get_verifying_key().to_string()

    return der.encode_sequence (
        der.encode_integer(1),
        der.encode_octet_string(self.to_string()),
        der.encode_constructed(0, param_sequence),
        der.encode_constructed(1, der.encode_bitstring(encoded_vk)),
    )

Also see https://github.com/joric/brutus (ecdsa_pure.py and ecdsa_ssl.py, I've updated them recently).

1JoricCBkW8C5m7QUZMwoRz9rBCM6ZSy96
Pages: [1]
  Print  
 
Jump to:  

Sponsored by , a Bitcoin-accepting VPN.
Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!