Valid 256-bit Private Keys (Not All of Them Are)

[butka]

Some time ago I did a post about creating a private key by flipping a coin. Recently, I stumbled upon this video related to Elliptic Cryptography, in which the author goes through a simple python code [1] for generating Bitcoin public key from a known private key.

Among the other interesting details, the author mentions that NOT every 256-bit private key is acceptable as an input for his script, which made me thinking about my previous (coin flipping) post.

(Note: I recommend watching this video even if you don't know anything about python programming. You may learn a lot about how the math of Elliptic Cryptography works, which is what protects Bitcoin in the first place.)

At first, this looked strange, but then I found this post which confirmed that the number of possible private keys is less than 2²⁵⁶.

So it turns out that this is a fine detail related to Elliptic Curve math, so when you flip a coin, a very small subset of private keys won't fit into the Bitcoin's derivation scheme.

The probability of getting one of these unacceptable private keys by flipping a coin is so minute, that it's not worth considering. Still, one should know about it.

Let's see how come this is even possible.

Some Elliptic Curve Examples

Bitcoin uses the following elliptic curve formula [2]:

y² = x³ + 7

The curve looks like shown below (if you plot it over real numbers):



(plotted on https://www.desmos.com/calculator)

Bit in Bitcoin, we don't use real numbers for x. In Bitcoin, we have to restrict x (x is on the horizontal axis) to a discrete set (field) of positive integers.

Because of this discrete nature of x, the curve above is no longer a curve but a set of points. Each point has an x and y coordinate, like this (please note that this is only an illustration on a much smaller field, the image is taken from reference [3]):



The number of points, albeit very very large, is finite. There are several very important points, and one of them is called generator point or base point:

G=(G_x, G_y)

Just like an illustration as to the exact position of G, here are the coordinates of the generator point:

G_x= 55066263022277343669578718895168534326250603453777594175500187360389116729240
G_y= 32670510020758816978083085130507043184471273380659243275938904335757337482424

Now, if you have a private key (Priv), the way you obtain your public key (Pub) by multiplying the generator point with your private key Priv:

Code:

 Pub = Priv * G, 

or equivalently, we can replace the operation of multiplication with addition:

Code:

 Pub = G + G + G + ...... + G
	  (Priv times)

We won't go into details here, but when you add G to itself (G+G), you end up on another point in the graph above. And then you continue adding another G. In a nutshell, your private key is a very large number, while you public key is a point on this graph where you end up after a huge number of additions (starting from the generator point).

It turns out that the maximum number of additions of G to itself is predetermined by the field itself and is expressed by another properties of this field called order N of G [4]:

N is very large:

Code:

 N = 115792089237316195423570985008687907852837564279074904382605163141518161494336

If you add G to itself N+1 times, you will leave (break) the graph, so the private key has to be a number between 1 and N.

Back to coin flipping.

When you flip a coin there are exactly 2²⁵⁶ possibilities, and 2²⁵⁶ distinct private keys can be generated. How large this number is? It is somewhat larger than the order N of G:

Code:

the number of possible private keys generated by coin flipping = 115792089237316195423570985008687907853269984665640564039457584007913129639936

So out of all possible combinations that produce a private key, about this many are not acceptable:

Code:

432420386565659656852420866394968145600

It may look like a huge number, but it's not. Not, given the size of the entire space (2²⁵⁶).

NOT that this will ever be the case, but if you use coin flipping for your private key and get a number with a lot of leading 1s, like this:

Code:

1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111010111010101011101101110011100110101011110100100010100000001110111011111111010010010111101000110011010000001101100100000101000001

it won't be a valid private key. (Fewer leading 1s in your private key are fine, but more 1s won't be acceptable as well).

References:

[1] https://github.com/wobine/blackboard101/blob/master/EllipticCurvesPart4-PrivateKeyToPublicKey.py
[2] https://en.bitcoin.it/wiki/Secp256k1
[3] https://bitcoin.stackexchange.com/questions/21907/what-does-the-curve-used-in-bitcoin-secp256k1-look-like
[4] https://www.coindesk.com/math-behind-bitcoin/

Edit: @achow101, in the discussion below, helped me realize that the usual notation for N is n. Mind this if you consult literature. Moreover, all private keys are modulo n (akka N above). This means that software producers can and should take this fact into account. If the private key is larger than n (akka N above), they can compute the following simple operation: "private key modulo n (akka N above)", and get a valid private key. If you flip a coin and it happens that you get one of these large private keys, you can do the same by hand.

[achow101]

Private keys are modulo n, so if your private key is larger than n, then it is really just key - n. Properly written wallet software should be able to handle this case (by doing mod n), although it is one that is extremely unlikely to happen.

[butka]

Private keys are modulo n, so if your private key is larger than n, then it is really just key - n. Properly written wallet software should be able to handle this case (by doing mod n), although it is one that is extremely unlikely to happen.

Yes they are modulo n, and n is this number here:

n = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F = 2²⁵⁶ - 2³² - 2⁹ - 2⁸ - 2⁷ - 2⁶ - 2⁴ - 1

The order N of G, given in the OP, is this number:

N = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141

So, n is larger than N.

I agree that every private key larger than n will be folded back in and it will be just key -n. The software could take care of that.

If I'm not totally mistaken, there should be a narrow stripe of private keys between N and n that are not larger than n and won't be able to be brought back in by the modulo operation. I could be wrong but I think these private keys could never be made valid.

[achow101]

Yes they are modulo n, and n is this number here:

n = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F = 2²⁵⁶ - 2³² - 2⁹ - 2⁸ - 2⁷ - 2⁶ - 2⁴ - 1

This term is known as p, not n. Private keys are not modulo p. The X and Y coordinates of points on the curve are modulo p.

The order N of G, given in the OP, is this number:

N = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141

This is n, and private keys are modulo this number.

So, n is larger than N.

I agree that every private key larger than n will be folded back in and it will be just key -n. The software could take care of that.

If I'm not totally mistaken, there should be a narrow stripe of private keys between N and n that are not larger than n and won't be able to be brought back in by the modulo operation. I could be wrong but I think these private keys could never be made valid.

You are mistaken. Private keys are modulo n (aka N) and not p (aka n).

[butka]

You are mistaken. Private keys are modulo n (aka N) and not p (aka n).

Thank you very much for your explanation.

I get it now. I've mixed up n and p, as you helped me realize. 

As you said in your first post, since the private keys are modulo n (aka N in the OP), the software (if written correctly) can always automatically take care of the private keys greater than n, (by doing mod n).

I will modify the OP to include this info.

Thanks again.

[wyplashdea]

Very interesting post. One question:

You mentioned de ecuation
y2 = x3 + 7
and then you draw that into x,y axes using R - real numbers.

Then you say that BT uses discrete values to x axe but i dont know how you got the picture with lots of blue points. As a discrete {x} i should expect the same picture as above but painted with dots.

Thank you han have a nice day.

[butka]

The math about elliptic cryptography is also new to me. I'll try to explain the best I can.

You mentioned de ecuation
y2 = x3 + 7
and then you draw that into x,y axes using R - real numbers.

The real numbers are an infinite set. They are not only infinite, but also they are uncountable. To this set belong all the integer numbers, rational numbers (fractions), numbers like square root of 2, etc.

When you have real numbers as your x, you can put literary any number for x larger than -1.9 something and get the appropriate y. That's why we have such a nice curve.

While looking nice, this elliptic curve is not useful for cryptography.

Then you say that BT uses discrete values to x axe but i dont know how you got the picture with lots of blue points.

This image is just an illustration of the concept, not the exact equivalent of the first picture. It is taken from reference [3].

As a discrete {x} i should expect the same picture as above but painted with dots.

No, it's not like that. Only the horizontal symmetry is preserved, not the shape of the curve.

The set of x that would be useful for cryptography is a finite field of integers modulo p.

When you have such a finite field of integers, you cannot put any number for x, as not all integer numbers x would satisfy the equation. Check, for example, this link for more info.

Because of the fact that for Bitcoin p is such a large number, we cannot really show the corresponding graph of discrete points. That's why in the original post the second image is just an illustration, and it uses a small group of integers modulo 59: F_(p=59).

So in the case of finite field, only a set of discrete values of x will be valid x-coordinates.

[Evil-Knievel]

NOT that this will ever be the case, but if you use coin flipping for your private key and get a number with a lot of leading 1s, like this:

Code:

1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111010111010101011101101110011100110101011110100100010100000001110111011111111010010010111101000110011010000001101100100000101000001

it won't be a valid private key. (Fewer leading 1s in your private key are fine, but more 1s won't be acceptable as well).

