解密随机数生成器 Random Generator

https://sockpuppet.org/blog/2014/02/25/safely-generate-random-numbers/

Why not {SecureRandom, OpenSSL, havaged, &c}?

These are userspace CSPRNGs. You want to use the kernel’s CSPRNG, because:

• The kernel has access to raw device entropy.
• It can promise not to share the same state between applications.
• A good kernel CSPRNG, like FreeBSD’s, can also promise not to feed you random data before it’s seeded.

generators almost always depend on the kernel’s generator anyways. Even if they don’t, the security of your whole system sure does. A userspace CSPRNG doesn’t add defense-in-depth; instead, it creates two single points of failure.

http://calvin1978.blogcn.com/articles/securerandom.html

1. /dev/random 与 /dev/urandom

Linux的两个随机数源, 从IO中断，网卡传输包这些外部入侵者不可预测的随机源中获取熵，混合后使用CSPRNG生成熵池。

当熵池估值为0时，/dev/random 会block住请求，而/dev/urandom 则会继续输出随机数。

2. JDK7的SecureRandom

2.1 generateSeed()与next*()

generateSeed()可以为其他安全算法生成种子，随机度需求更高些。
nextInt(), nextLong()则是我们更关心的生成随机数，最后都是调用nextBytes()。 

2.2 seedSource

seedSource由两者决定，首先看 -Djava.security.egd ,
没设置则看jre/lib/security/java.security，JDK7中securerandom.source=file:/dev/urandom 

2.3 SHA1PRNG 与 NativePRNG

从名字就知道，两者都是伪随机算法。另外，两种算法都会有synchronized关键字，都会有阻塞，只有时间长短的不同。

• SHA1PRNG 比 NativePRNG消耗小一半，synchronized的代码少一半，不与系统/dev/urandom交互所以偶发高延时也更少一些，所以没特殊安全要求的话建议用SHA1，比如生成sessionId，traceId的场景
• 如果想用SHA1， 设成-Djava.security=file:/dev/./urandom总是对的
• 如果想用Native，什么都不设置就好了。
• 如果自己能控制，在应用或框架启动时，先调用一下相应SecureRandom算法实例的nextInt()函数，总能减少一点首次服务调用所花的时间

解密随机数生成器（1）――真随机数生成器 - Now is better than never - ITeye技术网站
常见的计算机随机数生成器有三种：一是使用物理方法，称为真随机数生成器（True Random Number Generator），生成的算是真正意义上的随机数，无法预测且无周期性；与真随机数对应的是伪随机数生成器（Pseudo Random Number Generator），它是由算法计算得来的，但这种方法生成的随机数是可预测、有周期的，并不能算真的随机数，因此得名伪随机数；还有第三种方法，叫随机数表法，就是用真随机数生成器事先生成好大量随机数，存到数据库中，使用时再从库中调用

二、真随机数生成器
生成真随机数的程序，就像永动机一样无法实现，要得到真正的随机数目前来讲只能看老天的眼色

1、基于电路的TRNG：

2、基于物理的TRNG：

3、基于其他因素的TRNG：

2 Linux自1.3.30版就在内核提供了真随机数生成器（至少是理论上），它利用机器的噪音生成随机数，噪音源包括各种硬件运行时速，用户和计算机交互时速。比如击键的间隔时间、鼠标移动速度、特定中断的时间间隔和块IO请求的响应时间等。

用Java可以使用java.security.SecureRandom 产生真随机数（待查）； 

Linux系统有/dev/random,/dev/urandom向用户提供真随机数；
Windows系统有CryptGenRandom 函数生成真随机数（待查） 

基于物理的随机数生成器，生成的随机数无周期，不可预测，分布均匀，然而，这种随机数生成器技术要求高，而且随机数生成效率不高，难以满足计算机高速计算的需要，因此为了提高数据产生效率，它们都常被用来生成伪随机数生成器的“种子”（seed），并以此生成伪随机的输出序列。

解密随机数生成器（2）——从java源码看线性同余算法
我重点介绍两个常用的算法：同余法（Congruential method）和梅森旋转算法（Mersenne twister）

同余法（Congruential method）是很常用的一种随机数生成方法，在很多编程语言中有应用，最明显的就是java了，java.util.Random类中用的就是同余法中的一种——线性同余法（Linear congruential method），除此之外还有乘同余法（Multiplicative congruential method）和混合同余法（Mixed congruential method）

