随机数
随机数的性质从弱到强分为3类: 详见:计算机中的随机数
1. 随机性
2. 不可预测性
3. 不可重现性
在上面的三个性质中,越往下就越严格。具备随机性,不代表一定具备不可预测性;具备不可预测性,不代表一定具备不可重现性;但如果具备不可重现性,一定具备随机性和不可预测性。
满足上面的3性依次对应着:弱伪随机数,强伪随机数,真随机数。
在计算机中,用软件生成的随机数都是伪随机数,即弱伪随机数和强伪随机数。由于弱伪随机数不具备不可预测性,因此在密码学中只使用强随机数和真随机数(在密码学中,随机数常常被用于生成密钥,因此具备可预测性是危险的)
至此,我们知道,密码学中使用的随机数一定是强伪随机数或者真随机数。由于真随机数用纯软件产生很困难,因此我们在软件设计中都是用强伪随机数。不过遗憾的是,一些语言提供的随机数生成函数都是弱随机数。比如java.util.Random类生成的就是弱伪随机数,当时java中的java.security.SecureRandom类提供的是强随机数。
UUID
UUID是指Universally Unique Identifier,翻译为中文是通用唯一识别码,UUID 的目的是让分布式系统中的所有元素都能有唯一的识别信息。如此一来,每个人都可以创建不与其它人冲突的 UUID,就不需考虑数据库创建时的名称重复问题。
UUID 的十六个八位字节被表示为 32个十六进制数字,以连字号分隔的五组来显示,形式为 8-4-4-4-12,总共有 36个字符(即三十二个英数字母和四个连字号)。例如:
123e4567-e89b-12d3-a456-426655440000
xxxxxxxx-xxxx-Mxxx-Nxxx-xxxxxxxxxxxx
数字M的四位表示 UUID 版本,当前规范有5个版本,M可选值为1, 2, 3, 4, 5;
数字N的一至四个最高有效位表示 UUID 变体( variant ),有固定的两位10xx因此只可能取值8, 9, a, b
UUID版本通过M表示,当前规范有5个版本,M可选值为1, 2, 3, 4, 5。这5个版本使用不同算法,利用不同的信息来产生UUID,各版本有各自优势,适用于不同情景。具体使用的信息
version 1, date-time & MAC address
version 2, date-time & group/user id
version 3, MD5 hash & namespace
version 4, pseudo-random number
version 5, SHA-1 hash & namespace
UUID Version 1:基于时间的UUID
基于时间的UUID通过计算当前时间戳、随机数和机器MAC地址得到。由于在算法中使用了MAC地址,这个版本的UUID可以保证在全球范围的唯一性。但与此同时,使用MAC地址会带来安全性问题,这就是这个版本UUID受到批评的地方。如果应用只是在局域网中使用,也可以使用退化的算法,以IP地址来代替MAC地址--Java的UUID往往是这样实现的(当然也考虑了获取MAC的难度)。
UUID Version 2:DCE安全的UUID
DCE(Distributed Computing Environment)安全的UUID和基于时间的UUID算法相同,但会把时间戳的前4位置换为POSIX的UID或GID。这个版本的UUID在实际中较少用到。
UUID Version 3:基于名字的UUID(MD5)
基于名字的UUID通过计算名字和名字空间的MD5散列值得到。这个版本的UUID保证了:相同名字空间中不同名字生成的UUID的唯一性;不同名字空间中的UUID的唯一性;相同名字空间中相同名字的UUID重复生成是相同的。
UUID Version 4:随机UUID
根据随机数,或者伪随机数生成UUID。这种UUID产生重复的概率是可以计算出来的,但随机的东西就像是买彩票:你指望它发财是不可能的,但狗屎运通常会在不经意中到来。
UUID Version 5:基于名字的UUID(SHA1)
和版本3的UUID算法类似,只是散列值计算使用SHA1(Secure Hash Algorithm 1)算法。
uuid应用:
从UUID的不同版本可以看出,Version 1/2适合应用于分布式计算环境下,具有高度的唯一性;Version 3/5适合于一定范围内名字唯一,且需要或可能会重复生成UUID的环境下;至于Version 4,我个人的建议是最好不用(虽然它是最简单最方便的)。
使用较多的是版本1和版本4,其中版本1使用当前时间戳和MAC地址信息。版本4使用(伪)随机数信息,128bit中,除去版本确定的4bit和variant确定的2bit,其它122bit全部由(伪)随机数信息确定。
因为时间戳和随机数的唯一性,版本1和版本4总是生成唯一的标识符。若希望对给定的一个字符串总是能生成相同的 UUID,使用版本3或版本5。
通常我们建议使用UUID来标识对象或持久化数据,但以下情况最好不使用UUID:
映射类型的对象。比如只有代码及名称的代码表。
人工维护的非系统生成对象。比如系统中的部分基础数据。
对于具有名称不可重复的自然特性的对象,最好使用Version 3/5的UUID。比如系统中的用户。如果用户的UUID是Version 1的,如果你不小心删除了再重建用户,你会发现人还是那个人,用户已经不是那个用户了。(虽然标记为删除状态也是一种解决方案,但会带来实现上的复杂性。)
随机 UUID 的重复机率:
Java中 UUID 使用版本4进行实现,所以由java.util.UUID类产生的 UUID,128个比特中,有122个比特是随机产生,4个比特标识版本被使用,还有2个标识变体被使用。利用生日悖论,可计算出两笔 UUID 拥有相同值的机率约为
其中x为 UUID 的取值范围,n为 UUID 的个数。
每秒产生10亿笔 UUID ,100年后只产生一次重复的机率是50%。如果地球上每个人都各有6亿笔 UUID,发生一次重复的机率是50%。与被陨石击中的机率比较的话,已知一个人每年被陨石击中的机率估计为170亿分之1,也就是说机率大约是0.00000000006 (6 x 10-11),等同于在一年内生产2000亿个 UUID 并发生一次重复。
综上所述,产生重复 UUID 并造成错误的情况非常低,是故大可不必考虑此问题。
机率也与随机数产生器的质量有关。若要避免重复机率提高,必须要使用基于密码学上的强伪随机数产生器来生成值才行。
Java中 UUID 对版本4进行了实现,原理是由强伪随机数生成器生成伪随机数。
UUID生成器:
Java UUID Generator (JUG):开源UUID生成器,LGPL协议,支持MAC地址。
UUID:特殊的License,有源码。
Java 5以上版本中自带的UUID生成器:好像只能生成Version 3/4的UUID。