butka


July 08, 2018, 06:20:18 PM Last edit: July 09, 2018, 07:38:48 AM by 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 256bit 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 ^{256}. 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 ExamplesBitcoin uses the following elliptic curve formula [2]: y ^{2} = x ^{3} + 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: Pub = Priv * G, or equivalently, we can replace the operation of multiplication with addition: 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: 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 ^{256} possibilities, and 2 ^{256} distinct private keys can be generated. How large this number is? It is somewhat larger than the order N of G: 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: 432420386565659656852420866394968145600 It may look like a huge number, but it's not. Not, given the size of the entire space (2 ^{256}). 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: 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/EllipticCurvesPart4PrivateKeyToPublicKey.py[2] https://en.bitcoin.it/wiki/Secp256k1[3] https://bitcoin.stackexchange.com/questions/21907/whatdoesthecurveusedinbitcoinsecp256k1looklike[4] https://www.coindesk.com/mathbehindbitcoin/ 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.






Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.

achow101
Moderator
Legendary
Offline
Activity: 2464
Merit: 3743
Just writing some code

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


July 08, 2018, 08:30:27 PM 

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 ^{256}  2 ^{32}  2 ^{9}  2 ^{8}  2 ^{7}  2 ^{6}  2 ^{4}  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
Moderator
Legendary
Offline
Activity: 2464
Merit: 3743
Just writing some code

Yes they are modulo n, and n is this number here:
n = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F = 2^{256}  2^{32}  2^{9}  2^{8}  2^{7}  2^{6}  2^{4}  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


July 09, 2018, 07:02:00 AM 

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
Jr. Member
Offline
Activity: 154
Merit: 3
Staker.network  POS Smart Contract ETH Token


July 09, 2018, 12:08:16 PM 

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.

★ PRiVCY ➢ Own Your Privacy! ➢ Best privacy cryptomarket! ★ ✈✈✈[PoW/PoS]✅[Tor]✅[Airdrop]✈✈✈ (https://privcy.io/)



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




EvilKnievel
Legendary
Offline
Activity: 1260
Merit: 1163


July 15, 2018, 02:48:01 AM Last edit: July 15, 2018, 11:53:33 AM by EvilKnievel 

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: 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


July 15, 2018, 08:31:47 AM 

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: 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?




EvilKnievel
Legendary
Offline
Activity: 1260
Merit: 1163


July 15, 2018, 11:52:28 AM Last edit: July 15, 2018, 12:05:52 PM by EvilKnievel 

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: 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): #! /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


July 15, 2018, 12:19:32 PM 

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/mathbehindbitcoin/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.




EvilKnievel
Legendary
Offline
Activity: 1260
Merit: 1163


July 15, 2018, 12:36:02 PM 

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: 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: ○ → 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 superprecise: 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


July 15, 2018, 12:49:25 PM 

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 superprecise: 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.




EvilKnievel
Legendary
Offline
Activity: 1260
Merit: 1163


July 15, 2018, 12:59:46 PM Last edit: July 15, 2018, 01:12:50 PM by EvilKnievel 

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
Jr. Member
Offline
Activity: 52
Merit: 1


July 20, 2018, 12:39:57 PM 

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

Looking for decentralized systems experts.



butka


July 20, 2018, 12:46:00 PM 

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.




EvilKnievel
Legendary
Offline
Activity: 1260
Merit: 1163


July 20, 2018, 02:31:25 PM 

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
Jr. Member
Offline
Activity: 52
Merit: 1


July 22, 2018, 10:45:03 AM 

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: 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)

Looking for decentralized systems experts.



butka


July 22, 2018, 11:39:41 AM 

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




