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 MATHEMATICSCENTRAL 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 = 8conjuntos 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.

Ao fazer isso, existem 28 possibilidades, portanto 256 possíveis Regras.

Nomes das regras: É dado pela configuração de saída dos conjuntos das 3 células em binário para decimal.

2

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 – professorda University of Southern Califórnia.Dr. Colomb propõe 3 três postulados para aleatoriedade: (o qual eleclassificou como passos preliminares)

Se uma string binária passar pelos três postulados, essa string pode serconsiderada como um pseudo-noise (pseudo-ruído) e qualificada para umafutura 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çõesbásicas, onde N é o tamanho da janela. O diagrama é um grafo (digraph) no qual suaconfiguração possui vértices e arestas dirigidas (flechas) exibindo sua progressão referente a

regra.

Célula vizinha do lado direitoCélula vizinha do lado esquerdo

Tamanho da janela (31 células nessa figura)

Semente

Tira de Teste

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).

Diagrama de Estado

Ciclo

Cauda

Ponto de Fim

Ponto de Ramificação

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 verificaraleatoriedade na tiras de teste para diferentes tamanhos de janela.

Abordagem Global:

Estudo completo do diagrama de estado de um CA – autômato celularcom diferentes tamanhos de janelas, observando característicasdiferentes 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 2𝑁

𝑁

(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.

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, mesmopara 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: Wiley-

Interscience 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.