這裡介紹一種方法,可從連續出現的數字序列,回推線性同餘函數的相關參數。先聲明一下,密碼學、亂數、數論並不是我的專長,只是最近看到有人問,碰巧我讀過而已,如果內容有錯漏歡迎指正。這裡介紹的只是通俗易記的做法,可能不是目前最好的方法。

線性同餘法是目前常見的偽亂數產生法之一,可以寫成:

x[n] = (a * x[n-1] + c) mod m

其中 a、c、m 為根據某些原則小心選定的常數,這裡不多介紹。假如我們取

  • a = 11
  • c = 5
  • m = 31
  • x[0] = 3

則得到一個週期31的序列:

7, 20, 8, 0, 5, 29, 14, 4, 18, 17, 6, 9,
11, 2, 27, 23, 10, 22, 30, 25, 1, 16, 26,
12, 13, 24, 21, 19, 28, 3, 7, ...

假如我們只知道其中片段連續數字,例如 7, 20, 8, 0, 5, 29, 14, 4,要如何推測接下來的數字呢?首先要得到 m,這並不容易,不過取前4個數字即可利用下面這個行列式可以求得 m 的整數倍 m* 。

| 7 20  1|
|20  8  1|
| 8  0  1|

這個行列式算出來的 m* = 248 = 31 * 8,確實符合我們一開始選擇的 m,但是現在我們假裝不知道 m 是多少。從 m* 猜測 m 有一些方法,首先 m 通常不會亂選,常見的選擇之一是梅森質數,或者為了速度起見選用2的次方。在這個例子裡 8 和 31 各自滿足一項條件,看一下數字範圍就知道不可能是 8,所以一定是31。

再者,假如我們得到的序列夠多,就可以利用上面的行列式求出多組 m* ,然後算一下 gcd 就八九不離十。這裡我們再取 5, 29, 14, 4,套用上面的行列式得到 465,算 gcd(248, 465) = 31。

有了 m 之後我們就可以解下列的方程組:

7a + c = 20 (mod 31)
20a + c = 8 (mod 31)
8a + c = 0 (mod 31)

細節就不多說了,總之可以兩兩相減把 c 都消掉,再把 a 求出來。如果只打算從 x[n-1] 預測 x[n],求出 a 以後其實也沒有必要再求 c 了,直接用下面算式就可以

x[n] = (a*x[n-1] + x[1] - a*x[0]) (mod m)

舉例來說,我們取 0 和 5 當成首兩項,求 4 的下一個數:(11 * 4 + 5) mod 31 = 18,和前面完全吻合。

這裡只是線性同餘法最簡單的情形,實用的亂數產生器通常還會在輸出時做一些 bit shift/mask 等等修飾,因此從輸出結果逆推常數會困難很多。


延伸閱讀

上面方法已經有人寫成程式:www.reteam.org/papers/e59.pdf

以下這篇是比較正規的作法,而且可以套用到更廣義的多項式同餘:

Joan Boyar (1989). "Inferring sequences produced by pseudo-random number generators". Journal of the ACM 36 (1): 129–141. DOI:10.1145/58562.59305.

Marsaglia,G. (1968). Random Numbers fall mainly in the planes. Proceedings of the National Academy of Sciences,61,25-28

novus 發表在 痞客邦 PIXNET 留言(2) 人氣()


留言列表 (2)

發表留言
  • 悄悄話
  • novus
  • 我怕樓上看不到悄悄話,所以在這裡回應:

    x[n] = (a * x[n-1] + c) mod m .....(1)

    x[n] = (a * x[n-1] + x[1] - a * x[0]) (mod m) .....(2)

    兩個算式其實是同一回事,只是 (1) 明確把 c 求出來,(2) 則是隱含在算式中。

    用法的差別,如果你要用 (1) 求 x[n],必須要先求出 a, c, m 三個常數,並且 x[n-1] 為已知。

    如果要用 (2) 求出 x[n],除了求出a,m 之外,最少必須知道 x[n-1],以及另外兩個相鄰的數列元素 x[0]、x[1],這相鄰的兩數可從數列中任取,不要和 x[n-1] 相同即可。