Statistical Tests for Cryptographic Randomness

Description

Performs cryptographic randomness tests on a sequence of random integers or bits. Included tests are greatest common divisor, birthday spacings, book stack, adaptive chi-square, topological binary, and three random walk tests. Tests except greatest common divisor and birthday spacings are not covered by standard test suites. In addition to the chi-square goodness-of-fit test, results of Anderson-Darling, Kolmogorov-Smirnov, and Jarque-Bera tests are also generated by some of the cryptographic randomness tests. Additionally, it includes functions for the calculation of greatest common divisor, the Stirling numbers of the second kind, critical value of the topological binary test, and base conversions from base 2 to 10 and vice versa.

Details

To test statistical randomness of cryptographic randomness use functions birthday.spacings and GCD.test for testing sequences of integers, functions adaptive.chi.square and book.stack for testing sequences of integers or bits, and use functions random.walk.tests and topological.binary for testing sequences of bits. The function random.walk.tests performs random walk-excursion, random walk-expansion, and random walk-height tests.

Additionally, use the function GCD.q to compute greatest common divisor (GCD), the number of iterations required to find GCD, and the sequence of partial quotients for two integers. Use the function GCD to compute GCD and the number iterations required to find GCD, recursively. Use the function GCD.big to compute GCD, the number iterations required to find GCD, and the sequence of partial quotients for two big integers. Use the function Strlng2 to compute the Stirling numbers of the second kind in an approximate manner when the inputs are large. Use the function TBT.criticalValue to compute the critical value for the topological binary test at a given level of significance. Use the function toBaseTwo to convert integers (including big integers) from base 10 to 2. Use the function toBaseTen to convert binary sequences (including long binary sequences) from base 2 to 10.

Note

Acknowledgement: The package CryptRndTest is based upon work supported by The Scientific and Technological Research Council of Turkey (TUBITAK) under Grant No. 114F249 of ARDEB-3001 grant.

Author(s)

Haydar Demirhan

Maintainer: Haydar Demirhan <haydarde@hacettepe.edu.tr>

References

Alcover, P.M., Guillamon, A., Ruiz, M.C., A new randomness test for bit sequences. Informatica (2013), 24(3), 339–356.

Bleick, W.W., Wang, P.C.C., Asymptotics of Stirling Numbers of the Second Kind. Proceedings of the American Mathematical Society (1974), 42(2), 575–580.

Doganaksoy, A., Calik, C., Sulak, F., Turan, M.S., New randomness tests using random walk, In: National Cryptology Symposium II, (2006), Ankara, Turkey.

Marsaglia, G., Tsang, W.W., Some Difficult-to-pass tests of randomness. Journal of Statistical Software (2002), 7(3).

Ryabko, B.Ya., Monarev, V.A., Using information theory approach to randomness testing. Journal of Statistical Planning and Inference (2005), 133, 95–110.

Ryabko, B.Ya., Stognienko, V.S., Shokin Yu.I., A new test for randomness and its application to some cryptographic problems. Journal of Statistical Planning and Inference (2004), 123, 365–376.

Temme, N.M., Asymptotic estimates of Stirling numbers. Studies in Applied Mathematics (1993), 89, 233–243.

See Also

adaptive.chi.square, birthday.spacings, book.stack, GCD.test, GCD, GCD.q, GCD.big, random.walk.tests, topological.binary, Strlng2, Stirling2

Examples

# ----- General settings ---
RNGkind(kind = "Super-Duper")
B=8                  # Bit length is 8.
k=2000               # Generate 20000 integers.
alpha=0.05

# ----- Adaptive chi-square -----
A=0
A=round(runif(k,0,(2^B-1)))
S=2                 # Divide alphabet to two sub-sets.
test1=adaptive.chi.square(x=A, B, S, alpha, bit = FALSE)
print(test1)

# ----- Birthday Spacings -----
m=16                  # Number of birthdays is 16.
n=2^B                 # Length of year is 256.
lambda=(m^3)/(4*n)     
x=round(runif(k,0,(2^B-1)))
test2=birthday.spacings(x, m, n, alpha, lambda, num.class=10)
print(test2)

# ----- Book Stack -----
n=B*(2^(B/2))         # Number of required bits.
N=n/B                 # Number of integers to be generated.
A=0
A=round(runif(N,0,(2^B-1)))
K=2                   # Divide alphabet to two sub-sets.
test3=book.stack(x=A, B, k = K, alpha, bit = FALSE)
print(test3)

# ----- Toplogical Binary Test -----

dat=round(runif(k,0,(2^B-1)))
x=sfsmisc::digitsBase(dat, base= 2, B) #Convert to base 2
critical.value=150                     #Obtained for B=8
test4=topological.binary(x, B, alpha, critical.value)
print(test4)

# ----- Other Functions -----
# ----- GCD -----
result=GCD(45,2)
print(result)

result=GCD(321235,25521)
print(result)

# ----- Striling 2 -----
Strlng2(1500,410,log=TRUE)  # Large values of n and k