This is just not true. This private key is perfectly valid!
The only invalid private key would be "0x00 mod n".

[butka]

NOT that this will ever be the case, but if you use coin flipping for your private key and get a number with a lot of leading 1s, like this:

Code:

1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111010111010101011101101110011100110101011110100100010100000001110111011111111010010010111101000110011010000001101100100000101000001

it won't be a valid private key. (Fewer leading 1s in your private key are fine, but more 1s won't be acceptable as well).

This is just not true. This private key is perfectly valid!
The only invalid private key would be "0x00".

But wouldn't this private key be larger than n (aka N in the OP)? Maybe you mean that one can do modulo n operation on this number to make it valid.

Would you care to explain your point a little bit more?

[Evil-Knievel]

NOT that this will ever be the case, but if you use coin flipping for your private key and get a number with a lot of leading 1s, like this:

Code:

1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111010111010101011101101110011100110101011110100100010100000001110111011111111010010010111101000110011010000001101100100000101000001

it won't be a valid private key. (Fewer leading 1s in your private key are fine, but more 1s won't be acceptable as well).

This is just not true. This private key is perfectly valid!
The only invalid private key would be "0x00".

But wouldn't this private key be larger than n (aka N in the OP)? Maybe you mean that one can do modulo n operation on this number to make it valid.

