30
SEG-6 Ivan Sendin Criptografia Cifradores Seguran¸ ca da Informa¸ ao Aula 6 Ivan Sendin FACOM - Universidade Federal de Uberlˆ andia [email protected],[email protected] 12 de setembro de 2017

Segurança da Informação Aula 6 - facom.ufu.brsendin/Cursos/SEG/2S2017/aula6.pdf · SEG-6 Ivan Sendin Criptogra a Cifradores Seguran˘ca da Informa˘c~ao Aula 6 Ivan Sendin FACOM

  • Upload
    vodieu

  • View
    221

  • Download
    0

Embed Size (px)

Citation preview

SEG-6

Ivan Sendin

Criptografia

Cifradores Seguranca da Informacao

Aula 6

Ivan Sendin

FACOM - Universidade Federal de [email protected],[email protected]

12 de setembro de 2017

SEG-6

Ivan Sendin

Criptografia

Cifradores Criptografia

cryptos graphos

Primordialmente confidencialidade

Inumeros dispositivos: tabua com cera,fita/cilindro,...

Inumeros sistemas: Livro codigo, tabela (pad),...

SEG-6

Ivan Sendin

Criptografia

Cifradores

Integridade, disponibilidade, autenticidade e naorepudio

Assinaturas DigitaisTrazem para o mundo digital as propriedadesexistentes no papel

Autenticacaoeu sou eu

Usar Wifi de forma segura!

”Dividir”um segredoCheque com varias assinaturas, cofre com 2fechaduras,...

SEG-6

Ivan Sendin

Criptografia

Cifradores

Provas de conhecimento ZeroSei colorir G com 3 cores....sem mostrar o grafo

Secure multi-party computation

Poker Mental(remoto), cara e coroa por telefone....

TimestampEu produzi alguma coisa primeiro...sem mostrar acoisa

Procuram alguma coisa sem mostrar o que euprocuroBloom Filters

SEG-6

Ivan Sendin

Criptografia

Cifradores

Convencer alguem que eu trabalhei

Assinar de forma anonimaEleicoes Digitais

Dinheiro DigitalB

Computacao remota confiavel“run exactly as programmed without any chance offraud, censorship or third-party interference.”(Ethereum)

SEG-6

Ivan Sendin

Criptografia

Cifradores

Cifradores

Alice e BobCanal inseguro

RadioFio do telegrafoGritandoInternet (3G,WiFi,...)

Eva (Eve - ”eavesdropper”)/OscarEva e poderosa

Constante na criptografia: considerar o adversariopoderoso.Conhece o cifrador (algoritmo)Conhece a linguagem que eles fala, processador detexto,...

Existe uma chave secreta compartilhadaUnica vantagem de Alice/Bob

SEG-6

Ivan Sendin

Criptografia

Cifradores

Criptossistema

Criptossistema: 5-Tupla (P , C,K, E ,D).

P - texto claro

C - texto cifrado

K - espaco de chaves

Para cada k ∈ K existe um regra deciframento/deciframento ek ∈ E , dk ∈ Dcom dk(ek(x)) = x ,∀x ∈ P(Def 1.1 de Stinson)

SEG-6

Ivan Sendin

Criptografia

Cifradores

Cifrador de Deslocamento

Shift Cipher

P == C = K = Z26

ek(x) = (x + k) (mod 26)

dk(x) = (x − k) (mod 26)

“Numero Circular”

Deslocamento em uma “fita”

Para K = 3 Cifrador De Cesar

SEG-6

Ivan Sendin

Criptografia

Cifradores

Cifrador de Deslocamento

Dado c ∈ C podemos fazer forca bruta no espaco dechaves

SEG-6

Ivan Sendin

Criptografia

Cifradores

Para k de 0 a 25:

d[i] = c[i] - k mod 26, para i de 1 a 100

Se d fizer sentido

imprime d,k

Para um texto cifrado de 100 letras

SEG-6

Ivan Sendin

Criptografia

Cifradores

Informacao

“fizer sentido” = casamento com dicionario (porexemplo)

Se c for pequeno: Confidencialidade perfeita

“Vamos fazer o teste da Bomba H amanha?”

c = r

Chave maior : One Time Pad

Claude Shannon - Communication Theory ofSecrecy Systems - 1949

“Comum” com ou-exclusivo

SEG-6

Ivan Sendin

Criptografia

Cifradores

Cifrador de Substituicao

A “Chave” define uma substituicao simples

Por exemplo a→ r , b → d , . . . , j → j , . . .

Para “voltar”, basta inverter a troca...

Espaco de chaves?

Tamanho?

Forca Bruta?

SEG-6

Ivan Sendin

Criptografia

Cifradores

Cifrador de Substituicao

Calcular 26!

Aproximacao de Stirling (1025)

Esta no alem do limite do poder computacionalrazoavel...

