Criptografia com bloco de correção de erros aplicados à evolução autômatos

Criptografia com bloco de correção de erros aplicados à evolução de autômatos

Laboratório de Processamento Digital de Sinais – LPDS/IFCEAutores:

Anderson Chaves, Bruno Sokal, Allex Albuquerque, Francisco AquinoApresentador:

Anderson Chaves

2

Criptologia

3

RAMOS DA CRIPTOLOGIA• Criptografia

É o estudo dos princípios e técnicas pelas quais a informação pode ser transformada da sua forma original para outra ilegível, de forma que possa ser conhecida apenas por seu destinatário.

• CriptoanáliseA criptoanálise é a arte de tentar descobrir o texto cifrado e/ou a lógica utilizada em sua encriptação. Representa o esforço de descodificar ou decifrar mensagens sem que se tenha o conhecimento prévio da chave secreta que as gerou.

Criptologia

4

RAMOS DA CRIPTOLOGIA• Esteganografia

É o estudo e uso das técnicas para ocultar a existência de uma mensagem dentro de outra, uma forma de segurança por obscurantismo.

OBS: É importante frisar a diferença entre criptografia e esteganografia. Enquanto a primeira oculta o significado da mensagem, a segunda oculta a existência da mensagem.

Criptologia

5

• Dentro da criptologia, a informação tratada é conhecida como texto simples, texto limpo, texto em claro, ou simplesmente mensagem.

• O processo de tornar uma mensagem irreconhecível ou segura é chamado de encriptação (codificação ou cifragem), e o resultante desse processo é o criptograma. O processo de reversão de um criptograma para uma mensagem legível é chamado de decriptação.

• Código: um código manipula o significado da mensagem.• Exemplo: No Dia-D da Segunda Guerra Mundial, as praias de

desembarque das tropas eram conhecidas pelos códigos Omaha, Juno, etc.

• Cifra: funciona como uma alteração da representação da mensagem.• Exemplo: Um exemplo clássico, é o cifrar da palavra “cubo” para “dvcp”,

em que apenas se substituiu cada letra pela seguinte do alfabeto (cifra de César). Podem ser de transposição ou de substituição.

TERMINOLOGIACriptologia

6

Exemplo de funcionamento da Cifra de César (uma cifra de substituição).

Anel decodificador da Cifra de César.

Criptologia

7

CriptologiaRAMOS DA CRIPTOLOGIA

8

CriptologiaRAMOS DA CRIPTOLOGIA

9

Por que criptografia com autômatos celulares?

10

Por que criptografia com autômatos celulares?

• RSA e Diffie-Hellman podem ser quebradas?

11

Por que criptografia com autômatos celulares?

• RSA e Diffie-Hellman podem ser quebradas?

12

Por que criptografia com autômatos celulares?

• RSA e Diffie-Hellman podem ser quebradas?

Alex Stamos

13

Por que criptografia com autômatos celulares?

• RSA e Diffie-Hellman podem ser quebradas?

Alex Stamos

14

Por que criptografia com autômatos celulares?

• RSA e Diffie-Hellman podem ser quebradas?

Alex Stamos

“Our conclusion is there is a small but definite chance

that RSA and classic Diffie-Hellman will not be usable for

encryption purposes in four to five years”

15

Por que criptografia com autômatos celulares?

• RSA e Diffie-Hellman podem ser quebradas?

Alex Stamos

“Our conclusion is there is a small but definite chance

that RSA and classic Diffie-Hellman will not be usable for

encryption purposes in four to five years”

16

Por que criptografia com autômatos celulares?

• RSA e Diffie-Hellman podem ser quebradas?

Problema da Fatoração de Primos

Alex Stamos

“Our conclusion is there is a small but definite chance

that RSA and classic Diffie-Hellman will not be usable for

encryption purposes in four to five years”

17

Por que criptografia com autômatos celulares?

• RSA e Diffie-Hellman podem ser quebradas?

Problema da Fatoração de Primos

Alex Stamos

“Our conclusion is there is a small but definite chance

that RSA and classic Diffie-Hellman will not be usable for

encryption purposes in four to five years”

18

Por que criptografia com autômatos celulares?

• RSA e Diffie-Hellman podem ser quebradas?

Problema da Fatoração de Primos

Problema do Logaritmo Discreto

Alex Stamos

“Our conclusion is there is a small but definite chance

that RSA and classic Diffie-Hellman will not be usable for

encryption purposes in four to five years”

19

Por que criptografia com autômatos celulares?

• RSA e Diffie-Hellman podem ser quebradas?

Problema da Fatoração de Primos

Problema do Logaritmo Discreto

Alex StamosAlex Stamos

“Our conclusion is there is a small but definite chance

that RSA and classic Diffie-Hellman will not be usable for

