(c) LSI-Tec 1999
História da Criptografia
Volnys Borges Bernal
Laboratório de Sistemas Integraveis
Escola Politécnica da USP
1
(c) LSI-Tec 1999
Agenda

Alguns algoritmos clássicos de criptografia
convencional
 Cifra de Cesar
 Playfair
 Máquina de rotação
2
(c) LSI-Tec 1999
Algoritmos Clássicos
Cifra de Cesar
3
(c) LSI-Tec 1999
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
4
(c) LSI-Tec 1999
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

5
(c) LSI-Tec 1999
6
Cifra de César (cont.)

Exemplo de encriptação
Plaintext:
“Este é um exemplo de mensagem”
Ciphertext:
“hvwhhxphuhpsorghphkvdjhp“
P
C
Encriptador
(E)
Chave: K = 3
(c) LSI-Tec 1999
7
Cifra de César (cont.)

Exemplo de decriptação
Ciphertext:
“hvwhhxphuhpsorghphkvdjhp“
Plaintext:
“Este é um exemplo de mensagem”
C
P
Decriptador
(D)
Chave: K = 3
(c) LSI-Tec 1999
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)

 (3)
Plaintext Conhecido
Direto: basta realizar a difereça do primeiro caractere para
obter a chave
Plaintext Escolhido / Ciphertext Escolhido:
8
(c) LSI-Tec 1999
Algoritmos Clássicos
Playfair
9
(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”
Plaintext: Es te éu me xe mp lo de me ns ag em
Ciphertext:
(c) LSI-Tec 1999
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
11
(c) LSI-Tec 1999
Playfair (cont.)

Exemplo:

Chave:
 “MONARQUIA”
 Na forma de Matriz 5x5:
M O N A R
Q U IJ
M
Q
D
K
V
O
U
E
L
W
N A
I
J B
F G
P S
X Y
R
C
H
T
Z
12
(c) LSI-Tec 1999
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
13
(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
Plaintext:
“Este é um exemplo de mensagem”
Ciphertext:
“ gllhleodwfnkwuefodapbsdo“
P
C
Encriptador
(E)
M
Q
D
K
V
O
U
E
L
W
N A
I
J B
F G
P S
X Y
R
C
H
T
Z
(c) LSI-Tec 1999
16
Playfair (cont.)

Exemplo de encriptação
M
Q
D
K
V
O
U
E
L
W
N A
I
J B
F G
P S
X Y
Chave
R
C
H
T
Z
Plaintext
es te éu me xe mp lo de me ns ag em
gl lh le od wf nk wu ef od ap bs do
Ciphertext
(c) LSI-Tec 1999
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
17
(c) LSI-Tec 1999
18
Playfair (cont.)

Exemplo de decriptação
Plaintext:
Ciphertext:
“ gllhleodwfnkwuefodapbsdo“
“Este é um exemplo de mensagem”
C
P
Decriptador
(D)
M
Q
D
K
V
O
U
E
L
W
N A
I
J B
F G
P S
X Y
R
C
H
T
Z
(c) LSI-Tec 1999
19
Playfair (cont.)

Exemplo de decriptação
M
Q
D
K
V
O
U
E
L
W
N A
I
J B
F G
P S
X Y
Chave
R
C
H
T
Z
Ciphertext
gl lh le od wf nk wu ef od ap bs do
es te éu me xe mp lo de me ns ag em
Plaintext
(c) LSI-Tec 1999
Playfair (cont.)

Criptoanálise
 Espaço de chaves = Nchaves = (25 !) / 25 = 24 !
 Bloco = dígrafo (2 caracteres)
 Espaço de blocos = Ndigrafos = 26x26 = 676
20
(c) LSI-Tec 1999
Playfair (cont.)

Criptoanálise
 Ataques
 (1) Somente Ciphertext

 (2)

 (3)

 (4)

Análise de padrões, etc
Plaintext Conhecido
Permite obter de imediato a função de encriptação de
alguns dígrafos
Plaintext Escolhido
Plaintext: “aa ab ac ... az ba bb bc ... bz ...”
Ciphertext Escolhido
Ciphertext: “aa ab ac ... az ba bb bc ... bz ...”
21
(c) LSI-Tec 1999
Algoritmos Clássicos
Máquina de rotação
22
(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
Máquina de Rotação (cont.)
a
b
c
d
e
f
g
h
i
j
k
l
m
n
o
p
q
r
s
t
u
v
w
x
y
z
a
b 
c
d
e
f
g
h 
i
j
k
l
m
n
o 
p
q
r
s
t
u
v
w
x
y
z
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
24
(c) LSI-Tec 1999
Máquina de Rotação (cont.)

a
b
c
d
e
f
g
h
i
j
k
l
m
n
o
p
q
r
s
t
u
v
w
x
y
z
cil. 3
cil. 2
cil. 1
a
b
c
d
e
f
g
h
i
j
k
l
m
n
o
p
q
r
s
t
u
v
w
x
y
z
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
25
(c) LSI-Tec 1999
Máquina de Rotação (cont.)

Encriptação
Plaintext:
Ciphertext:
P
C
Encriptador
(E)
26
(c) LSI-Tec 1999
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

27
(c) LSI-Tec 1999
Máquina de Rotação (cont.)

Exemplo de encriptação
Ciphertext:
Plaintext:
C
P
Decriptador
(D)
28
(c) LSI-Tec 1999
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

29
(c) LSI-Tec 1999
Máquina de Rotação (cont.)

Criptoanálise
 Ataques
 (1) Ciphertext Somente

 (2)

 (3)
Força bruta
Plaintext conhecido
Se for longo o suficiente, direto
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)

30
(c) LSI-Tec 1999
Algoritmos Clássicos
Exercícios
31
(c) LSI-Tec 1999
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”
32
(c) LSI-Tec 1999
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”
33
(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
Algoritmos Clássicos
Bibliografia
35
(c) LSI-Tec 1999
Bibliografia

Livro:
 Network and Internetwork Security - Principles and
Practice - Second Edition
Willian Stallings
Prentice Hall
1998
36