我的程式碼是否有模偏差
我正在用 Go 編寫密碼生成器，但我想確保避免模數偏差。
我的解決方案是從crypto/rand中獲取 [0, len(alphabet) ** passwordLength) 範圍內的隨機數，然後通過除以 len(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 >= 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
目標是在 中生成字元字元串，
password分佈均勻（假設不包含重複字元），同時最小化從假設均勻隨機的源中提取的八位位組的消耗（以下簡稱八位位組）。length``alphabet``alphabet原始程式碼中的一個錯誤抑制了
alphabet生成密碼左側的第一個字元，從而對任何剩餘的左側字元產生了偏差。目前程式碼似乎是正確的：它生成一個統一的任意大整數，可以將其視為在所有可能密碼的字典排序向量中生成的密碼的索引，然後通過在對應於的基數中表示該整數來推斷密碼
alphabet。這在概念上是乾淨的，但是：
- 與目標相反，它經常過度消耗八位字節。根本原因是 Go 的實現
rand.Int(rand.Reader, max)（通過crypto/rand#Int或math/big/nat#random，我不知道）重複生成一個均勻隨機整數，小於max四捨五入到 2 的下一個冪，直到該整數小於max。對於 17 個字元中的 2 個字元的密碼，每次迭代消耗 2 個八位字節；每個密碼平均超過 3.5 個八位字節；16 個八位字節或更多字節在 336 次中被消耗一次，沒有上限。- 平均執行時間是密碼長度的二次方，而不是簡單算法的線性。這是因為模除的成本隨著被除數的長度線性增長。
- 雖然 Go 語言帶有任意精度整數庫，但並非所有語言都有；並且有時會在該庫不可用的環境中使用（例如Java）的語言（例如大多數Java Card）。
除非長度
alphabet是 2 的冪，否則任何不引入偏差的方法都會消耗無限的八位字節。證明：
- 假設一個方法總是最多消耗 B 個八位字節並且沒有偏差。
- 對於總是消耗
B八位字節的方法也沒有偏見，這是通過在必要時最終丟棄八位字節來獲得的。- 該方法有 2 B個可能的輸入和
length(alphabet)``length可能的輸出。它沒有偏見，因此後者必須劃分前者。- 因此
length(alphabet)必須是二的冪。很難判斷使用 是否
big會或多或少地表現出時間依賴性或其他側通道洩漏有關生成密碼的一些資訊。我不知道實際使用的是什麼 RNG，更不用說它是否在密碼學上是健全的並正確播種了。
固定精度算法
注意：這是正在進行的工作，缺少一個實現（對 OP 來說更具可讀性），以及在大時減少八位字節消耗的優化
len(alphabet)。這是沒有任意精度算術的方法的虛擬碼。它簡單，快速，不產生偏差，並且與問題的隨機字節消耗方法相比具有競爭力
len(alphabet)<80（特別是在某些參數可能過度消耗的可能性上）。所有變數都是小於256*len(alphabet)和方便地擬合整數變數的非負整數。
- 放 $ n\gets 256 $
$$ $n$ is the number of possible input symbols (here, bytes) $$
- 放 $ k\gets $
len(alphabet)$$ $k$ is the number of possible output symbols $$
- 放 $ r\gets0 $
放 $ s\gets1 $
$$ $s$ is the number of possible values for randomness buffer $r$ $$
- 將密碼設置為空
- 對於要生成的每個字元
$$ $r$ is uniformly random with $0\le r<s<n$ $$
儘管 $ r\ge\lfloor s/k\rfloor\cdot k $
- 放 $ r\gets r-\lfloor s/k\rfloor\cdot k $
放 $ s\gets s-\lfloor s/k\rfloor\cdot k $
$$ $r$ is uniformly random with $0\le r<s<k$ $$
- 獲得一個新的均勻隨機符號 $ x $
$$ $x$ is uniformly random with $0\le x<n$ $$
- 放 $ r\gets r\cdot n+x $
放 $ s←s\cdot n $
$$ $r$ is uniformly random with $0\le r<s<k\cdot n$ $$
讓 $ y\gets r\bmod k $ .
$$ $y$ is uniformly random with $0\le y<k$ $$ 3. 讓 $ r\gets \lfloor r/k\rfloor $
讓 $ s\gets \lfloor s/k\rfloor $
$$ $r$ is uniformly random with $0\le r<s<n$ $$ 4. 將索引處的字元附加到密碼 $ y $ 在
alphabet正確性的證明來自註釋和算術事實。還有更多，包括為什麼這對消耗的隨機性是經濟的（沒有聲稱是最優的）。儘管很簡單，但我無法在文獻中找到參考。
符號：對於 Go 程序員， $ \lfloor r/k\rfloor $ 是
r/k和 $ r\bmod k $ 是r%k。擴展：一個可以修改 $ n $ 在步驟 1 的第二個項目符號處（例如，適應由骰子或投擲硬幣選擇的輸入符號）。一個可以修改 $ k $ 在第 4 步之後（例如，生成始終以字母開頭的密碼，然後也允許數字），但這也需要重新初始化 $ r $ 和 $ s $ （這會失去一些隨機性），或者仔細調整這些變數。
警告：我經常在多次修改後才能得到正確的答案，而我們只是虛擬碼本身的第二個版本。
統計測試是密碼學的重要組成部分。這是檢查的替代方法，如果您修改程式碼，您可以有信心按需證明對自己沒有偏見。它也可以集成到單元測試中。
密碼通常是可列印的字元，比如 n 個字元。簡單地對長時間執行的 n*n 個字元的輸出進行直方圖。Go 可能在庫中有某種直方圖工具。然後執行最終返回機率值的卡方檢驗。這也可能在圖書館中提供（但我不熟悉 Go）。如果您必須自己直接從卡方值計算 p，您可以使用表格進行正態分佈。如果 p 似乎重複地在 0 和 1 之間均勻變化，那麼你就沒有偏見，瞧。