Bitcoin Forum
June 19, 2018, 01:14:28 PM
 News: Latest stable version of Bitcoin Core: 0.16.1  [Torrent]. (New!)
 Home Help Search Donate Login Register
 Pages: [1] 2  All
 Author Topic: How to create an N bit ECDSA compatible private key from dice rolls in python  (Read 2115 times)
bitsec731
Jr. Member

Offline

Activity: 32
Merit: 0

 January 18, 2017, 11:50:24 PM

How can you create an N bit uniformly random ECDSA private key from indepentend dice rolls, that to be inputed in phython console.

Let me explain. I would like to create a private key just from combining dice rolls, with 6 sided dice.

You can create a random private key already in python with:

Code:
import ecdsa

privkey = ecdsa.util.randrange(pow(2, n))

Where the n is the number of bits, so if n=160, that would be a classic 160 bit private key, which would be as strong as an unspent bitcoin address (no need to utilize the full 256 bits).

Of course this relies on the RNG of the computer, which can be weak. So I want to do it manually with dices.

A perfect 6 sided dice, has an entropy of 2.5849625007, so I need to roll 62 times a dice, or less times multiple dices.

Rolling 62 times gives us an entropy of 160.2676750447, which wouldbe equivalent to what the code above would give us, except that this one is manual.

Alright, so we have 62 random numbers ranging from (1-6), the question is, how to combine these 62 random numbers into an ECDSA compatible integer like the one generated above with that script?

I need a python code for that, thank you.

1529414068
Hero Member

Offline

Posts: 1529414068

Ignore
 1529414068

1529414068
 Report to moderator
1529414068
Hero Member

Offline

Posts: 1529414068

Ignore
 1529414068

1529414068
 Report to moderator
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: 1428
Merit: 1351

 January 19, 2017, 01:44:39 AM

An ECDSA private key is simply a 256 bit integer between 0x1 and 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364140. So all you need to do is combine those random numbers so that the result is in that range. The result is your private keys. I'm pretty sure that however you combine those numbers will still be safe, so how you want to do it is up to you.

ArcCsch
Full Member

Offline

Activity: 224
Merit: 100

▲ Portable backup power source for mining.

 January 19, 2017, 03:17:33 AM

An ECDSA private key is simply a 256 bit integer between 0x1 and 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364140.
There is a roughly 1 in 2^128 chance (not worth worrying about) of a random 256 bit key not falling in this range.
What would happen to a wallet program if this happened?

If you don't have sole and complete control over the private keys, you don't have any bitcoin!  Signature campaigns are OK, zero tolorance for spam!
1JGYXhfhPrkiHcpYkiuCoKpdycPhGCuswa
achow101
Moderator
Legendary

Offline

Activity: 1428
Merit: 1351

 January 19, 2017, 03:30:52 AM

There is a roughly 1 in 2^128 chance (not worth worrying about) of a random 256 bit key not falling in this range.
What would happen to a wallet program if this happened?
The wallet should be checking that the keys generated are in that range. If it is not, then a new key should be generated and the first one discarded.

prezbo
Sr. Member

Offline

Activity: 430
Merit: 250

 January 19, 2017, 07:40:30 AM

There is a roughly 1 in 2^128 chance (not worth worrying about) of a random 256 bit key not falling in this range.
What would happen to a wallet program if this happened?
The wallet should be checking that the keys generated are in that range. If it is not, then a new key should be generated and the first one discarded.

Wouldn't everything still work but it would wrap around, basically becoming X - 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141? At least that's what math tells us - if group order is n, then G^(n+x) = g^n * g^x = g^x.
bitsec731
Jr. Member

Offline

Activity: 32
Merit: 0

 January 21, 2017, 05:49:17 AM

An ECDSA private key is simply a 256 bit integer between 0x1 and 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364140. So all you need to do is combine those random numbers so that the result is in that range. The result is your private keys. I'm pretty sure that however you combine those numbers will still be safe, so how you want to do it is up to you.

