[.NET][C#]密碼學(隨機數筆記)

2016-09-11

最近研究晶片讀卡機產生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次，可接受的碰撞率而且還比較安全。