Results

R version 3.3.1 (2016-06-21) -- "Bug in Your Hair"
Copyright (C) 2016 The R Foundation for Statistical Computing
Platform: x86_64-pc-linux-gnu (64-bit)

R is free software and comes with ABSOLUTELY NO WARRANTY.
You are welcome to redistribute it under certain conditions.
Type 'license()' or 'licence()' for distribution details.

R is a collaborative project with many contributors.
Type 'contributors()' for more information and
'citation()' on how to cite R or R packages in publications.

Type 'demo()' for some demos, 'help()' for on-line help, or
'help.start()' for an HTML browser interface to help.
Type 'q()' to quit R.

> library(CryptRndTest)
Loading required package: MissMech
Loading required package: kSamples
Loading required package: SuppDists
Loading required package: sfsmisc
Loading required package: Rmpfr
Loading required package: gmp

Attaching package: 'gmp'

The following objects are masked from 'package:sfsmisc':

    factorize, is.whole

The following objects are masked from 'package:base':

    %*%, apply, crossprod, matrix, tcrossprod

C code of R package 'Rmpfr': GMP using 64 bits per limb


Attaching package: 'Rmpfr'

The following objects are masked from 'package:stats':

    dbinom, dnorm, dpois, pnorm

The following objects are masked from 'package:base':

    cbind, pmax, pmin, rbind

Loading required package: parallel
> png(filename="/home/ddbj/snapshot/RGM3/R_CC/result/CryptRndTest/CryptRndTest-package.Rd_%03d_medium.png", width=480, height=480)
> ### Name: CryptRndTest-package
> ### Title: Statistical Tests for Cryptographic Randomness
> ### Aliases: CryptRndTest-package CryptRndTest
> ### Keywords: Anderson-Darling, chi-Square, goodness-of-fit test, greatest
> ###   common divisor, Stirling numbers of the second kind, Jarque-Bera,
> ###   Kolmogorov-Smirnov, nonparametric, randomness test
> 
> ### ** Examples
> 
> # ----- General settings ---
> RNGkind(kind = "Super-Duper")
> B=8                  # Bit length is 8.
> k=2000               # Generate 20000 integers.
> alpha=0.05
> 
> # ----- Adaptive chi-square -----
> A=0
> A=round(runif(k,0,(2^B-1)))
> S=2                 # Divide alphabet to two sub-sets.
> test1=adaptive.chi.square(x=A, B, S, alpha, bit = FALSE)
> print(test1)

    Test results for Adaptive Chi-Square test
    -----------------------------------------
     Value  : 4.5
      p-Value: 0.034
     Result : Reject H0
    -----------------------------------------> 
> # ----- Birthday Spacings -----
> m=16                  # Number of birthdays is 16.
> n=2^B                 # Length of year is 256.
> lambda=(m^3)/(4*n)     
> x=round(runif(k,0,(2^B-1)))
> test2=birthday.spacings(x, m, n, alpha, lambda, num.class=10)
> print(test2)

    Test results for Birthday Spacings test      
    ----------------------------------------------
     with Anderson-Darling goodness of fit test:
      Value  : 21.692
      p-Value: <0.001
      Result : Reject H0
    ----------------------------------------------
     with Kolmogorov-Smirnov goodness of fit test:
      Value  : 0.344
      p-Value: <0.001
      Result : Reject H0
    ----------------------------------------------
     with Chi-Square goodness of fit test:
      Value  : 71.927
      p-Value: <0.001
      Result : Reject H0
    ----------------------------------------------> 
> # ----- Book Stack -----
> n=B*(2^(B/2))         # Number of required bits.
> N=n/B                 # Number of integers to be generated.
> A=0
> A=round(runif(N,0,(2^B-1)))
> K=2                   # Divide alphabet to two sub-sets.
> test3=book.stack(x=A, B, k = K, alpha, bit = FALSE)
> print(test3)

    Test results for Book Stack test
    -----------------------------------------
     Value  : 209.067
     p-Value: <0.001
     Result : Reject H0
    -----------------------------------------> 
> # ----- Toplogical Binary Test -----
> 
> dat=round(runif(k,0,(2^B-1)))
> x=sfsmisc::digitsBase(dat, base= 2, B) #Convert to base 2
> critical.value=150                     #Obtained for B=8
> test4=topological.binary(x, B, alpha, critical.value)
> print(test4)

    Test results for Topological Binary test
    -----------------------------------------
     Value  : 256
     Result : Not reject H0
    -----------------------------------------> 
> # ----- Other Functions -----
> # ----- GCD -----
> result=GCD(45,2)
> print(result)
$k
[1] 2

$g
[1] 1

> 
> result=GCD(321235,25521)
> print(result)
$k
[1] 13

$g
[1] 1

> 
> # ----- Striling 2 -----
> Strlng2(1500,410,log=TRUE)  # Large values of n and k
[1] 6952.462
> 
> 
> 
> 
> 
> dev.off()
null device 
          1 
>