Would you care to explain your point a little bit more?

First of all, here a python example showing you that this private key is valid (without applying any modulo N to it):

Code:

#! /usr/bin/env python

import random

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."

class Private_key( object ):
  def __init__( self, public_key, secret_multiplier ):
    self.public_key = public_key
    self.secret_multiplier = secret_multiplier

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

if __name__ == "__main__":
 
  n = g.order()
  secret = 1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111010111010101011101101110011100110101011110100100010100000001110111011111111010010010111101000110011010000001101100100000101000001
  
  print 'private key', hex(secret)
  
  ### generate pubkey
  pubkey = Public_key( g, g * secret )
 
  print 'pubkey', hex(pubkey.point.x()), hex(pubkey.point.y())

The thing is, why should it not be valid?

If your private key is p, that means that your public key is formed by adding the point G exactly p times (G + G + G ....[p times]).
Why should there be a limit? No way you will at some point reach a magical "barrier" where you cannot add one more G; you can add as many G as you want - there is no limit. Just make sure that your key is not == 0 (mod n)

Sure, at some point you will get public key collisions, but that alone does not "require" you to apply any modulus to your private key.

[butka]

The thing is, why should it not be valid?

If your private key is p, that means that your public key is formed by adding the point G exactly p times (G + G + G ....[p times]).
Why should there be a limit? No way you will at some point reach a magical "barrier" where you cannot add one more G; you can add as many G as you want - there is no limit. Just make sure that your key is not == 0 (mod n)

As far as I understand it, there is a limit. Here is a reference indicating that after you add one more time beyond the order n, you get an infinite slope, a vertical line and you cannot continue adding:

The order of the base point, which is not independently selected but is a function of the other parameters, can be thought of graphically as the number of times the point can be added to itself until its slope is infinite, or a vertical line. The base point is selected such that the order is a large prime number.
[......]
Here it is in a nutshell: In ECDSA, the private key is an unpredictably chosen number between 1 and the order. The public key is derived from the private key by scalar multiplication of the base point a number of times equal to the value of the private key. Expressed as an equation:

public key = private key * base point

This shows that the maximum possible number of private keys (and thus bitcoin addresses) is equal to the order.

Source: https://www.coindesk.com/math-behind-bitcoin/

Furthermore in the OP I've linked a post indicating that the number of private points is not 2^256, but somewhat less than that.

[Evil-Knievel]

Infinite Slope? Geometry in a quotient space? I wouldn't be soooo sure

Have you tried out the python script?

If you change the main routine to:

Code:

if __name__ == "__main__":
 
  n = g.order()
  secret = 1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111010111010101011101101110011100110101011110100100010100000001110111011111111010010010111101000110011010000001101100100000101000001
  
  print 'private key', hex(secret)
  
  ### generate pubkey
  pubkey = Public_key( g, g * secret )
  print 'pubkey', hex(pubkey.point.x()), hex(pubkey.point.y())


  secret = secret+1
  print 'private key', hex(secret)

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

Result:

Code:

○ → python slope.py 
private key 0x978d438a5388c5d36fc32ac332a9b43159e20b54a8c9c15ed3f8eeaa978fcdce8942e6c977cb2fc0b61392859ad36d10a63aa5412662566c93f72b6c382137d93e63fdf1699b7c8fde0a72dd09bc5c5d0af59e3692ae6806d6e9cca8f8c838ec3086fa3ef9502d1d6341L
pubkey 0x95a72837426cba0bdf82ee776933e4dd723eb0ab7e1b55ff505a5645e1aaed9L 0xda33f35585b25e80082e64b9be2caaaf74666b81b8c0a37ec371fc195d19f9e3L

