The goal is to generate string password
of length
characters among alphabet
, with uniform distribution (assuming alphabet
does not contain duplicate characters), while minimizing consumption of octets drawn from a source assumed uniformly random (hereafter just octets).
A bug in the original code suppressed the first character of alphabet
on the left of the generated password, creating a bias for any remaining left character.
The current code seems correct: it generates a uniform arbitrarily large integer that can be thought as index of the generated password in a lexicography sorted vector of all possible passwords, then deduce the password by expressing that integer in a base corresponding to alphabet
. This is conceptually clean, but:
- Contrary to the objective, it frequently over-consumes octets. The underlying cause is that Go's implementation of
rand.Int(rand.Reader, max)
(by crypto/rand#Int or math/big/nat#random, I can't tell) repeatedly generates a uniformly random integer less than max
rounded up to the next power of two, until that integer is less than max
. For a password of 2 characters among 17, 2 octets are consumed at each iteration; the average is over 3.5 octets per password; 16 octets or more are consumed over once in 336, with no upper limit.
- Average execution time is quadratic with the length of the password, rather than linear for simpler algorithms. That's because cost of modular division grows linearly with the length of the number divided.
- While the language Go comes with an arbitrary precision integer library, not all languages do; and languages that do (like Java) sometime are used in an environment where that library is unavailable (e.g. most Java Cards).
Unless the length of alphabet
is a power of two, whatever method introducing no bias can consume unbounded octets. Proof:
- Assume a method always consume at most B octets and has no bias.
- There's also no bias for a method always consuming exactly
B
octets, obtained by throwing away octets in the end as necessary.
- That method has 2B possible inputs and
length(alphabet)
length
possible outputs. It has no bias, hence the later must divide the former.
- Hence
length(alphabet)
must be a power of two.
It is hard to tell if the use of big
makes it more or less difficult to exhibit a timing dependency or other side-channel leaking some info about the generated password.
I can't tell what RNG is actually used, much less if it is cryptographically sound and properly seeded.
A fixed-precision algorithm
Note: this is work in progress, missing an implementation (more readable to the OP), and optimizations to reduce octet consumption when len(alphabet)
is large.
Here is pseudocode for a method without arbitrary precision arithmetic. It is simple, fast, yields no bias, and is competitive with the question's method on consumption of random bytes when len(alphabet)<80
(in particular, on likelihood of large over-consumption for some parameters). All variables are non-negative integers less than 256*len(alphabet)
and conveniently fit integer variables.
- Set $n\gets 256$
[ $n$ is the number of possible input symbols (here, bytes) ]
- Set $k\gets$
len(alphabet)
[ $k$ is the number of possible output symbols]
- Set $r\gets0$
Set $s\gets1$
[ $s$ is the number of possible values for randomness buffer $r$ ]
- Set the password to empty
- For each character to be generated
[ $r$ is uniformly random with $0\le r<s<n$ ]
- While $r\ge\lfloor s/k\rfloor\cdot k$
- set $r\gets r-\lfloor s/k\rfloor\cdot k$
set $s\gets s-\lfloor s/k\rfloor\cdot k$
[ $r$ is uniformly random with $0\le r<s<k$ ]
- Get one new uniformly random symbol $x$
[ $x$ is uniformly random with $0\le x<n$ ]
- Set $r\gets r\cdot n+x$
Set $s←s\cdot n$
[ $r$ is uniformly random with $0\le r<s<k\cdot n$ ]
- Let $y\gets r\bmod k$.
[ $y$ is uniformly random with $0\le y<k$ ]
- Let $r\gets \lfloor r/k\rfloor$
Let $s\gets \lfloor s/k\rfloor$
[ $r$ is uniformly random with $0\le r<s<n$ ]
- Append to the password the character at index $y$ in
alphabet
Proof of correctness follows from the comments and arithmetic facts. More there, including why this is economical on randomness consumed (no claim of optimality). Despite the simplicity, I fail to find a reference in the literature.
Notation: to the Go programmer, $\lfloor r/k\rfloor$ is r/k
and $r\bmod k$ is r%k
.
Extension: One can modify $n$ at the second bullet of step 1 (e.g. to adapt to input symbols variably chosen by dice or coin throw). One can can modify $k$ after step 4 (e.g. to generate passwords always starting with a letter then also allowing digits), but that also requires re-initializing $r$ and $s$ (which looses some randomness), or careful adjustment of these variables.
Caution: I often get my answers correct only after many revisions, and we are only at the second version of the pseudocode itself.