So if I multiply the 62 numbers together, would that work?

But if I add them together , won't that create a very weak key, a small number that is still in the range of computers that go through addresses 1 by 1? So isn't it important to have the key at the higher ends of the randomness.

An ECDSA private key is simply a 256 bit integer between 0x1 and 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364140.
There is a roughly 1 in 2^128 chance (not worth worrying about) of a random 256 bit key not falling in this range.
What would happen to a wallet program if this happened?

Well my key would only be 160 bit, so it would be even lower + I would check it later if the address that derives from it is BTC compatible.

ArcCsch
Full Member

Offline

Activity: 224
Merit: 100

▲ Portable backup power source for mining.

 January 21, 2017, 06:11:49 AM

So if I multiply the 62 numbers together, would that work?

But if I add them together , won't that create a very weak key, a small number that is still in the range of computers that go through addresses 1 by 1? So isn't it important to have the key at the higher ends of the randomness.
No, multiplying the numbers would destroy the informational entropy, you should string them together and take a hash of the string (SHA3-256 for example).

If you don't have sole and complete control over the private keys, you don't have any bitcoin!  Signature campaigns are OK, zero tolorance for spam!
1JGYXhfhPrkiHcpYkiuCoKpdycPhGCuswa
DannyHamilton
Legendary

Offline

Activity: 2184
Merit: 1357

 January 21, 2017, 06:49:36 AM

So if I multiply the 62 numbers together, would that work?

But if I add them together , won't that create a very weak key, a small number that is still in the range of computers that go through addresses 1 by 1? So isn't it important to have the key at the higher ends of the randomness.
No, multiplying the numbers would destroy the informational entropy, you should string them together and take a hash of the string (SHA3-256 for example).

Perhaps take a photograph of the dice and then calculate the SHA-256 hash of the photo file?

bitsec731
Jr. Member

Offline

Activity: 32
Merit: 0

 January 21, 2017, 06:54:10 AM

So if I multiply the 62 numbers together, would that work?

But if I add them together , won't that create a very weak key, a small number that is still in the range of computers that go through addresses 1 by 1? So isn't it important to have the key at the higher ends of the randomness.
No, multiplying the numbers would destroy the informational entropy, you should string them together and take a hash of the string (SHA3-256 for example).

Perhaps take a photograph of the dice and then calculate the SHA-256 hash of the photo file?

That would depend on the randomness of the picture, and how random the bits are in the picture, which might not be that random.

So if I multiply the 62 numbers together, would that work?

But if I add them together , won't that create a very weak key, a small number that is still in the range of computers that go through addresses 1 by 1? So isn't it important to have the key at the higher ends of the randomness.
No, multiplying the numbers would destroy the informational entropy, you should string them together and take a hash of the string (SHA3-256 for example).

Doesn't the SHA256 function cut off entropy too? Or is it just the entropy beyond the 256 bits?

For example SHA256 has only 128 bits of security, should I use SHA-512 for this, wouldn't SHA256 cut off the entropy into half?
DannyHamilton
Legendary

Offline

Activity: 2184
Merit: 1357

 January 21, 2017, 08:18:06 AM

So if I multiply the 62 numbers together, would that work?

But if I add them together , won't that create a very weak key, a small number that is still in the range of computers that go through addresses 1 by 1? So isn't it important to have the key at the higher ends of the randomness.
No, multiplying the numbers would destroy the informational entropy, you should string them together and take a hash of the string (SHA3-256 for example).

Perhaps take a photograph of the dice and then calculate the SHA-256 hash of the photo file?

That would depend on the randomness of the picture, and how random the bits are in the picture, which might not be that random.

Since the photo is of the dice, and the dice are random, then the values and arrangement of the dice in the photo would be random.  Therefore, the entropy in the photo should be significantly higher than the entropy of the dice values themselves (since values of the photo would also take into consideration the location and orientation of the dice as well as the background).

