随机数发生器

1、什么是随机数发生器？

定义：一个随机数发生器就是一个产生数据流的设备，数据流中的每一位都是不可预测，偶然的。但是从一定长度的数据流来看，它又符合某种分布。

随机程度：通常在产生的一系列声称是随机的数值时，我们关心的是这些数值在某种统计意义上是随机的。即均匀分布和独立性。
不可预测程度：对于“真正的”随机序列，每个数与序列中的其他数都是统计独立的，因此不可预测。然而，实际上我们很少能使用到真正的随机数；相反我们用到的都是由某种算法生成的。这个时候，我们得防止攻击者从序列前边的元素预测出将来的元素。

2、 随机数发生器的分类

一般来说，随机数发生器有三种，它们分别是真随机数发生器(TRNG，True Random Number Generator)、伪随机数发生器(PRNG，Pseudo Random Number Generator)和密码学安全随机数发生器(CSPRNG，Cryptographically Secure Pseudo Random Number Generator)。

本文介绍的LFSR（Linear Feedback Shift Register)实际上是PRNG。首先，移位寄存器包括两个部分：1）级，每一级包含一个比特，比如11010110是一个8级的移位寄存器产生的 2）反馈函数，线性反馈移位寄存器的反馈函数是线性的，非线性反馈移位寄存器的反馈函数是非线性的。先来看一个例子：

一个 $n$ 级的移位寄存器产生的序列的最大周期为 $2^{n}-1$ ，当然这个最大周期跟反馈函数有很大关系，线性反馈函数实际上就是这个 $n$ 级的移位寄存器选取“某些位”进行异或后得到的结果，得到线性反馈函数之后，把这个移位寄存器的每次向右移动一位，把最右端的作为输出，把“某些位”的异或结果作为输入放到最左端的那位，这样所有的输出对应一个序列，这个序列叫做M序列，是最长线性移位寄存器序列的简称。理论表明，要使LFSR得到最长的周期，这个抽头序列构成的多项式加1必须是一个本原多项式（即不可约）。

#include "stdafx.h"

#include <vector>

#include <stdint.h>

#include <stdlib.h>

#include <iostream>

using namespace std;

#define BIT12 (0X1<<12)

#define BIT11 (0X1<<11)

#define BIT10 (0X1<<10)

#define BIT0 0x1

int _tmain(int argc, _TCHAR* argv[]){

unsigned short lfsr=0xffffu;

unsigned period=0;

do{

unsigned short lsb=lfsr>>(16-1)&1;

cout.setf(ios::hex,ios::basefield);

unsigned short xor1=(lsb^(lfsr>>12&1))<<12;

unsigned short xor2=(lsb^(lfsr>>11&1))<<11;

unsigned short xor3=(lsb^(lfsr>>10&1))<<10;

lfsr&=~BIT12; //flip-flop，D触发器，因为首先需要移位

lfsr&=~BIT11;

lfsr&=~BIT10;

lfsr|=xor1; //replace BIT12 with xor result

lfsr|=xor2; //replace BIT11 with xor result

lfsr|=xor3; //replace BIT10 with xor result

lfsr<<=1; //left shift

lfsr|=lsb; //replace BIT0 with original BIT15

++period;

if(period%8==0)

cout<<lfsr<<endl;//8th state of the LFSRs

}while(lfsr!=0xffffu);

cout<<"period= "<<period<<endl;

system("pause");

return 0;

}

可以看到周期为FFFF，即 $2^{16}-1$ ，说明该随机数发生器有很好的随机性。这个随机数可以用来对scrambled后的control data 进行descramble。

扩展：在百度或者Google这样的搜索引擎中，爬虫要对爬取的网页进行判重，这个是通过信息指纹来实现的。具体来说就是把每一个网址随机地映射到128位二进制，这样每一个网址只占用16个字节的空间，这个128位的随机数就是这个网址的信息指纹，可以证明，只要产生的随机数足够好，那么就可以保证几乎不可能有两个网址的信息指纹相同，就如同不可能有两个人的指纹相同一样，而梅森旋转算法是产生高质量伪随机数的算法。《数学之美》