1. /** 
2.      * Creates a new random number generator. This constructor sets 
3.      * the seed of the random number generator to a value very likely 
4.      * to be distinct from any other invocation of this constructor. 
5.      */  
6.     public Random() {  
7.         this(seedUniquifier() ^ System.nanoTime());  
8.     }  
9.    
10.     private static long seedUniquifier() {  
11.         // L'Ecuyer, "Tables of Linear Congruential Generators of  
12.         // Different Sizes and Good Lattice Structure", 1999  
13.         for (;;) {  
14.             long current = seedUniquifier.get();  
15.             long next = current * 181783497276652981L;  
16.             if (seedUniquifier.compareAndSet(current, next))  
17.                 return next;  
18.         }  
19.     }  
20.    
21.     private static final AtomicLong seedUniquifier  
22.         = new AtomicLong(8682522807148012L);  
23.     public Random(long seed) {  
24.         if (getClass() == Random.class)  
25.             this.seed = new AtomicLong(initialScramble(seed));  
26.         else {  
27.             // subclass might have overriden setSeed  
28.             this.seed = new AtomicLong();  
29.             setSeed(seed);  
30.         }  
31.     }  
32.     private static long initialScramble(long seed) {  
33.         return (seed ^ multiplier) & mask;  
34.     }  

这里使用了System.nanoTime()方法来得到一个纳秒级的时间量，参与48位种子的构成，然后还进行了一个很变态的运算——不断乘以181783497276652981L，直到某一次相乘前后结果相同——来进一步增大随机性，这里的nanotime可以算是一个真随机数，不过有必要提的是，nanoTime和我们常用的currenttime方法不同，返回的不是从1970年1月1日到现在的时间，而是一个随机的数——只用来前后比较计算一个时间段，比如一行代码的运行时间，数据库导入的时间等，而不能用来计算今天是哪一天。

好了，现在我不得不佩服这位工程师的变态了：到目前为止，这个程序已经至少进行了三次随机：

1、获得一个长整形数作为“初始种子”（系统默认的是8682522807148012L）

2、不断与一个变态的数——181783497276652981L相乘（天知道这些数是不是工程师随便滚键盘滚出来的-.-）直到某一次相乘前后数值相等

3、与系统随机出来的nanotime值作异或运算，得到最终的种子

1. public int nextInt() {  
2.     return next(32);  
3. }  

1. protected int next(int bits) {  
2.     long oldseed, nextseed;  
3.     AtomicLong seed = this.seed;  
4.     do {  
5.         oldseed = seed.get();  
6.         nextseed = (oldseed * multiplier + addend) & mask;  
7.     } while (!seed.compareAndSet(oldseed, nextseed));  
8.     return (int)(nextseed >>> (48 - bits));  
9. } 

1. nextseed = (oldseed * multiplier + addend) & mask;  

和Xn+1=(a*Xn+c)(mod m)的形式很像有木有！

没错，就是这一行代码应用到了线性同余法公式！不过还有一个问题：怎么没见取余符号？嘿嘿，先让我们看看三个变量的数值声明：

1. private static final long multiplier = 0x5DEECE66DL;  
2. private static final long addend = 0xBL;  
3. private static final long mask = (1L << 48) - 1;  

 其中multiplier和addend分别代表公式中的a和c，很好理解，但mask代表什么呢？其实，x & [(1L << 48)–1]与 x（mod 2^48）等价。解释如下：

x对于2的N次幂取余，由于除数是2的N次幂，如：
0001，0010，0100，1000。。。。
相当于把x的二进制形式向右移N位，此时移到小数点右侧的就是余数，如：
13 = 1101 8 = 1000
13 / 8 = 1.101，所以小数点右侧的101就是余数，化成十进制就是5

然而，无论是C语言还是java,位运算移走的数显然都一去不复返了。（什么，你说在CF寄存器中？好吧，太高端了点，其实还有更给力的方法）有什么好办法保护这些即将逝去的数据呢？

学着上面的mask，我们不妨试着把2的N次幂减一：
0000，0001，0011，0111，01111，011111。。。

怎么样，有启发了吗？
我们知道，某个数（限0和1）与1作与（&）操作，结果还是它本身；而与0作与操作结果总是0，即：
a & 1 = a, a & 0 = 0

而我们将x对2^N取余操作希望达到的目的可以理解为：
1、所有比2^N位（包括2^N那一位）高的位全都为0
2、所有比2^N低的位保持原样
因此， x & （2^N-1）与x（mod 2^N）运算等价，还是13与8的例子：

1101 % 1000 = 0101 1101 & 0111 = 0101

二者结果一致。

