View
216
Download
0
Category
Preview:
Citation preview
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.
Recommended