对于随机数生成器写成容器加算法的形式：

容器：

//.cpp

#include "stdafx.h"

#include "TmdsScramblerGenerator.h"

#define BIT12 (0X1<<12)

#define BIT11 (0X1<<11)

#define BIT10 (0X1<<10)

TmdsScramblerGenerator::TmdsScramblerGenerator() {

_scrambler[2]=SCRAMBLER_RESET_VALUE ; //TMDS channel_0 LFSR_value

_scrambler[1]=SCRAMBLER_RESET_VALUE1 ; //TMDS channel_1 LFSR_value

_scrambler[0]=SCRAMBLER_RESET_VALUE2 ; //TMDS channel_2 LFSR_value

}

TmdsScramblerGenerator::TmdsScramblerGenerator(int initialValue,int initialValue1,int initialValue2) {

_scrambler[2]=initialValue & 0xFFFF; //TMDS channel_0 LFSR_value

_scrambler[1]=initialValue1 & 0xFFFF; //TMDS channel_1 LFSR_value

_scrambler[0]=initialValue2 & 0xFFFF; //TMDS channel_2 LFSR_value

}

void TmdsScramblerGenerator::AdvanceScrambler(){

// calculating the Scrambler value

for ( int n=0; n<8; n++ ) {

/* author:nihui*/

for(int i=0;i<3;i++)

{

unsigned short lsb=((this->_scrambler[i])>>(16-1))&1;

unsigned short xor1=(lsb^((this->_scrambler[i])>>12&1))<<12;

unsigned short xor2=(lsb^((this->_scrambler[i])>>11&1))<<11;

unsigned short xor3=(lsb^((this->_scrambler[i])>>10&1))<<10;

//lfsr&=~BIT0;

(this->_scrambler[i])&=~BIT12;

(this->_scrambler[i])&=~BIT11;

(this->_scrambler[i])&=~BIT10;

(this->_scrambler[i])|=xor1; //replace BIT12 with xor result

(this->_scrambler[i])|=xor2; //replace BIT11 with xor result

(this->_scrambler[i])|=xor3; //replace BIT10 with xor result

(this->_scrambler[i])<<=1; //left shift

(this->_scrambler[i])|=lsb; //replace BIT0 with original BIT15

}

void TmdsScramblerGenerator::ResetScrambler()

{

this->_scrambler[2] = TmdsScramblerGenerator::SCRAMBLER_RESET_VALUE;

this->_scrambler[1] = TmdsScramblerGenerator::SCRAMBLER_RESET_VALUE1;

this->_scrambler[0] = TmdsScramblerGenerator::SCRAMBLER_RESET_VALUE2;

}

const int& TmdsScramblerGenerator::GetScramblerValue(int i) const

{

return this->_scrambler[i];

}

#ifndef TMDS_SCRAMBLER_GENERATOR_DEFINED

#define TMDS_SCRAMBLER_GENERATOR_DEFINED

#ifdef HARDWARELAYER_EXPORTS

#define EXPORT_DECLSPEC __declspec(dllexport)

#else

#define EXPORT_DECLSPEC __declspec(dllimport)

#endif

class EXPORT_DECLSPEC TmdsScramblerGenerator{

static const unsigned short SCRAMBLER_RESET_VALUE =0xFFFFu;

static const unsigned short SCRAMBLER_RESET_VALUE1 =0xFFFEu;

static const unsigned short SCRAMBLER_RESET_VALUE2 =0xFFFDu;

unsigned short _scrambler[3];

public:

TmdsScramblerGenerator();

//Creates a TmdsScramblerGenerator with the scrambler generator initialized to a specified value.

//The low 8 bits are the bits used to XOR with the TMDS 8-bit data. The LSB of the initial value will

//be XOR'd with the LSB of the TMDS 8-bit data.

TmdsScramblerGenerator(int initialValue,int initialValue1,int initialValue2);

void AdvanceScrambler();

void ResetScrambler();

//Gets the current 16-bit scrambler value. The low 8-bits are the bits used to XOR with

//TMDS 8-bit data to scramble/descramble. The LSB of the scrambler value is XOR'd with the LSB

//of the TMDS 8-bit data.

const int& GetScramblerValue(int i) const;

};

#endif

迭代器：

#ifndef TMDS_SCRAMBLING_ITERATOR_INCLUDED

#define TMDS_SCRAMBLING_ITERATOR_INCLUDED

#include <iterator>

#include "TmdsDecodedData.h"

#include "TmdsScramblerGenerator.h"

#include "TmdsDepacketizedData.h"

#ifdef HARDWARELAYER_EXPORTS

#define EXPORT_DECLSPEC __declspec(dllexport)

#else

#define EXPORT_DECLSPEC __declspec(dllimport)

#endif

class Tmds8IteratorInterface;

class EXPORT_DECLSPEC TmdsScramblingIterator : public std::iterator<

std::forward_iterator_tag,

Tmds_8Bit /* TmdsData */,

ptrdiff_t,

Tmds_8Bit*,

Tmds_8Bit>

{

private:

Tmds8IteratorInterface* _pIter;

TmdsScramblerGenerator _scramblerGenerator;

int _rrCount;

public:

TmdsScramblingIterator (Tmds_8Bit* to_be_encoded);

TmdsScramblingIterator(TmdsDescramblingIterator to_be_encoded);

TmdsScramblingIterator(const TmdsScramblingIterator& other); //Copy constructor

TmdsScramblingIterator(TmdsScramblingIterator&& other); //Move constructor

TmdsScramblingIterator& operator=(const TmdsScramblingIterator& other); //Copy-Assign operator

TmdsScramblingIterator& operator=(TmdsScramblingIterator&& other); //Move-Assign operator

~TmdsScramblingIterator(); //Destructor

TmdsScramblingIterator& operator++(); //Prefix operator

TmdsScramblingIterator operator++(int); //Postfix operator

Tmds_8Bit operator*() const; // Dereference

bool operator==(const TmdsScramblingIterator& other) const;

bool operator!=(const TmdsScramblingIterator& other) const;

//Resets the randomizer (scrambler) and inserts four RR symbols into the stream

void ResetRandomizer();

//Resets the randomizer (scrambler) and inserts n_symbols RR symbols into the stream.

//This can be used to add a non-standard number of RR symbols

void ResetRandomizer(int n_symbols);

//Advances the internal iterator by 1, but does not advance the scrambler.

//Pre-condition: The TmdsScramblingIterator currently points to a gap character

//void SkipGap();

};

#endif

区别操作符的前缀和后缀形式：

问题：他们的形参数目和类型相同，普通重载不能区别所定义的是前缀操作符还是后缀操作符。

为了解决这一问题，后缀式操作符函数接受一个额外的int型参数。使用后缀操作符时，编译器提供0作为这个形参的实数。为了与内置操作符一致，后缀式操作符应咖灰旧值（尚未自增或自减），并且应作为值返回，而不是引用返回。

1 2	TmdsScramblingIterator& operator++(); //Prefix operator TmdsScramblingIterator operator++(int); //Postfix operator

TmdsScramblingIterator& TmdsScramblingIterator::operator++(){ //Prefix operator

if(_rrCount==8)

this->_scramblerGenerator.ResetScrambler();

else

this->_scramblerGenerator.AdvanceScrambler();

return *this;

}

TmdsScramblingIterator TmdsScramblingIterator::operator++(int){ //Postfix operator

auto temp = *this;

this->operator++();

return temp;

}