Of course that assumes that the photo has enough detail and clarity to make out the values of all the dice.

bitsec731
Jr. Member

Offline

Activity: 32
Merit: 0

 January 23, 2017, 02:03:41 AM

Since the photo is of the dice, and the dice are random, then the values and arrangement of the dice in the photo would be random.  Therefore, the entropy in the photo should be significantly higher than the entropy of the dice values themselves (since values of the photo would also take into consideration the location and orientation of the dice as well as the background).

Of course that assumes that the photo has enough detail and clarity to make out the values of all the dice.

I am sorry but that just makes no sense, the information entropy of a number is raw entropy with 0% noise/signal ratio.

When you consider a picture, which has bits of repeating colors all over the place, that is just not raw entropy anymore, because the bits of the colors are repeating. I highly doubt that is high quality randomness.

Maybe if it's just a black/white binary image of random 0 and 1, but then that image is already 100% descriptive of the information contained in itself.

But just the dice itself, which is not even in the same language, I doubt it. It's the bits that are the language, and repeating bits are not a good quality.

ArcCsch
Full Member

Offline

Activity: 224
Merit: 100

▲ Portable backup power source for mining.

 January 23, 2017, 03:13:54 AM

I am sorry but that just makes no sense, the information entropy of a number is raw entropy with 0% noise/signal ratio.
I am sorry but that just makes no sense.
When you consider a picture, which has bits of repeating colors all over the place, that is just not raw entropy anymore, because the bits of the colors are repeating. I highly doubt that is high quality randomness.
...
But just the dice itself, which is not even in the same language, I doubt it. It's the bits that are the language, and repeating bits are not a good quality.
The photo as is is not high quality randomness, but it has much more total entropy than the dice roll values.
Think about it, if you roll ten dice and record the values, they have 60466176 possibilities, how many possible images of the dice do you think there are?
Definitely many more, and entropy is just a measure of the amount of possibilities (adjusted by probability, so that equal probabilities have more entropy than different probabilities).
Also, high quality randomness is not very important for the seed value, a ten bit seed is inadequate no matter how high-quality they are are, but 65536 bits are enough even if each bit is biased 10% to 90%.

If you don't have sole and complete control over the private keys, you don't have any bitcoin!  Signature campaigns are OK, zero tolorance for spam!
1JGYXhfhPrkiHcpYkiuCoKpdycPhGCuswa
bitsec731
Jr. Member

Offline

Activity: 32
Merit: 0

 January 23, 2017, 04:31:03 AM

I am sorry but that just makes no sense, the information entropy of a number is raw entropy with 0% noise/signal ratio.
I am sorry but that just makes no sense.
When you consider a picture, which has bits of repeating colors all over the place, that is just not raw entropy anymore, because the bits of the colors are repeating. I highly doubt that is high quality randomness.
...
But just the dice itself, which is not even in the same language, I doubt it. It's the bits that are the language, and repeating bits are not a good quality.
The photo as is is not high quality randomness, but it has much more total entropy than the dice roll values.
Think about it, if you roll ten dice and record the values, they have 60466176 possibilities, how many possible images of the dice do you think there are?
Definitely many more, and entropy is just a measure of the amount of possibilities (adjusted by probability, so that equal probabilities have more entropy than different probabilities).
Also, high quality randomness is not very important for the seed value, a ten bit seed is inadequate no matter how high-quality they are are, but 65536 bits are enough even if each bit is biased 10% to 90%.

Alright I have to concede, cryptography is not my field, I'm an IT guy.

However I imagined that the seed is good if it's truly random. For example an image is a highly repetitive cluster of bits. When you have a blue dice on a white background, that is pretty easy to reconstruct and find similarities.

Random in the entropy sense means something that doesn't repeat, otherwise what is the point on generating a key from that.

If you have a picture of something where the bits are highly repetitive, doesn't that automatically mean low quality randomness?

