0

I have seen many videos regarding the math behind the bitcoin elliptical curve but none of them show the public key generation. They are just defining few steps. I need the complete math behind the elliptical curve in which the generation of the public key is defined. Actually, I would like to see a visualization of the public key generation, could someone give me a link which explains the math behind elliptical curve?

What I understand that is k * n times G is equal to the public key but my question remains the same. If kn times G (where every point of G we get from point multiplication and point addition ) then at every multiplication of kG will result a different value then how can we combine them to get the public key?

1
  • 1
    I recommend reading SEC 1, the official document that defines the math of ECDSA. Then you might want to look at my Ruby ECDSA gem, which is a straight-forward implementation of the math. Feb 25 at 19:36
4

In ECDSA, the private key is a scalar 256-bit number. The public key is a elliptic curve point on the secp256k1 curve. Elliptic curves are abelian groups made up of the set of points resulting from repeatedly applying its group operation starting with its base point G. The group operation is the addition of two points. So, starting with the base point as the first element, the second element is G+G, the addition of G to itself. The third element is G+G+G, etc. To enumerate all points of the curve would take eons, because the group order is 115792089237316195423570985008687907852837564279074904382605163141518161494337.

Anyway, to find the public key Q corresponding to a private key k, you have to "walk" k generator steps from the base point. We write this elliptic curve scalar multiplication as

Q = G+G+…+G [k-times] = kG

Now secp256k1 is defined as

y² = x³+7 mod P

where P is

P = 2256 - 232 - 29 - 28 - 27 - 26 - 24 - 1.

In secp256k1, the base point is G(Gx,Gy), where

Gx = 55066263022277343669578718895168534326250603453777594175500187360389116729240

Gy = 32670510020758816978083085130507043184471273380659243275938904335757337482424

The addition of two points is defined as

P + Q = R

(xp, yp) + (xq, yq) = (xr, yr)

Which works out to be

xr = (yq - yp) / (xq - xp) - xp - xq

yr = ((yq - yp) / (xq - xp)) × (xp - xr) - yp

Note that the values are limited to [mod P]. So, taking your private key k, you now add G k times. There are some recommended shortcuts like first splitting k into a sum of factors of 2 (e.g. 37 = 1 + 22 + 25), because it will speed up your calculation immensely. Since the numbers involved are kinda hard to keep track of manually, I'd recommend using a software library.


Sources:

4
  • 1
    Mentioning that elliptic curves are not “continuous” is kind of a red-herring, in a truly mathematical sense. Elliptic curves are typically not expressed as functions, thus it doesn’t make sense to talk about continuity. Using the implicit function theorem, we actually can talk about continuity and even differentiability for most EC’s, though as you say, what’s more important is their group structure.
    – Prince M
    Feb 26 at 4:59
  • 2
    Thanks, I dropped that phrase! :)
    – Murch
    Feb 26 at 13:27
  • 1
    As is usual for you, the rest of the answer is great and I enjoyed reading. I only mentioned that bit since OP was specifically asking about the mathematics :)
    – Prince M
    Feb 26 at 21:19
  • 2
    Thank you for the praise. If you have other suggestions, please let them be heard, I'm not a mathematician and did feel a bit out of my element writing this one.
    – Murch
    Feb 26 at 21:28
2

Have you checked the "Keys, Addresses" chapter from "Mastering Bitcoin"?

You can read it for free here: https://github.com/bitcoinbook/bitcoinbook/blob/develop/ch04.asciidoc

The Generating a Public Key section has also a visual representation for the "multiplication of a point G by an integer k on an elliptic curve"

2
  • Thank you for you reply, what i understand that k * n times G is equals to public key but question is remain same if kn times G (where every point of G we get from point multiplication and point addition ) then at every multiplication of kG will result a different value then how can we combine them get the public key Feb 25 at 10:32
  • 1
    G - is a contant point, always the same accros all implementations; k - is a 256 bit number (private key); K = k * G; More about G here: bitcoin.stackexchange.com/questions/29904/…
    – Vlad Stan
    Feb 25 at 12:52
1

For me, the key video explaining the math for bitcoin elliptic curve secp256k1 was this: Bitcoin 101 - Elliptic Curve Cryptography - Part 4 - Generating the Public Key (in Python)

