nist

package
v0.0.0-...-c8519f9 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: May 7, 2024 License: MIT Imports: 7 Imported by: 0

Documentation

Index

Constants

This section is empty.

Variables

View Source 
var (
	ErrNotEnoughLength = errors.New("input length of sequence is too small (n < 128)")
	ErrInvalidValueK   = errors.New("invalid value of K")
	ErrInvalidValueM   = errors.New("invalid value of M")
)
View Source 
var (
	// MAXLOG is the maximum log value to prevent underflow.
	MAXLOG float64 = 7.09782712893383996732e2

	// MACHEP is the machine epsilon, which is the smallest number such that
	// 1.0 + MACHEP > 1.0. It is used as a convergence criterion.
	MACHEP float64 = 1.38777878078144567553e-17
)
View Source 
var ErrEmptyBitStream = errors.New("empty bitstream")
View Source 
var ErrSequenceTooShort = errors.New("input sequence length should be at least 100 bits")

Functions

func ApproximateEntropy 

func ApproximateEntropy(m uint64, bs *b.BitStream) (float64, bool, error)

func BlockFrequencyTest 

func BlockFrequencyTest(bs *b.BitStream, M uint64) (float64, bool, error)

BlockFrequencyTest performs the Frequency Test Within a Block as defined in NIST SP800-22. It takes a BitStream and block size M as input and returns the P-value of the test, a bool representing if the P-value suggests randomness (true if P >= 0.01), and an error if any.

Parameters:

  • B: The template to be searched for in the bitstream.

Returns:

  • p_value: The p-value of the test.
  • bool: True if the test passes (p-value >= 0.01), False otherwise.
  • error: Any error that occurred during the test, such as invalid input parameters.

func CumulativeSums 

func CumulativeSums(mode int, bs *b.BitStream) (float64, bool, error)

func DFT 

func DFT(bs *b.BitStream) (float64, bool, error)

DFT performs the Discrete Fourier Transform (Spectral) test on the given bitstream. The purpose of this test is to detect periodic features in the input sequence that would indicate a deviation from the assumption of randomness. The test uses the discrete Fourier transform to calculate the magnitude of the Fourier coefficients of the input sequence. It then compares the peak heights (the moduli of the Fourier coefficients) to a threshold value. If the number of peaks exceeding the threshold is significantly different from the expected number (95% of n/2), the sequence is considered non-random.

Parameters:

  • B: The template to be searched for in the bitstream.

Returns:

  • p_value: The p-value of the test.
  • bool: True if the test passes (p-value >= 0.01), False otherwise.
  • error: Any error that occurred during the test, such as invalid input parameters.

func FrequencyTest 

func FrequencyTest(bs *b.BitStream) (float64, bool, error)

FrequencyTest evaluates the randomness of a sequence of numbers ranging from 0 to 255, which are read from a file and used as a bitstream. This function applies the monobit test, a basic test of randomness, which counts the number of 0s and 1s in the bitstream and assesses whether their distribution is close enough to 50/50 as would be expected in a random sequence.

The test calculates the test statistic S_n as follows: 

S_n = |sum from i=1 to n of (2 * x_i - 1)|

where x_i represents each bit in the sequence (0 or 1).

This statistic is then normalized to account for the length of the sequence: 

S_obs = S_n / sqrt(n)

where n is the total number of bits.

The final result of the test is determined by calculating a P-value using the complementary error function: 

P = erfc(S_obs / sqrt(2))

A P-value of 0.01 or higher suggests that the sequence can be considered random with a confidence level of 99%. If the P-value is less than 0.01, the sequence is considered non-random, indicating potential patterns or biases in the distribution of bits.

Returns the P-value of the test, a boolean indicating whether the sequence is considered random, and an error if there is an issue with the input bitstream.

Parameters:

  • B: The template to be searched for in the bitstream.

Returns:

  • p_value: The p-value of the test.
  • bool: True if the test passes (p-value >= 0.01), False otherwise.
  • error: Any error that occurred during the test, such as invalid input parameters.

func LinearComplexity 

func LinearComplexity(M uint64, bs *b.BitStream) (float64, bool, error)

LinearComplexity implements the linear complexity test from NIST SP-800-22. The purpose of this test is to determine the length of the linear feedback shift register (LFSR) that generates the given sequence. The linear complexity of a sequence is the length of the shortest LFSR that can generate the sequence.

The test partitions the input sequence into N independent blocks of length M, where n = M*N and n is the length of the input sequence. It then determines the linear complexity of each block using the Berlekamp-Massey algorithm.

The Berlekamp-Massey algorithm is an iterative algorithm that finds the shortest LFSR that generates a given sequence. It maintains two arrays: C (the connection polynomial) and B (the feedback polynomial). At each iteration, it computes the discrepancy d between the next bit of the sequence and the bit generated by the current LFSR. If d is 1, it updates the connection polynomial C and the feedback polynomial B.

The test computes the theoretical mean and a normalized value T for each block's linear complexity. It then counts the occurrences of T values in predefined ranges and computes a chi-square statistic. Finally, it computes the p-value using the incomplete gamma function.

The test returns the p-value, a boolean indicating whether the p-value is greater than or equal to 0.01 (the significance level), and an error (if any).

Recommended input 500 ≤ M ≤ 5000

func LongestRunOfOnes 

func LongestRunOfOnes(bs *b.BitStream) (float64, bool, error)