嘿嘿，讲明白了这个与运算的含义，我想上面那行代码的含义应该很明了了，就是线性同余公式的直接套用，其中a = 0x5DEECE66DL, c = 0xBL, m = 2^48，就可以得到一个48位的随机数，而且这个谨慎的工程师进行了迭代，增加结果的随机性。再把结果移位，就可以得到指定位数的随机数。

1. public int nextInt(int n) {  
2.     if (n <= 0)  
3.         throw new IllegalArgumentException("n must be positive");  
4.   
5.     if ((n & -n) == n)  // i.e., n is a power of 2  
6.         return (int)((n * (long)next(31)) >> 31);  
7.   
8.     int bits, val;  
9.     do {  
10.         bits = next(31);  
11.         val = bits % n;  
12.     } while (bits - val + (n-1) < 0);  
13.     return val;  
14. }  

显然，这里基本的思路还是一样的，先调用next函数生成一个31位的随机数（int类型的范围），再对参数n进行判断，如果n恰好为2的方幂，那么直接移位就可以得到想要的结果；如果不是2的方幂，那么就关于n取余，最终使结果在[0,n)范围内。另外，do-while语句的目的应该是防止结果为负数。

你也许会好奇为什么(n & -n) == n可以判断一个数是不是2的次方幂，其实我也是研究了一番才弄明白的，其实，这主要与补码的特性有关：

众所周知，计算机中负数使用补码储存的（不懂什么是补码的自己百度恶补），举几组例子：

2 ：0000 0010      -2 ：1111 1110

8 ：0000 1000      -8 ：1111 1000

18 ：0001 0010     -18 ：1110 1110

20 ：0001 0100     -20 ：1110 1100

不知道大家有没有注意到，补码有一个特性，就是可以对于两个相反数n与-n，有且只有最低一个为1的位数字相同且都为1，而更低的位全为0，更高的位各不相同。因此两数作按位与操作后只有一位为1，而能满足这个结果仍为n的只能是原本就只有一位是1的数，也就是恰好是2的次方幂的数了。

不过个人觉得还有一种更好的判断2的次方幂的方法：

n & (n-1) == 0

上文中的线性同余法，主要用来生成整数，而某些情景下，比如科研中，常常只需要（0，1）之间的小数，这时，乘同余法是更好的选择，它的基本公式和线性同余法很像：

