real time random number generator testing - ISEL

REAL TIME RANDOM NUMBER GENERATOR TESTING
João Dionísio e Tiago Mota
Instituto Superior de Engenharia de Lisboa (ISEL),
Área Departamental de Engenharia Electrónica e Telecomunicações e de Computadores (ADEETC), Lisboa, Portugal,
[email protected] [email protected]
Iola Pinto
Instituto Superior de Engenharia de Lisboa (ISEL),
Área Departamental de Matemática (ADM), Lisboa, Portugal,
[email protected]
Manfred Niehus
Instituto Superior de Engenharia de Lisboa (ISEL),
Área Departamental de Física (ADF), Lisboa, Portugal,
[email protected]
Keywords: Statistics Tests, Binary Sequence, Cryptography, Random Number Generator, p-values, Quantum Optics
Abstract:
1
We present a random number generator (RNG) testing application in LabVIEW®, based on six of the
statistical tests from the ubiquitous NIST suite that is widely used in the field of cryptography. The
implementation is described, and tests measuring performance, both regarding precision and speed, are
demonstrated. The application can be interfaced to real time true RNGs based on quantum optics
experiments.
INTRODUCTION
Numa era informatizada a área da segurança
informática e da criptografia têm vindo a assumir
papéis cada vez mais importantes na proteção de
dados e preservação de privacidade [1]. A segurança
dos cripto-sistemas mais avançados, sejam eles
clássicos [2] ou quânticos [3], depende da
disponibilidade de uma chave de encriptação que só
pode ser utilizada uma única vez (One-Time-Pad), e
cuja sequência terá que ser absolutamente
imprevisível. No entanto, parece agora que
geradores de números aleatórios comerciais
atualmente em uso não garantem, a partida, a
imprevisibilidade da sequência gerada [4].
São disponíveis no domínio público testes
estatísticos de forma a avaliar e quantificar os
geradores de sequências aleatórias. Um conjunto de
de testes estatísticos mais utilizado em aplicações de
criptografia é o NIST Test suite [5].
Apresentamos aqui uma aplicação em
LabVIEW®
(Laboratory Virtual
Instrument
Engineering Workbench), baseado nestes testes, que
permite o processamento e a análise em tempo real
de uma sequência binária, bem como a realização de
testes de aleatoriedade e consequente quantificação
do grau de aleatoriedade da sequência binária.
2
STATISTICAL TESTS
Entende-se por uma sequência aleatória uma
sucessão binária cuja sua ordem não se consegue
prever e que não evidencie qualquer tipo de padrão
ou periodicidade.
O NIST Test Suite [5] é um conjunto de testes
que permitem quantificar o grau de aleatoriedade de
sequências binárias, produzidas por hardware ou
software (RNG). Estes testes concentram-se numa
variedade de diferentes tipos de não-aleatoriedade
que podem existir numa sequência, permitindo
verificar e quantificar o grau de aleatoriedade da
mesma. Foram implementados os testes enumeradas
na tabela 1.
Testes
Frequency
(Monobit) Test
Descrição
Verifica se o número de uns e de zero é
aproximadamente igual
Frequency Test
Within a Block
Verifica se a proporção de uns e zeros
dentro dos blocos de M-bits é
aproximadamente
.
Verifica se a repetição de zeros e uns é o
expectável para uma sequência aleatória.
Verifica se a sequência mais longa de uns,
num bloco de dimensão M, vai de
encontro ao comprimento da maior
sequência de uns, expectável numa
sequência aleatória.
Verifica se existem dependências lineares
entre as sub-matrizes obtidas a partir da
sequência original.
Verifica algumas características
periódicas numa sequência,
nomeadamente repetição intensiva de
certos padrões.
Runs Test (Teste
de Oscilação)
Longest Run of
Ones in Block
Binary Matrix
Rank Test
Discrete Fourier
TransformTest
Tabela 1:Descrição dos testes implementados.
3
Figura 1 - Diagrama de Blocos da aplicação.
3.1 INDIVIDUAL TESTS
Para cada teste estatístico, referidos na Tabela 1
procedeu-se à sua implementação em LabVIEW®.
Descrevemos aqui, a título de exemplo, a estatística
e implementação do Teste 1.
Descrição da estatística do Teste 1
Denota-  '  [1  2 ...  n ] uma sequência binária
de tamanho n pelo vector.
Recebendo como input uma sequência  ' de
tamanho n, os seus zeros e uns são convertidos em 1 e +1 respetivamente e posteriormente somados,
sendo a estatística de teste dada por:
IMPLEMENTATION
Implementou-se em LabVIEW® uma aplicação
capaz de realizar em tempo real os seis testes
descritos, tentando-se aliar a rapidez e eficácia, i.e. o
equilíbrio entre a precisão na análise dos resultados
e a rapidez na aquisição experimental.
Dividir a aplicação em quatro blocos funcionais
principais como mostra a figura1.
No primeiro bloco procede-se à aquisição de
dados que pode ser feita de três formas:
No segundo bloco as sequências binárias são
submetidas ao pacote dos seis testes estatísticos
consoante os parâmetros de inpus fornecidos pelo
utilizador.
No terceiro bloco é realizada uma análise
estatística dos resultados. Começam-se por obter os
P-values para cada um dos testes estatísticos. Para
um dado nível de significância existe uma proporção
de P-values que indicam falhas de aleatoriedade. Por
exemplo, se o nível de significância for 0,01 esperase que cerca de 1% das sequências testadas
indiquem falhas de aleatoriedade. Por fim realiza-se
um histograma dos P-values e procede-se à
realização dum teste estatístico não paramétrico para
avaliar a uniformidade dos mesmos.
No quarto bloco é dada a opção no início de cada
teste de o utilizador guardar num ficheiro de texto os
resultados finais dos testes realizados.
n
X
S
i 1
i
,
n
X i  2 i  1, i  1,..., n
(1)
(2)
Supondo que a hipótese nula é verdadeira (a
proporção de uns é igual a ½), e que a dimensão da
sequência é suficientemente grande, a estatística de
teste segue distribuição normal standardizada.
O cálculo do p-value obtém-se por:
 S 