LongestRunOfOnes implements the Longest Run test from NIST SP 800-22. The purpose of this test is to measure the longest run of ones in the input bitstream and evaluate the randomness of the bitstream.

The test proceeds in the following steps:

  1. Determine the block size (M) and the number of blocks (N) based on the length of the input bitstream.
  2. Divide the bitstream into blocks of size M bits.
  3. Measure the longest run of ones in each block and increase the frequency of the corresponding category.
  4. Calculate the chi-square statistic and compute the P-value based on it.
  5. If the P-value is greater than or equal to 0.01, the bitstream is considered random.

The function returns the P-value, the test result (whether the P-value is greater than or equal to 0.01), and an error (if any occurred).

Parameters:

  • B: The template to be searched for in the bitstream.

Returns:

  • p_value: The p-value of the test.
  • bool: True if the test passes (p-value >= 0.01), False otherwise.
  • error: Any error that occurred during the test, such as invalid input parameters.

func NonOverlappingTemplateMatching 

func NonOverlappingTemplateMatching(B []uint8, eachBlockSize uint64, bs *b.BitStream) (float64, bool, error)

NonOverlappingTemplateMatching performs the Non-overlapping Template Matching test from NIST SP-800-22. It counts the number of occurrences of a given template B in non-overlapping blocks of the input bitstream. The bitstream is divided into N independent blocks of length M, and the test determines whether the number of occurrences of B in each block is approximately what would be expected for a random sequence.

Parameters:

  • B: The template to be searched for in the bitstream.
  • eachBlockSize: The length of each independent block (M).
  • bs: The input bitstream.

Returns:

  • p_value: The p-value of the test.
  • bool: True if the test passes (p-value >= 0.01), False otherwise.
  • error: Any error that occurred during the test, such as invalid input parameters.

func OverlappingTemplateMatching 

func OverlappingTemplateMatching(B []uint8, eachBlockSize uint64, bs *b.BitStream) (float64, bool, error)

OverlappingTemplateMatching performs the Overlapping Template Matching test from NIST SP-800-22. It checks for the number of occurrences of a given template B in the input bitstream. The bitstream is divided into N independent blocks of length M, and the test determines whether the number of occurrences of B in each block is approximately what would be expected for a random sequence.

Parameters:

  • B: The template to be searched for in the bitstream.
  • eachBlockSize: The length of each independent block (M).
  • bs: The input bitstream.

Returns:

  • p_value: The p-value of the test.
  • bool: True if the test passes (p-value >= 0.01), False otherwise.
  • error: Any error that occurred during the test, such as invalid input parameters.

func Pr 

func Pr(u int, eta float64) float64

Pr calculates the probability of observing u occurrences of the template in a block of length M, given the expected number of occurrences (eta).

Parameters:

  • u: The number of occurrences of the template.
  • eta: The expected number of occurrences of the template.

func RandomExcursions 

func RandomExcursions(bs *b.BitStream) ([]float64, []bool, error)

func RandomExcursionsVariant 

func RandomExcursionsVariant(bs *b.BitStream) ([]float64, []bool, error)

func Rank 

func Rank(bs *b.BitStream) (float64, bool, error)

Rank performs the Binary Matrix Rank Test on the given bitstream. The purpose of this test is to check for linear dependence among fixed-length substrings of the original sequence. The test constructs matrices from the input sequence and determines the rank of each matrix. It then compares the rank distribution to the expected distribution for a random sequence. Deviations from the expected distribution indicate non-randomness.

The test proceeds as follows:

  1. Divide the input sequence into M = n/Q non-overlapping blocks of length Q, where n is the length of the input sequence.
  2. Construct a Q x Q matrix from each block by writing the bits in the block in row-major order.
  3. Determine the binary rank of each matrix using Gaussian elimination.
  4. Count the number of matrices with each rank (full rank, full rank-1, and other ranks).
  5. Compute the Chi-square statistic based on the observed and expected counts for each rank.
  6. Compute the p-value using the incomplete Gamma function.

Parameters:

  • B: The template to be searched for in the bitstream.

Returns:

  • p_value: The p-value of the test.
  • bool: True if the test passes (p-value >= 0.01), False otherwise.
  • error: Any error that occurred during the test, such as invalid input parameters.

func RankComputationOfBinaryMatrices 

func RankComputationOfBinaryMatrices(matrix [][]uint8) uint64

func Runs 

func Runs(bs *b.BitStream) (float64, bool, error)

Runs function returns "The total number of runs" across all n bits.Runs The total number ofruns + the total number of one-runs.

Parameters:

  • B: The template to be searched for in the bitstream.

Returns:

  • p_value: The p-value of the test.
  • bool: True if the test passes (p-value >= 0.01), False otherwise.
  • error: Any error that occurred during the test, such as invalid input parameters.

func Serial 

func Serial(m uint64, bs *b.BitStream) ([]float64, []bool, error)

func Uint_To_BitsArray_size_N 

func Uint_To_BitsArray_size_N(input uint64, N uint64) (bitArray []uint8)

func Universal 

func Universal(L uint64, Q uint64, n uint64, bs *b.BitStream) (float64, bool, error)

input size recommendation n >= (Q + K) * L 6 <= L <= 16, Q = 10 * 2^L, k = floor(n/L) - Q ~= 1000 * 2^L

func UniversalRecommendedValues 

func UniversalRecommendedValues(bs *b.BitStream) (float64, bool, error)

Types

This section is empty.

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.