encryption purposes in four to five years”

20

Por que criptografia com autômatos celulares?

• RSA e Diffie-Hellman podem ser quebradas?

Problema da Fatoração de Primos

Problema do Logaritmo Discreto

Alex StamosAlex Stamos

“Our conclusion is there is a small but definite chance

that RSA and classic Diffie-Hellman will not be usable for

encryption purposes in four to five years”

21

Por que criptografia com autômatos celulares?

Estudos com técnicas alternativas de criptografia alternativas mostram-se necessários em momentos como os atuais, de risco de uma crise na segurança digital.

22

O que são autômatos celulares?

23

O que são autômatos celulares?DEFINIÇÃO

São ferramentas simples e poderosas para a representação de sistemas evolutivos que a partir de uma configuração inicial aleatória, cada componente do sistema tem sua evolução baseada na situação atual de seus vizinhos e num conjunto de regras que são iguais para todos os componentes.

24

O que são autômatos celulares?DEFINIÇÃO

São ferramentas simples e poderosas para a representação de sistemas evolutivos que a partir de uma configuração inicial aleatória, cada componente do sistema tem sua evolução baseada na situação atual de seus vizinhos e num conjunto de regras que são iguais para todos os componentes.

Stephen Wolfram

25

O que são autômatos celulares?DIMENSÃO

26

O que são autômatos celulares?LATTICE OU FORMA GEOMÉTRICA

27

O que são autômatos celulares?CORES OU ESTADOS

As cores ou estados (p) são o conjunto de valores que cada célula do autômato celular pode assumir.

p = 7

p = 2

28

O que são autômatos celulares?RAIO E VIZINHANÇA

Raio (r) é a distância na qual a vizinhança deve ser considerada, a partir da célula em questão.

Vizinhança (k) é o conjunto de células que influenciaram no próximo estado da célula em questão.

29

O que são autômatos celulares?REGRA DE EVOLUÇÃO OU FUNÇÃO DE TRANSIÇÃO

Regra 90 de evolução para um autômato celular linear unidimensional com raio r = 1, vizinhança k = 2r+1 = 3, e dois estados (p = 2).

30

O que são autômatos celulares?Autômatos celulares elementares são a classe mais simples de autômatos celulares unidimensionais. Autômatos celulares elementares possuem dois valores possíveis para cada célula (0 ou 1), e regras que dependem somente dos vizinhos mais próximos.

• Unidimensionais• p = 2• r = 1• k = 2r + 1 = 3

AUTÔMATOS CELULARES ELEMENTARES

31

O que são autômatos celulares?

Neste trabalho foram utilizados autômatos celulares elementares e suas respectivas regras de evolução para a cifragem e decifragem da mensagem desejada.

32

Modelando a técnicaSendo o par de regras complementares (R,R’) tal que o resultado da evolução de uma pode ser revertido com a outra, temos que:

Que seria o modelo intuitivo mais simples para uma técnica criptográfica.

33

Melhorando o modeloMelhorando nosso algoritmo para permitir usos simultâneos de várias regras nos processos, cada uma podendo ser usada por n ciclos (ou n vezes).

34

Evolução do autômatoA cifragem da mensagem é realizada pela evolução de um autômato celular elementar com uma ou mais regras de evolução determinadas, e por um número n de ciclos de repetição cada uma.

A evolução da primeira e da última célula do autômato celular são evoluções especiais, pois dependem dos estados atuais uma da outra para determinar seu próximo estado, causando uma circularidade do autômato.

35

Resultados IniciaisTestando a combinação (R,R’) com todos os pares de regras para autômatos celulares elementares possíveis, da regra 0 à 255, encontramos que:

Portanto, a técnica modelada funcionaria para estes pares de regras.

36

Resultados Iniciais

• Todos os outros pares de combinações de regras não conseguiram uma reversão completa do criptograma para a mensagem original.

• Notou-se durante o trabalho que determinadas combinações de caracteres na mensagem aumentavam muito a quantidade de erros gerados depois das evoluções com o autômato celular. Para resolver este problema, foram idealizadas as etapas de pré-processamento e pós-processamento.

37

Pré-processamentoNa etapa de pré-processamento da mensagem são adicionados caracteres especiais auxiliares na mensagem de modo intercalado e seguindo condições específicas com o intuito de diminuir o erro gerado pela combinação de caracteres geradores de erros na mensagem.

Caracteres Auxiliares Mensagem

Mensagem Pré-

processada

38

Pós-processamentoNa etapa de pós-processamento da mensagem são retirados todos os caracteres especiais auxiliares adicionados no pré-processamento na mensagem.

Mensagem Pré-

processada

Caracteres Auxiliares Mensagem

39

Bloco de Correção de Erros

