(c) LSI-Tec 1999 1 História da Criptografia Volnys Borges Bernal Laboratório de Sistemas Integraveis Escola Politécnica da USP

(c) LSI-Tec 1999 1

História da Criptografia

Volnys Borges Bernal

Laboratório de Sistemas IntegraveisEscola Politécnica da USP

(c) LSI-Tec 1999 2

Agenda Alguns algoritmos clássicos de criptografia

convencional Cifra de Cesar Playfair Máquina de rotação

(c) LSI-Tec 1999 3

Algoritmos Clássicos

Cifra de Cesar

(c) LSI-Tec 1999 4

Cifra de Cesar Utilizada por Julio César Uso mais antigo de criptografia Cada letra do plaintext é substituida pela letra

localizada a “d” posições à frente no alfabeto A chave do algoritmo é o deslocamento

K = “d” Julio César utilizava K=3

(c) LSI-Tec 1999 5

Cifra de Cesar (cont.) Atribui-se valores a cada letra do alfabeto:

00 01 02 03 04 05 06 07 08 09 10 11 12 a b c d e f g h i j k l m

13 14 15 16 17 18 19 20 21 22 23 24 25 n o p q r s t u v w x y z

Encriptação:Ci = Ek(Pi)

= ( Pi + k) mod 26 Decriptação:

Pi = Dk(Ci) = (Ci - k + 26) mod 26

(c) LSI-Tec 1999 6

Cifra de César (cont.) Exemplo de encriptação

PEncriptador

(E)

C

Plaintext:“Este é um exemplo de mensagem”

Ciphertext: “hvwhhxphuhpsorghphkvdjhp“

Chave: K = 3

(c) LSI-Tec 1999 7

Cifra de César (cont.) Exemplo de decriptação

CDecriptador

(D)

P

Chave: K = 3


Ciphertext: “hvwhhxphuhpsorghphkvdjhp“

(c) LSI-Tec 1999 8

Cifra de César (cont.) Criptoanálise

Espaço de chaves: Nchaves = 25 Bloco = caractere Espaço de blocos: 26 (qtde de blocos diferentes) Ataques

(1) Somente ciphertext: Força Bruta:Existem somente 25 chaves possíveis Decifração símples: teste de todas as alternativas

(2) Plaintext Conhecido Direto: basta realizar a difereça do primeiro caractere para obter a

chave (3) Plaintext Escolhido / Ciphertext Escolhido:

Basta a seguinte mensagem: “a”

(c) LSI-Tec 1999 9


Playfair

(c) LSI-Tec 1999 10

Playfair Criado em 1854 e utilizado na 1a guerra mundial pelos

governos da Inglaterra e EUA A encriptação é realizada traduzindo-se dois caracteres

por vez

Exemplo: Plaintext: “Este é um exemplo de mensagem”

Es te éu me xe mp lo de me ns ag emPlaintext:

Ciphertext:

(c) LSI-Tec 1999 11

Playfair (cont.) Chave:

(a) A chave utilizada é uma palavra qualquer (uma seqüência de letras)

(b) Estas letras são dispostas em uma matriz 5x5. (c) O restante da matriz é preenchido com as letras do

alfabeto não utilizadas OBS:

Não devem existir letras repetidas na matriz Como o alfabeto inglês possui 26 letras e existem

somente 25 posições, as letras “i” e “j” são representadas de forma única

(c) LSI-Tec 1999 12

Playfair (cont.) Exemplo:

Chave: “MONARQUIA”Na forma de Matriz 5x5:

M O N A RQ U I

J

M O N A RQ U I

J B CD E F G HK L P S TV W X Y Z

(c) LSI-Tec 1999 13

Playfair (cont.) Regras de codificação:

(1) Este algoritmo não permite a tradução de pares de letras iguais do plaintext. Pares de letras iguais no plaintext devem ser separadas por uma letra especial pré estabelecida.

Exemplo: “ESSA” --> “ESXSA”

(2) Se as duas letras estão em uma mesma linha, cada uma é substituida pela letra imediatemente a seguir na mesma linha

(c) LSI-Tec 1999 14

Playfair (cont.) Regras de codificação (continuação)

(3) Se as duas letras estão em uma mesma coluna cada uma é substituida pela letra imediatamente abaixo na mesma coluna

(4) Se as duas letras estão em linhas e colunas diferentes:

A primeira letra é substituida pela letra da matriz na mesma linha cuja coluna cruza a segunda letra.

A segunda letra é substituida pela letra da matriz na mesma linha cuja coluna cruza a primeira letra

(c) LSI-Tec 1999 15

Playfair (cont.) Exemplo de encriptação

PEncriptador

(E)

C


Ciphertext: “ gllhleodwfnkwuefodapbsdo“

M O N A RQ U I


(c) LSI-Tec 1999 16

Playfair (cont.) Exemplo de encriptação

es te éu me xe mp lo de me ns ag em

gl lh le od wf nk wu ef od ap bs do

M O N A RQ U I


Plaintext

CiphertextChave

(c) LSI-Tec 1999 17

Playfair (cont.) Regras de decriptação

“Regras Inversas da encriptação”:

(2) Se as duas letras estão em uma mesma linha, cada uma é substituida pela letra imediatemente anterior na mesma linha

(3) Se as duas letras estão em uma mesma coluna cada uma é substituida pela letra imediatamente acima na mesma coluna

(4) Se as duas letras estão em linhas e colunas diferentes: A primeira letra é substituida pela letra da matriz na mesma

linha cuja coluna cruza a segunda letra. A segunda letra é substituida pela letra da matriz na mesma

linha cuja coluna cruza a primeira letra

(c) LSI-Tec 1999 18

