在KW3x上产生真伪随机数

NXP管管

在KW3x上产生真伪随机数

1、概述


在我们日常生活当中会遇到很多的随机事件，比如玩掷骰子，骰子只有6个面，掷到每个面的概率是一样的，只要掷的次数足够多，每个点数出现的次数基本一致。但是点数出现的顺序没有规律，也没办法预测下次掷到的点数，这是真随机事件。


固定去某个饭店吃饭，菜单里有ABCDEFG套餐，选哪个套餐是随机的，但某些套餐比较合你口味或者比较实惠，所以你选这些套餐的次数比较多，而其他不合口味或者偏贵的套餐吃得比较少甚至从来不吃，长期下来可能变成ABC套餐轮流吃。这就是伪随机事件。


在计算机领域也存在真随机数和伪随机数，它们有各自的特点和适用领域。NXP KW3x芯片内置真随机数生成模块TRNG及SDK提供伪随机数生成算法，本文将介绍真伪随机数的特点、统计测试方法和在KW3x芯片中的实现和效率对比。


2、什么是真伪随机数

1. 真随机数

真随机数是通过真实随机事件取得的随机数，一般是通过物理现象产生的，比如抛硬币，掷骰子等。在计算机领域通常使用电子元件的嗓音（也包含温度漂移、电压变化等）来获取随机采样数据。

2. 伪随机数

伪随机数是由确定性的算法产生的，呈现均匀分布的随机数序列，具有周期性，但并不是真正随机。算法中相同的输入会得到相同的输出。在调用伪随机数算法之前一般需定义初始种子，作为算法的初始输入，算法执行一次后的输出可作为下次算法执行的输入。

3. 熵

在物理学中，熵（Entropy）是一个描述系统混乱程度的物理量，熵越大说明系统越无序、越混乱，不确定性越大。信息熵是描述信息的复杂程度，如果信息杂乱无章，毫无规律可循，随机性强，说明信息熵比较高；反之，如果信息可预测，有一定的确定性，就说明熵比较低。
计算机领域的随机数一般表示为一串0和1组成的无序比特序列。计算机硬件或者芯片通过采集随机噪声生成真随机数，这个真随机数也称为熵。这个熵可以直接用于加密等一些程序应用，也可以作为伪随机数算法的种子，通过算法产生伪随机数。


3、随机数统计测试方法


上文提到，计算机随机数是由0和1组成的无序比特序列。一些标准里制定了相关统计测试方法，可检测这个比特序列的随机性是否足够强。常用测试方法有频率测试（Monobit test）、扑克测试（Pokertest）、游程测试（Runs test）、长游程测试（Long runs test）等。

1. 频率测试

比特序列只含0和1，频率测试需要保证一个长比特序列里0和1的个数基本相等，避免0或1过多的情况。具体判断范围可以设定，过于严苛可能导致随机数反复生成失败，过于宽泛会导致随机性过低。比如256位的比特序列，我们可能设定0和1出现的合理次数为(118,138)，如果0和1在这个序列的个数落在这个范围里，表示符合测试，否则不符合测试，需要重新生成。

2. 游程测试

一个游程是指在一个长序列中连续0或1的短序列。1位游程是指连续出现1个0或1个1的短序列，2位游程是指连续出现2个0或2个1的短序列，3、4、5位游程以此类推。连续6个及以上0或1的短序列统称为6位游程或6+位游程。


举例0101 1001 1110 0011这个16位序列，它的1位游程个数3；2位游程个数为3；3位游程为1；4位游程为1；5和6+位游程为0。


游程测试则是根据随机长序列的总位数，设定合理的各位游程最大最小出现次数，如果随机序列各位游程出现次数均在设定范围内，表示通过测试，否则不通过。

3. 长游程测试

如果一个长序列中出现一个特别长的连续0或1的序列，称为存在长游程。举例随机数为256位的长序列，设置长游程位数为20，假如这个长序列中出现连续20个以上的0或1，则表示测试不通过。

4. 扑克测试

将长比特序列连续每4位分为一组，每组里的比特序列有16种可能（0000,0001…1111）。将每种可能在这个长比特序列里出现的次数分别相加，得到16个数据，然后计算这16个数据的平方和。如果这个结果落在某个范围内，表示通过扑克测试，否则不通过。


