¿Cómo se obtiene una clave pública de Bitcoin a partir de una clave privada?

Intentaré responder esto nuevamente de una manera diferente, usando números pequeños para que sea legible.

1. convierta la clave privada a representación binaria, de modo que el número decimal 105, que es 0x69 en hexadecimal, se convierta en 01101001.

2. calcular esta lista de puntos, duplicando repetidamente el punto generador G:

   1*G
   2*G = G+G
   4*G = 2*G + 2*G
   8*G = 4*G + 4*G
   16*G = 8*G + 8*G
   32*G = 16*G + 16*G
   64*G = 32*G + 32*G
   

3. escriba los bits de la clave privada al lado de esta lista de esta manera:

   privkey    pointlist
      1          1*G
      0          2*G
      0          4*G
      1          8*G
      0         16*G
      1         32*G
      1         64*G
   

4. ahora comience a agregar solo aquellos puntos que tienen un 1escrito junto a ellos.

       9*G = 1*G + 8*G
      41*G = (9+32)*G = 9*G + 32*G
     105*G = (41+64)*G = 41*G + 64*G
   

5. ahora ha calculado la clave pública para la clave privada 105 usando solo operaciones de duplicación de puntos y adición de puntos.

El valor real será:

(0xf219ea5d6b54701c1c14de5b557eb42a8d13f3abbcd08affcc2a5e6b049b8d63,
 0x4cb95957e83d40b0f73af4544cccf6b1f4b08d3c07b27fb8d8c2962a400766d1)

La clave pública estará entonces en uno de dos formatos:

• lleno, este es un número de 65 bytes, comenzando con un byte0x04
• comprimido, esta es una forma más corta, 33 bytes, comenzando con 0x02 o 0x03.

La clave pública completa es 0x04, seguida de 32 bytes de la coordenada x, seguida de 32 bytes de la coordenada y.

La clave pública comprimida es 0x02 o 0x03 dependiendo de si la coordenada y es un número par o impar, seguida de 32 bytes de la coordenada x.

Luego, algunas notas más sobre su pregunta:

• Algunos textos antiguos solían referirse a la multiplicación de puntos escalares, como exponenciación, es por eso que a veces la clave privada se refiere al exponente privado.

• los parámetros de la curva se eligieron aleatoriamente una vez. lo que significa que los diseñadores de la curva secp256k1 intentaron sin éxito transmitir que no existe una estructura específica para esta curva. Lo que significa que la NSA podría o no haber puesto una puerta trasera matemática en los parámetros de la curva.

• al usar esta curva y generar tu clave pública, -tienes- que elegir tu clave privada al azar, de manera que sea imposible que nadie la adivine.

• el generador Ges un punto específico de la curva elíptica, definido en la curva secp256k1 .

Aquí hay un script de Python autónomo que realiza la conversión. Puede verificar su trabajo comparándolo con ingresar su clave privada como el "Exponente secreto" en Brainwallet . Tomé el script de este hilo de Bitcointalk y eliminé cosas innecesarias (como el código para usar la clave pública para firmar un mensaje y verificar esa firma).

Convertir Python en instrucciones para un ser humano se deja como un ejercicio para el lector (aunque diría que en un escenario como este código de Python, con la documentación adecuada, está bien como instrucciones para un ser humano). Tenga en cuenta que es completamente posible calcular esto con lápiz y papel, pero podría llevar un tiempo y es probable que cometa un error debido a que tiene que lidiar con números tan enormes.

También tenga en cuenta que no hay operaciones individuales aquí que sean mucho más complicadas de lo que aprendería en la escuela primaria/primaria. Hay comparaciones básicas < > ==, aritmética + - *, división en la que te preocupas por el cociente /, el resto %o ambos divmod, y AND bit a bit ( &, que es bastante fácil si trabajas en hexadecimal; o se puede replicar con aritmética).

No creo que un niño de 5 años (que no sea un genio) pueda hacerlo (lo siento, la bruja malvada gana esta ronda), pero creo que un adulto promedio con suficiente paciencia podría aprender las matemáticas necesarias en muy poco tiempo (con el Secuencia de comandos de Python como ... bueno ... secuencia de comandos, a seguir). Sin embargo, calcular incluso una sola clave pública sin la ayuda de dispositivos informáticos electrónicos podría llevar mucho tiempo (aproximadamente: años).

#! /usr/bin/env python
# python 2.x