P  value  erfc  obs  ,
 2 
(3)
Onde erfc representa a complementar error function.
Se P-value <0,01 a sequência não rejeita a hipótese
de aleatoriedade
Implementação do Teste 1
De modo a obter o somatório S, a implementação
inicial processa elemento a elemento: tinha-se um
ciclo for que percorria os elementos do array, a
transformar os zeros em -1. Assim, o teste tornou se
demasiado lento para execução em tempo real.
esta
Figura 2 – LV snippet do Frequency (Monobit) Test
.
Para tornar o teste mais eficiente, implementouse o seguinte procedimento:
1º Passo - Cálculo do número de uns:
n
S1    i
Figura 4 - Histograma de P-Values.
(1)
i 1
2º Passo - Cálculo do número de zeros:
N0  n  S1
(2)
3º Passo - Obtenção do somatório S n :
Sn  S1  N0 .
(3)
4ª Passo - Por fim é calculado o P-value de cada
sequência a partir da fórmula:
S 
P  value  erfc  obs 
 2
(4)
Na Fig. 2 apresentamos um snippet de LV com o
ciclo a realizar o Teste 1.
3.2 DATA ANALYSIS
Após a realização de cada teste a um dado
número de sequências, é avaliada a proporção de pvalues que rejeitam a hipótese de aleatoriedade e
obtem-se (Fig. 3) um histograma de P-values, (Fig.
4) em que no eixo das abcissas estão representadas
as 10 classes de valores em que os P-values se
podem encontrar. O eixo das ordenadas corresponde
à frequência relativa de cada classe.
Neste bloco, verifica-se se com o P-value obtido
se deve rejeitar ou não a hipótese de aleatoriedade,
para um valor de significância , à escolha do
utilizador. Por fim calcula-se a proporção de casos
em que a hipótese de aleatoriedade é rejeitada.
Para um gerador ser considerado aleatório, a
proporção de P-values que levam à rejeição à
hipótese de aleatoriedade para um dado nível de
significância, deverá ser a expectável [6]: por
exemplo para 1000 sequências em teste e para o
nível de significância de 0,01, será expectável obter
aproximadamente dez p-values inferiores a 0,01.
Demonstra-se ainda que a distribuição dos p-values,
para um dado número de sequências, deverá ser
uniforme. Assim sendo, procede-se ao cálculo da
proporção de p-values que levam a rejeitar a
hipótese de aleatoriedade e de forma a avaliar a
uniformidade na distribuição de P-values, realiza-se
um teste à bondade do ajustamento, cuja estatística
de teste, quando a hipótese nula é verdadeira, segue
uma distribuição do Qui-quadrado com nove graus
de liberdade (número de classes) escrevendo-se:
k
X2 
i 1
(Oi  Ei )
Ei
(%
(5
onde:
Oi = # casos observados em cada classe
Ei = # casos expectável em cada classe
K = Número de classes
Após o cálculo do valor observado para a
estatística de teste ( QOBS ), obtém-se o P-value,
2
Figura 3 – LV snippet do cálculo da proporção de Pvalues inferiores a 0,01 em Labview.
calculando a P[ X  QOBS ] . Se P-value  0,01,
podemos considerar a distribuição uniforme e por
consequência aceitar o gerador como tendo boas
propriedades de aleatoriedade.
Figura 5 – LV snippet Histograma de p-values e de χ2
Após a realização dos histogramas parciais
procede-se a análise global dos P-values. Com a
totalidade dos P-values obtém-se o histograma
global, O teste de Qui-quadrado permite concluir
sobre a uniformidade da distribuição.
3.3 User Interface
O interface do utilizador é apresentado na Fig. 6
e descrito seguidamente.
1-Para cada teste é feito um histograma relativo
à frequência dos p-values.
2-Para cada sequência testada é calculado um pvalue, que é colocado num array sendo possível ao
utilizador ver todos os p-values calculados, de notar
que se um p-value for superior a 0,01, a sequência
correspondente pode ser considerada aleatória.
3-Neste ponto são mostrados o número de pvalues inferiores a 0,01 e a respectiva proporção
consoante o número de sequências em teste.
4-Para cada teste é calculada a estatística de teste
respectiva e calculado o p-value relativo à
distribuição xi-quadrado, se o valor for inferior a
0,01 a distribuição não é uniforme e por
consequência o meio é não aleatório.
5-Se o p-value relativo à distribuição chiquadrado for superior a 0,01 o led ficará verde, caso
contrário ficará vermelho.
6-Indica o tempo execução do teste em questão.
7- Indica a quantidade de bit por segundo
processada em cada teste.
Figura 6 – Output Teste
De modo a tornar a aplicação visualmente mais
simples e mais rápida recorreu-se à utilização de
Subvi´s. Este método é o equivalente à chamada de
uma sub-rotina em linguagens de programação
baseadas em texto. Foi assim para cada teste um
Subvi. Bem como um Subvi que procede ao cálculo
da proporção de p-values e um de forma a realizar
os histrogramas e o teste à bondade do ajustamento,
Qui-Quadrado.
Foram em seguida realizados alguns cenários que
obtiveram os seguintes resultados registados na
Tabela 2 e Tabela 3
Pode-se concluir de acordo com os cenários
acima descritos (análise das tabelas 2 e 3), verificase que os todos os cenários podem ser utilizados
para futuras experiencias laboratoriais em tempo
real, pelo facto de apresentarem baixos tempos de
execução perante uma aquisição de dados, quer em
modo individual quer em modo simultâneo.
Observando a tabela 3, verifica-se que existe
uma grande aquisição de bits por segundo em cada
teste estatísticos. No entanto comparando os
cenários, conclui-se que o primeiro está abaixo da
média, apresentando valores entre 2 e 5 megabits por
segundo.
3.4 TIMING
Para quantificar o tempo de execução dos testes
realizados,
realizaram-se
análises
com
quantificadores de tempo real em cada teste. A
figura 7 descreve o formato em que foram colocados
os quantificadores no LabView.
Figura 7 – LV snippet de quantificadores de tempo
Teste 1
Teste 2
Teste 3
Teste 4
Teste 5
Teste 6
1 x n=100000
3
8
7
3
6
6
100 x n=10000
26
43
36
26
28
36
100 x n=100000
280
279
275
251
265
273
Tabela 2 - Tempo de execução de cada Teste em
milissegundo.
Teste 1
Teste 2
Teste 3
Teste 4
Teste 5
Teste 6
1 x n=100000
8,20
8,11
7,26
7,19
6,99
5,73
100 x n=10000
7,06
6,87
5,72
6,72
6,78
5,72
100 x n=100000
8,28
8,14
7,98
7,99
8,21
6,8
Tabela 3 - MegaBits por Segundo de cada Teste.
Constatou-se também uma melhoria significativa
em termos de eficiência no simulador tornando-o
bastante mais rápido com os diversos SubVi’s.
3.5 INTERFACE TO REAL TIME
EXPERIMENT
De forma a implementar uma interface capaz de
realizar testes em tempo real, recorre-se ao uso de
ficheiros TDMS, um formato desenvolvido pela
National Instruments que permite armazenar grandes
quantidades de dados gerados em simulações de uma
forma rápida e estruturada.
Desta forma é dada a possibilidade ao utilizador
de configurar o DAQmx, e integrar em aplicações já
existentes ficheiros TDMS. Utilizando um método
de transmissão de dados em disco que por meio de
várias operações de memória e fazendo bypassings
aos buffers do Windows aumentará a velocidade de
streaming, obtendo um aumento de eficiência
podendo atingir taxas de 1,2 GB/s.
Figura 8 - Implementação TDMS.
O uso de ficheiros TDMS permite a ligação da
aplicação do LabView com uma experiencia
laboratorial, no que diz respeito à captação e leitura
de dados no momento da aquisição, sendo possível
ao utilizador a localização de um determinado
conjunto de dados de forma rápida.
Na Fig. 8 demonstra-se o código que estabelece
o modo de funcionamento do TDMS para aquisição
de dados. Tendo como funções a escrita e leitura
TDMS.
4
RESULTS AND DISCUSSION
Após a implementação da aplicação procedeu-se
à realização dos 6 testes a geradores aleatórios
disponíveis no LabView, o MLS e o Rand, também
existente em Matlab.
Devido ao input mínimo recomendado para o
teste 5 Binary Matrix Rank Test ser de 40000,
optou-se por produzir 100 sequências binárias de
tamanho 50000 de modo a averiguar a qualidade do
gerador. Os resultados dos respetivos testes para os
geradores MLS e Rand seguem abaixo descritos na
Nº PValues<0,01
MLS
RAND
Teste 1
Teste 2
Teste 3
Teste 4
Teste 5
Teste 6
HISTOGRAMA
FINAL
0
1
0
3
0
0
-
1
0
3
0
0
0
-
Uniformidade
MLS
RAND
SIM
SIM
SIM
SIM
NÃO
SIM
NÃO
SIM
SIM
SIM
SIM
NÃO
NÃO
NÃO
Tabela 4 – Resultados Aos Geradores.
Após uma análise aos resultados aos dois geradores
observou-se que ambos apresentam algumas falhas
relativamente à uniformidade da distribuição dos Pvalues, como se verifica na tabela 6. Para o gerador
MLS observa-se que não existe uniformidade no
teste 5 embora não apresente qualquer P-value
inferior ao nível de significância. O mesmo acontece
para o gerador Rand do Mathscript nos testes 5 e 6.
Estas falhas levam a que o Histograma Final, que
reúne o conjunto dos P-values também não tenha
distribuição uniforme. Embora isso aconteça num
balanço final podemos concluir que os dois
geradores apresentam boas características de
aleatoriedade.
REFERENCES
[1] Singh, S., The Code Book: The Science of Secrecy
from Ancient Egypt to Quantum Cryptography, ed. Fourth
Estate London (1999).
[2] Vernam, G., Cipher printing telegraph systems for
secret wire and radio telegraphic communications, J. Am.
Inst. Electr. Eng. 45, 109–115. (1926) ; Shannon, C. E.,
Communication theory of secrecy systems, Bell Syst.
Tech. J. 28, p. 656–715 (1949).
[3]. Gisin, N., et. al ., Quantum Cryptography, Rev.
Mod. Phys. 74, p. 145-193, (2002).
[4] B. Schneier, in the Guardian, 5th of 9, 2013,
www.theguardian.com/commentisfree/2013/sep/05/govern
ment-betrayed-internet-nsa-spying
[5] Rukhin, A. et. al. ; A Statistical Test Suite for
Random and Pseudorandom Number Generators for
Cryptographic Applications, NIST Special Publication
800-22 Revision 1a; 2011
[6] Branning, D. , Bermudez, M., Testing Quantum
Randomness in Single-photon Polarization Measurements
with NIST Test Suite, J. Opt. Soc. Am. B Vol. 27, (2010).
[7] J. Dionísio e T. Mota, Testes estatisticos em tempo
real, Final year project, ISEL (2013)