Does my code have modulo bias I am writing a password generator in Go, but I want to make sure I am avoiding modulo bias.

My solution is to get a random number from crypto/rand in the range [0, len(alphabet) ** passwordLength),
and then encode that into the alphabet by dividing by len(alphabet), and using the remainder as an index into the alphabet.

if length == 0 {
    return "", nil
}
if len(alphabet) == 0 {
    return "", errors.New("Alphabet has length 0")
}

// Reading from rand.Reader once for each character would read more bits than necessary.
base := big.NewInt(int64(len(alphabet)))
max := big.NewInt(0).Exp(base, big.NewInt(int64(length)), nil)
num, err := rand.Int(rand.Reader, max)
if err != nil {
    return "", errors.Wrap(err, "Cannot get random data")
}

m := big.NewInt(0)
password := make([]rune, length)
// Add characters in reverse, so that the encoded characters
// follow the same order as the bytes read from rand.Reader.
for i := length-1; i &gt;= 0; i-- {
    // Divmod sets num = num / base,
    // and m = num % base.
    num.DivMod(num, base, m)
    password[i] = alphabet[int(m.Int64())]
}

return string(password), nil
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)&lt;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&lt;s&lt;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&lt;s&lt;k$ ]
Get one new uniformly random symbol $x$
[ $x$ is uniformly random with $0\le x&lt;n$ ]
Set $r\gets r\cdot n+x$
Set $s←s\cdot n$
[ $r$ is uniformly random with $0\le r&lt;s&lt;k\cdot n$ ]

Let $y\gets r\bmod k$.
[ $y$ is uniformly random with $0\le y&lt;k$ ]
Let $r\gets \lfloor r/k\rfloor$
Let $s\gets \lfloor s/k\rfloor$
[ $r$ is uniformly random with $0\le r&lt;s&lt;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.