如果我只知道輸出的模數，是否可以破解線性同餘生成器？
fgrieu 建議的編輯：
我有一百個整數 $ {0,1,2,3,4,5} $ 我懷疑是連續的值 $ \lfloor x_n/2^{16}\rfloor\bmod6 $ 計算為 $ x_{n+1}:=a\cdot x_n+b\bmod m $ ， 和 $ m=2^{31} $ ， 和 $ (a,b)\in{(214013,2531011),(22695477,1)} $ . 我如何驗證這個假設，找到 $ (a,b) $ 使用，並預測序列中的後續內容？
關於“在現代台式 PC 上以編譯語言完成一個稱職的實現將需要一秒鐘”的問題。
我寫了一些程式碼，但預計它們會執行 20 小時。
我正在嘗試找到隨機種子。首先，我將我的數據輸入到一個數組中。由於我不知道我的第一個數據是伺服器生成的第一個數字，我需要找出它。我只知道伺服器每週四下午 2:00 關閉，並在當天下午 2:45-3:45 左右重新啟動。當伺服器開啟時，ir 每 45 秒生成 3 個數字。我的數據是在周五凌晨 1:50 收集的，所以我的第一個數據可能是 LCG 的第 2400-2640 個數據。
我首先執行 rand 2399 次以丟棄前 2399 個數字。接下來，我循環 241 次以查找我的第一個數據是伺服器生成的第一個數字。（伺服器重啟時間不確定 2:45-3:45pm，每小時240個號碼）
我的方法是：如果第 2400 個 x 的第 16 位等於第 0 位 $ y_1 $ ，然後我檢查第 2401 個 x 的第 16 位和第 0 位 $ y_2 $ ， 等等。如果不相等，則中斷循環然後開始另一個循環，比較第 2401 個 x 和第 0 位 $ y_1 $ .
更好的方法是什麼？我兩週前才開始學習c++，請原諒我的無知。
#include <stdio.h> #include <stdlib.h> #include <stdint.h> #include <iostream> #include <inttypes.h> using namespace std; const int RESULT[3][7] = { {0,1,0,1,1,1,1}, {1,0,1,0,0,0,0}, {0,1,1,0,1,0,0} }; static unsigned long x; int test_rand(void) { x = 214013 * x + 2531011; // or is it 22695477*x+1 return (int)((x >> 16) & 0x7FFF); }; int onlyx16(void) { x = 214013 * x + 2531011; // or is it 22695477*x+1 return (x >> 16) & 1; }; void chk_seed(unsigned long seed) { int d1[241]{}; int d2[241]{}; int d3[241]{}; x = seed; for (int i = 0; i < 2399; i++) { test_rand(); } for (int i = 0; i < 241; i++) { d1[i] = onlyx16(); d2[i] = onlyx16(); d3[i] = onlyx16(); }; int correct = 0; for (int k = 0; k < 236; k++) { correct = 0; for (int i = 0; i < 7; i++) { if ((d1[i + k]) == RESULT[0][i]) { correct += 1; } else { correct = 0; break; }; if ((d2[i + k]) == RESULT[1][i]) { correct += 1; } else { correct = 0; break; }; if ((d3[i + k]) == RESULT[2][i]) { correct += 1; } else { correct = 0; break; }; }; if (correct == 21) { printf("seed 0x%d is OK\n", seed); printf("results forecast:\n"); for (int round = 0; round < 5; round++) { printf("round%d ", round + 1); int new_d[3]{}; for (int i = 0; i < 3; i++) { new_d[i] = test_rand()% 6; printf("%d", new_d[i]); }; printf("\n"); } }; } }; int main() { for (unsigned long seed = 0; seed < 0x100000000; seed++) chk_seed(seed); };$ x_{n+1} = (a \cdot x_{n} + b) \mod m $
在正常情況下， $ x_{n+1} $ 和 $ x_n $ 是已知的。但現在我只知道 $ x_n\mod 6 $ 和 $ x_{n+1}\mod 6 $ .
我在Google上搜尋了很多網站，但我只找到一個關於這個問題的問題。
但是，這不是很清楚，讀完之後我仍然不知道該怎麼辦。我希望有人可以提供一些數學或範常式式碼，以便我可以從反複試驗中學習。
我想找到 a,b,m 然後使用我在此處找到的 C++ 原始碼來暴力破解種子。
我在這裡找到了一個關於如何找到m的答案，但我不知道 $ x_{n+1} $ 和 $ x_n $ .
https://security.stackexchange.com/questions/4268/cracking-a-linear-congruential-generator
我是這個話題的新手，但是我非常想破解這個PRNG，這個PRNG讓我吃了不少苦頭，我因為這個PRNG決定學習程式。謝謝您的幫助！
根據修改原始問題的評論：OP 推測 100 位數字 $ y_n $ 在 $ {0,1,2,3,4,5} $ 他們擁有使用 C(++) 表達式獲得，相當於
rand()%6使用rand()基於線性同餘生成器的（非加密）PRNG，程式碼相當於static unsigned long x; int rand(void) { x = 214013*x+2531011; // or is it 22695477*x+1 return (int)((x>>16)&0x7FFF); }請注意 $ x $ 至少是 32 位，但只有低位 31 位很重要，因為
(x>>16)&0x7FFFC 執行unsigned long乘法運算並截斷不適合變數的高位位。抽象程式細節，猜想是 $ x $ 每進化 $ x_{n+1}:=a\cdot x_n+b\bmod m $ 和 $ m=2^{31} $ 和 $ (a,b) $ 對於一些被認為是的固定常數 $ (214013,2531011) $ 或者 $ (22695477,1) $ . 並
rand()輸出位 30…16 $ x $ 就這樣 $ y_n:=\lfloor x_n/2^{16}\rfloor\bmod 6 $ 被給予 $ n=0 $ 至 $ 99 $ （種子是一個未知整數 $ x_{-1} $ 在一些無關緊要的範圍內，因為只有 $ x_{-1}\bmod m $ 很重要；我們最好試著找到 $ x_0 $ 反正）。OP詢問是否有可能證實或證實該猜想，並且（如果為真）找到哪個 $ (a,b) $ 被使用並預測序列中接下來的內容。
是的，這是可能的，非常有信心。所考慮的 PRNG 的有效狀態為 31 位，只考慮了兩個 PRNG，它們對於模擬目的是可以通過的，因此我們應該能夠找到它們的狀態，並且使用多一點 $ 31+1=32 $ 一點資訊；我們得到 $ 100\cdot\log_2(6)\approx258.5 $ 位，這將給予充分的確認。
最簡單的就是嘗試對兩個猜想 $ (a,b) $ ，並探索可能的值 $ x_0 $ . 只有 $ 2^{31} $ , 知道 $ y_0 $ 允許系統地減少一個因素 $ 6 $ . 以下每一個 $ y_i $ 進一步消除 $ 5 $ 候選人出 $ 6 $ . 如果沒有候選人在所有 $ y_i $ , 假設被推翻。如果找到匹配項，我們知道哪個 $ (a,b) $ 我們使用，並且可以計算額外的 $ y_i $ . 在現代台式 PC 上，以編譯語言完成一個稱職的實現將需要一秒鐘的時間。
但也許想用 0.2美元的電池執行現代 0.5美元的 CPU來實時打破這件事，或者堅持使用 1970 年代的可程式計算器或ENIAC。請注意 $ 6 $ 是偶數，除數是 $ 2^{16} $ . 它遵循 $ y_n\bmod 2 $ 有點 $ 16 $ 的 $ x_n $ . 另請注意，由於 $ m $ 是二的冪，變化的有點 $ x_n $ 不會傳播到的低階位 $ x_{n+1} $ . 如果遵循第 16 位 $ x_n $ 僅取決於低 17 位 $ x_0 $ . 我們知道第 16 位 $ x_0 $ ，因此最多需要測試 $ 2^{16} $ 位 15…0 的候選者 $ x_0 $ . 然後我們可以找到上面的其他 14 位。這種分而治之的方法將允許在現代 CPU 上處理更大的參數，例如
x類型變數uin64_t和。return x>>33我想知道如果我們能做些什麼 $ a $ , $ b $ 和/或 $ m $ 是未知的。
以上註意事項：
- 它使用電腦科學中的主要約定（以及密碼學，除了 DES 等少數例外）：位從 0（低位）開始計數，因此如果一個非負整數 $ v $ 以二進製表示為 $ k $ 位 $ b_j $ ， 然後 $ v=\sum b_j $ 和 $ 0\le j<k $ . 在 big-endian 約定中，位 0 寫在右邊： $ 6\times7=42 $ 十進制是 $ 110\times111=101010 $ 在二進制。
- 電腦變數
x至少是 32 位的，但只有低位 31 位（0 到 30）才重要並用於 $ x_n $ ， 因此 $ 0\le x_n<m=2^{31} $ . 的輸出rand()至少是 16 位，但只有低 15 位（0 到 14）才重要，其他的都是零，因此 $ 0\le $rand()$ \le $RAND_MAX$ =2^{15}-1 $ . 如果 $ 0\le i<15 $ 然後位 $ j $rand()匹配位的輸出 $ j+16 $ 的x。它遵循第 0 位 $ y_n $ 匹配第 16 位 $ x_n $ .（題外話）對目前程式碼的評論：
它試圖使用通過
6平均實現的加速。我認為這不需要以秒為單位達到執行時間，如果
- 我們探索可能的值 $ x_0 $ ，而不是種子之前的許多步驟。
- 我們用那個 $ x_0 $ 是 31 位的，因此我們可以將外部搜尋限制為 [
0,0x7fffffff] 即 $ 2^{31} $ 候選人 $ x_0 $ .- 我們使用我們知道的 $ y_0 $ ，因此 $ x_0=2^{16}\cdot(6\cdot u+ y_0)+v $ 為了 $ 0\le u<\lceil2^{15}/6\rceil $ 和 $ 0\le v<2^{16} $ ，這限制在大約 $ 2^{31}/6 $ 候選人 $ x_0 $ .
- 我們優化了檢查候選人的測試 $ x_0 $ 反對 $ y_1 $ 在內部循環上 $ v $ .
可選加速注意的本質
6是先找到第 16…0 位 $ x_0 $ 匹配值 $ y_0 $ 收集，然後位 30…17。程式碼不這樣做！有了這種加速，執行時間將下降到毫秒。我們需要完整的價值觀 $ y_n $ 收集（在非優化搜尋和優化搜尋的第二部分），但它們似乎在輸入中不可用，我猜是 $ y_n\bmod2 $ . 此外，我不明白為什麼那是在二維數組
RESULT[3][7]中。什麼時候 $ x_0 $ 找到，如果有必要在已知步數之前找到種子（或者更確切地說是 30…0 位），可以通過使用 $ x_{n-1}:=a^{-1},(x_n-b)\bmod m $ 在哪裡 $ a^{-1} $ 是的模逆 $ a $ 模組 $ m $ .
這是沒有可選加速的工作程式碼（因此能夠使用奇數的最終縮減模數 $ r $ 問題在哪裡
6）。線上嘗試！#include <stdint.h> #include <stdio.h> #include <inttypes.h> #define A 214013 // for VC; 22695477 for BC #define B 2531011 // for VC; 1 for BC #define R 6 // modulus, in [2, 32768] // static_assert(A > 0 && A % 8 == 5, "A mod 8 must be 5"); // static_assert(B > 0 && B % 2 == 1, "B mod 2 must be 1"); // static_assert(R >= 2 && R <= 32768, "R must be in [2, 32768]"); // decide modulo, reduced when R is a power of two #define M ((uint32_t)(((R-1)&R)!=0 ? 0x8000 : R)<<16) // Sequence of yn for VC (a=214013, b=2531011), n=6, seed=1639326023 // If R is a power of two, ceil(16/log2(R))+1 entries are enough // Otherwise, that's ceil(31/log2(R)) entries, thus 12 for R=6. const int16_t y[] = { 0,5,3,0,4,3,1,0,4,5,4,4,4,5,5,3,0,2,0,5,4,5,0, // 0,2,5,1,3,5,5,5, }; // modular inverse INVA of A modulo M #define INVA (IN_A(IN_A(IN_A(IN_A((uint32_t)A))))&(M-1)) #define IN_A(v) (v*(2-v*A)) int main(void) { // decide starting x0 so that it matches y0 const uint32_t y0 = y[0], y1 = y[1]; int32_t x0 = (int32_t)(((M >> 16) - y0) / R * R + y0) << 16 | 0xffff; uint32_t found = 0; printf("generator: ((int)((x = %" PRIu32 " * x + %" PRIu32 ") >> 16) & 0x7fff) %% %u\n", (uint32_t)A, (uint32_t)B, (unsigned)R); while (x0 >= 0) { uint32_t x1 = A * (uint32_t)x0 + B; do { // assert( (x0 >> 16) % R == y0); // assert( x1 == A * (uint32_t)x0 + B); if (((x1 >> 16) & 0x7fff) % R == y1) { uint32_t x = x1; int n; for (n = 2; n < sizeof(y) / sizeof(*y); ++n) if ((((x = A * x + B) >> 16) & 0x7fff) % R != y[n]) goto nxt; // found a solution x = (INVA * ((uint32_t)x0 - B)) & (M - 1); printf("x0 can be %" PRId32 ", that is seed=%" PRIu32 " modulo 0x%" PRIx32 ", yielding:\n", x0, x, M); // prove out point by showing the output for (n = 0; n < sizeof(y) / sizeof(*y) + 8; ++n) printf(" %d", ((int)((x = A * x + B) >> 16) & 0x7fff) % R); printf("\n"); ++found; } nxt: x1 -= (uint32_t)A; } while (((x0--) & 0xffff) != 0); x0 -= (int32_t)(R - 1) << 16; } printf("found %" PRIu32 " solution%s\n", found, found > 1 ? "s" : ""); return 0; } // yielding: // generator: ((int)((x = 214013 * x + 2531011) >> 16) & 0x7fff) % 6 // x0 can be 531633902, that is seed=1639326023 modulo 0x80000000, yielding: // 2 3 4 1 5 1 1 5 4 0 3 2 2 5 5 3 5 5 3 4 0 1 1 4 1 3 3 2 5 4 4 // found 1 solution