问题描述
大桥游戏的玩法是那些在四个选手随机分布的52种不同的扑克牌,每个玩家有13张牌结束了:所谓的交易。 。在获取生成随机的交易描述如下程序的要求:
This document goes on to state that pseudo random generators cannot be used to generate deals as seeing the first elements of a pseudo random sequence will make it possible to compute the seed used and thus enable a hacker to predict the deals that will follow.
Moreover, as most pseudo random generators take a seed of 32 bits it should follow that these generators will be capable of producing at best 2^32 different Bridge deals as opposed to the required 2^96 and that, following the so called Birthday paradox, it is likely that the same deal will be produced after the square root of 2^32 deals.
The author of the document that describes the requirements of a Bridge deal producing application has written a program, used world wide to produce random deals, that generates a 96 bit seed using a human typing randomly on the keyboard. In fourteen years no flaws have been demonstrated in this approach.
I would like to write a routine that forgoes the need to use human input to generate the seed required.
In comes the RNGCryptoServiceProvider
. I used this using the code below to generate random numbers, first in the range 1 to 52, then in the range 1 to 51, and so forth until one card remains.
Testing the resulting deals I am pretty confident that this code is capable of producing any deal it is capable of with the same probability and that the chance of any card ending up with one of the four players equals 0.25.
But as the strength of the seed used in the RNGCryptoServiceProvider is not known to me I am wondering if:
- This code will be able to, or can be adapted to, producing 2^96 different deals.
- This code's next deal is not going to be predictable.
EDITThe method to obtain random numbers previously mentioned in this question was flawed. This distracted from the main question, being if this code is able to produce 2^96 distinct Bridge deals. I replaced the random number generator with the one published by Stephen Taub and Shawn Farkas in the MSDN magazine
Code used to produce a cryptographically secure random number in the ranges 1-52, 1-51, and so on up to 1-2, taken from 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));
}
}
}
Once you have a random number generator (RNG) that is "truly uniform", do the following:
Initialize the RNG with a seed based on an external source. This could be keyboard input, the program start time, or a number of other things. From my research, it appears that the RNGCryptoServiceProvider already does this part.
Most importantly, at (frequent) intervals, draw a number from the RNG. Just throw the number away, the important part is that you have "cycled" the RNG. If desired, you can make the intervals random to increase unpredictability. More cycles are better, so I would pick a max interval as low as you feel you can go.
- There are two choices for the random intervals, (a) use a weaker RNG (which they do use), and (b) ignore it. In a slot machine, the user's input (pressing "SPIN") causes the actual RNG draw. Combined with a sufficiently quick cycling interval, it's considered unpredictable enough.
- There are two choices for the random intervals, (a) use a weaker RNG (which they do use), and (b) ignore it. In a slot machine, the user's input (pressing "SPIN") causes the actual RNG draw. Combined with a sufficiently quick cycling interval, it's considered unpredictable enough.
(Somewhat optional) Don't draw all the numbers in a row. Wait a random amount of time (allowing the RNG to cycle a random amount of times) before drawing the next number (or set of numbers). Because the initial draw is likely based on user input, you should be able to get away with drawing them all at once. It can't hurt though.
This is the process used in the gaming (gambling) industry, where unpredictable RNGs are heavily regulated (and of course, required). Draws involving 500 cards (from 100 separate decks) are done using this method. Note that the RNGs used typically take 32-bit seeds, and are perfectly acceptable.
这篇关于如何才能RNGCryptoServiceProvider被用来生成桥手?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!