随机数生成器（Random number generator）是通过一些算法、物理讯号、环境噪音等来产生看起来似乎没有关联性的数列的方法或装置。丢硬币、丢骰子、洗牌就是生活上常见的随机数产生方式。大部分计算机上的伪随机数，并不是真正的随机数，只是重复的周期比较大的数列，是按一定的算法和种子值生成的。  ----维基百科

       由此我们可以看出随机数生成器分为两类，一类是非确定性随机数产生器，这是基于完全不可预测的物理过程，比如在random.org上提供了“真”随机值，据说是根据“atmospheric noise”来产生的；另一类是确定性随机数产生器，利用算法来生成，如果种子保密且算法优质的话，我们可以认为它的输出是随机的序列。这些输出的随机序列将会用于密码学的应用中。

       但是，如果选取的种子范围不够大，那么就很容易被爆破，而这些随机数常用于关键的枢纽上，后果不言而喻，这往往是程序员自身的问题。可当随机算法产生漏洞时，带来的效果更是毁灭性的，任何依此搭建的体系将会轰然倒塌，安全将不复存在。这次我将详解Dual_EC_DRBG所带来的问题。

 

---

背景

       Dual_EC_DRBG，全称为Dual Elliptic Curve Deterministic Random Bit Generation，是基于椭圆曲线的确定性随机数生成器。2007，两名微软的研究人员Dan Shumow和Niels Ferguson就发现，Dual_EC_DRBG算法可以被植入后门。他们提到，如果算法中使用的常数经过特殊选择，并且用来选择这些常数所使用的数据被算法设计者保存下来，那么该算法设计者在知道该算法生成随机序列的前32个字节的情况下，可以预知未来所有生成的“随机”序列。

       目前最新的进展是，斯诺登披露的文件证明了，美国国家安全局（NSA）通过贿赂RSA公司，使其在BSafe安全软件中采用Dual_EC_DRBG算法。而Dual_EC_DRBG则是NSA精心设计的留有后门的算法（当然NSA可能没有告诉RSA公司这一点）。

 

---

基础知识

     

       上图是随机数产生器的原理图，是公开的。additional input我们暂时把它设为null；φ的作用只是大整数和二进制数之间的映射，可忽略；x(A)表示A点的x坐标，P是椭圆的基点，Q是官方直接给出的（但并没说给出的原因）。我们整体来看下。

        它首先随机产生了一个数t，经过了φ(x(t*P))，然后分为了两部分，分别进入内部和外部状态。内部状态就是这样不断地经过φ(x(t*P))来改变，而外部状态经过内部状态弹出的一个数s，经φ(x(s*Q))变化再提取出相应字节成为了伪随机数。过程就是这么简单。下面举前两轮的例子：

       令i_n表示内部种子的值，o_n表示输出值。

       第一轮：

   

       第二轮：

     

       原理已经介绍完了，下面的问题是我们能否通过第一轮输出的o₀推测第二轮输出的o₁呢？那我们简单推一下（仔细盯着上面式子），要想知道第二轮输出o₁，就必须知道第二轮的内部状态i₂，但要知道i₂，就必须要知道第一轮的内部状态i₁。但我们不可能知道该随机数产生器的内部状态。可我们知道第一轮的输出o₁啊，万一我们让第一轮输出状态o₀跟第二轮内部状态i₂产生联系呢，再细一点，万一让P和Q之间产生某种联系呢，那么是否就可以通过第一轮输出o₀直接解出第二轮的输出o₁呢？

       我们假设下P=Qd。（d就被称为NSA留下的后门）

       假设第一轮输出o₀的点为 A = i₁Q （注：o₀是A的x坐标），

 

       然后两边同时乘以d，得到  dA = i₁dQ ，

       因为P=dQ，所以 i₁P = dA，

       那么第二轮的内部种子值 i₂=φ( x( dA ) )，即我们就可以根据o₁= φ( x( i₂Q ) )，很轻松地将o₁计算出。  

       总述，现在我只要算出第一轮输出值o₀的点坐标A，乘以d，取x坐标，再乘以Q，最后再取x坐标，就可以得到o₁了。

       追根溯源，造成问题的关键是常数Q，在标准中根本就没涉及到选择此常数的原因。如果Q经过特殊选择，并且用来选择这些常数所使用的数据被算法设计者保存下来，那么该算法设计者在知道该算法生成随机序列的前32个字节的情况下，可以预知未来所有生成的“随机”序列。这就跟DES的S盒来路不明是一样，被人们所怀疑诟病。补充：在实际情况中，输出一般是30个字节，我们可通过爆破的方法去求解，2的16次方，完全在可以接受的范围内。

---

实验

1. 选定一条NIST P-256椭圆曲线，其中a, b, p, r等都是已知的；  y²= x³+ ax + b ( mod p )

2. 随机选取一数e；