class CurveFp( object ):
  def __init__( self, p, a, b ):
    self.__p = p
    self.__a = a
    self.__b = b

  def p( self ):
    return self.__p

  def a( self ):
    return self.__a

  def b( self ):
    return self.__b

  def contains_point( self, x, y ):
    return ( y * y - ( x * x * x + self.__a * x + self.__b ) ) % self.__p == 0

class Point( object ):
  def __init__( self, curve, x, y, order = None ):
    self.__curve = curve
    self.__x = x
    self.__y = y
    self.__order = order
    if self.__curve: assert self.__curve.contains_point( x, y )
    if order: assert self * order == INFINITY

  def __add__( self, other ):
    if other == INFINITY: return self
    if self == INFINITY: return other
    assert self.__curve == other.__curve
    if self.__x == other.__x:
      if ( self.__y + other.__y ) % self.__curve.p() == 0:
        return INFINITY
      else:
        return self.double()

    p = self.__curve.p()
    l = ( ( other.__y - self.__y ) * \
          inverse_mod( other.__x - self.__x, p ) ) % p
    x3 = ( l * l - self.__x - other.__x ) % p
    y3 = ( l * ( self.__x - x3 ) - self.__y ) % p
    return Point( self.__curve, x3, y3 )

  def __mul__( self, other ):
    def leftmost_bit( x ):
      assert x > 0
      result = 1L
      while result <= x: result = 2 * result
      return result / 2

    e = other
    if self.__order: e = e % self.__order
    if e == 0: return INFINITY
    if self == INFINITY: return INFINITY
    assert e > 0
    e3 = 3 * e
    negative_self = Point( self.__curve, self.__x, -self.__y, self.__order )
    i = leftmost_bit( e3 ) / 2
    result = self
    while i > 1:
      result = result.double()
      if ( e3 & i ) != 0 and ( e & i ) == 0: result = result + self
      if ( e3 & i ) == 0 and ( e & i ) != 0: result = result + negative_self
      i = i / 2
    return result

  def __rmul__( self, other ):
    return self * other

  def __str__( self ):
    if self == INFINITY: return "infinity"
    return "(%d,%d)" % ( self.__x, self.__y )

  def double( self ):
    if self == INFINITY:
      return INFINITY

    p = self.__curve.p()
    a = self.__curve.a()
    l = ( ( 3 * self.__x * self.__x + a ) * \
          inverse_mod( 2 * self.__y, p ) ) % p
    x3 = ( l * l - 2 * self.__x ) % p
    y3 = ( l * ( self.__x - x3 ) - self.__y ) % p
    return Point( self.__curve, x3, y3 )

  def x( self ):
    return self.__x

  def y( self ):
    return self.__y

  def curve( self ):
    return self.__curve

  def order( self ):
    return self.__order

INFINITY = Point( None, None, None )

def inverse_mod( a, m ):
  if a < 0 or m <= a: a = a % m
  c, d = a, m
  uc, vc, ud, vd = 1, 0, 0, 1
  while c != 0:
    q, c, d = divmod( d, c ) + ( c, )
    uc, vc, ud, vd = ud - q*uc, vd - q*vc, uc, vc
  assert d == 1
  if ud > 0: return ud
  else: return ud + m

# secp256k1
_p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2FL
_r = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141L
_b = 0x0000000000000000000000000000000000000000000000000000000000000007L
_a = 0x0000000000000000000000000000000000000000000000000000000000000000L
_Gx = 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798L
_Gy = 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8L

class Public_key( object ):
  def __init__( self, generator, point ):
    self.curve = generator.curve()
    self.generator = generator
    self.point = point
    n = generator.order()
    if not n:
      raise RuntimeError, "Generator point must have order."
    if not n * point == INFINITY:
      raise RuntimeError, "Generator point order is bad."
    if point.x() < 0 or n <= point.x() or point.y() < 0 or n <= point.y():
      raise RuntimeError, "Generator point has x or y out of range."

curve_256 = CurveFp( _p, _a, _b )
generator_256 = Point( curve_256, _Gx, _Gy, _r )
g = generator_256

if __name__ == "__main__":
  print '======================================================================='
  ### set privkey
  # wiki
  #secret = 0xE9873D79C6D87DC0FB6A5778633389F4453213303DA61F20BD67FC233AA33262L
  # question
  secret = 0x18E14A7B6A307F426A94F8114701E7C8E774E7F9A47E2C2035DB29A206321725L

  ### print privkey
  print 'secret', hex(secret)
  ### generate pubkey
  pubkey = Public_key( g, g * secret )
  ### print pubkey
  print 'pubkey', hex(pubkey.point.x()), hex(pubkey.point.y())
  print '======================================================================='