And if you want to check with a python script I extracted from the video, you can use this:

#!/usr/bin/python3

# Super simple Elliptic Curve Presentation. No imported libraries, wrappers, nothing.
# For educational purposes only.
# Below are the public specs for Bitcoin's curve - the secp256k1

# webs for checking
# https://www.bitaddress.org/bitaddress.org-v3.3.0-SHA256-dec17c07685e1870960903d8f58090475b25af946fe95a734f88408cef4aa194.html
# https://www.mobilefish.com/services/cryptocurrency/cryptocurrency.html


# datos para usar la curva secp256k1
Pcurve = 2 ** 256 - 2 ** 32 - 2 ** 9 - 2 ** 8 - 2 ** 7 - 2 ** 6 - 2 ** 4 - 1  # The proven prime
N = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141  # Number of points in the field
Acurve = 0
Bcurve = 7  # These two defines the elliptic curve. y^2 = x^3 + Acurve * x + Bcurve
Gx = 55066263022277343669578718895168534326250603453777594175500187360389116729240
Gy = 32670510020758816978083085130507043184471273380659243275938904335757337482424
GPoint = (Gx, Gy)  # This is our generator point. Trillions of dif ones possible

# Individual Transaction/Personal Information
privKey = 0x0C28FCA386C7A227600B2FE50B7CAE11EC86D3BF1FBE471BE89827E19D72AA1D


def modinv(a: int, n: int = Pcurve):  # MAXIMO COMUN DIVISOR: Extended Euclidean Algorithm/'division' in elliptic curves
    lm, hm = 1, 0
    resto = a % n
    high = n
    while resto > 1:
        ratio = high // resto
        nm = hm - lm * ratio
        new = high - resto * ratio
        lm, resto, hm, high = nm, new, lm, resto
    return lm % n


def ECadd(a, b):  # Not true addition, invented for EC. Could have been called anything.
    LamAdd = ((b[1] - a[1]) * modinv(b[0] - a[0], Pcurve)) % Pcurve
    x = (LamAdd * LamAdd - a[0] - b[0]) % Pcurve
    y = (LamAdd * (a[0] - x) - a[1]) % Pcurve
    return x, y


def ECdouble(a):  # This is called point doubling, also invented for EC.
    Lam = ((3 * a[0] * a[0] + Acurve) * modinv((2 * a[1]), Pcurve)) % Pcurve
    x = (Lam * Lam - 2 * a[0]) % Pcurve
    y = (Lam * (a[0] - x) - a[1]) % Pcurve
    return x, y


def EccMultiply(gen_point: tuple, scalar_hex: int):  # Double & add. Not true multiplication
    if scalar_hex == 0 or scalar_hex >= N:
        raise Exception("Invalid Scalar/Private Key")
    ScalarBin = str(bin(scalar_hex))[2:]  # string binario sin el comienzo 0b
    Q = gen_point  # esto es una tupla de dos  integer del punto de generacion de la curva
    for i in range(1, len(ScalarBin)):
        Q = ECdouble(Q)
        if ScalarBin[i] == "1":
            Q = ECadd(Q, gen_point)  #
    return Q


print("******* Public Key Generation *********")
print()
PublicKey = EccMultiply(GPoint, privKey)
print("the private key:")
print(privKey)
print()
print("the uncompressed public key (not address):")
print(PublicKey)
print()
x = hex(PublicKey[0])[2:].upper()
y = hex(PublicKey[1])[2:].upper()
print(f"The x: {x}")
print(f"The y: {y}")
print()
print("the uncompressed public key (HEX):")
pub_uncomp = f"04{hex(PublicKey[0])[2:].upper()}{hex(PublicKey[1])[2:].upper()}"
print(pub_uncomp)
print()
print("the official Public Key - compressed:")

if PublicKey[1] % 2 == 1:  # If the Y value for the Public Key is odd.
    print("03" + str(hex(PublicKey[0])[2:]).zfill(64).upper())
else:  # Or else, if the Y value is even.
    print("02" + str(hex(PublicKey[0])[2:]).zfill(64).upper())

Lastly you can see how to get the whole process, including WIF format and public addresses, check this.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.