Slight bias in conversion

[DaveCTurner]

Hi,

The number you get from 100 dice rolls may have 65 hex digits, and this script throws away the first one to leave the remaining 64. This means that some of the possible outputs are twice as likely as the others. It's a tiny difference in practice, but it'd be nice if it at least warned you if the top digit was nonzero, as if you want an unbiased result then you should re-roll.

A slightly nicer approach (from a practical point of view) is to do the calculation as 4 sets of 25 rolls, each giving 16 hex digits. The chance of having to discard a straight 100 rolls due to bias is rather high (>80%), and re-rolling 100 dice is tedious. The chance of having to discard a block of 25 rolls is much lower (~35%) and the cost of re-rolling is much lower too.

Cheers,

David

[swansontec]

You are right! It is biased.

We are mapping the range 6^100 (6.53e77) into the range 2^256 (1.16e77). The two ranges do not fit cleanly within each other, so some outcomes are more likely than others. There are 6 ways to get each of the numbers between 0 and 7.3e76, but only 5 ways to get the numbers between 7.3e76 and 1.16e77. I'm not 100% sure how to convert this into bits, but I do know that we are looking at less than a quarter-bit of bias here.

The solution you suggest would not solve the bias, but would only reduce it a little. Another way to reduce the bias is to just throw more dice rolls into the mix. This will map an even larger range of numbers into 2^256, so now you are looking at probability differences of 11/12 or 17/18 instead of 5/6. The script already supports this.

A 255.75-bit key is so far into the "safe" zone that it's not even worth worrying about. There are about 2^256 atoms in the universe, so even if you converted all visible matter into a giant supercomputer, these numbers would barely be reachable. Going to 102 dice rolls gets you 255.9 bits of clean key material, which is a bit better, but still so far into "unbreakable" territory that it really isn't worth the effort.

[DaveCTurner]

I realise this is a long way into the zone of stupidly small probabilities, but anyway...

The number of bits is obtained by taking log₂ of the number of possiblities: log₂(6¹⁰⁰) ≈ 258.496 and log₂(2²⁵⁶) = 256.

I'd apparently forgotten that there's no bias introduced by discarding a whole bit, so yes, it's just 0.496 bits of bias, not 2.496 as I seemed to be claiming. Moreover, the bias is concentrated in the most significant bits (of which you discard 2-3) so the effective bias is really rather small indeed.

Nonetheless, rerolling if the MSB is set does give you an unbiased result.