Consulte también una versión aún más simplificada escrita en C#.

class CalcPub
{
    public static void Main()
    {
        var p = BigInteger.Parse("0FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F", NumberStyles.HexNumber);
        var b = (BigInteger)7;
        var a = BigInteger.Zero;
        var Gx = BigInteger.Parse("79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798", NumberStyles.HexNumber);
        var Gy = BigInteger.Parse("483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8", NumberStyles.HexNumber);

        CurveFp curve256 = new CurveFp(p, a, b);
        Point generator256 = new Point(curve256, Gx, Gy);

        var secret = BigInteger.Parse("18E14A7B6A307F426A94F8114701E7C8E774E7F9A47E2C2035DB29A206321725", NumberStyles.HexNumber);

        Console.WriteLine("secret {0}", secret.ToString("X"));
        var pubkeyPoint = generator256 * secret;
        Console.WriteLine("pubkey {0}{1}", pubkeyPoint.X.ToString("X"), pubkeyPoint.Y.ToString("X"));
    }
}
class Point
{
    public static readonly Point INFINITY = new Point(null, default(BigInteger), default(BigInteger));
    public CurveFp Curve { get; private set; }
    public BigInteger X { get; private set; }
    public BigInteger Y { get; private set; }

    public Point(CurveFp curve, BigInteger x, BigInteger y)
    {
        this.Curve = curve;
        this.X = x;
        this.Y = y;
    }
    public Point Double()
    {
        if (this == INFINITY)
            return INFINITY;

        BigInteger p = this.Curve.p;
        BigInteger a = this.Curve.a;
        BigInteger l = ((3 * this.X * this.X + a) * InverseMod(2 * this.Y, p)) % p;
        BigInteger x3 = (l * l - 2 * this.X) % p;
        BigInteger y3 = (l * (this.X - x3) - this.Y) % p;
        return new Point(this.Curve, x3, y3);
    }
    public override string ToString()
    {
        if (this == INFINITY)
            return "infinity";
        return string.Format("({0},{1})", this.X, this.Y);
    }
    public static Point operator +(Point left, Point right)
    {
        if (right == INFINITY)
            return left;
        if (left == INFINITY)
            return right;
        if (left.X == right.X)
        {
            if ((left.Y + right.Y) % left.Curve.p == 0)
                return INFINITY;
            else
                return left.Double();
        }

        var p = left.Curve.p;
        var l = ((right.Y - left.Y) * InverseMod(right.X - left.X, p)) % p;
        var x3 = (l * l - left.X - right.X) % p;
        var y3 = (l * (left.X - x3) - left.Y) % p;
        return new Point(left.Curve, x3, y3);
    }
    public static Point operator *(Point left, BigInteger right)
    {
        var e = right;
        if (e == 0 || left == INFINITY)
            return INFINITY;
        var e3 = 3 * e;
        var negativeLeft = new Point(left.Curve, left.X, -left.Y);
        var i = LeftmostBit(e3) / 2;
        var result = left;
        while (i > 1)
        {
            result = result.Double();
            if ((e3 & i) != 0 && (e & i) == 0)
                result += left;
            if ((e3 & i) == 0 && (e & i) != 0)
                result += negativeLeft;
            i /= 2;
        }
        return result;
    }

    private static BigInteger LeftmostBit(BigInteger x)
    {
        BigInteger result = 1;
        while (result <= x)
            result = 2 * result;
        return result / 2;
    }
    private static BigInteger InverseMod(BigInteger a, BigInteger m)
    {
        while (a < 0) a += m;
        if (a < 0 || m <= a)
            a = a % m;
        BigInteger c = a;
        BigInteger d = m;

        BigInteger uc = 1;
        BigInteger vc = 0;
        BigInteger ud = 0;
        BigInteger vd = 1;

        while (c != 0)
        {
            BigInteger r;
            //q, c, d = divmod( d, c ) + ( c, );
            var q = BigInteger.DivRem(d, c, out r);
            d = c;
            c = r;

            //uc, vc, ud, vd = ud - q*uc, vd - q*vc, uc, vc;
            var uct = uc;
            var vct = vc;
            var udt = ud;
            var vdt = vd;
            uc = udt - q * uct;
            vc = vdt - q * vct;
            ud = uct;
            vd = vct;
        }
        if (ud > 0) return ud;
        else return ud + m;
    }
}
class CurveFp
{
    public BigInteger p { get; private set; }
    public BigInteger a { get; private set; }
    public BigInteger b { get; private set; }
    public CurveFp(BigInteger p, BigInteger a, BigInteger b)
    {
        this.p = p;
        this.a = a;
        this.b = b;
    }
}