4、在KW3x上生成随机数

1. TRNG模块功能

在KW3x系列芯片内部有一个真随机数生成器（TrueRandom Number Generator，TRNG）。TRNG通过一个对噪声敏感的环形振荡器，来生成512位的随机数。


噪声会导致振荡器周期发生各种微小变化，在每段设定的时间段里对环形振荡器时钟周期的计数进行采样，则每次采样时该计数都会不一样。通过使用大量样本中此计数的差异，可以得出随机位，最后输出512位随机数，也称512位的熵。


熵生成的快慢，取决于所选取的时钟、采样位数、每位数的设定采样时间等。生成熵后，TRNG也会自动使用频率测试、游程测试等方法对所生成的数进行统计测试。


举例KW36，在SDK/devices/MKW36A4/drivers/fsl_trng.h中，定义了trng_config_t结构体，用于配置TRNG的相关参数：

1. typedef struct_trng_user_config
   
2. {
   
3.     bool lock;
   
4.     trng_clock_mode_t clockMode;
   
5.     trng_ring_osc_div_t ringOscDiv;
   
6.     trng_sample_mode_t sampleMode;
   
7.     uint16_t entropyDelay;
   
8.     uint16_t sampleSize;
   
9.          …
   
10.     trng_statistical_check_limit_tmonobitLimit;
    
11.     trng_statistical_check_limit_trunBit1Limit;
    
12.     trng_statistical_check_limit_trunBit2Limit;
    
13.     …
    
14.     trng_statistical_check_limit_trunBit6PlusLimit;
    
15.     trng_statistical_check_limit_t pokerLimit;
    
16.     trng_statistical_check_limit_tfrequencyCountLimit;
    
17. } trng_config_t;

复制代码

其中ringOscDiv、sampleMode、entropyDelay、sampleSize等用于配置TRNG随机数的生成，而monobitLimit、runBit1Limit、pokerLimit等用于随机数统计测试参数的设置。


TRNG_GetDefaultConfig()用于获取TRNG在SDK中的默认配置，但这些配置参数是相关联的，比如改了sampleSize后，那用于统计测试的参数如monobitLimit等也要做相应修改，否则可能导致随机数生成失败。


sampleMode默认为kTRNG_SampleModeRaw，即采用所采集的裸比特数据作为真随机数的输出，用户可根据需要配置成kTRNG_SampleModeVonNeumann或kTRNG_SampleModeVonNeumannRaw，即采用冯-诺依曼校正器对采集比特序列进行校正，即序列两位为1组，为00或11时丢弃，为01时输出1，为10时输出0。这种模式在纠正序列的均匀分布和相关性上有一定效果，但是会丢弃一半以上采样数据，所以生成最终所需真随机数的速率会下降。


在生成随机数前，需将trng_config_t配置参数传入TRNG_Init()进行TRNG初始化。


基于SDK提供的例程：


SDK_2.2.5_MKW36A512xxx4\boards\frdmkw36\driver_examples\trng\random，设置不同的sampleMode和entropyDelay，测量例程中TRNG_GetRandomData()的执行时间，结果如下：

用户可自行修改参数进行测试。但仍请注意修改某些参数可能需要配合修改其他配置参数，否则会导致随机数生成失败。

2. TRNG寄存器

TRNG模块定义了TRNG0寄存器组，用于存放TRNG的配置、生成数据和状态等。比如StatisticalCheck Monobit Limit Register (SCML)用于存放trng_config_t中的monobitLimit参数，StatisticalCheck Monobit Count Register (SCMC)用于存放当前TRNG所生成随机数的monibit测试结果。更多寄存器说明可参考官网MKW36/35/34Reference Manual中的Chapter 44 True Random Number Generator(TRNG) - TRNG0 register descriptions。