52!, . . . , 255! 2255

Impossıvel com forca bruta!

SEG-6

Ivan Sendin

Criptografia

Cifradores

Cifrador de Substituicao

A letra a sempre gera a letra ek(“a′′) (para o mesmok)

A letra b sempre gera a letra ek(“b′′) (para omesmo k)

Analise de frequencia

Sistema monoalfabetico

SEG-6

Ivan Sendin

Criptografia

Cifradores

Cifrador Vigenere

Similar ao Deslocamento

Chave e maior

(K0,K1,K2,K3)

ek(xi) = (xi + ki (mod 4)) (mod 26)

Substituicao polialfabetica

Em geral e mais seguro

Textos grandes (em relacao ao tamanho da chave...)

SEG-6

Ivan Sendin

Criptografia

Cifradores

Cifrador de Vigenere

Ataque de texto claro conhecido

cabecalho, por exemplo

SEG-6

Ivan Sendin

Criptografia

Cifradores

Cifrador de Vigenere

Ataque de texto claro escolhido

Voce esta sendo vigiado

acesso a uma “maquina”

SEG-6

Ivan Sendin

Criptografia

Cifradores

Cifrador Afim

Inverso multiplicativo

a−1

a.a−1 = 1

a = 3, a−1 =? em Z14

SEG-6

Ivan Sendin

Criptografia

Cifradores

Cifrador Afim

3.1 = 3 (mod 14)

3.2 = 6 (mod 14)

3.3 = 9 (mod 14)

3.4 = 12 (mod 14)

3.5 = 15 ≡ 1 (mod 14)

....

SEG-6

Ivan Sendin

Criptografia

Cifradores

Cifrador Afim

Definido um modulo m

E(x) = ax + b (mod m)

Chave (a, b)

D(c) = a−1(c − b) (mod m)

SEG-6

Ivan Sendin

Criptografia

Cifradores

Cifrador Afim

k = (3, 7) m = 14

x = 8

E(8) = 3.8 + 7 (mod 14)

E(8) = 24 + 7 (mod 14)

E(8) = 31 (mod 14)

E(8) = 3 (mod 14)

SEG-6

Ivan Sendin

Criptografia

Cifradores

Cifrador Afim

kd = (5, 7) m = 14

c = 3

D(3) = 5.(3− 7) (mod 14)

D(3) = 5.− 4 (mod 14)

D(3) = −20 (mod 14)

D(3) = −6 (mod 14)

D(3) = −6 + 14 (mod 14)

D(3) = 8 (mod 14)

SEG-6

Ivan Sendin

Criptografia

Cifradores

Cifrador Afim

7.a−1 = 1 (mod 14)

7.1 = 7 (mod 14)

7.2 = 14 ≡ 0 (mod 14)

7.3 = 21 ≡ 7 (mod 14)

7.4 = 28 ≡ 0 (mod 14)

....

Nao tem inverso

O Deciframento nao “volta”

SEG-6

Ivan Sendin

Criptografia

Cifradores

Cifrador Afim

a e m precisam ser primos relativos!

ab ≡ 1 (mod m)

ab − 1 ≡ 0 (mod m)

m|ab − 1

gcd(a,m) = q(q > 1) (Contradicao)

qm′|qa′b − 1

q|qa′b − 1

q|qa′b e q| − 1 (errado!)

Teorema 1.1 de Stinson

SEG-6

Ivan Sendin

Criptografia

Cifradores

Cifrador Afim

Para m = 26 = 13.2

a pode assumir 1,3,5,7,9,11,15,17,19,21,23 ou 25

b de 0 a 25

312 chaves

No caso geral? Quantos primos relativos possui m?

SEG-6

Ivan Sendin

Criptografia

Cifradores

Cifrador Afim

m =n∏

i=1

peii

com ei > 0

SEG-6

Ivan Sendin

Criptografia

Cifradores

Cifrador Afim

φ(m) =n∏

i=1

(peii − p(ei−1)i )

Numero de primos relativos a m.

SEG-6

Ivan Sendin

Criptografia

Cifradores

Cifrador Afim

Para m = 26

m = 2.13

φ(m) = (21 − 20)(131 − 130)

φ(m) = (2− 1)(13− 1)

φ(m) = 12

SEG-6

Ivan Sendin

Criptografia

Cifradores

Cifrador Afim

Para m = 60

m = 22.31.35

φ(m) = (22 − 21)(31 − 30)(51 − 50)

φ(m) = (4− 2)(3− 1)(5− 1)

φ(m) = 2.2.4

φ(m) = 16

60 tem 16 primos relativos

O cifrador afim tem 16.60 chaves

SEG-6

Ivan Sendin

Criptografia

Cifradores

Cifrador Afim

Ao cifrador Afim usa chaves diferentes

Relacao matematica

A forca bruta nao usa uma busca exaustiva em m.m