System.Guid.NewGuid()是如何随机的？(拿两个)

Question

在您开始将其标记为重复之前,请将我读出来.另一个问题是(很可能)不正确的接受答案.

我不知道.NET如何生成其GUID,可能只有微软这样做,但它很有可能只是调用CoCreateGuid().但是,该函数被记录为调用UuidCreate().并且用于创建UUID的算法已被很好地记录.

长话短说,尽管如此,似乎System.Guid.NewGuid()确实使用了版本4 UUID生成算法,因为它生成的所有GUID都符合标准(参见自己,我尝试了几百万个GUID,它们都匹配).

换句话说,除了一些已知位之外,这些GUID 几乎是随机的.

这再次提出了一个问题 - 随机是如何随机的？正如每个优秀的小程序员都知道的那样,伪随机数算法只与其种子(即熵)一样随机.那么种子是UuidCreate()什么？PRNG如何重新播种？它是加密强大的,或者如果两台计算机同时意外呼叫System.Guid.NewGuid(),我可以期望相同的GUID开始倾泻吗？如果收集到足够多的顺序生成的GUID,是否可以猜测PRNG的状态？

补充:为了澄清,我想知道我可以信任的随机性因此 - 我在哪里可以使用它.那么,让我们在这里建立一个粗略的"随机性"量表:

1. 基本随机性,以当前时间为种子.可以在纸牌中使用洗牌,但是即使没有尝试也很容易碰到碰撞.
2. 更高级的随机性,不仅使用时间,还使用其他机器特定的种子因子.也许在系统启动时也只播种一次.这可用于在DB中生成ID,因为不太可能重复.尽管如此,它对安全性并不好,因为可以用足够的努力预测结果.
3. 密码随机,使用设备噪声或其他先进的种子随机源.每次调用或至少经常重新播种.可用于会话ID,分发给不受信任的各方等.

我在想到是否可以将它们用作数据库ID时,以及Guid.comb算法的实现System.Guid.NewGuid()(如NHibernate的实现方式)是否有缺陷,我就来到了这个问题.

Answer 1

对相关问题的接受答案表明:

GUID不保证随机性,它保证了唯一性.如果您想要随机性,请使用Random生成字符串.

其他任何东西都是一个实现细节(可能会改变).

更新:为了使我的观点更清楚:即使当前的.NET 3.5实现产生了一个真正随机的guid(事实并非如此),也不能保证将来会出现这种情况,或者对于BCL的其他实现也是如此(例如Mono,Silverlight,CF等)

更新2:UUID的格式由RFC4122指定.第6节明确声明了安全性:

不要以为UUID难以猜测; 例如,它们不应被用作安全功能(仅仅拥有访问权限的标识符).可预测的随机数源将加剧这种情况.

Answer 2

有些人已经暗示了这一点,但我想重复一遍,因为那里似乎存在一种误解:

随机性和唯一性是正交概念.

随机数据可以是唯一的或冗余的,同样唯一的数据可以使用随机源或确定性源(想想一个全局计数器,它为每个创建的GUID锁定和递增).

GUID被设计为独特的,而不是随机的.如果.NET生成器似乎使用随机输入,那很好.但不要依赖它作为随机的来源,既不是密码学,也没有任何其他目的(特别是,你希望得到什么样的分布函数？).另一方面,您可以合理地确定.NET创建的GUID(即使是大批量)也是唯一的.

Answer 3

生成随机字节但未明确记录以生成加密强随机字节的API不能被信任以产生加密强随机字节.

如果您需要加密强大的随机字节,那么您应该使用明确记录的API来生成它们.

public Guid CreateCryptographicallyStrongGuid() {
    var rng = new System.Security.Cryptography.RNGCryptoServiceProvider();
    var data = new byte[16];
    rng.GetBytes(data);
    return new Guid(data);
}

这些GUID只是128位加密随机性.它们没有结构化,也不会发生碰撞.

有关一些数学,请参阅此文章.使用"一般生日公式",重新排列给出

n = sqrt(-2T*ln(p))

其中n是所选元素的数量,T是元素的总数(2 ^ 128),p是所有n个所选元素将不同的目标概率.当p = .99时,这给出*n = 2.61532104*10 ^ 18*.这意味着我们可以在系统内每秒生成十亿个真正随机的GUID,持续十亿秒(32年),并且最终有99%的机会在系统中每个都是唯一的.

Answer 4

随机的定义绝不与全球唯一的定义有关.

两次掷硬币并获得HH,HT,TH,TT都是随机的.HH和HT一样随机.

两次翻转"特殊"硬币并保证只获得HT或TH是唯一性.