小结: 通读NIST的文档，大致明白其中随机性的检测的原理。
-
Frequency (Monobit) Test:
频数测试: 二进制中的0和1出现的次数应该基本一样 -
Frequency Test within a Block:
块内频数测试: 非重叠的区块(M bit)中1出现的次数应该接近一半(M/2) -
Runs Test:
游程测试: 0序列的长度与1序列的长度是否随机 -
Test for the Longest Run of Ones in a Block:
块内游程测试: 非重叠的区块(M bit)中0序列的长度与1序列的长度是否随机 -
Binary Matrix Rank Test:
矩阵秩的测试: 转化为矩阵, 求秩, 判断固定长度的的子串的相关性 -
Discrete Fourier Transform (Spectral) Test:
离散傅里叶变换测试: 做离散傅里叶变换, 看峰高的差异: 判断是否有周期性特征 -
Non-overlapping Template Matching Test:
非重叠模板匹配测试: 做模板匹配测试: (不重叠)搜索重复出现的相同序列 -
Overlapping Template Matching Test:
重叠模板匹配测试: 搜索重复出现的特定长度的1的序列 -
Maurer’s “Universal Statistical” Test:
可压缩性测试: 可压缩率与随机性负相关 -
Linear Complexity Test:
线性复杂度测试: 与随机性负相关 -
Serial Test:
连续性测试: m-bit的序列在2^m bit内的唯一性 -
Approximate Entropy Test:
近似熵测试: m-bit的序列在2^m bit的所有区块出现的频度 -
Cumulative Sums (Cusum) Test:
部分和测试: 区块累加, 然后左右平移, 看累加值变化 -
Random Excursions Test:
随机游走测试: 某个特定状态出现的次数是否远远超过真随机序列中的情况 -
Random Excursions Variant Test:
随机游走变量测试: 某一特定状态在一个游机游程中出现次数与真随机序列的偏离程度
- 128KiB (以/dev/urandom测试得出)
- Small Crush (大约10种测试的组合)
- Crush (大约60种测试的组合)
- Big Crush (大约45种测试的组合)
- Introduction to Secure PRNGs
- TestU01: AC library for empirical testing of random number generators
- TestU01: A Software Library in ANSI C for Empirical Testing of Random Number Generators--User's Guide, Compact Version
package main
import (
"bytes"
"errors"
"fmt"
"os"
"os/exec"
"regexp"
"strconv"
"strings"
"github.com/urfave/cli"
)
var (
errSTFail = errors.New("Statistical Testing Failed")
cmdPath = `test.sh`
cmdShell = `
#! /bin/sh
bitRNG=$1
LEN=100000
BITSTREAM=10
rm -rf ./experiments/AlgorithmTesting/finalAnalysisReport.txt
./assess $LEN <<-EOF 2>&1 | grep 'Statistical Testing'
0
$bitRNG
0
111111111010011
0
$BITSTREAM
1
EOF
cat ./experiments/AlgorithmTesting/finalAnalysisReport.txt
`
)
func main() {
app := cli.NewApp()
app.Name = "rank"
app.Usage = "Rank RNG"
app.Flags = []cli.Flag{
cli.StringFlag{
Name: "file, f",
Usage: "RNG Date Path",
},
}
app.Action = func(c *cli.Context) error {
dataPath := c.String("file")
if 0 == len(dataPath) {
cli.ShowAppHelp(c)
} else {
fout, err := os.Create(cmdPath)
if err != nil {
return err
}
defer fout.Close()
defer os.Remove(cmdPath)
fout.Write([]byte(cmdShell))
if err := os.Chmod(cmdPath, 0755); err != nil {
return err
}
cmd := exec.Command("/bin/sh", cmdPath, dataPath)
var cmdOut bytes.Buffer
cmd.Stdout = &cmdOut
if err = cmd.Run(); err != nil {
return errSTFail
}
result := cmdOut.String()
if !strings.Contains(result, "Statistical Testing Complete") ||
!strings.Contains(result, fmt.Sprintf("generator is <%s>", dataPath)) {
return errSTFail
}
fraction := regexp.MustCompile(".*[^0-9]([0-9]+/[0-9]+).*").ReplaceAllString(result, "$1")
// fmt.Printf("%+v", fraction)
fractions := regexp.MustCompile("([0-9]+/[0-9]+)").FindAllString(fraction, -1)
// fmt.Printf("%+v", fractions)
extract := regexp.MustCompile("([0-9]+)/([0-9]+)")
numeratorSUM, denominatorSUM := 0, 0
for _, str := range fractions {
numerator, _ := strconv.Atoi(extract.ReplaceAllString(str, "$1"))
numeratorSUM += numerator
denominator, _ := strconv.Atoi(extract.ReplaceAllString(str, "$2"))
denominatorSUM += denominator
}
fmt.Printf("Rank: %.8f (%d of %d NIST-Test Passed!)\n",
float64(numeratorSUM)/float64(denominatorSUM),
numeratorSUM, denominatorSUM,
)
}
return nil
}
if err := app.Run(os.Args); err != nil {
fmt.Println(err)
}
}~/sts-2.1.2 » dd if=/dev/urandom of=./data/urandom bs=128K count=1
1+0 records in
1+0 records out
131072 bytes (131 kB, 128 KiB) copied, 0.000853436 s, 154 MB/s
~//sts-2.1.2 » go run rank.go -f data/urandom
Rank: 0.98633540 (1588 of 1610 NIST-Test Passed!)#include "unif01.h"
#include "ulcg.h"
#include "bbattery.h"
#include <stddef.h>
int main (void) {
unif01_Gen *gen1, *gen2, *gen3;
gen1 = ulcg_CreateLCG (2147483543, 10064, 0, 12345);
gen2 = ulcg_CreateLCG (2147483563, 16493, 0, 12345);
gen3 = unif01_CreateCombAdd2 (gen1, gen2,"My Combination of LCGs");
bbattery_SmallCrush (gen3);
unif01_DeleteCombGen (gen3);
ulcg_DeleteGen (gen1);
ulcg_DeleteGen (gen2);
return 0;
}- Faster Randomness Testing with the NIST Statistical Test Suite