Tomé la respuesta de Tim S y eliminé más cosas hasta que me quedó en una sola página:

https://gist.github.com/dooglus/3b1fcbc2449063a1c3f7f1003ca26447

#! /usr/bin/env python

class Point(object):
    def __init__(self, _x, _y, _order = None): self.x, self.y, self.order = _x, _y, _order

    def calc(self, top, bottom, other_x):
        l = (top * inverse_mod(bottom)) % p
        x3 = (l * l - self.x - other_x) % p
        return Point(x3, (l * (self.x - x3) - self.y) % p)

    def double(self):
        if self == INFINITY: return INFINITY
        return self.calc(3 * self.x * self.x, 2 * self.y, self.x)

    def __add__(self, other):
        if other == INFINITY: return self
        if self == INFINITY: return other
        if self.x == other.x:
            if (self.y + other.y) % p == 0: return INFINITY
            return self.double()
        return self.calc(other.y - self.y, other.x - self.x, other.x)

    def __mul__(self, e):
        if self.order: e %= self.order
        if e == 0 or self == INFINITY: return INFINITY
        result, q = INFINITY, self
        while e:
            if e&1: result += q
            e, q = e >> 1, q.double()
        return result

    def __str__(self):
        if self == INFINITY: return "infinity"
        return "04 %x %x" % (self.x, self.y)

def inverse_mod(a):
    if a < 0 or a >= p: a = a % p
    c, d, uc, vc, ud, vd = a, p, 1, 0, 0, 1
    while c:
        q, c, d = divmod(d, c) + (c,)
        uc, vc, ud, vd = ud - q*uc, vd - q*vc, uc, vc
    if ud > 0: return ud
    return ud + p

p, INFINITY = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2FL, Point(None, None) # secp256k1
g = Point(0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798L, 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8L,
          0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141L)
secret =  0x18E14A7B6A307F426A94F8114701E7C8E774E7F9A47E2C2035DB29A206321725L
print '  privkey:    %x\n   pubkey: %s' % (secret, g * secret)

Produce esta salida:

  privkey:    18e14a7b6a307f426a94f8114701e7c8e774e7f9a47e2c2035db29a206321725
   pubkey: 04 50863ad64a87ae8a2fe83c1af1a8403cb53f53e486d8511dad8a04887e5b2352 2cd470243453a299fa9e77237716103abc11a1df38855ed6f2ee187e9c582ba6

Casi puedo entender cómo funciona ahora. :)

La descripción de la multiplicación de puntos en Wikipedia fue útil para comprender de dónde lprovienen los valores. lsignifica 'lambda'.

La clave pública es un punto (x, y)en la curva secp256k1 que se puede calcular multiplicando el punto base Gcon la clave secreta sk. Aquí hay una función de python concisa e independiente, que hace esto:

def sk_to_pk(sk):
    """
    Derive the public key of a secret key on the secp256k1 curve.

    Args:
        sk: An integer representing the secret key (also known as secret
          exponent).

    Returns:
        A coordinate (x, y) on the curve repesenting the public key
          for the given secret key.

    Raises:
        ValueError: The secret key is not in the valid range [1,N-1].
    """
    # base point (generator)
    G = (0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798,
         0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8)

    # field prime
    P = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F

    # order
    N = (1 << 256) - 0x14551231950B75FC4402DA1732FC9BEBF

    # check if the key is valid
    if not(0 < sk < N):
        msg = "{} is not a valid key (not in range [1, {}])"
        raise ValueError(msg.format(hex(sk), hex(N-1)))

    # addition operation on the elliptic curve
    # see: https://en.wikipedia.org/wiki/Elliptic_curve_point_multiplication#Point_addition
    # note that the coordinates need to be given modulo P and that division is
    # done by computing the multiplicative inverse, which can be done with
    # x^-1 = x^(P-2) mod P using fermat's little theorem (the pow function of
    # python can do this efficiently even for very large P)
    def add(p, q):
        px, py = p
        qx, qy = q
        if p == q:
            lam = (3 * px * px) * pow(2 * py, P - 2, P)
        else:
            lam = (qy - py) * pow(qx - px, P - 2, P)
        rx = lam**2 - px - qx
        ry = lam * (px - rx) - py
        return rx % P, ry % P

    # compute G * sk with repeated addition
    # by using the binary representation of sk this can be done in 256
    # iterations (double-and-add)
    ret = None
    for i in xrange(256):
        if sk & (1 << i):
            if ret is None:
                ret = G
            else:
                ret = add(ret, G)
        G = add(G, G)

    return ret

