Apresentação do artigo que avalia o quão aleatórios são os dados

CELLULAR AUTOMATA: IS
RULE 30 RANDOM?
APRESENTAÇÃO GRUPO DCA DE SEGURANÇA
21 de Agosto de 2015 – Campinas - SP
Sílvia Regina Leite Magossi
Prof. Dr. Marco Aurélio Amaral Henriques
Autores:
AUTORES:
DUSTIN GAGE - UNIVERSITY OF MAINE – FARMINGTON
ELIZABETH LAUB - SUSQUEHANNA UNIVERSITY
BRIANA MCGARRY - CENTRAL MICHIGAN UNIVERSITY
DR. KEN SMITH - FACULTY ADVISER
DEPARTMENT OF MATHEMATICS
CENTRAL MICHIGAN UNIVERSITY
Propósito da pesquisa :
Investigar a afirmação feita pelo Dr. Stephen Wolfram:
“Que a regra30 pode ser usada em esquemas de criptografia de forma eficaz
devido às suas qualidades aleatórias.”
Ele acredita que o uso de um particular algoritmo, que se refere a regra 30, produz
uma sequência binária que é suficientemente randômica e pode ser usada como
PRGN (gerador de números pseudo-aleatórios)em sistemas de criptografia.
Estudo:
O artigo investiga a afirmação de Wolfran usando uma bateria de testes estatísticos, bem
como identifica propriedades que ajudam a caracterizar a sua segurança, se usada para
criptografia.
Resultados:
Os resultados fornecem evidências de que a regra 30 mostra aleatoriedade adequada
para um alto nível de segurança com deficiências isoladas , mesmo para tamanhos de
sementes diferentes .
Revisão:
Um CA – (Automato Celular) unidimensional é formado através da definição de 23 = 8
conjuntos de 3 células (a célula, a célula vizinha à esquerda, e a célula vizinha do lado
direito).
Cada um desses oito conjuntos dá uma saída, produzindo uma nova célula das três
anteriores e criando um mapeamento dessa configuração.
Nomes das regras: É dado pela configuração de saída dos conjuntos das 3 células em
binário para decimal.
2
Ao fazer isso, existem 28 possibilidades, portanto 256 possíveis Regras.
A regra local para um autômato celular dever ser considerada uma função Booleana de
uma célula com suas vizinhas. A possível função equivalente módulo dois é apresentada
a seguir :
Esta expressão genérica pode ser escrita para a regra 30 de um autômato celular
binário unidimensional de raio unitário, como apresentado abaixo.
𝑡
𝑡
𝑎𝑖𝑡+1 = 𝑎𝑖−1
⊕ 𝑎𝑖𝑡 ∨ 𝑎𝑖+1
Uma outra evolução da regra 30 pode ser observada abaixo com um número maior de
iterações. A regra30 evolui alterando o valor de 0s e 1s de cada célula, e produzindo uma
nova linha. Comportamento randômico é observado e digno de investigação.
Aleatoriedade:
Considerar a definição de aleatoriedade ao Dr. Solomon Golomb – professor
da University of Southern Califórnia.
Dr. Colomb propõe 3 três postulados para aleatoriedade: (o qual ele
classificou como passos preliminares)
Se uma string binária passar pelos três postulados, essa string pode ser
considerada como um pseudo-noise (pseudo-ruído) e qualificada para uma
futura investigação.
Postulado é uma sentença que não é provada ou demonstrada, e por
isso se torna óbvia ou se torna um consenso inicial para a aceitação de
uma determinada teoria.
O postulado não é necessariamente uma verdade muito clara, é uma
expressão formal usada para deduzir algo, a fim de obter um resultado
mais facilmente, através de um conjunto de sentenças. O postulado é uma
proposição que, apesar de não ser evidente, é considerada verdadeira
sem discussão.
http://www.significados.com.br/postulado/
Primeiro postulado:
Se p é par então o ciclo de comprimento p deve conter um número igual de zeros e uns. (0s e 1s).
Se p é impar então o número de zeros deve ser mais ou menos o números de uns.
Segundo postulado:
Em um ciclo de comprimento p para cada i para o qual existem pelo menos
tem comprimento i.
Todavia, para cada desses comprimentos, existem igualmente muitos gaps e blocos.
Terceiro postulado:
Para passar neste postulado, deve ser impossível prever o próximo valor da faixa a partir de valores
anteriores.
Definições
Definição 1. Célula vizinha do lado direito  é a célula imediadamente da direita com
relação a célula avaliada.
Célula vizinha do lado esquerdo  é a célula imediatamente da esquerda
Definição 2. Tamanho da janela  é o número de bits para uma dado autômato.
Observação: Para janelas de tamanho finito, a condição limite para o primeiro e último bit da
configuração, é torná-los adjacente ou efetivamente a janela é “wrap” embrulhada.
Definição 3. Semente  é a combinação de 0s e 1s onde o autômato inicia sua iteração.
Definição 4. Diagrama de Estado  é a estrutura que contem todo os 2𝑁 configurações
básicas, onde N é o tamanho da janela. O diagrama é um grafo (digraph) no qual sua
configuração possui vértices e arestas dirigidas (flechas) exibindo sua progressão referente a
regra.
Tamanho da janela (31 células nessa figura)
Semente
Célula vizinha do lado esquerdo
Tira de Teste
Célula vizinha do lado direito
Diagrama de Estado
Ponto de Ramificação
Ciclo
Cauda
Ponto de Fim
A figura acima mostra um diagrama de estado para uma CA tamanho 4 (janela = 4) em cima da Regra30. As flechas
denotam a direção da progressão, e o maior ciclo está na área circulada. Nos pontos de ramificações observamos
duas ou mais flechas (exemplo 1110), e nos pontos periféricos (pontos de fim) não tem (exemplo 0011).
Definição 5. Ciclo  é um laço no diagrama de estado.
Definição 6. Cauda  é a sequência de configuração no diagrama de estado na qual a
progressão não retorna. Sequências de bits que fazem parte da cauda e não do ciclo.
Definição 7. Ponto de Fim  é a configuração na cauda que não tem predecessor em
sua progressão.
Definição 8. Ponto de Ramificação  é a configuração na qual tem dois ou mais
predecessores em sua progressão.
Definição 9. Tira de Teste  é uma tira binária, selecionando uma célula na
semente e seguindo em linha reta para baixo passando por um número de
iterações.
Observações: Tiras de teste são usadas para testes estatísticos. A semente
tipicamente usada nesta pesquisa para produzir tiras de testes foi uma simples
célula 1 e as outras células 0s.
Definição 10. Seja G ser um grupo de permutações agindo no conjunto X. Seja
C uma coleção de cores de X. Então 𝑐1 , 𝑐2 Є C são equivalentes fornecendo
que há uma permutação f Є G tal que f * 𝑐1 = 𝑐2 .
Desenvolvimento da Pesquisa
A pesquisa foi dividida em dois aspectos – utilizando a Regra30
• Local – Consiste de uma fita simples de dados binários
• Global – toda a estrutura do autômato
Abordagem local:
Compreendeu de testes estatísticos de desempenho para verificar
aleatoriedade na tiras de teste para diferentes tamanhos de janela.
Abordagem Global:
Estudo completo do diagrama de estado de um CA – autômato celular
com diferentes tamanhos de janelas, observando características
diferentes e que foram examinadas, tais como:
• Tamanho do ciclos
• Quantidade de ciclos
• Quantidade de caudas
Local
Estrutura Local
Utilizados dois computadores para investigar e quantificar propriedades das
regras, inclusive Regra30, com diferentes tamanhos de janelas.
1º Computador Output: bits da tira de testes separados por vírgula (,);
Tamanho do ciclo;
Tamanho da cauda que precede o ciclo.
2º Computador Output: Um bit por linha;
Tamanho da Janela.
Programas Utilizados
• NIST – National Institute of Standards and Technology - Pacote
distribuído pelo NIST para a principal bateria de testes.
• Programa MiniTab .
• Programa Maurer’s Universal Test do NIST.
• Programa Escrito pelo Dr.John Daniels (Prof. de Estatítica da Central
Michigan University ), linguagem SAS
Global
Estrutura Global
1º Identificado Nível de Aleatoriedade Local a um nível aceitável.
2º Observar Perspectiva Global da Regra30 , identificando
propriedades que ajudam ou identificam a utilização em criptografia.
Observações a partir da utilização de computadores confiáveis em evidência
empírica, devido a natureza exponencial e intratabilidade computacional da
Regra30.
Trabalhos publicados sobre caudas desses ciclos são poucos.
Dificuldades em manter computacionalmente o controle sobre cauda e ciclo,
por isso uma abordagem algorítmica foi necessária para recolher dados.
• Utilização da propriedade shift invariance;
• Número de computações necessárias cai aproximadamente para
(se N = 8 então
28
8
=
256
8
= 32 )
• Utilização do Código Gray para aumentar a eficiência.
• Polya’s Couting Theorema.
2𝑁
𝑁
Resultados
Resultados locais.
Utilizando a variedade de programas apresentados , foram capazes de criar
uma grande bateria de testes estatísticos e uma grande quantidade de
valores (p-value).
Resultados globais.
A Tabela 1 mostra:
• Número de cada comprimento de ciclo;
• Tamanho das janelas de 5-24;
• Ciclo máximo separado dos outros ciclos;
• Porcentagem de todas as configurações que aparecem nas
caudas e o ciclo de maior quantidade de valores.
Observa-se que ocorre uma domínio dos valores nas caudas, mesmo
para janelas pequenas.
Resultados Global
A Tabela 2 mostra:
O ciclo de comprimento máximo ∏𝑁 para o tamanho da janela N 4-36.
Um quadro semelhante foi publicado em Wolfram, Stephen. “Random
Sequence Generation by Cellular Automata.” Advances in Applied
Mathematics 7, 1986, pp. 123-126, de modo que o trabalho fornecido
para produzir estes resultados foi para confirmar os dados publicados
anteriormente.
Obrigada
References
[1] Beker, Henry and Fred Piper. Cipher Systems, The Protection of Communications. New York: WileyInterscience Publication (1982)
[2] Maurer, Ueli. “A Universal Statistical Test for Random Bit Generators.” Journal of Cryptology 5, no. 2, 1992,
pp. 89-105.
[3] Rukhin, Andrew, et al. A Statistical Test Suite for Random and Pseudorandom Number Generators for
Cryptologic Applications. NIST special publication 800-822; Revised 15 May 2001. http://nist.gov.
[4] Wolfram, Stephen. A New Kind of Science. Illinois: Stephen Wolfram LLC, 2002.
[5] Wolfram, Stephen. “Random Sequence Generation by Cellular Automata.” Advances in Applied Mathematics
7, 1986, pp. 123-126.
[6] Brualdi, Richard. Introductory Combinatorics Third ed.. New Jersey: Prentice Hall Inc, 1999.