pythonpublic-key-encryptionelliptic-curveecdsa

Reputation: 11523

How to get an elliptic curve public key from a private key

So, I need to get a public key from a corresponding 256 bit number using ECC spec256k1.

So, lets say I get a private key using a sha256 from any passphrase, like this:

>>> import hashlib
>>> private_key = hashlib.sha3_256(b"Led Zeppelin - No Quarter").hexdigest()
>>> private_key
'c0b279f18074de51d075b152c8ce78b7bddb284e8cfde19896162abec0a0acce'

How do I get a public key from that private key? I need to print the public key as a string.

Upvotes: 9

Answers (4)

Roman Starkov

Reputation: 61382

Here's how it can be done in .NET, because this question comes up in generic searches:

byte[] privateKey = ...;
var ecp = new ECParameters { Curve = ECCurve.<your curve>, D = privateKey };
var ecdsa = ECDsa.Create(ecp);
var publicKey = ecdsa.ExportParameters(false).Q;

The point is that ECDsa accepts a partially populated ECParameters struct, where Q (public key) is left uninitialised. It will generate the missing public key which can then be extracted with ExportParameters.

Upvotes: 0

Arty

Reputation: 16737

Other two answers using module fastecdsa are correct, but you may want to implement elliptic curve arithmetics from scratch without any external non-standard modules, for educational purposes and just for fun of learning.

So did I, below I present my code that implements Elliptic Curve Points Addition and Multiplication (read linked Wiki, it has all math described) from scratch, without using any non-standard modules. Mathematics of elliptic curves is quite simple and can be fully implemented in few dozens lines of code in Python.

Params of standard curve secp256k1 I've taken from BitCoin wiki page, also this curve params and other curves like secp256r1, secp384r1, secp521r1 are taken from public SECG pdf. These params give coordinate and params of so called base point.

Afterwards public key is just base point (standard curve point) multiplied by private key (integer). While private key is simple big integer, public key is elliptic curve point represented by two integer coordinates (X, Y) and standard non-modifiable params (A, B, P, Q).

In my code you can uncomment #import gmpy2 line if you want for some reason use external gmpy2 library and have installed it through python -m pip install gmpy2. This library gives around 2x speedup of all curves mathematics. But you don't need to uncomment this line, usage of this library is non-compulsory, my code works with just standard Python modules pretty fast.

Code below as an example computes private key presented in your question, prints it, computes public key and prints X and Y coordinates of public key. As you can see obtained public key is identical to public key printed in other answer, obtained through fastecdsa.

Console output of my program (printed private and public keys) can be seen after the code.

Try it online!

