最近研究晶片讀卡機產生UN(EMV 9F37 Unpredictable Number)不可預期編號,過程中要使用隨機數演算法取值,來筆記幾種隨機種子對於偽隨機數結果的差異。
隨機數筆記
隨機數也稱亂數,英文是Random Number,經常使用在電腦抽獎系統;在統計學中,蒙地卡羅方法正是使用隨機數來作統計模擬。
在隨機數可以區分幾以下2種分類:
1.真隨機數(TRNG:True Random Number Generator)通常是運用物理現象產生的,像是擲銅板、骰子、求神擲筶,真隨機數需要同時具備統計學上的(隨機性)、密碼學安全偽隨機性(不可預測)及真隨機性(不可重現)
2.偽隨機數(PRNG:pseudorandom Number Generator)使用固定的電腦演算法計算出近乎是隨機的值,偽隨機數中的弱偽隨機數(PRNG)至少需要具備統計上的隨機性。
1.C# System.Random類別: 一般符合隨機方式的特定統計需求。
2.C# CSP中的RNGCryptoServiceProvider類別: 資訊安全上的需求使用。
這邊我們有6組測試組別:
- 1-4組分別使用4種隨機種子(預設、時間刻度、GUID、次數)
- 第5組C語言srand函數(線性同餘法)給隨機種子
- 第6組CSP使用Windows Crypto API
從1-100取隨機數值,短時間內各執行100次
過程中如果取出的數值如果重複,就醜1,我們來統計每一組執行100次後的醜度,希望結果至少不會出現統計學上的偏差。
短暫時間定義:秒殺的那一瞬間
各組的測試都Run 3次,驗證隨機數是否有可重現的問題。
1.預設隨機種子(CPU時間作為隨機數種子值(Random seed))
void rng1(int Range)
{
List<int> li = new List<int>();
int dup = 0;
for (int i = 0; i < Range; i++)
{
Random Rng = new Random();
int r = Rng.Next(1, Range);
if (li.Contains(r))
{
dup++;
}
else
{
li.Add(r);
if (li.Count <= 3) Console.WriteLine("CPU時間隨機數:{0} ", r);
}
}
Console.WriteLine("CPU時間隨機種子重複次數:{0}", dup);
}
2.時間刻度隨機種子
void rng2(int Range)
{
List<int> li = new List<int>();
int dup = 0;
for (int i = 0; i < Range; i++)
{
//Random Rng = new Random((int)DateTime.Now.Ticks);
Random Rng = new Random((int)DateTime.Now.Millisecond);
int r = Rng.Next(1, Range);
if (li.Contains(r))
{
dup++;
}
else
{
li.Add(r);
if (li.Count <= 3) Console.WriteLine("時間刻度隨機數:{0} ", r);
}
}
Console.WriteLine("時間刻度隨機種子重複次數:{0}", dup);
}
3.GUID隨機種子(指定全域唯一識別項Guid(globally unique identifier)作為隨機種子值(Random seed))
void rng3(int Range)
{
List<int> li = new List<int>();
int dup = 0;
for (int i = 0; i < Range; i++)
{
Random Rng = new Random(Guid.NewGuid().GetHashCode());
int r = Rng.Next(1, Range);
if (li.Contains(r))
{
dup++;
}
else
{
li.Add(r);
if (li.Count <= 3) Console.WriteLine("唯一識別項Guid種子隨機數:{0} ", r);
}
}
Console.WriteLine("唯一識別項Guid隨種子重複次數:{0}", dup);
}
4.次數隨機種子
void rng4(int Range)
{
List<int> li = new List<int>();
int dup = 0;
for (int i = 0; i < Range; i++)
{
Random Rng = new Random(i);
int r = Rng.Next(1, Range);
if (li.Contains(r))
{
dup++;
}
else
{
li.Add(r);
if (li.Count <= 3) Console.WriteLine("次數隨機種子隨機數:{0} ", r);
}
}
Console.WriteLine("次數隨機種子重複次數:{0}", dup);
}
5. C函式srng,固定種子3
[DllImport("msvcrt.dll")]
public static extern int srand(int seed);
[DllImport("msvcrt.dll")]
public static extern int rand();
void srng(int Range)
{
List<int> li = new List<int>();
int dup = 0;
srand(3);
for (int i = 0; i < Range; i++)
{
//srand(i);
//srand(time(NULL));
int r = rand() % Range;
if (li.Contains(r))
{
dup++;
}
else
{
li.Add(r);
if (li.Count <= 3) Console.WriteLine("srnd次數隨機數:{0} ", r);
}
}
Console.WriteLine("srnd重複次數:{0}", dup);
}
6.RNGCryptoServiceProvider
private static RNGCryptoServiceProvider rngCsp = new RNGCryptoServiceProvider();
void rng6(int Range)
{
List<int> li = new List<int>();
int dup = 0;
for (int i = 0; i < Range; i++)
{
byte[] randomNumber = new byte[4];
rngCsp.GetBytes(randomNumber);
int r = Math.Abs(BitConverter.ToInt32(randomNumber, 0)) % Range;
if (li.Contains(r))
{
dup++;
}
else
{
li.Add(r);
if (li.Count <= 3) Console.WriteLine("CSP隨機數:{0}", r);
}
}
Console.WriteLine("CSP重複次數:{0}", dup);
}
[TestMethod]
public void TestMethod1()
{
rng1(100);
Console.WriteLine("==================================");
rng2(100);
Console.WriteLine("==================================");
rng3(100);
Console.WriteLine("==================================");
rng4(100);
Console.WriteLine("==================================");
srng(100);
Console.WriteLine("==================================");
rng6(100);
Console.WriteLine("==================================");
}
測試結果:
總共各測試了3次
- 第一組醜99次,.NET預設用CPU時間作為隨機數種子值,短時間內每次都取出相同的值,每次都碰撞(頭昏),沒有隨機性。
- 第二組醜99次,短時間內也因為時間刻度種子相同也都取出相同的值,每次都碰撞(頭昏),沒有隨機性。
- 第三組醜38次,GUID種子是可接受的碰撞率。
- 第四組醜24次,更低的碰撞率,但在3次測試中,因為隨機種子固定是次數#(1-100),取出的亂數值及順序每次都相同,出現了可重現性的缺點!
- 第五組醜12次,碰撞率很低,雖然用C Library,但在3次測試中,因為隨機種子固定是次數#(1-100),取出的亂數值及順序每次都相同!出現了可重現性的缺點!
- 第六組醜33次,可接受的碰撞率而且還比較安全。
小結:
- 短暫時間內取大量相較安全的隨機數數:用CSP取隨機數,不易被預測。
- 短暫時間內取大量相較安全的隨機數數:用GUID作為隨機種子,也不易被預測。
- 短暫時間內取大量沒有安全需求的隨機數:可以用次數作為隨機種子,被猜到也沒有風險。
- 較長時間內取沒有安全需求的隨機數: 用預設或時間刻度作為種子就OK了
如果曾被弱掃拜訪過家裡,應該會熟悉:
CWE-330: Use of Insufficiently Random Values(不足夠安全的隨機數)
CWE-337: Predictable Seed in PRNG(弱偽隨機數中可預測的隨機種子)
CWE-339: Small Seed Space in PRNG(弱偽隨機數中隨機種子太小)
其他:
- 弱偽隨機數(PRNG)用GUID作為隨機種子相較時間或次數種子安全,但有資訊安全上的需求可以用CSP中的RNGCryptoServiceProvider類別。
- 硬體隨機數產生器(HRNG): 支付產業的應用上如果要取隨機數,記得要用PCI-approved hardware RNG
參考
亂數產生器:Random 與 RNGCryptoServiceProvider