3. 计算Q = P*e，P作为椭圆的基点；

4. 根据以上伪随机数产生规则，输出o₀；

5. 求出下一产生数o₁，并验证是否正确。

      细心的同学可能注意到了，这里为什么是Q=P*e，而不是上面讲的P=Q*d。因为P是基点，是固定了的，所以我们需要先选取后门d模r的逆e。     

      第一轮的输出o₀，后门d和Q都是已知的。     

     下面是该椭圆曲线和Dual_EC_DRBG后门的代码，并打印出已知条件Q、e和第一轮输出o₀：

#!/usr/bin/env python
# -*- coding: utf-8 -*-

import os
import random
import seccure
import struct
import gmpy

def gen_d(order):
    d = os.urandom(32)
    d = int(d.encode('hex'),16)
    return d % order

def generate_backdoor(curve,d):
    #Create a known relationship between P and Q
    Q = curve.base
    Q = Q * d

    return Q

class dual_ec_dbrg(object):
    def __init__(self,seed,curve,qx,qy):
        self.i0 = seed
        self.curve = curve
        self.P = curve.base
        self.Q = seccure.AffinePoint(qx,qy,self.curve)
        if (not self.Q.on_curve):
            print "Chosen Q Not on Curve!"
            return
#Q = d*P
    def getrand(self):
        first = self.P * gmpy.mpz(self.i0)
        x = first.x
        out = self.Q * x
        self.i0 = int(first.x)
        return int(out.x)

p256curve = seccure.Curve.by_name_substring('nistp256')
e = gen_d(p256curve.order)
Q = generate_backdoor(p256curve,e)

gen = dual_ec_dbrg(random.randint(0,2 ** 32),p256curve,int(Q.x),int(Q.y))

o0 = gen.getrand()
print "Q.x: "+str(int(Q.x))
print "Q.y: "+str(int(Q.y))
print "e: "+ str(int(e))
print "o0: "+str(int(o0))

       我们的思路就是根据刚才的结论倒推回去。x(A)表示点A的x坐标。      

       o₁=x(i₂*Q) <-- i₂ = x(dA) <-- o₀=x(A)。

      难点在于通过x坐标o₀求出其点A，这里要用到二次剩余系解法 （Tonelli–Shanks Algorithm）。该算法用到了欧拉判别条件，通过一系列的步骤判断，得到结果，没看懂。这毕竟是数学家的事，我就拿来用用。此处应有传送门。

      d的值等于e关于模r的逆，r是椭圆曲线事先给出的定值，e已知的。      

      然后基本上就没什么要点了。   

def modular_sqrt(a, p):

    if legendre_symbol(a, p) != 1:
        return 0
    elif a == 0:
        return 0
    elif p == 2:
        return p
    elif p % 4 == 3:
        return pow(a, (p + 1) / 4, p)

    s = p - 1
    e = 0
    while s % 2 == 0:
        s /= 2
        e += 1

    n = 2
    while legendre_symbol(n, p) != -1:
        n += 1


    x = pow(a, (s + 1) / 2, p)
    b = pow(a, s, p)
    g = pow(n, s, p)
    r = e

    while True:
        t = b
        m = 0
        for m in xrange(r):
            if t == 1:
                break
            t = pow(t, 2, p)

        if m == 0:
            return x

        gs = pow(g, 2 ** (r - m - 1), p)
        g = (gs * gs) % p
        x = (x * gs) % p
        b = (b * g) % p
        r = m


def legendre_symbol(a, p):#欧拉判别

    ls = pow(a, (p - 1) / 2, p)
    return -1 if ls == p - 1 else ls

a = p256curve.a
b = p256curve.b
m = p256curve.m  #mod p

y = gmpy.mpz(0)
y = (pow(o0,3,m)+ a*o0 + b)%m
y = modular_sqrt(y,m)

A = seccure.AffinePoint(o0,y,p256curve)

assert(A.on_curve)

r = p256curve.order
d = gmpy.mpz(0)
d = gmpy.invert(gmpy.mpz(e),r)

i2 = (A*d).x
o1 = (Q*i2).x
print "predict o1: "+ str(o1)

real_o1 = gen.getrand()
print "real o1: "+ str(real_o1)

---

 待续

       实验是经过简化的，在实际情况中会比这个复杂，但关键点都讲到了。由于Q的参数来历不明，可能被设计者精心设计过拿到d了，如果真要修复的话，那就每次运行伪随机数产生器PRNG时都随机产生Q，所以d的值就不可能得到了。

       在下一篇文章中，我将会讲解另一个随机数产生器是怎么被攻破的，与因Dual_EC_DRBG的后门被攻破的原理不同，它已普遍地应用在php、ruby、python中，如果开发者不慎重，那将会产生严重的后果。

参考资料：

http://redswallow.github.io/2013/12/ecc-and-dual-ec-drbg

https://www.zhihu.com/question/22343037