Los parámetros requeridos ( G, Py N) se pueden encontrar en la especificación: http://www.secg.org/sec2-v2.pdf#page=13 . Tenga en cuenta que esta implementación tiene como objetivo la claridad. No es eficiente en absoluto y probablemente tampoco sea seguro contra ataques de sincronización de canal lateral. Un atacante podría usar el tiempo de ejecución de una llamada a esta función para obtener información sobre la clave secreta.

Esperaba una respuesta como esta y no la vi, así que aquí está la mía:

Una curva elíptica ("EC") es una función en la que el cuadrado de la coordenada y es igual a un polinomio de tercer grado de la coordenada x.

1. Una propiedad interesante de las curvas elípticas es que dos puntos cualesquiera de una EC definirán una línea que también llega a la curva en un lugar más. La "suma" de los dos primeros puntos se define como la imagen especular (sobre el eje X) de ese lugar, así que después de encontrar la intersección, simplemente niega la coordenada Y, y tendrás el punto que es la "suma" de la otros dos.
2. Para agregar un punto a sí mismo, usa una línea que es tangente a la EC. También se cruzará con la curva en alguna parte. (Puede ver por qué esto funciona si imagina que los dos puntos que está agregando se acercan más y más en la curva).
3. Tienes que sumar el "punto de generación" ("G") a sí mismo un número de veces igual al número representado por la clave privada para encontrar el punto que te da la clave pública.
4. Si haces el álgebra, encuentras que las ecuaciones para identificar el punto en la curva que se cruza con la línea (ya sea tangente a un punto que estás duplicando, o que pasa por dos puntos que estás sumando) son las implementadas en el secuencia de comandos de Python en otra respuesta. **
5. Para agregar el punto G a sí mismo [clave privada] veces, puede convertirlo en un número binario. Puede duplicar el punto G usando la línea tangente y la intersección como se describe arriba para obtener 2G (un nuevo punto), y luego nuevamente para 4G, 8G, etc., todos los puntos nuevos. Así que ahora cada posición de bit en su clave privada (binaria) está asociada con un punto.
6. Comience con el punto asociado del bit menos significativo (LSB) como resultado. Para cada otro bit (a la izquierda del LSB) en su clave privada que es 1 (omita los ceros), calcule el punto de "suma" como se describe en el paso 1 usando el punto asociado de ese bit del paso 5 y su resultado actual. Repita esto hasta que haya hecho todos los bits en su clave privada. La suma es asociativa, así que puedes hacerlas en el orden que quieras.
7. Imagine que esta curva está graficada en su plenitud infinita en un plano transparente infinitamente grande. Ahora imagina que el avión se corta en cuadrados de modo que cada cuadrado tenga p unidades de lado, y luego todos los cuadrados se apilan uno encima del otro. Por lo tanto, todos los puntos con coordenadas mayores que p están sobre un punto para el cual ambas coordenadas son menores que p. Esa es la función de módulo en el trabajo. En todas las matemáticas que haces en los otros 5 pasos, cuando obtienes una respuesta que es mayor que p, encuentra la respuesta módulo p.
8. Terminas con un resultado que es un punto. Supongo que concatenas las coordenadas X e Y y esa es tu clave pública, pero no estoy tan seguro de este último paso.

Así es como entiendo ECC, y puede ser inexacto. Agradecería mucho cualquier corrección o pregunta para poder perfeccionar esta descripción. Dadas las otras respuestas aquí ya, pensé que esta podría ayudar a mucha gente.

**Sería bueno ver el álgebra que muestra cómo obtener la tangente de la EC (para duplicaciones) y también para el cálculo del punto de intersección entre una línea definida por otros dos puntos y la propia curva.