class ECPoint:
    gmpy2 = None
    #import gmpy2
    import random
    
    class InvError(Exception):
        def __init__(self, *pargs):
            self.value = pargs
    
    @classmethod
    def Int(cls, x):
        return int(x) if cls.gmpy2 is None else cls.gmpy2.mpz(x)
    
    @classmethod
    def std_point(cls, t):
        if t == 'secp256k1':
            # https://en.bitcoin.it/wiki/Secp256k1
            # https://www.secg.org/sec2-v2.pdf
            p = 0xFFFFFFFF_FFFFFFFF_FFFFFFFF_FFFFFFFF_FFFFFFFF_FFFFFFFF_FFFFFFFE_FFFFFC2F
            a = 0
            b = 7
            x = 0x79BE667E_F9DCBBAC_55A06295_CE870B07_029BFCDB_2DCE28D9_59F2815B_16F81798
            y = 0x483ADA77_26A3C465_5DA4FBFC_0E1108A8_FD17B448_A6855419_9C47D08F_FB10D4B8
            q = 0xFFFFFFFF_FFFFFFFF_FFFFFFFF_FFFFFFFE_BAAEDCE6_AF48A03B_BFD25E8C_D0364141
        elif t == 'secp256r1':
            # https://www.secg.org/sec2-v2.pdf
            p = 0xFFFFFFFF_00000001_00000000_00000000_00000000_FFFFFFFF_FFFFFFFF_FFFFFFFF
            a = 0xFFFFFFFF_00000001_00000000_00000000_00000000_FFFFFFFF_FFFFFFFF_FFFFFFFC
            b = 0x5AC635D8_AA3A93E7_B3EBBD55_769886BC_651D06B0_CC53B0F6_3BCE3C3E_27D2604B
            x = 0x6B17D1F2_E12C4247_F8BCE6E5_63A440F2_77037D81_2DEB33A0_F4A13945_D898C296
            y = 0x4FE342E2_FE1A7F9B_8EE7EB4A_7C0F9E16_2BCE3357_6B315ECE_CBB64068_37BF51F5
            q = 0xFFFFFFFF_00000000_FFFFFFFF_FFFFFFFF_BCE6FAAD_A7179E84_F3B9CAC2_FC632551
        elif t == 'secp384r1':
            # https://www.secg.org/sec2-v2.pdf
            p = 0xFFFFFFFF_FFFFFFFF_FFFFFFFF_FFFFFFFF_FFFFFFFF_FFFFFFFF_FFFFFFFF_FFFFFFFE_FFFFFFFF_00000000_00000000_FFFFFFFF
            a = 0xFFFFFFFF_FFFFFFFF_FFFFFFFF_FFFFFFFF_FFFFFFFF_FFFFFFFF_FFFFFFFF_FFFFFFFE_FFFFFFFF_00000000_00000000_FFFFFFFC
            b = 0xB3312FA7_E23EE7E4_988E056B_E3F82D19_181D9C6E_FE814112_0314088F_5013875A_C656398D_8A2ED19D_2A85C8ED_D3EC2AEF
            x = 0xAA87CA22_BE8B0537_8EB1C71E_F320AD74_6E1D3B62_8BA79B98_59F741E0_82542A38_5502F25D_BF55296C_3A545E38_72760AB7
            y = 0x3617DE4A_96262C6F_5D9E98BF_9292DC29_F8F41DBD_289A147C_E9DA3113_B5F0B8C0_0A60B1CE_1D7E819D_7A431D7C_90EA0E5F
            q = 0xFFFFFFFF_FFFFFFFF_FFFFFFFF_FFFFFFFF_FFFFFFFF_FFFFFFFF_C7634D81_F4372DDF_581A0DB2_48B0A77A_ECEC196A_CCC52973
        elif t == 'secp521r1':
            # https://www.secg.org/sec2-v2.pdf
            p = 2 ** 521 - 1
            a = 2 ** 521 - 4
            b = 0x0051_953EB961_8E1C9A1F_929A21A0_B68540EE_A2DA725B_99B315F3_B8B48991_8EF109E1_56193951_EC7E937B_1652C0BD_3BB1BF07_3573DF88_3D2C34F1_EF451FD4_6B503F00
            x = 0x00C6_858E06B7_0404E9CD_9E3ECB66_2395B442_9C648139_053FB521_F828AF60_6B4D3DBA_A14B5E77_EFE75928_FE1DC127_A2FFA8DE_3348B3C1_856A429B_F97E7E31_C2E5BD66
            y = 0x0118_39296A78_9A3BC004_5C8A5FB4_2C7D1BD9_98F54449_579B4468_17AFBD17_273E662C_97EE7299_5EF42640_C550B901_3FAD0761_353C7086_A272C240_88BE9476_9FD16650
            q = 0x01FF_FFFFFFFF_FFFFFFFF_FFFFFFFF_FFFFFFFF_FFFFFFFF_FFFFFFFF_FFFFFFFF_FFFFFFFA_51868783_BF2F966B_7FCC0148_F709A5D0_3BB5C9B8_899C47AE_BB6FB71E_91386409
        else:
            assert False
        return ECPoint(a, b, p, x, y, q = q)
    
    def __init__(self, A, B, N, x, y, *, q = 0, prepare = True):
        if prepare:
            N = self.Int(N)
            A, B, x, y, q = [self.Int(e) % N for e in [A, B, x, y, q]]
            assert (4 * A ** 3 + 27 * B ** 2) % N != 0
            assert (y ** 2 - x ** 3 - A * x - B) % N == 0, (hex(N), hex((y ** 2 - x ** 3 - A * x) % N))
            assert N % 4 == 3
            assert y == pow(x ** 3 + A * x + B, (N + 1) // 4, N)
        self.A, self.B, self.N, self.x, self.y, self.q = A, B, N, x, y, q
    
    def __add__(self, other):
        A, B, N = self.A, self.B, self.N
        Px, Py, Qx, Qy = self.x, self.y, other.x, other.y
        if Px == Qx and Py == Qy:
            s = ((Px * Px * 3 + A) * self.inv(Py * 2, N)) % N
        else:
            s = ((Py - Qy) * self.inv(Px - Qx, N)) % N
        x = (s * s - Px - Qx) % N
        y = (s * (Px - x) - Py) % N
        return ECPoint(A, B, N, x, y, prepare = False)
    
    def __rmul__(self, other):
        assert other >= 1
        if other == 1:
            return self
        other = self.Int(other - 1)
        r = self
        while True:
            if other & 1:
                r = r + self
                if other == 1:
                    return r
            other >>= 1
            self = self + self
    
    @classmethod
    def inv(cls, a, n):
        a %= n
        if cls.gmpy2 is None:
            try:
                return pow(a, -1, n)
            except ValueError:
                import math
                raise cls.InvError(math.gcd(a, n), a, n)
        else:
            g, s, t = cls.gmpy2.gcdext(a, n)
            if g != 1:
                raise cls.InvError(g, a, n)
            return s % n

    def __repr__(self):
        return str(dict(x = self.x, y = self.y, A = self.A, B = self.B, N = self.N, q = self.q))

    def __eq__(self, other):
        for i, (a, b) in enumerate([(self.x, other.x), (self.y, other.y), (self.A, other.A),
                (self.B, other.B), (self.N, other.N), (self.q, other.q)]):
            if a != b:
                return False
        return True
        
def get_pub(priv_key):
    bp = ECPoint.std_point('secp256k1')
    pub = priv_key * bp
    return pub.x, pub.y

def main():
    import hashlib
    priv_key = int(hashlib.sha3_256(b"Led Zeppelin - No Quarter").hexdigest(), 16)
    print('priv key :', hex(priv_key))
    pubx, puby = get_pub(priv_key)
    print('pub key x:', hex(pubx))
    print('pub key y:', hex(puby))

main()

Output:

priv key : 0xc0b279f18074de51d075b152c8ce78b7bddb284e8cfde19896162abec0a0acce
pub key x: 0xbaa41af234cb2744ddaa039929c6ff21f0d5ab5ebce045d4a7513236f9bd429a
pub key y: 0x30252bd111b42e5195355f7fbcb5d6586ae76facbb4b7118fa96a2e99b40f716

Upvotes: 3

MrD

Reputation: 545

The currently accepted answer described how to generate a fresh pair and does not address the question.

Generate a non-random private key

Any random 256-bit integer is suitable as private key for this curve so generating a private key is extremely fast compared to, e.g., RSA.

import hashlib
private_key = hashlib.sha3_256(b"Led Zeppelin - No Quarter").hexdigest()
print(private_key)

c0b279f18074de51d075b152c8ce78b7bddb284e8cfde19896162abec0a0acce

This is the same as in your question.

Derive public key

Public keys in elliptic curve cryptography are points on the curve - a pair of integer coordinates {X,Y}, laying on the curve. We can compute it like

import fastecdsa.keys
import fastecdsa.curve

curve = fastecdsa.curve.secp256k1
private_key_raw = int(private_key, base=16)
pubkey = fastecdsa.keys.get_public_key(private_key_raw, curve)
print(pubkey)

X: 0xbaa41af234cb2744ddaa039929c6ff21f0d5ab5ebce045d4a7513236f9bd429a
Y: 0x30252bd111b42e5195355f7fbcb5d6586ae76facbb4b7118fa96a2e99b40f716
(On curve <secp256k1>)

Compressed form of the public key

It may be worthwhile to note that, due to their special properties, public EC points can also be "compressed" in SEC1 encoding to just one of the coordinates plus a parity (odd or even) bit. In other words, the public key of a 256-bit private be also expressed as an 257-bit integer rather than two coordinates:

import fastecdsa.encoding.sec1
compressed_pubkey = fastecdsa.encoding.sec1.SEC1Encoder().encode_public_key(pubkey)
print("0x" + compressed_pubkey.hex())

0x02baa41af234cb2744ddaa039929c6ff21f0d5ab5ebce045d4a7513236f9bd429a

which is the X coordinate above, prefixed with 0x02. The first byte will be either 0x02 (even Y) or 0x03 (odd Y).

As even/odd corresponds to pubkey.y % 2 in SEC1 encoding, you could even encode it yourself without the assistance of fastecdsa:

compressed_pubkey = pubkey.x + ((2 if pubkey.y % 2 == 0 else 3) << 256)
print(hex(compressed_pubkey))

0x2baa41af234cb2744ddaa039929c6ff21f0d5ab5ebce045d4a7513236f9bd429a

Generate PEM-encoded keys

Last but not least, we can generate PEM-encoded forms of your key pair which is what many applications working with public keys expect. Furthermore, it is an efficient method to store the keys on disk.

Public key

pubkey_pem = fastecdsa.keys.export_key(pubkey, curve)
print(pubkey_pem)

-----BEGIN PUBLIC KEY-----
MFYwEAYHKoZIzj0CAQYFK4EEAAoDQgAEuqQa8jTLJ0TdqgOZKcb/IfDVq1684EXU
p1EyNvm9QpowJSvREbQuUZU1X3+8tdZYaudvrLtLcRj6lqLpm0D3Fg==
-----END PUBLIC KEY-----

Private key

privkey_pem = fastecdsa.keys.export_key(private_key_raw, curve)
print(privkey_pem)

Upvotes: 3

Raphael

Reputation: 1001

pip install fastecdsa

from fastecdsa import keys, curve,ecdsa
priv_key, pub_key = keys.gen_keypair(curve.secp256k1) 

print(pub_key)

which yields

X: 0xcc228e1a4c8e187a0deeabcd6e43bc8f7b6bdd91b8f823912f2de188fba054e6
Y: 0x7995a9d3866a8fa11a9af933c76216a908995ec5cec6ed7d3056b787fa7d39d7

Supported Primitives

Curves over Prime Fields - Source

Name                      Class

P192 / secp192r1          fastecdsa.curve.P192  
P224 / secp224r1          fastecdsa.curve.P224  
P256 / secp256r1          fastecdsa.curve.P256  
P384 / secp384r1          fastecdsa.curve.P384  
P521 / secp521r1          fastecdsa.curve.P521 
secp192k1                 fastecdsa.curve.secp192k1     
secp224k1                 fastecdsa.curve.secp224k1     
secp256k1 (bitcoin curve) fastecdsa.curve.secp256k1     
brainpoolP160r1           fastecdsa.curve.brainpoolP160r1   
brainpoolP192r1           fastecdsa.curve.brainpoolP192r1   
brainpoolP224r1           fastecdsa.curve.brainpoolP224r1   
brainpoolP256r1           fastecdsa.curve.brainpoolP256r1   
brainpoolP320r1           fastecdsa.curve.brainpoolP320r1   
brainpoolP384r1           fastecdsa.curve.brainpoolP384r1
brainpoolP512r1           fastecdsa.curve.brainpoolP512r1

Upvotes: 6