It would be the equivalent of flipping coins where 1 side has  an enormously bias. If you think of a picture as a bitmap, if the background is white,then that is already a huge bias. Then you have some blue, and the signs on the dice are also white. I doubt that is a high source of entropy.

So maybe a photography could be a source of entropy, but it should be a more diverse photo, like taking random photos of a town, and mixing it together as a composite, so that the colors and the patterns are more uniformly distributed.

I have also read that using a microphone to gather background nosie from an empty room is also a decent source.

It all depends on the quality too, I believe.
bitsec731
Jr. Member

Offline

Activity: 32
Merit: 0

 January 23, 2017, 04:54:10 AM

For example here is a simple photography:

https://postimg.org/image/megtvko1j/

And here is the same photography overlayed other photographies.

https://postimg.org/image/6onp27xf1/

I believe the 2nd image has a better source of entropy than the 1st, since the patterns in it are more random.
ArcCsch
Full Member

Offline

Activity: 224
Merit: 100

▲ Portable backup power source for mining.

 January 23, 2017, 05:10:33 AM

Say you have two ways to get a random seed, one way gives this, with "x" representing an independently chosen perfectly random bit, and zero representing a certain zero:
(1)
000xx00x00000xx00xx0000000000000x000x0x0x0x00x0000000xx0000000000x000x
xx0x0xxx00000000x00000x0x00000x0000000x0x0xx000000x00xx0xx0xxx00000000
00x0xx0000000x0xx000000xx00xx0x00000000x0000x00000x0x0x000x0x0x00xx000
0000x0000000x000000x00x000x0xx00x000x0xx0000x0000x000000x00x00xx000000
0000000x0x0000000x0x0000000000x00x0x00000xx00000x00xx0000000000x000000
00000000x00000xx00x00000x000x0000x00xx000000000x000000x00xx0000000x0xx
xx0xx00x000x0000x0x0000000x0x00000000x0x00x00xx00xx0000x00000000000000
0000000x0xxx0000000000
(2)
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
The first way provides very low-quality randomness (about 7/8 of the bits are zero), but provides much more security than the second way, because the second way has 64 random bits, and the first has 128 (count the number of "x").
The camera image is like the first, it has low quality randomness, but far more total randomness than the dice numbers.
The hash converts large volumes of low-quality randomness into a smaller amount (256 bits) of high quality randomness for your keys.

I believe the 2nd image has a better source of entropy than the 1st, since the patterns in it are more random.
True, but either of those photographs has more than enough entropy to be the seed.
Don't use those particular images because you just published them

If you don't have sole and complete control over the private keys, you don't have any bitcoin!  Signature campaigns are OK, zero tolorance for spam!
1JGYXhfhPrkiHcpYkiuCoKpdycPhGCuswa
bitsec731
Jr. Member

Offline

Activity: 32
Merit: 0

 January 23, 2017, 05:22:31 AM

Say you have two ways to get a random seed, one way gives this, with "x" representing an independently chosen perfectly random bit, and zero representing a certain zero:
(1)
000xx00x00000xx00xx0000000000000x000x0x0x0x00x0000000xx0000000000x000x
xx0x0xxx00000000x00000x0x00000x0000000x0x0xx000000x00xx0xx0xxx00000000
00x0xx0000000x0xx000000xx00xx0x00000000x0000x00000x0x0x000x0x0x00xx000
0000x0000000x000000x00x000x0xx00x000x0xx0000x0000x000000x00x00xx000000
0000000x0x0000000x0x0000000000x00x0x00000xx00000x00xx0000000000x000000
00000000x00000xx00x00000x000x0000x00xx000000000x000000x00xx0000000x0xx
xx0xx00x000x0000x0x0000000x0x00000000x0x00x00xx00xx0000x00000000000000
0000000x0xxx0000000000
(2)
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
The first way provides very low-quality randomness (about 7/8 of the bits are zero), but provides much more security than the second way, because the second way has 64 random bits, and the first has 128 (count the number of "x").
The camera image is like the first, it has low quality randomness, but far more total randomness than the dice numbers.
The hash converts large volumes of low-quality randomness into a smaller amount (256 bits) of high quality randomness for your keys.