Xn+1=（a*Xn ）(mod m ）

其实只是令线性公式中的c=0而已。只不过，为了得到小数，我们多做一步：

Yn = Xn/m  

由于Xn是m的余数，所以Yn的值介于0与1之间，由此到（0，1）区间上的随机数列。

除此之外，还有混合同余法，二次同余法，三次同余法等类似的方法，公式类似，也各有优劣，在此不详细介绍了。

同余法优势在计算速度快，内存消耗少。但是，因为相邻的随机数并不独立，序列关联性较大。所以，对于随机数质量要求高的应用，特别是很多科研领域，并不适合用这种方法。

JDK源码分析——从java.util.Random源码分析线性同余算法

为什么Random使用的是48位种子
初始种子8682522807148012L
关于java的Ranom类的a,c,m参数说明
3.关于Random类中的高斯分布（正态分布）实现说明

这个实现使用了的极坐标法 (polar method)，该方法在 Donald E. Knuth 的 The Art of Computer Programming, Volume 3:Seminumerical Algorithms 的第 3.4.1 节，小节 C，算法 P 中进行了描述，可详细参考计算机编程艺术。

public double nextDouble() {
        return (((long)(next(26)) << 27) + next(27))
        / (double)(1L << 53);
    }

这里获取的是53位随机数，对于这个选择JDK源码的实现者很谨慎，也是尽量力求完美。其实在Java 的早期版本中，实现为(((long)next(27) << 27) + next(27)) / (double)(1L << 54)。这好像看似等效，但实际上根据IEE754标准双精度浮点数的有效位数是52位，最高有效位默认为1相当于可以保存53位，所以浮点数的舍入会存在偏差，因此54位会引入较大的不均匀性：有效数的低位出现 0 的可能性是 1 的三倍！(原来的值是舍入值的中间值时，会采取向偶数舍入，在二进制中，偶数我们认为是末尾为0的数)。同样的nextFloat获取的是24位随机数。

另外serialPersistentFields定义了Random类的需要序列化的字段。
http://blog.csdn.net/ultrani/article/details/7818082

1. public double nextDouble() {  
2.     return (((long)(next(26)) << 27) + next(27))    
3.  / (double)(1L << 53);  
4. } 

1. public int nextInt(int n) {  
2.     if (n <= 0)  
3.         throw new IllegalArgumentException("n must be positive");  
4.   
5.     if ((n & -n) == n)  // i.e., n is a power of 2  
6.         return (int)((n * (long)next(31)) >> 31);  
7.   
8.     int bits, val;  
9.     do {  
10.         bits = next(31);  
11.         val = bits % n;  
12.     } while (bits - val + (n-1) < 0);   // 这里为什么要这么判断，请见附录a  
13.     return val;  
14. }  

无论从准确性和效率，nextInt(n)都比Math.random()要好。

2段程序中可以看到，最终实现随机数的生成还是依赖于next(n)。
（注：next(n)的功能是产生n位bits，每个bit位随机为0或1,当n<32时，next(n)产生的随机数范围为0~2^31-1，当n=32时，产生随机数范围为-2的31次方~2^31-1。源码中的next函数最终返回return (int)(nextseed >>> (48 - bits)) 是因为随机种子是48位，所以最终返回的是随机种子的高n位bit）

而nextDouble()中铁定调用了2次next(n)，而nextInt(n)则不确定，但平均调用next(n)的次数在2次以下（见附录b证明）。所以nextInt(n)比nextDouble()获取随机数的效率要高。

另外，通过(int) （n * Math.random()）获取的整数随机数其实是通过double随机数近似而来，准确性相对nextInt(n)来说应该会低些。

a. nextInt(n)函数解析

该函数进行的工作是把31位的原始随机范围next(31)的结果映射到[0,n)范围之内。但是，如果不经过特殊处理会出现概率不均匀。考虑下面这么一个例子，设原有均匀的随机数范围是1～100，当我要产生新的随机数范围为1～30时候，我本来可以用原随机范围产生的数分为三组，但是因为100不被30整除，所以余下第四组是不匀称的：[1,30), [31, 60), [61, 90), [91,100),所以实际产生的结果中，产生1～10的随机数概率会比11～30的要高。jdk对这种情况的做法是，如果对31bit的随机数映射到[0,n)的时候，如果next(31)产生的数字是最后那部分，则丢弃重试。所以nextInt(n)的循环部分就是处理这个问题。

当n是2的整数次幂时，n铁定能被2^31整除，这时候可以直接映射，进行一次next(31)运算即可。

当n不是2的整数次幂是，那就会出现刚才例子中的不均匀情况。所以就要特殊处理：当bits - val + (n-1) < 0 时，判断为不均匀部分，继续循环重试。那这句判断是什么意思呢。

对于 2^31 / n = max ...val ,val是2^31除以n的余数, max是倍数，2^31-val=nMax 也就是获取不大于2^31的能整除n的最大整数。则[nMax,2^31)就是不均匀部分。如果bits落入这个范围可判为丢弃并重试。这里我们可以获得：nMax < 2^31 < n(Max+1) 

当调用bits = next(31)时候，获取的是[0,2^31)的一个随机数，

假如bits<nMax,则bits - val一定等于n的某个的倍数(小于Max)中，且bits-val+n-1一定小于nMax,故不需重试，直接返回结果。

假如bits>=nMax,则bits-val = nMax, 则bits-val+n-1=nMax+n-1=n(Max+1) - 1 > 2^31 -1 ,等价于若bits>=nMax,则bits-val+n-1 >= 2^31 ,由于int型2^31溢出，所以2^31<0,

所以用while(bits-val+n-1 < 0) 来判断是否需要重试。

b. nextInt(n)的的循环次数为什么平均小于2

附录a介绍了nextInt(n)的原理，了解到产生不均匀数后需要重试。但这个重试次数是多少呢。考虑最坏情况，如nextInt(n)的javadoc中所说，当n=2^30+1时，最糟糕，[nMax,2^31)的范围达到最大。要使因为如果n<2^30+1更小，那么一定能找到newMax使得[nNewMax, 2^31) 的范围更小。

当n=2^30+1,则不均匀范围[2^30+1, 2^31)和均匀范围[0, 2^30)的数目基本是一样的，所以这个时候有50%的机会要重试。即最坏情况下也只有50%的概率重试。

所以总体上来说nextInt(n)的平均调用next(n)次数小于2，这也是为什么比Math.random()要快的原因。

对安全性有要求的随机数应用情景，可以用java.security.SecureRandom。代替伪随机的Random类。该类继承自Random类，并覆盖了next(n)函数，所以可以利用其提供的强随机的种子算法(SHA1PRNG)来生成随机数。

Java 随机数比较和分析
Read full article from 解密随机数生成器（1）――真随机数生成器 - Now is better than never - ITeye技术网站