使用從 nextInt(6)+1 生成的輸出反轉 Java 種子
給定一組 1-6 範圍內的數字：
$$ 3,4,3,4,5,6,2,3,1,5,2,3,6,2,2,3,3,6,6,4,5,2,5,3,5,2,4,4,2,6,3,6,1,5,1,3,6,1,1,2,2,4,5,3,1,2,3,4,4,6 $$ 使用 Java 的 nextInt(6)+1 生成，是否可以對其進行逆向工程以找到種子？
在研究 Java 的原始碼後，我了解到 nextInt() 方法是這樣工作的：
public static int nextInt(int n){ if (n <= 0) throw new IllegalArgumentException("n must be positive"); if ((n & -n) == n) // i.e., n is a power of 2 return (int) ((n * (long) next(31)) >> 31); int bits, val; do { bits = next(31); val = bits % n; } while (bits - val + (n - 1) < 0); //do, until its a positive number return val; }由於在這種情況下n是 6，它不是 2 的冪，所以它執行這部分程式碼：
do { bits = next(31); val = bits % n; } while (bits - val + (n - 1) < 0); //do, until its a positive number return val;它現在呼叫 next(31) ，這是它本質上通過線性同餘生成器執行的程式碼
public static int next(int bits){ seed = (seed * 0x5DEECE66DL + 0xBL) & ((1L << 48) - 1); return (int) (seed >>> (48 - bits)); }這個 31位數字作為 int 返回並分配到位
最後我們做位% 6 ，這給出了最終值。
我有幾個問題：
(1) 這行程式碼的目的是什麼？
while (bits - val + (n - 1) < 0);(2) 如何逆向工程並從該過程生成的一組數字中找到種子？
這行程式碼的目的是什麼？
while (bits - val + (n - 1) < 0);子句法的角度來看，它結束了
do上面的打開。從功能的角度來看，它使生成的偽隨機數在指定的間隔上一致。我將重點放在後面的方面。假設
n是 $ 3\cdot2^{29}, $ （即3<<29）而不是 $ 6 $ . 在聲明之後，bits = next(31);這個數量是均勻隨機的 $ [0,2^{31}) $ . 因此val = bits % n;是
bits機率為 75%；然後統一 $ [0,3\cdot2^{29}) $- 或
bits-(3<<29)機率為 25%；然後統一 $ [0,2^{29}) $因此，在 之前
while，val在 $ [0,2^{29}) $ 機率為 50%，在 $ [2^{29},3\cdot2^{29}) $ 機率為 50%。第二個區間是第一個區間的兩倍大，我們看到val在整個區間上與均勻相差很遠 $ [0,3\cdot2^{29})\ $ !在有問題的
while第二個項目符號中重複循環，從而使結果在整個間隔上保持一致 $ [0,3\cdot2^{29}) $ .小數字的替代解釋
想像一下，從 $ b=0 $ ，四次：我們加倍 $ b $ ， 然後加 $ 1 $ 至 $ b $ 如果我們從公平的硬幣投擲中得到尾巴。結果是 $ b $ 一個小於的非負整數 $ 2^4=16 $ ，並且這些中的每一個 $ 16 $ 整數同樣可能。也就是說，結果是一個離散的均勻隨機數 $ b $ 在 $ [0,16) $ .
由此我們想要一個統一的隨機數 $ v $ 在 $ [0,6), $ 就像
nextInt(6)被賦予任務一樣。問題是，如果我們使用固定的值分配 $ b $ 從 $ [0,16) $ 的值 $ v $ 在 $ [0,6) $ ，結果不可能一致。我們能得到的最多的是 $ 4 $ 的值 $ v $ 有機率 $ 3/16 $ , 和 $ 2 $ 其他 $ 2/16 $ . 想分開 $ 16 $ 薄荷糖（ $ b $ ） 進入 $ 6 $ 人（ $ v $ ).一個簡單的解決方案是：當 $ b $ 在 $ [0,6) $ , 那是我們的 $ v $ . 什麼時候 $ b $ 在 $ [6,12), $ ， 我們的 $ v $ 是 $ b-6 $ . 否則，我們再試一次，生成另一個 $ b $ 使用投擲硬幣。這就是程式碼在它的
do … while循環中所做的，只有 $ 2^{31} $ 使用next(31)我們的類比使用的地方 $ 2^4 $ 和投擲硬幣；用於bits_ $ b $ ，並且val對於 $ v $ .題外話：怎麼了
bits - val + (n - 1) < 0？人們想知道如何
while (bits - val + (n - 1) < 0);設法完成上述操作。bits是在範圍內[0, 0x7FFFFFFF]，n是 6，val是bits % n，因此val < bits成立並且bits - val是非負的。但這並不意味著它bits - val + (n - 1)是非負數，因為這些操作是按32 位的補碼算法進行的。這就是
intJava、許多其他電腦語言和大多數現代電腦硬體在將有符號整數作為 32 位量進行操作時的工作原理。如果int數量u和v表示整數 $ u $ 和 $ v $ , 這些整數都在範圍內 $ [-2^{31},2^{31}-1] $ , 那麼u + v是一個int表示整數的量 $ w $ 在範圍內 $ [-2^{31},2^{31}-1] $ 和 $ u+v\equiv w\bmod2^{32} $ ，即根據定義 $ u+v-w $ 的倍數 $ 2^{32} $ ，並取決於 $ (u,v) $ 多個可以是 $ 0 $ , $ 2^{32} $ ， 或者 $ -2^{32} $ . 到底， $ w $ 是整數 $ ((u+v+2^{31})\bmod2^{32})-2^{31} $ . 該算術是可交換的，關聯的，具有中性零，並且每個元素都有對立面。一個警告： $ -2^{31} $ ，即-0x80000000與零共享作為它自己的對立面的屬性。例如，如果
bits是 $ 2^{31}-2 $ ,val是 $ 0 $ ,bits - val是 $ 2^{31}-2 $ ,bits - val + (n - 1)是 $ ((2^{31}-2+(6-1)+2^{31})\bmod2^{32})-2^{31} $ ， 那是 $ ((2^{32}+3)\bmod2^{32})-2^{31}=3-2^{31} $ ，這是負面的。對於那些只想繼續前進的人：條件
bits - val + (n - 1) < 0在邏輯上等同於bits - val >= ((long)1<<31) + 1 - n（沒有溢出，只有非負數，感謝long64 位）。現在應該很明顯，
bits - val + (n - 1) < 0當bit在其區間的頂部時成立[0, 0x7FFFFFFF]。留給讀者作為練習，以表明間隔的其餘部分包含n整數倍數，因此在所有n值都是val的假設下，循環退出時的所有值的可能性完全相同bits。一名逆向工程師如何
那已經完成了。這個問題已經對算法進行了逆向工程，甚至更多：通過刪除執行緒安全的東西（或及時返回以獲取添加之前的原始碼），從最近的 Java 環境中簡化程式碼；並考慮刪除在這種情況下明顯無法訪問的程式碼部分。
並從這個過程生成的一組數字中找到種子？
下一步是：計算
while語句中的條件在何時n為真的機率 $ 6 $ ，並決定對這種情況可以做些什麼。然後繼續。有幾種解決途徑：
- 蠻力，嘗試一切 $ 2^{48} $ 初始狀態值。這是可行的，但不優雅且需要大量資源。
- 將上述搜尋空間減少一倍 $ 6 $ 通過利用可用的第一個結果。
- 使用那個 $ 6 $ 甚至是從 48 個種子中獲得 18 個位（以公平的機率），然後蠻力其餘的。這是相對簡單和有教育意義的。我的這個答案中對此進行了概述。與上述調整的一些組合有效。
- 使用 SAT 求解器（在相同的答案中）的一種可以很好工作但我沒有費心嘗試的方法。
可能還有其他方法，但如果這里或這裡有任何適用的方法，我就錯過了。
如果卡住了，請在目前問題的底部說明是什麼時候。