Topic: How to create an N bit ECDSA compatible private key from dice rolls in python (Read 2281 times)

I wrote a page on the wiki about this a while ago: https://en.bitcoin.it/wiki/Passphrase_generation#Generating_keys.2C_seeds.2C_and_random_numbers_.28Advanced.29

My recommended method is to just hash a string containing the dice rolls. The rolls will contain enough entropy in themselves (if you're using enough dice), and the hash should not degrade this in any significant way.

No.  You have that backwards.

I'm saying that any representation of a number has at minimum as much entropy as the choice of the number itself.  Entropy isn't lost from the selection method when the selection is represented, regardless of whether that representation is a die, pencil on paper, a computer file, or a wall painting.


Note that "a number" (such as 2384923482983) doesn't have ANY entropy at all.  In order for that number on that wall to have an amount of informational entropy there needs to be some randomness to what that value could be.  If that number on that wall was a choice between 2384923482981 and 2384923482985, then it has very little entropy at all (no matter how it was chosen).  If it was a completely random selection between 0 and 1000¹⁰⁰⁰ where every value had equal probability of being selected, then it has significantly more entropy.

https://en.wikipedia.org/wiki/Entropy_(information_theory)

Entropy is a measure of randomness in information.  If the information being represented is a number, and the representation of that information is distinguishable from the other representations.  Then the randomness of the representation of the information will never be less than the randomness of the information itself, since the actual information hasn't changed (only the representation).

Think about this for a moment...

Lets say I have a machine that gives me truly random numbers between 0 and 2²⁵⁶ (perhaps it uses radioactive decay as a source of randomness).  Is the entropy of the representation any less (or more) if I represent that number in binary than if I represent that number in decimal or base 58, or hexadecimal?  The "information"  (the concept of the number itself) hasn't been lost with any of those representations, has it?

Yes, provided the Chinese characters and the MP3 file have sufficient quality to make it possible to recover the number.

Wow, amazing.

A very interesting view on information.

So you are saying basically that every number or text that physically exists in the world as an object has minimum as much entropy as the computational representation of it?

So if we have the number 2384923482983, and this number in Chinese characters painted on a wall. Then if we take a picture of that wall, then that picture will have minimum as much entropy as the number itself? Or if I say out the number 2384923482983 in German and record it in an MP3 file, then that MP3 file will also have minimum as much entropy as the number itself?


A very interesting theory, do you know any scientific papers on it, I would like to read more?

Yes.  They are.  They are both just numbers.


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


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

And here is the picture of the '1':

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.


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


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


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 6⁶² different series of pixel values for the picture.

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


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.

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.

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:

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.

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.





Of course not.

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.

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

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.

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.

I am sorry but that just makes no sense.
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%.

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.

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.

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


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?

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

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

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.


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.

I am asking about the private key's randomness here.

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.