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

最近研究晶片讀卡機產生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

 

 

 

參考


隨機數

srand

全局唯一識別元

RNGCryptoServiceProvider

亂數產生器:Random 與 RNGCryptoServiceProvider