Re: Ternary Encoding :-)

Chax Plore <ftilojim@tznvy.pbz> wrote:

On 2025-01-03 06:03, Rich wrote:

Stefan Claas <pollux@tilde.club> wrote:

My old pads program is already updated.  It compiled flawlessly for
many different platforms, including macOS, but I do not know if they
all support TPM 2.0, like Windows and Linux does.
>
https://github.com/706f6c6c7578/pads

 
Looking over your pads program, while you are retreiving true random
numbers from the TPM chip, you are introducing a bias when you use the
random bytes from the TPM to output letters or digits.
 
Take for example your "letters" arm:
 
   if l {
     random, _ := tpm2.GetRandom(rwc, 5)
     for m := 0; m < 5; m++ {
       fmt.Printf("%c", 'A'+(random[m]%26))
     }
   }
 
Now, if I've decoded the awful documentation for the TPM2 module
properly [1] the tpm2.GetRandom call will return five bytes (presumably
unsigned bytes) of random data.
 
Then, you loop over the five bytes, outputting the letter that
corresponds to ASCII A plus the remainder after dividing the byte by
26.  Which is where you introduce a bias.
 
A byte will have a value from 0 to 255, for 256 total values.
 
But 26 does not evenly divide 256.  256/26 ~ 9.846
 
26 divides 256 evenly 9 times, no problem here.  That covers values 0
to 233.  But for any bytes returned from GetRandom that fall into the
range 234 to 255, you have only 21 possible values that can return from
the modulo.  So your remainder will be only 0 through 21.  You'll never
get 22 through 25 out, because there is not enough numeric range in the
"tail" to return 22 through 25 from the modulo.  So for any bytes with
values 234 to 255 from the TPM, you can return A through V but will
never return W, X, Y or Z.
 
So your resulting letters will have a bias for A through V.
 
The fix is easy, first check the value of the byte you are about to
use, and if it happens to be greater than 233, throw that byte away and
pull another from the TPM.

Why waste 8.98% of random bytes, especially when generating large
keys from slow source of randomness?

My post was to point out the bias, and offer a simple [1] solution that
is easy to understand.

Lumbroso's FastDiceRoller algorithm
consumes the exact number of bits needed to produce integer in requested
range: https://arxiv.org/abs/1304.1916

Interesting algorithm, thanks for the reference, although I'll have to
spend some time later giving it a go over to fully grok what it is
doing.


[1] Note that "simple" does not mean "optimal".