非确定性随机数生成

• 下载源码（无EXE） - 101.8 KB
• 下载源码 - 101.8 KB

引言

提供的 C# WPF .NET 解决方案以非确定性的方式生成真正的随机数。 这些在密码学中最有用，并有助于防止侧信道攻击。 虽然此解决方案是针对 Intel 多处理器开发的，但针对具有单个处理器的机器可能会产生不同的结果。

什么是随机数序列？

例如（正如编辑友好地指出的那样）

"314159......." 是一个确定性例程的输出示例，用于生成随机数（如果它确实使用了一种算法来生成 pi 值）。 大多数随机数生成器都是这些类型； 它们使用特定的数学公式，通常需要一个“种子”值（通常使用系统计时器）。

使用确定性例程生成随机值有什么问题？ 在密码学中，如果使用的算法是已知的，那么只需知道生成器的初始种子就可以重现随机值。 为什么这是一个问题？ 嗯，使用随机数生成器来生成秘密“密钥”是很常见的。

那么我们如何创建非确定性随机值呢？ 很简单，我们必须求助于非算法方法（例如白噪声采样）或生成我们自己的 非确定性算法。

来自 Wiki 文章

“由于竞争条件，并发算法在不同的运行中可能会表现不同。”

在这里，我展示了一个专门做到这一点的类

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading;
using System.Threading.Tasks;

namespace randTesting
{
    /// <summary>
    /// Random byte generator
    /// </summary>
    public class RandomBytes
    {
        static volatile int v = 0;
        /// <summary>
        /// Creates the requested number of random bytes
        /// </summary>
        /// <param name="count"></param>
        /// <returns></returns>
        public static List<byte> GenerateBytes(int count)
        {
            List<byte> resbytes = new List<byte>();
            List<Thread> threadList = new List<Thread>();

            //get the number of processors on this os
            var pcount = Environment.ProcessorCount == 1 ? 2 : Environment.ProcessorCount;

            //initialize our bit value
            v = 1;

            //create a few threads
            for (int i = 0; i < pcount; i++)
            {
                var ts = new ThreadStart(mashup);
                var thd = new Thread(ts);
                thd.Start();
                threadList.Add(thd);
            }

            //wait on them to start up
            while (threadList.Any(a => a.ThreadState != ThreadState.Running));

            string bts = "";

            while (count > 0)
            {
                System.Threading.Thread.Sleep(5);
                int res = 0;
                if (v == 1) res = 1;
                bts += res;
                if (bts.Length == 8)
                {
                    int val = 0;
                    for (int x = 0; x < 8; x++)
                    {
                        val += (int)(Math.Pow((double)2, (double)x) * int.Parse(bts.Substring(x, 1)));
                    }
                    bts = "";

                    //add the byte value
                    resbytes.Add((byte)val);
                    count--;
                }
            }

            //thread cleanup
            threadList.ForEach(thd =>
                {
                    try
                    {
                        thd.Abort();
                    }
                    catch { }
                });

            return resbytes;
        }

        static void mashup()
        {
            while (true)
            {
                v *= -1;
            }
        }
    }
} 

背景

我经常怀疑计算机生成真正随机值的能力。 我想到的一个方法是让处理器不断地为同一个共享内存“争斗”，直到暂停和读取。 这被称为创建“竞争条件”。 如果允许经过足够的时间，共享内存位置中的值应该是未知的或随机的，因为只有操作系统控制分配给每个处理器的时间。

Using the Code

RandomBytes.cs 文件包含方法 "GenerateBytes"，它返回请求的指定数量的随机字节。

var bytes = RandomBytes.GenerateBytes(20);

这是一个使用此调用生成的 100 个随机字节的示例

220,252,230,230,105,62,1,101,143,95,78,243,215,3,95,45,66,33,160,29
114,147,147,39,12,68,249,95,59,225,86,237,95,190,91,79,160,214,169,105
29,218,77,54,12,246,244,101,204,158,95,169,249,104,41,128,251,33,79,20
124,247,207,53,216,129,222,74,161,214,247,94,179,229,103,22,184,213,14,132
43,15,130,147,207,27,77,47,196,111,143,94,197,177,67,65,81,202,126,157
51,176,166,171,137,111,227,171,151,206,150,218,23,37,74,37,20,95,204,226

关注点

1. 在循环和采样变量 (v) 时的暂停（5 毫秒）可能需要根据目标机器的速度进行调整。
2. 此处理器： Intel Core I7, 2201 Mhz, 4 Cores
3. 用于播种确定性（或伪随机数生成器）
4. 非周期性
5. 效率低下

很多人似乎对所有可用的不同随机数生成器感到困惑——而且有充分的理由。 大多数 RNG（显然，一些 GUID 生成器）通过使用非确定性数字生成器来播种自己（又名调理），然后用于生成确定性值（为了更高效和完美的分发）。 对于非确定性部分，大多数使用高速计时器和/或鼠标的 X 和 Y 移动的混合。 有些甚至使用屏幕捕获的哈希。

此外，我收到了很多关于 Microsoft 所做的事情的问题。 因此，对于 Microsoft 的密码随机数生成器

http://en.wikipedia.org/wiki/CryptGenRandom[^]

请注意，算法（或确定性）部分甚至没有发布。 然而，计时器混合（或非确定性）部分已明确暗示。

谢谢大家的评论，感谢大家帮助我写出更好的文章。

一些参考资料

• http://www.random.org/randomness/
• http://en.wikipedia.org/wiki/Nondeterministic_algorithm
• http://en.wikipedia.org/wiki/Race_condition