Introducao a Criptologia

Luis Henrique Assumpcao Lolis

8 de marco de 2013

Luis Henrique Assumpcao Lolis Introducao a Criptologia 1

Conteudo

1 Criptografia e criptanalise

2 Esquematico geral de sistemas cifrados

3 Sistemas cifrados

4 Quantidade de informacao e seguranca

5 A distancia de unicidade

Luis Henrique Assumpcao Lolis Introducao a Criptologia 2

Sumario

1 Criptografia e criptanalise

2 Esquematico geral de sistemas cifrados

3 Sistemas cifrados

4 Quantidade de informacao e seguranca

5 A distancia de unicidade

Luis Henrique Assumpcao Lolis Introducao a Criptologia 3

Militar

Transacoes bancaria

TV a cabo

Sistemas celulares

Criptografia

Desenvolvimentos de sistemas seguros

Criptoanalise

Estudo de maneiras de quebrar a seguranca

Luis Henrique Assumpcao Lolis Introducao a Criptologia 4

Sumario

1 Criptografia e criptanalise

2 Esquematico geral de sistemas cifrados

3 Sistemas cifrados

4 Quantidade de informacao e seguranca

5 A distancia de unicidade

Luis Henrique Assumpcao Lolis Introducao a Criptologia 5

C = Tk(M)

Luis Henrique Assumpcao Lolis Introducao a Criptologia 6

Tipos de ataqueConhecendo somente a mensagem criptada:

Estatıstica do sinalProcura da chava

Conhecendo parte da mensagem plana

Tentando encontrar logica de interacao entre trechos damensagem criptada e a mensagem plana

Podendo escolher a mensagem plana

Escolhe a mensagem plana e testa interacoes com amensagem criptada.

Taxa de atualizacao da chave e disponibilidade detempo/dados

Sistema de armazenamento de dadosSistema de transmissao de dados

Luis Henrique Assumpcao Lolis Introducao a Criptologia 7

Sumario

1 Criptografia e criptanalise

2 Esquematico geral de sistemas cifrados

3 Sistemas cifrados

4 Quantidade de informacao e seguranca

5 A distancia de unicidade

Luis Henrique Assumpcao Lolis Introducao a Criptologia 8

Tipos de encriptagem

De fluxo: ConvolucaoDe bloco

Transposicao

Mensagem: the invasion will beginSeparacao em blocos: thein vasio nwill beginTexto criptado: ehnti saovi iwlnl genbiA ordem no bloco e a chave : 32514

Decifrando a transposicao:

Aprender o perıodo (tamanho dos blocos)

Testar as chafes (nao todas pois o numero de combinacoes deum bloco n e n!)

Usar caracterısticas estatısticas da informacao tratada. Lınguapor exemplo.

Luis Henrique Assumpcao Lolis Introducao a Criptologia 9

Substituicao

Dois alfabetos A = [a1, . . . , a26] B = [b1, . . . , b26]Deslocamento do alfabeto: Somente 26 chaves (SubstituicaoCaesar).Embaralhamento do alfabeto: 26! chaves.Ainda facil de decifrar visto a repetitividade das letras

Substituicao polifabetica

O deslocamento do alfabeto e feito letra por letra.O deslocamento depende da palavra chave.Tableau de Vigenere:

Luis Henrique Assumpcao Lolis Introducao a Criptologia 10

Tabela de Vigenere

Luis Henrique Assumpcao Lolis Introducao a Criptologia 11

Exemplo usando tabela de Vigenere

Mensagem plana : the invasion will beginChave (radio) : rad ioradior adio radioMensagem encriptada : khh qbmavqce wltz sejqb

Um bom codigo de fonte faz que os sımbolos tenham umadistribuicao uniforme

Usando o metodo de Huffman para representar a fonte antesda encriptagem desempenha esse papel.

Luis Henrique Assumpcao Lolis Introducao a Criptologia 12

Exercıcio

Codificar a frase ”Teoria da Informacao”usando a tabela deVigenere e a chave ”Erble”

xvpcmeubtrjfsxegrp

Luis Henrique Assumpcao Lolis Introducao a Criptologia 13

Exercıcio

Codificar a frase ”Teoria da Informacao”usando a tabela deVigenere e a chave ”Erble”

xvpcmeubtrjfsxegrp

Luis Henrique Assumpcao Lolis Introducao a Criptologia 13

Sumario

1 Criptografia e criptanalise

2 Esquematico geral de sistemas cifrados

3 Sistemas cifrados

4 Quantidade de informacao e seguranca

5 A distancia de unicidade

Luis Henrique Assumpcao Lolis Introducao a Criptologia 14

Quantidade de informacao da fonte

H(M) = −n∑

i=1

p(Mi) log p(Mi)

Quantidade de informacao da chave H(K) e da mensagemencriptada H(C)

Equivoco ou incerteza sobre a chave conhecendo a mensagemencriptada:

H(K|C) = −l∑

h=1

m∑j=1

p(Kh, Cj) log p(Kh|Cj)

Para ser decifravel:

H(H|C,K) = 0

Equıvoco do aparencia da chave:

H(M |C,K = 0)

Luis Henrique Assumpcao Lolis Introducao a Criptologia 15

H(K|M,C) = H(K|C)−H(M |C)

Dilema: Um largo valor da incerteza de K em funcao de M eC, pode ser obtido diminuindo a incerteza de M em funcao deC.

No entanto nao se pode ter baixa incerteza de C em relacao aM.

Informacao mutua entre M e C.

Sistema de encriptagem absolutamente seguro: I(M ;C) = 0

Sendo I(M ;C) ≥ H(M)−H(K), entao para I(M ;C) = 0:H(K) ≥ H(M)

A chave deve entao ser ao menos tao grande quanto amensagem plana.

Luis Henrique Assumpcao Lolis Introducao a Criptologia 16

Sumario

1 Criptografia e criptanalise

2 Esquematico geral de sistemas cifrados

3 Sistemas cifrados

4 Quantidade de informacao e seguranca

5 A distancia de unicidade

Luis Henrique Assumpcao Lolis Introducao a Criptologia 17

Quanto maior o texto criptografado em maos do criptanalista,maior a chance de decifrar o texto.

A incerteza sobre a chave diminui a medida que o tamanho dotexto criptografado aumenta.

A distancia de unicidade e o menor tamanho N da mensagemcriptografada cuja a incerteza sobre a chave tende a zero.

N0 'H(K)

r log(Ly)

Ly e o tamanho do alfabeto do texto criptografado, r e aredundancia percentual da informacao dada por:

r = 1− H(M)

log(Ly)

Luis Henrique Assumpcao Lolis Introducao a Criptologia 18