重点提出的是，TRNG所产生的512位随机数存放在EntropyRead Register (ENT0-ENT15)共16个寄存器中，每个寄存器存放32位数。在TRNG_GetRandomData()中会调用trng_ReadEntropy()依次读取ENT0-ENT15寄存器的值。当读到ENT15时，ENT0-ENT15的值会自动被清零，随机数会重新生成。当用TRNG_GetRandomData()获取小于512位的数时，会返回前面寄存器的值，如128位则返回ENT0-ENT4的值，然后函数里会主动读取ENT15使所有ENTx的值清零，下次获取时使用新的随机数；当TRNG_GetRandomData()获取大于512位的数时，会先返回ENT0-ENT15的值，然后再次生成新一轮随机数继续输出。也就是说，如果ENT15没有被读取，下次用TRNG_GetRandomData()依然会获取到旧的随机数。

3. 产生伪随机数

TRNG每次生成真随机数都需要硬件实时采集，需要耗费较长的时间。而伪随机数是采用算法生成，效率会快很多，实际应用中经常采用这种方式来获取随机数。


需给伪随机数算法一个初始输入（种子），输出一个随机数，然后这个随机数作为下一次算法执行的输入，继续输出下一个随机数。当初始输入相同时，第一次算法输出就相等，下一次输出也相等，前后会得到完全相同的随机数序列。这并不是我们所期望的，所以我们常给一个随机的初始输入。在KW3xSDK中，TRNG的真随机数即作为伪随机算法的初始输入，然后生成不同的随机数序列。


在SDK\boards\frdmkw36\wireless_examples\bluetooth的例程当中，ApplMain.c中main_task()里会调用RNG_Init()进行伪随机数生成器的初始化。在RNG_Init()里，会用TRNG_GetRandomData()获取一个32位真随机数作为种子，用SecLib_set_rng_seed()将此种子设置到安全算法库中，这时即可用SecLib_get_random()获取32位随机数。RNG_Init()执行后用RNG_SetPseudoRandomNoSeed()设置RNG算法的256位种子，这个256位种子是由用SecLib_get_random()获取8个32位随机数来组成。至此，RNG算法的种子设置完成，后面就可以用RNG_GetPseudoRandomNo()获取任意长度的随机数。

4. 真伪随机数产生效率

真随机数基于实际硬件当前噪声产生，随机性强，没有规律，但是耗费时间较长；而伪随机数通过算法产生，具有一定的周期性和可预测性，但是生成效率快。两者均有各自的适用场景。下面基于
SDK\boards\frdmkw36\wireless_examples\bluetooth\w_uart配合GPIO 和逻辑分析仪测试下两者的效率。

在main_task()里面已经完成对TRNG和RNG的初始化，直接在board.c的hardware_init()和wireless_uart.c的BleApp_Init()增加以下代码进行测试:

1. void hardware_init(void)
   
2. {
   
3.     static uint8_t initialized = 0;
   
4.     if( !initialized )
   
5.     {
   
6.         …
   
7.                PORT_SetPinMux(PORTC, 5U, kPORT_MuxAsGpio);
   
8.                 gpio_pin_config_t test_config = { kGPIO_DigitalOutput, 1,  };
   
9.                 GPIO_PinInit(GPIOC, 5U, &test_config);
   
10.      }
    
11. }
    
12. 
    
13. void BleApp_Init(void)
    
14. {
    
15.         ……
    
16. 
    
17.         uint8_t pRandom[16] = {0};
    
18.             uint32_t tRandom[4] = {0};
    
19.             GPIO_ClearPinsOutput(GPIOC, (1 << 5U));
    
20.             RNG_GetPseudoRandomNo(pRandom, 16, NULL);
    
21.             GPIO_SetPinsOutput(GPIOC, (1 << 5U));
    
22.             TRNG_GetRandomData(TRNG0, tRandom, 4 * sizeof(uint32_t));
    
23.             GPIO_ClearPinsOutput(GPIOC, (1 << 5U));
    
24. }

复制代码

从测试结果发现，用TRNG_GetRandomData()产生128位随机数需要67.66ms，而RNG_GetPseudoRandomNo()只需要0.3038ms，效率相差百倍以上。

图1：真伪随机数产生效率时间对比

由此可见，伪随机数在一些对效率要求高的场合比较适用。当然，伪随机算法也很重要，具体可参考SDK中RNG_GetPseudoRandomNo()的代码实现。

阅读全文

jobszheng5

随机数的产生还有这么大的学问呢啊~~
长见识了。