这个用于生成随机数的算法叫什么名字？

Question

我已经对生成随机数的以下算法进行了逆向工程；

int __cdecl sub_40BB60()
{
  char v0; // si@1
  int v1; // edx@1
  int v2; // ecx@1
  unsigned int v3; // eax@1
  int v4; // edi@1
  int v5; // esi@1
  int result; // eax@1

  v0 = random_state;
  v1 = dword_685440[((_BYTE)random_state - 3) & 0xF];
  v2 = dword_685440[random_state] ^ v1 ^ ((v1 ^ 2 * dword_685440[random_state]) << 15);
  v3 = ((unsigned int)dword_685440[((_BYTE)random_state - 7) & 0xF] >> 11) ^ dword_685440[((_BYTE)random_state - 7) & 0xF];
  v4 = v3 ^ dword_685440[random_state] ^ v1 ^ ((v1 ^ 2 * dword_685440[random_state]) << 15);
  dword_685440[random_state] = v4;
  v5 = (v0 - 1) & 0xF;
  result = dword_685440[v5] ^ v2 ^ v4 ^ 32 * (v4 & 0xFED22169) ^ 4 * (dword_685440[v5] ^ ((v2 ^ (v3 << 10)) << 16));
  random_state = v5;
  dword_685440[v5] = result;
  return result;
}

dword_685440 是一个 int[16] 数组，而且可以看到 random_state 发生了变化。

我认为这可能是一个扭曲算法。有人认识这个算法吗？

- kvanbere

Answer 1

看起来这可能是一个线性反馈移位寄存器算法。这些可以通过位移和异或操作在字级别上实现，这似乎就是它的实现方式。

- pjs

---

起初我持怀疑态度，但是当我注意到所有的& 0xF时，我认为你是正确的。 - kvanbere

Answer 2

我之前也曾对这段代码进行过逆向工程，并认为它会对其他人作为参考有用。

这是WELL512随机数生成器。这里有一个实现：https://github.com/masfj/RNG/blob/master/WELLRNG512.cpp

如果你正在寻找常量0xFED22169，在WELL-512中是找不到的。它的常量是0xDA442D20。代码本身已经被编译器进行了代数优化。

我最初反编译的代码如下：

DWORD a = g_state[g_stateIdx];
DWORD b = g_state[(g_stateIdx - 3) % 16]; 
DWORD c = a ^ b ^ ((b ^ 2 * a) << 15);
DWORD d = (g_state[(g_stateIdx - 7) & 0xF] >> 11) ^ g_state[(g_stateIdx - 7) & 0xF] ^ c;
DWORD e = d ^ c;
g_state[g_stateIdx] = e;
DWORD f = e ^ 0x20 * (e & 0xFED22169);
g_stateIdx = (g_stateIdx - 1) % 16;
DWORD g = g_state[g_stateIdx];
DWORD h = f ^ 4 * (g ^ ((c ^ (d << 10)) << 16));
g_state[g_stateIdx] = g ^ c ^ h;
return g_state[g_stateIdx];

这里的代码：

DWORD f = e ^ 0x20 * (e & 0xFED22169);

是一样的：

d  = a ^ ((a << 5) & 0xda442d20UL);

其中包含了WELL512常量0xda442d2d0。

((signed)0xda442d24 >> 5) == 0xfed2169
0x20 == 1 << 5

从记忆中来看，在线编译WELL512源代码，可以在VS2013或VS2015下生成完全相同的代码。

- Lloyd Macrohon

---

请注意Wikipedia Well512文章的第二句话指出其为LFSR。 - pjs