O bloco de correção de erros utilizado foi um sistema FEC de bloco linear (8,4) como descrito abaixo:

40

Encriptação

• Adição de caracteres especiais.

Pré-processamento

• Adição de bits de correção de erros intercalados.

Adição de bits de correção de erros • Evoluir o bloco

segundo a regra de evolução definida R.

Evolução do autômato celular

41

Decriptação

• Evoluir o bloco segundo a regra R’ complementar do par escolhido.

Evolução do autômato celular

• Verificação e correção dos erros bem como a remoção de bits de correção de erros intercalados.

Verificação e remoção correção de erros • Remoção dos

caracteres especiais auxiliares.

Pós-processamento

42

Resultados Finais

Com o código corretor de erros implementado foi possível expandir o uso do sistema criptográfico para mais dois pares de regras antes não perfeitamente invertíveis.

43

Resultados Finais

Interface do software produzido para realizar encriptação pela técnica desenvolvida.

44

Resultados Finais

Interface do software produzido para realizar decriptação pela técnica desenvolvida.

45

Resultados Finais

Histograma da frequência de caracteres da mensagem e do criptograma gerado.

46

Referências[1] OECD. Machine-to-Machine Communications: Connecting Billions of Devices. OECD Digital Economy Papers, No. 192, OECD Publishing. Disponível em: <http://dx.doi.org/10.1787/5k9gsh2gp043-en>. Acesso em 16 de agosto de 2013.[2] SIMONITE, T. Math Advances Raise the Prospect of an Internet Security Crisis. MIT Technology Review, Cambridge, Massachusetts, Aug. 2013. Disponível em: <http://www.technologyreview.com/news/517781/math-advances-raise-the-prospect-of-an-internet-security-crisis/>. Acesso em 16 de agosto de 2013.[3] UNO, D. N.; FALEIROS, A. C. Princípios de Criptografia Quântica. São José dos Campos, São Paulo, 2003.[4] ALT, L. S.; FERREIRA, G. B.; MARTINS, M. V.; MARTINS, L. G. A.; OLIVEIRA, G. M. B. Um modelo criptográfico baseado em autômatos celulares com texto cifrado de tamanho variável. IX Encontro Interno & XIII Seminário de Iniciação Científica – PIBIC, 2009.[5] TARDIVO FILHO, M.; HENRIQUES, M. A. A. Estudo sobre a Aplicação de Autômatos Celulares Caóticos em Criptografia. IV Encontro dos Alunos e Docentes do Departamento de Engenharia de Computação e Automação Industrial - EADCA, v. CD-ROM, pp. 1–4, Abr. 2011.[6] BOJINOV, H. Neuroscience Meets Cryptography. 21st USENIX Security Symposium, Bellevue, Whashington, Aug. 2012.[7] MACHICAO, J. M.; MARCO, A. G.; BRUNO, O. M. Chaotic Encryption Method Based on Life-Like Cellular Automata. arXiv [math.DS], Cornell University Library, Ithaca, New York, Dec. 2011.[8] WOLFRAM, S. Cryptograpy with cellular automata. Advances in Cryptology - CRYPTO ’85 Proceedings. Lecture Notes in Computer Science 218, Springer-Verlag. p. 429-432, Santa Barbara, California, 1985.[9] USP. Para pesquisadores do IFSC, criptografia baseada no caos é promessa de segurança online. Redação USP, Tecnologia, São Paulo, São Paulo, 7 Feb. 2012. Disponível em: <http://www5.usp.br/6242/para-pesquisadores-do-ifsc-criptografia-baseada-no-caos-e-promessa-de-seguranca-online/>. Acesso em 16 de agosto de 2013.[10] CASTRO, M. L. A.; CASTRO, R. O. Autômatos Celulares: Implementações de Von Neumann, Conway e Wolfram. Revista de Ciência e Tecnologia, Vol. lll, Nº 3, 2008.[11] FENWICK, J. W.; DOWELL, L. J. Electrical substation service-area estimation using cellular automata: an initial report. InSAC ’99: Proceedings of the 1999 ACM symposiumon Applied computing, p. 560–565, 1999.[12] REITE, C. A. A Local Cellular Model for Snow Crystal Growth. Chaos, Solitons & Fractals, Easton – PA, v.23, n. 4, p. 1111-1119, Feb. 2005.[13] MELOTTI, G. Aplicação de Autômatos Celulares em Sistemas Complexos: Um estudo de Caso em Espalhamento de Epidemias. MACSIN-UFMG, Belo Horizonte,Fev.2009.[14] MICHEL, G. V. Estudo de Mecanismo FEC para Transmissão Confiável em UDP. Porto Alegre, Jun. 2010.

Fim da Apresentação

Obrigado!