Bridge的游戏是用52种不同的扑克牌进行的,这些扑克牌随机分布在四个玩家中,每个玩家最终得到13张牌:所谓的"deal" . Roughly a little less than 2^96 Bridge deals are possible . 在this document中,生成随机交易的程序的要求描述如下:
软件应该能够生成所有可能的桥接交易,因为这也可以通过手动交易实现 . 软件应该以相同的概率生成每笔交易,而不受董事会编号,之前的手或任何其他情况的影响 . 即使在 Session 中看到所有其他交易之后,也无法预测交易 .
本文继续说明伪随机生成器不能用于生成交易,因为看到伪随机序列的第一个元素将使得计算所使用的种子成为可能,从而使黑客能够预测随后的交易 .
此外,由于大多数伪随机生成器采用32位的种子,因此应该遵循这些生成器将能够产生最多2 ^ 32个不同的桥接交易,而不是所需的2 ^ 96,并且遵循所谓的Birthday paradox,在2 ^ 32交易的平方根之后,可能会产生相同的交易 .
描述Bridge交易生成应用程序要求的文档的作者编写了一个程序,在世界范围内用于生成随机交易,使用键盘上的人类输入生成96位种子 . 十四年来,这种方法没有出现任何缺陷 .
我想编写一个例程,放弃使用人工输入来生成所需种子的需要 .
来了RNGCryptoServiceProvider . 我使用下面的代码来生成随机数,首先在1到52的范围内,然后在1到51的范围内,依此类推,直到剩下一张卡 .
测试产生的交易我非常有信心这个代码能够以相同的概率产生任何交易能力,并且任何一张牌最终与四个玩家之一的机会等于0.25 .
但由于我不知道RNGCryptoServiceProvider中使用的种子的强度,我想知道是否:
-
此代码将能够或可以适应,产生2 ^ 96个不同的交易 .
-
此代码的下一笔交易不可预测 .
EDIT 获得此问题中先前提到的随机数的方法存在缺陷 . 如果这个代码能够产生2 ^ 96个不同的Bridge交易,这就分散了主要问题 . 我用the one published by Stephen Taub and Shawn Farkas in the MSDN magazine替换了随机数发生器
用于生成加密安全随机数的代码,范围为1-52,1-51,依此类推,最高为1-2,取自this website
/// <summary>
/// Returns a random number within a specified range.
/// </summary>
/// <returns>
/// A 32-bit signed integer greater than or equal to <paramref name="minValue"/> and less than <paramref name="maxValue"/>; that is, the range of return values includes <paramref name="minValue"/> but not <paramref name="maxValue"/>. If <paramref name="minValue"/> equals <paramref name="maxValue"/>, <paramref name="minValue"/> is returned.
/// </returns>
/// <param name="minValue">The inclusive lower bound of the random number returned.</param>
/// <param name="maxValue">The exclusive upper bound of the random number returned. <paramref name="maxValue"/> must be greater than or equal to <paramref name="minValue"/>.</param>
/// <exception cref="T:System.ArgumentOutOfRangeException"><paramref name="minValue"/> is greater than <paramref name="maxValue"/>.</exception>
public override Int32 Next(Int32 minValue, Int32 maxValue)
{
if (minValue > maxValue) throw new ArgumentOutOfRangeException("minValue");
if (minValue == maxValue) return minValue;
Int64 diff = maxValue - minValue;
while (true)
{
//The cryptoProvider is of type RNGCryptoServiceProvider.
cryptoProvider.GetBytes(uint32Buffer); //The uint32Buffer has a size of 4 bytes.
UInt32 rand = BitConverter.ToUInt32(uint32Buffer, 0);
Int64 max = (1 + (Int64)UInt32.MaxValue);
Int64 remainder = max % diff;
if (rand < max - remainder)
{
return (Int32)(minValue + (rand % diff));
}
}
}
1 回答
一旦你有一个“真正统一”的随机数发生器(RNG),请执行以下操作:
使用基于外部源的种子初始化RNG . 这可以是键盘输入,程序开始时间或许多其他事情 . 根据我的研究,似乎RNGCryptoServiceProvider已经完成了这一部分 .
最重要的是,在(频繁)间隔,从RNG中抽取一个数字 . 只需抛弃数字,重要的是你已经“循环”了RNG . 如果需要,您可以随机设置间隔以增加不可预测性 . 更多的周期更好,所以我会选择一个你认为可以去的最大间隔 .
随机区间有两种选择:(a)使用较弱的RNG(它们使用的是),以及(b)忽略它 . 在老虎机中,用户's input (pressing 607407 ) causes the actual RNG draw. Combined with a sufficiently quick cycling interval, it'被认为是不可预测的 .
(有些可选)不要连续绘制所有数字 . 在绘制下一个数字(或一组数字)之前,等待一段随机时间(允许RNG循环一段时间) . 因为初始绘制可能基于用户输入,所以您应该能够立即完成所有绘制 . 但它不会伤害 .
这是游戏(赌博)行业中使用的过程,其中不可预测的RNG受到严格监管(当然,也是必需的) . 使用此方法完成涉及500张牌(来自100个单独的牌组)的抽签 . 请注意,使用的RNG通常采用32位种子,完全可以接受 .