Playfair (cont.) Exemplo de decriptação

CDecriptador

(D)

P


Ciphertext: “ gllhleodwfnkwuefodapbsdo“

M O N A RQ U I


(c) LSI-Tec 1999 19

Playfair (cont.) Exemplo de decriptação

es te éu me xe mp lo de me ns ag em

gl lh le od wf nk wu ef od ap bs doM O N A RQ U I


Ciphertext

PlaintextChave

(c) LSI-Tec 1999 20

Playfair (cont.) Criptoanálise

Espaço de chaves = Nchaves = (25 !) / 25 = 24 ! Bloco = dígrafo (2 caracteres) Espaço de blocos = Ndigrafos = 26x26 = 676

(c) LSI-Tec 1999 21

Playfair (cont.) Criptoanálise

Ataques (1) Somente Ciphertext

Análise de padrões, etc (2) Plaintext Conhecido

Permite obter de imediato a função de encriptação de alguns dígrafos

(3) Plaintext Escolhido Plaintext: “aa ab ac ... az ba bb bc ... bz ...”

(4) Ciphertext Escolhido Ciphertext: “aa ab ac ... az ba bb bc ... bz ...”

(c) LSI-Tec 1999 22


Máquina de rotação

(c) LSI-Tec 1999 23

Máquina de rotação Técnica de substituição com vários estágios a fim de

dificultar a criptoanálise Consiste de um conjunto de cilindros independentes.

Cada cilindro possui 26 pinos de entrada e 26 pinos de saída com uma ligação interna que conecta cada pino de entrada a um pino de saída

Maquinas deste tipo foram utilizadas na Segunda Guerra Mundial Alemanha: Enigma Japão: Purple

Allan Turing (matemático ingles) trabalhou para os aliados na criptoanalise deste tipo de máquinas

(c) LSI-Tec 1999 24

Máquina de Rotação (cont.)

A cada letra codificada o cilindro é rotacionado em 1 posição

Após 26 letras codificadas o cilindro retorna à posição original

Ex: Plaintext: abc Ciphertext: def

abcdefghijklmnopqrstuvwxyz


(c) LSI-Tec 1999 25

Máquina de Rotação (cont.)

Com vários Cilindros A dificuldade de criptoanálise

cresce com a utilização de vários cilindros concatenados

A cada letra codificada o cilindo 1 rotaciona 1 posição.

Sempre que o cilindro 1 voltar a posição original o cilindro 2 rotaciona 1 posição

Sempre que o cilindro 2 voltar a posição original o cilindro 3 rotaciona 1 posição


abcdefghijklmnopqrstuvwxyzcil. 1

cil. 2

cil. 3

(c) LSI-Tec 1999 26

Máquina de Rotação (cont.) Encriptação

PEncriptador

(E)

C

Plaintext: Ciphertext:

(c) LSI-Tec 1999 27

Máquina de Rotação (cont.) Decriptação

Mesmo algoritmo Mesma sequência de cilindros Mesmo sentido de rotação Realiza a substituição no sentido inverso

(c) LSI-Tec 1999 28

Máquina de Rotação (cont.) Exemplo de encriptação

CDecriptador

(D)

P

Ciphertext: Plaintext:

(c) LSI-Tec 1999 29

Máquina de Rotação (cont.) Criptoanálise

Espaço de chaves = Nchaves = (26 !) N

(p/ N cilindros distintos) Bloco = caractere Espaço de blocos = 26

porém um mesmo bloco pode ser codificado de forma diferente de acordo com sua posição no plaintext

(c) LSI-Tec 1999 30

Máquina de Rotação (cont.) Criptoanálise

Ataques (1) Ciphertext Somente

Força bruta (2) Plaintext conhecido

Se for longo o suficiente, direto (3) Plaintext Escolhido

Direto, exemplo: Plaintext: “aaaaaaaaaaaaa...a” (26N vezes p/ N cilindros)

(4) Ciphertext Escolhido Direto, exemplo: Ciphertext: “aaaaaaaaaaaaa...a” (26N vezes p/ N cilindros)

(c) LSI-Tec 1999 31


Exercícios

(c) LSI-Tec 1999 32

Exercícios (1) Criptografe o plaintext “exercício” utilizando os

algoritmos apresentados neste módulo. Utilize como valor da chave K os valores utilizados nos exemplos.

(2) Dentre os algoritmos vistos quais podem ser descobertos de forma direta (imediata) pelo ataque com “Plaintext Escolhido” onde é utilizada a seguinte mensagem: “abcdefghijklmnopqrstuvwxyz”

(c) LSI-Tec 1999 33

Exercícios (3) Dentre os algoritmos vistos quais podem ser descobertos

de forma direta (imediata) pelo ataque com “Plaintext Escolhido” onde é utilizada a seguinte mensagem: “aaaaaaaaaaaaaaaaaaaaaa....a”

(4) Dentre os algoritmos vistos quais podem ser descobertos de forma direta (imeditata) pelo ataque com “Plaintext Escolhido” onde é utilizada a seguinte mensagem: “a”

(c) LSI-Tec 1999 34

Exercícios (5) A facilidade ao ataque pela força bruta também está

relacionado ao numero de chaves possíves no algoritmo.Qual o número de chaves possíveis de cada um dos algoritmos apresentados?

(c) LSI-Tec 1999 35


Bibliografia

(c) LSI-Tec 1999 36

Bibliografia Livro:

Network and Internetwork Security - Principles and Practice - Second EditionWillian StallingsPrentice Hall1998

Documents

(c) LSI-Tec 1999 1 História da Criptografia Volnys Borges Bernal Laboratório de Sistemas Integraveis Escola Politécnica da USP