GBC083 – Seguranca da InformacaoAula 1 - Introducao a Criptografia
Prof. Marcelo Keese Albertini
9 de Marco de 2016
Seguranca da Informacao - Metas
I ConfidencialidadeI Criptografia classica (ate 1970)
I IntegridadeI Criptografia moderna = Confidencialidade + Integridade
I DisponibilidadeI Prevencao contra ataques de negacao de servicosI Prevencao contra perda de dados
Criptografia moderna
I Comunicacao segura (SSH, HTTPS)
I Armazenamento seguro (TrueCrypt)
I Assinatura digital (RSA)
I Comunicacao anonima (mix net, tor)
I Dinheiro digital anonimo (bitcoin)
I Contratos inteligentes (ethereum)
I Protocolos de eleicao (Neff e Chaum) e leiloes privados
I Computacao segura entre multiplos atores (homomorfismos)
Criptografia classica
I Ate os anos 1970I usa informacao secreta (uma chave) compartilhada entre
somente as partes comunicantes
I Criptografia de chave privadaI tambem chamada de chave secreta, chave compartilhada ou
chave simetrica
Criptografia de chave privada
chave k chave k
Texto cifrado:c = “alkshdaioshfahr”
Textolimpom =
“oi bobcomovai”
Encriptacao:c ← Enck(m)
Decriptacao:m← Deck(c)
Criptografia de chave privada
k
mc ← Enck(m)
k
m ← Deck(c)
c
c
Criptografia de chave privada
I Um esquema de criptografia de chave-privada e definido poruma espaco de mensagens M e algoritmos (Gen,Enc ,Dec):
I Gen (algoritmo de geracao de chave): cria kI Enc (algoritmo de encriptacao): recebe chave k e mensagem
m ∈M como entrada; produz texto cifrado c
c ← Enck(m)
I Dec (algoritmo de decriptacao): recebe chave k e texto cifradoc como entrada e produz m ou “erro”
I Para todo m ∈M e k produzido por Gen,Deck(Enck(m)) = m
A cifra de deslocamento
I Considere encriptar texto em ingles
I Associar ‘a’ com 0. ‘b’ com 1; . . .; ‘z’ com 25
I k ∈ {0, . . . , 25}I Para encriptar usando chave k , deslocar toda letra do texto
limpo em k posicoes “dando a volta” ao chegar em ‘z’I Para decriptar e so fazer o reverso
I helloworld ⊗ cccccccccc = jgnnqyqtnfb
Aritmetica modular
I x = x ′ mod N se e so se N divide x − x ′
I [x mod N] = o resto quando x e dividido por NI Isto e, o unico valor x ′ ∈ {0, . . . ,N − 1} tal que x = x ′
mod N
I 25 = 35 mod 10
I 25 6= [35 mod 10]
I 5 = [35 mod 10]
I Cuidado! No C e no Java, o operador de resto % retornanumeros negativos!
A cifra de deslocamento, formalmente
I M = { string sobre o alfabeto minusculo ingles }I Gen: escolher k ∈ {0, . . . , 25}I Enck(m1 . . .mt): obter c1 . . . ct onde ci ← [mi + k mod 26]
I Deck(c1 . . . ct): obter m1 . . .mt onde mi ← [ci − k mod 26]
A cifra de deslocamento e segura?
I Nao – existem apenas 26 chaves possıveisI Dado um texto cifrado, tente decriptar com todo chave
possıvelI Se texto cifrado e longo (e texto original e em ingles comum),
somente um texto decriptado fara sentido
Exemplo
I Texto cifrado: uryybjbeyqI Tentar cada chave:
I tqxxauadxpI spwwzhzcwoI . . .I helloworld
Princıpio de Kerckhoffs
I O esquema de encriptacao nao deve ser secretoI O unico segredo e a chaveI A chave deve ser escolhida aleatoriamente e mantida em sigilo
I Alguns argumentos em favor desse princıpioI Mais facil manter chave secreta que algoritmo secreto
I Algoritmo quebrado leva a todos os segredos serem expostos
I Mais facil mudar chave que mudar algoritmoI Chave descuberta leva a alguns segredos expostos
I PadronizacaoI Facilita instalacao do esquemaI Validacao publica
Princıpio do espaco suficiente de chaves
I Princıpio de seguranca informal
I Espaco de chave deve ser grande o suficiente para prevenir“forca-bruta” em ataques de busca exaustiva
Cifra de Vigenere
I A chave da Cifra de Vigenere e uma string e nao um caracterecomo antes
I Para encriptar, Enc , deslocar cada caractere no texto limpopela quantidade indicada pelo proximo caractere da chave
I Voltar ao inıcio da chave se necessario
I Para desencriptar, Dec , reverter processo
I tellhimaboutme ⊕ cafecafecafeca = veqpjiredozxoe
A cifra de Vigenere
I Tamanho do espaco de chavesI Se chave e de 10 carateres entao tamanho do espaco de chaves
e 2610
I Se chaves e strings de N caracteres entao espaco da chavestem tamanho 26N
I Busca por forca-bruta e cara e por isso impossıvel
I A cifra de Vigenere e segura?
Implementacao - ASCII
Hex nibble Decimal0 0000 01 0001 12 0010 23 0011 34 0100 45 0101 56 0110 67 0111 7
Hex nibble Decimal8 1000 89 1001 9A 1010 10B 1011 11C 1100 12D 1101 13E 1110 14F 1111 15
I nibble = pedaco de 4 bits
I 1 nibble = 1 dıgito hexadecimal
Hexadecimal – base 16
I 0x10I 0x10 = 16× 1 + 0 = 16I 0x10 = 0001 0000
I 0xAFI 0xAF = 16× A + F = 16× 10 + 15 = 175I 0xAF = 1010 1111
ASCII
I Caracteres representados em ACIII 1 byte por caractere = 2 dıgitos hexas por caractere
ASCII
I ‘1’ = 0x31 = 00110001
I ‘F’ = 0x46 = 01000110
Base64
I Base64 e codificacao para representar binario em ASCII.
I Texto: M a n
I ASCII: 77 (0x4d), 97 (0x61), 110 (0x6e)
I Padrao de 8 bits : 01001101 01100001 01101110I Padrao de 6 bits : 010011 010110 000101 101110
I 26 = 64
I Numero de ındice: 19 22 5 46I A=0 . . . Z=25, a=26. . . z=51, 0=52 . . . 9=61, + = 62, / = 63
I Base64: T W F uI Caractere especial ‘=’ indica padding de 1 byte para quando
texto nao tiver numero de bits multiplo de 6I Possıvel usar 1 byte ‘=’ ou 2 ‘==’ de padding
Representacao de dados
I Como armazenar o valor 0x1F em um arquivo?I Uma opcao
I hexadecimal puro: armazenar 00011111mas para visualizar nao e possıvel usar um editor de textos
I Outra opcaoI texto: guardar caracteres ASCII 1F ou em Base64
I Ou seja, em binario: 001100011000110I Se abrimos com editor de texto, veremos 1FI Ao ler de volta para descriptografar, necessario converter de
volta para 0x1F
Exercıcios
I Faca um programa para converter uma string em hexa parabase64.
I Usar somente hexa/base64 para produzir arquivo texto facilde ler
I Em codigos sempre opere em binario (byte em Java, euint8 t em C)
I Implemente a cifra de Vigenere usado a entrada e a saıda detexto cifrado em hexa
I Encriptacao e decriptacao
I Implemente um ataque de forca bruta contra a cifra deVigenere