Alright but is there a way to actually quantify the amount of entropy an image has, to just make sure it's safe?

Because at least a dice roll can be quantified, because even a slightly deformed dice has 90% entropy, thats 2.3264662506 bits.

So any casino quality dice should be much better than that.

Quote
Don't use those particular images because you just published them

Of course not.
ArcCsch
Full Member

Offline

Activity: 224
Merit: 100

▲ Portable backup power source for mining.

 January 23, 2017, 05:51:40 AM

Alright but is there a way to actually quantify the amount of entropy an image has, to just make sure it's safe?
You can always estimate, if the image has reasonable colour depth (represents each colour value with high precision) you can take the conservative estimate of one bit per pixel (it is probably more than that) any image bigger than 16x16 probably has more than enough entropy.
This is what a totally random image looks like:

As an example, here is a very non-random image (most of it is blank, broad areas of colour, visible text, recognizable qr codes) that contains enough randomness to be a seed:

Of course not.
It is unfortunately not uncommon for people to use things like "Satoshi Nakamoto", "correct horse battery staple" and even "" as private seeds.
There is a well known case of someone putting 250BTC using "how much wood could a woodchuck chuck if a woodchuck could chuck wood" as a seed, and being hacked by a DEFCON hacker who later gave back the coins.
Someone else stole coins from the Bloomberg show, because someone was given a paper wallet by the host, and, after opening it, held up the private key to the camera for everyone to see it over live TV.

The lesson:
Private keys are called private keys for a reason, and hackers are willing to go through a lot of work to get them.

If you don't have sole and complete control over the private keys, you don't have any bitcoin!  Signature campaigns are OK, zero tolorance for spam!
1JGYXhfhPrkiHcpYkiuCoKpdycPhGCuswa
DannyHamilton
Legendary

Offline

Activity: 2184
Merit: 1357

 January 23, 2017, 06:09:31 AM

Alright but is there a way to actually quantify the amount of entropy an image has, to just make sure it's safe?

Because at least a dice roll can be quantified, because even a slightly deformed dice has 90% entropy, thats 2.3264662506 bits.

So any casino quality dice should be much better than that.

Well, if you take a picture of the 62 dice (and the photo has enough detail and clarity to make out the values of all the dice) then the photo would have to have more entropy than the the dice rolls themselves.  Each die value contributes its entropy to the photo, but additionally the exact orientations and exact positions of the dice relative to each other within the photo are random as well which increases the entropy.  Furthermore, the background behind whatever you roll the dice on is likely to have some variations to its color and brightness which contributes additional entropy.

bitsec731
Jr. Member

Offline

Activity: 32
Merit: 0

 January 23, 2017, 07:01:27 AM

The lesson:
Private keys are called private keys for a reason, and hackers are willing to go through a lot of work to get them.

I may not be an expert on cryptography but I am an expert in computer security.

Alright but is there a way to actually quantify the amount of entropy an image has, to just make sure it's safe?

Because at least a dice roll can be quantified, because even a slightly deformed dice has 90% entropy, thats 2.3264662506 bits.

So any casino quality dice should be much better than that.

Well, if you take a picture of the 62 dice (and the photo has enough detail and clarity to make out the values of all the dice) then the photo would have to have more entropy than the the dice rolls themselves.  Each die value contributes its entropy to the photo, but additionally the exact orientations and exact positions of the dice relative to each other within the photo are random as well which increases the entropy.  Furthermore, the background behind whatever you roll the dice on is likely to have some variations to its color and brightness which contributes additional entropy.

I partially disagree, because I don't think they are the same language.