(now adding one more)

private key 0x978d438a5388c5d36fc32ac332a9b43159e20b54a8c9c15ed3f8eeaa978fcdce8942e6c977cb2fc0b61392859ad36d10a63aa5412662566c93f72b6c382137d93e63fdf1699b7c8fde0a72dd09bc5c5d0af59e3692ae6806d6e9cca8f8c838ec3086fa3ef9502d1d6342L
pubkey 0x68882ccbdd804e8b4270c0f664dc5754339a341070f963f4845767cbd3d80a38L 0xbad5caa505f780adc5b2afa56a466b5d211bdb82490a2bc467281d06db45824cL

You will see, that you can very well add more G's, there is no such thing as an "infinite slope" and you (as I would expect) end up with totally different public keys.

Ah, and to be super-precise:

Furthermore in the OP I've linked a post indicating that the number of private points is not 2^256, but somewhat less than that.

There is also no such thing as "private points". Private keys are numbers ... they can be 256bit, 2048bit, 4096bit, or anything you like. The number of public key points is limited though.

[butka]

Infinite Slope? What? Geometry in a quotient space? Really?

So this would imply that the linked article is wrong with this respect. Don't take me wrong, I have nothing against your arguments. I'm not an expert and the purpose of my post was to learn about the mathematics behind Bitcoin.

Have you tried out the python script?

No, I'm not really a programmer to be able to test your code.

Ah, and to be super-precise:

Furthermore in the OP I've linked a post indicating that the number of private points is not 2^256, but somewhat less than that.

There is also no such thing as "private points". Private keys are numbers ... they can be 256bit, 2048bit, 4096bit, or anything you like. The number of public key points is limited though.

It was a typo. Of course, I meant private keys.

Still, somewhere has to be a contradiction, and it would be nice to know where. Either the linked articles are wrong or your argument is wrong. If you are right, of course I would have to change the OP, as the basic premise of the OP was that there are less than 2^256 private keys.

[Evil-Knievel]

So this would imply that the linked article is wrong with this respect. Don't take me wrong, I have nothing against your arguments. I'm not an expert and the purpose of my post was to learn about the mathematics behind Bitcoin.

Yep, it's wrong.

Correct would be:

Here it is in a nutshell: In ECDSA, the private key is an arbitrary number P between 1 and infinity (with P%N!=0). The public key is derived from the private key by scalar multiplication of the base point a number of times equal to the value of the private key, i.e:

pubkey = privkey * basepoint

Even though the number of private keys is infinite, the series of public keys has a period that is equal to the order of the curve, at which point they start repeating. This shows that the maximum possible number of public keys (and thus bitcoin addresses) is equal to the order.

[d34thkn3ll]

Excuse me, but why are you treating it as a decimal number rather than a binary?

[butka]

Excuse me, but why are you treating it as a decimal number rather than a binary?

It doesn't matter how you treat it or what numeral system (decimal, binary, hexadecimal,...) your code uses, as long as it is the same number.

[Evil-Knievel]

Excuse me, but why are you treating it as a decimal number rather than a binary?

Well, no matter if binary or decimal, both numbers are bigger than this „N“ claimed in the original post! Furthermore, there was no specification as to which numerical system to use in the original post ... which doesnt even matter at all since the decimal interpretation is even bigger than the binary one.

[d34thkn3ll]

Excuse me, but why are you treating it as a decimal number rather than a binary?

It doesn't matter how you treat it or what numeral system (decimal, binary, hexadecimal,...) your code uses, as long as it is the same number.

Why is it the same number?

I added the 0b preffix to the number and got "Generator point has x or y out of range." quod erat demonstrandum.
Quick digging into the code shows that in the multiplication operator there is a modulo operation:

Code:

if self.__order: e = e % self.__order

so it doesn't matter how big number you use, the operation will be done with its modulus (which is no bigger than 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141 by the definition)

[butka]

Excuse me, but why are you treating it as a decimal number rather than a binary?

It doesn't matter how you treat it or what numeral system (decimal, binary, hexadecimal,...) your code uses, as long as it is the same number.

Why is it the same number?

I added the 0b preffix to the number and got "Generator point has x or y out of range." quod erat demonstrandum.
Quick digging into the code shows that in the multiplication operator there is a modulo operation:

Code:

if self.__order: e = e % self.__order

so it doesn't matter how big number you use, the operation will be done with its modulus (which is no bigger than 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141 by the definition)

Thanks for clearing this up. I wasn't knowledgeable enough to go through the python code myself, but there had to be a modulo operation somewhere. Either that or the math is wrong.