The values of the dice, is just raw information, which can be let's say  "61235" after roll with 5 dices, which in it's basic binary form is:
110110 110001 110010 110011 110101

I highly doubt this sequence of information must inside the binary form of the picture of the dice, because it's not the same language. It may be inside it, but that is only due to coincidence, but it doesnt necessarly have to be.

We just interpreted the output of the dice as being 6 but the computer only sees the pixel values of the dice, but not the "6" itself.

So humans and computers think in different language, and that is why the picture itself is only as good randomness, as random the pixels are inside it, but have probably nothing to do with the informational content that it carries for humans.

Now maybe the picture has a higher entropy value than the roll information itself, but that is another issue.
DannyHamilton
Legendary

Offline

Activity: 2184
Merit: 1357

 January 23, 2017, 08:12:52 AM

I partially disagree, because I don't think they are the same language.

Yes.  They are.  They are both just numbers.

The values of the dice, is just raw information, which can be let's say  "61235" after roll with 5 dices, which in it's basic binary form is:
110110 110001 110010 110011 110101

I highly doubt this sequence of information must inside the binary form of the picture of the dice, because it's not the same language.

It doesn't need to be.  You just need the same amount of entropy. It doesn't need to be the same value.

We just interpreted the output of the dice as being 6 but the computer only sees the pixel values of the dice, but not the "6" itself.

Actually, it does.

Lets look at the most simple example.

Lets imagine that we have a black and white bitmap picture of only 1 die, and the image resolution is 7x7 pixels.  In this bitmap, 1 will represent white and 0 will represent black.

Here is a perfectly centered picture of the '6':
Code:
1111111
1101011
1111111
1101011
1111111
1101011
1111111

And here is the picture of the '1':
Code:
1111111
1111111
1111111
1110111
1111111
1111111
1111111

Hopefully, you can see that in this overly simplified photo system, there are 6 unique possible ways to arrange the 49 pixels. Each of the 6 arrangements has equal probability (assuming you used a perfectly fair die).

In a larger image (more pixels), you could fit more dice.  If the dice were all perfectly aligned with the rows in the bitmap, and each die was 7 pixels wide in the larger bitmap, then each 49 pixel square representing a die would have as much entropy as the die itself. Each 49 pixel portion of the picture that had a die would have 6 unique possibilities each with equal probability.

So, at the bare minimum, the picture would be guaranteed to have at least as much entropy as the dice.  As the resolution of the picture increases, and the pixel values increase from black&white to full color, orientation, brightness, and color of the "dice pixels" increases the entropy significantly higher than the minimum provided by the dice values.

the picture itself is only as good randomness, as random the pixels are inside it,

And the randomness of the pixels inside the picture is partly due to the randomness of the values on the dice. Meaning that the randomness of the pixels overall are even more random than the values on the dice

but have probably nothing to do with the informational content that it carries for humans.

Correct.  This has nothing to do with informational content for humans.  It has to do with the fact that each dice value will create a unique set of pixel values that will ALWAYS be different than pixels of ANYTHING that is not a die of that value (because if the pixels were exatly identical to those of the dice value, then it would be a picture of an identical looking die face).

Now maybe the picture has a higher entropy value than the roll information itself, but that is another issue.

It does.  But what we are trying to get you to understand is that the fact that the die are in the picture GUARANTEES that the entropy will NOT be any lower than the rolled dice themselves.

A picture of a perfect white surface perfectly lit such that every pixel has EXACTLY the same value will have NO entropy.  Every time you take that picture, you will end up with the EXACT same series of pixel values.  BUT if you roll a die, perfectly centered on the surface just before taking the picture, you'll ALWAYS have at least 6 different series of pixel values for the picture (since the die will change the pixel values depending on the value of the die.  Roll 2 dice before taking the picture, and you'll ALWAYS have at least 36 different series of pixel values for the picture.  Roll 62 dice, and you'll ALWAYS have at least 662 different series of pixel values for the picture.

 Pages: [1] 2  All