Implementaçãodeumsistemadedecriptografiaemhardwarepara controlebancário

Prévia do material em texto

1
IMPLEMENTAÇÃO DE UM SISTEMA DE DECRIPTOGRAFIA EM
HARDWARE PARA CONTROLE BANCÁRIO
Augusto Ken Morita(1), Wilhelmus A. M.Van Noije
LSI/PSI – Escola Politécnica, Universidade de São Paulo
Av. Prof. Luciano Gualberto, 158, trav.3, São Paulo, SP, Brasil
(1) Atualmente está na empresa NEC do Brasil S.A.
Rodovia Presidente Dutra, Km 214, Guarulhos, SP, Brasil
AUGUSTKM@nec.com.br noije@lsi.usp.br
Abstract
This paper addresses a implementation of a
hardware system to decrypt data in real-time from an
encrypted floppy disks. The encryption protocol
used was DES (Data Encription Standard). The
hardware was modeled in VHDL and tested in
FPGA. Investigation on possible advantages and
disadvantages using this technology, compared
against traditional software techniques is also
considered. Also is demonstrated that using VHDL
we can produce technology independent circuits.
Introdução
Por um longo tempo a criptografia foi e tem sido
implementada com técnicas de software. Poucas
pessoas se interessavam para a implementação em
hardware. Este fato é devido à complexidade do
circuito, para se implementar algoritmos de
criptografia, os quais são sempre baseadas em
funções matemáticas.
Nos dias de hoje com o aumento do poder de
processamento dos computadores pessoais e também
pelo avanço das redes de Internet, é muito mais fácil
utilizar-se de grande poder de processamento em
conjunto para se quebrar a segurança de um sistema.
Junto com o aumento da possibilidade de quebra
de segurança em menos tempo, cresce a necessidade
de algoritmos de criptografias mais sofisticadas os
quais levam mais tempo para se criptografar ou
decriptografar os dados, pois utilizam funções
matemáticas que demandam um maior
processamento. Conseqüentemente levaria mais
tempo para quem tentasse decodificar os dados
criptografados.
Hoje com a demanda que existe para sistemas de
criptografia cada vez mais sofisticadas e lentas para
se realizar com implementações em software, há
uma grande necessidade para se implementar
sistemas dedicados em circuitos integrados para que
realizem algoritmos criptográficos.
A grande vantagem de se utilizar hardware em
vez de software é que quando feito uma função
criptográfica em circuito temos o aumento do poder
de processamento em relação a uma implementação
em software, no que se refere ao algoritmo de
criptografia ou decriptografia. Este fato de deve a
natureza dos circuitos elétricos ser paralela, isto é,
poder fazer múltiplas operações simultaneamente,
como também não podemos deixar de citar as
estruturas dedicadas para a realização das funções
matemáticas que envolvem em cada algoritmo de
criptografia, o qual computadores normais não
possuem.
Já em uma implementação em software as
funções matemáticas são realizadas de modo
seqüencial, executando cada linha de instrução uma
a uma.
Existe uma grande gama de pesquisas referentes
a técnicas de implementação de funções
criptográficas em circuitos integrados dedicados.
Este trabalho se refere a uma das muitas
possibilidades da implementação do DES (Data
Encryption Standard) em hardware e nosso escopo
não envolve somente a função de criptografia
propriamente dita, e sim a um sistema completo de
segurança.
A escolha do algoritmo de criptografia não se
baseou somente no algoritmo mais sofisticado para
ser decriptografado ou implementado. A decisão foi
por ser um padrão muito bem conhecido como
também de grande utilização, mesmo tendo um
tempo razoavelmente grande desce a sua primeira
utilização, ainda hoje no mercado é utilizado com
grande freqüência, principalmente no que ser refere
a segurança bancária.
A utilização de VHDL (Very high-speed
integrated circuit Hardware Description Language)
para a implementação do sistema de segurança foi a
facilidade de se descrever circuito utilizando esta
linguagem.
O tamanho físico também foi considerado onde
não poderia ser de forma alguma ser utilizado
circuitos discretos devido a complexidade do
circuito a ser desenvolvido.
 Muitas são as vantagens do VHDL, a
possibilidade de fazer circuitos não dependentes de
tecnologia, isto é, possível utilização do mesmo
código em tecnologias diferentes como por exemplo
2
FPGA (Field-Programmable Gate-Arrays) e ASIC
(Application-Specific Integrated Circuits)[1] sem a
necessidade de mudanças no código. Utilizando
VHDL o nível de abstração é muito alto, isto é, não
precisamos nos preocupar com os vários problemas
existentes em projetos de circuitos dedicados. Este
faz com que o projeto seja fácil de se desenvolver e
também flexível, rápido e compacto. A
documentação é de fácil entendimento e elimina o
problema de futuras mudanças no circuito.
Foi utilizado o FPGA, componente que pode ser
gravado com o circuito descrito em VHDL, esta
gravação pode ser feita quase que instantaneamente
após a compilação do circuito. A facilidade de
gravação facilita na depuração do circuito
propriamente dito como também não precisamos
esperar longos meses para que um protótipo seja
confeccionado, assim diminuímos muito o ciclo de
projeto.
Tanto para os testes de bancada como também
para o produto final foi utilizado FPGA, dada a
pequena demanda das unidades com o sistema de
segurança.
Idéia Inicial
O sistema consiste de um módulo que tem por
função decriptografar, via hardware, os dados lidos
em um disquete de 3,5 polegadas, este compatível,
em termos de formatação, com a linha de
microcomputadores IBM-PC.
A motivação deste projeto foi diminuir os custos
operacionais da atualização dos arquivos nos caixas
automáticos dos bancos. Atualmente, o caixa
automático é composto de um PC padrão que possui
um disk drive que serve tanto para carregar novas
versões de programas/dados quanto para ler arquivos
contendo os logs das transações efetuadas.
Do modo como está atualmente os caixas, é
possível inclusive incializar -“dar o Boot”- a
máquina, o que torna o sistema vulnerável, pois
qualquer programador mais experiente poderia
iniciar a máquina e rodar um aplicativo que fizesse a
máquina liberar dinheiro indevidamente.
Para evitar transtornos como o citado, o disk
drive é montado no cofre junto com o numerário e
qualquer Upload/Download exige a abertura do
cofre. Operacionalmente, o processo de Upload/
Download de dados/programas é muito caro, pois
exige seguranças armados durante o processo da
abertura do cofre, além de exigir uma pessoa com
certa confiança, já que este terá acesso interno ao
cofre onde se encontram as caixas com dinheiro,
aumentando muito os custos.
A solução para diminuir os custos operacionais é
criptografar o conteúdo dos floppy disks utilizados
nos disk drives dos caixas automáticos, de tal forma
que somente disquetes criptografados, utilizando
uma chave de conhecimento restrito, poderiam ser
utilizados para fazer o download de
programas/dados na máquina.
A decriptografia dos dados/programas contidos
no disquete é totalmente feita em hardware. Poder-
se-ia argumentar que a decriptografia poderia ser
feita por software via BIOS (Basic Instruction
Operational System) modificada, porém é sabido
que sistemas operacionais, como o Windows NT,
por exemplo, capturam as interrupções e têm suas
próprias rotinas de acesso a disco, tornando a
decriptografia por software inócua.
Utilizando-se um sistema de decriptografia em
hardware pode-se obter algumas vantagens como na
velocidade de decriptografia, a transparência, tanto
para o usuário como para qualquer sistema
operacional sem a utilização e manipulação de
softwares específicos a cada sistema operacional e
plataforma.
O método de criptografia utilizado foi o Data
Encryption Standard (DES), por sua rapidez, aliada
a facilidade de implementação em hardware.
O circuito desenvolvido, “intercepta" os dados
lidos do disquete, recompõe os frames originais
lidos, validando-os e descartando os parâmetros de
controle desses frames (número da trilha e cabeça,
setor do frame, bytes de sincronismo e CRC).
Em tempo real a leitura de cada frame, o circuito
decriptografa os dados contidos nos frames lidos,
utilizando algoritmo DES.Num segundo momento, o circuito monta novos
frames, usando os bytes decriptografados,
conservando, entretanto, as posições originais
relativas, equivalentes aos bytes originais. Todas as
informações de controles (número de trilha e setor,
setor do frame, bytes de sincronismo e novo CRC),
são gerados conforme as características dos bytes
decriptografados. Estes novos frames são então
direcionados à placa controladora de floppy disk do
micro IBM-PC.
Tendo em vista que as operações acima descritas
são feitas em tempo real a leitura dos dados no
disquete, a placa controladora não percebe a
existência do módulo decriptografador.
Evidentemente, a existência do referido módulo,
num micro IBM-PC, habilita a leitura, apenas, dos
disquetes cujos dados estejam criptografados, com a
particular chave gravada no módulo. Isto evita a
leitura indevida, proposital ou acidental, de arquivos
que não tenham sido criptografados com a particular
chave de cada módulo.
Outra característica importante do módulo
decriptografador é a possibilidade de troca da chave
de decriptografia, a qualquer tempo, de acordo com
a opção do usuário do micro, o que dificulta as
3
eventuais tentativas para descoberta ou quebra
dessas chaves.
A opção por um sub-sistema autônomo traz a
vantagem do uso, no micro IBM-PC, de mother-
boards de mercado, sem a necessidade de alterações,
retrabalhos, especificações particulares ou limitações
das características dessas unidades.
Metodologia
Técnicas de codificação dos dados no
disquete
O controlador de floppy escreve dados no disk
drive serialmente como pulsos codificados. Estes
pulsos são então convertidos pelo drive em variações
de fluxo magnético na superfície do disquete. Os
pulsos podem ser posteriormente lidos pelo drive e
convertidos de volta para pulsos codificados, que
podem ser decodificados pelo controlador resultando
os dados originais. [2]
Como o dado é um conjunto de bits seriais e,
devido a imperfeições no processo de escrita/leitura,
podem haver variações e deslocamento nas
informações seriais, o relógio está embutido na
seqüência de bits recebidos do floppy, o que
possibilita a sincronização dinâmica dos dados
durante a leitura.
Os dois esquemas de codificação mais populares
utilizados em disquete são: FM (Frequency
Modulation) e MFM (Modified Frequency
Modulation). FM define uma célula para cada bit de
dados. Cada célula contém uma posição para o pulso
de dado e outra para o pulso de relógio. Cada uma
destas posições são conhecidas como janelas. O
pulso de relógio está presente em todas as células e
os pulsos de dados estão presentes somente se o bit
de dado para aquela célula for um. Quando este dado
é lido a partir de um disco, o relógio de leitura pode
ser gerado a partir dos pulsos de relógio do sinal. A
codificação FM foi o primeiro método usado para
gravar dados em disquete. No sistema FM somente
50% da área útil do disco é utilizada para gravar
dados enquanto os outros 50% são utilizados para
gravar pulsos de relógio.
A Codificação MFM destina 100% da área útil
do disco para armazenar dados. MFM define uma
célula para cada bit de dado, como no FM.
Novamente cada célula contém uma posição para
pulso de relógio (Janela de relógio) e uma posição
para o pulso de dado (Janela de dado). Um pulso de
dado está presente se o bit de dado for um. O pulso
de relógio está presente somente se o bit de dado for
zero e o anterior também for zero. Veja Figura 1
Figura 1. Exemplo de como o dado e o relógio são
codificados em MFM.
Comparando os dois métodos, pode-se observar
que o método MFM requer menos pulsos para
codificar a mesma quantidade de dados, gastando
metade do espaço requerido pelo FM.
O único problema do MFM é que requer uma
cabeça de leitura/escrita melhor e circuitos
eletrônicos melhores. É também necessário um
separador de dados mais preciso do que o necessário
para o FM.
Como o MFM é a técnica dominante utilizada
nos discos flexíveis atuais e a utilização do FM nos
discos atuais é quase insignificante, enfocaremos
neste trabalho a codificação e decodificação desta
técnica.
Formato típico de um setor
Cada trilha contém um conjunto de vários
setores. Cada setor contém um campo de endereço e
um campo de dados. A seguir será abordado em
detalhes o formato IBM para dupla densidade,
apesar de existirem outros formatos no mercado,
este formato é o mais comum nos dias atuais.
O campo de endereço dentro de um setor é usado
para identificar a qual setor e trilha pertence o
campo de dados. Começa com um campo de
sincronização ou preâmbulo para permitir que o
separador de dados sincronize a velocidade na qual
os dados são lidos do disco.
Depois um address mark (AM) identifica
univocamente este campo como um campo de
endereço. Os address marks são codificados com um
padrão ilegal único que é uma violação da regra de
codificação do MFM. Esta violação consiste em um
pulso de relógio faltando em uma posição particular
dentro de um byte. Este padrão ilegal garante que
este é um address mark e não um padrão de dados
de alguma outra área do disco. Os quatro bytes
seguintes identificam o setor que está sendo lido.
Este é seguido por um campo de CRC (Cyclic
Redundance Check). O CRC permite ao controlador
verificar se a informação lida está livre de erros.
Este é seguido por um GAP que é simplesmente uma
4
série de bytes que separa fisicamente o campo de
endereço com o campo de dados. [3]
O campo de dados contém os dados que o setor
representa. Começa com um preâmbulo e um
address mark do campo de dados, de forma
semelhante ao campo de endereços. O campo de
dados é seguido por um CRC e depois por um GAP,
que separa o setor atual do próximo. O formato das
ordens de informações que compõe o quadro do
floppy disk esta ilustrado na Figura 2
G A P
8 0 O F 
4 E
T
R
A
C
K
H
E
A
D
C
R
C
C
R
C
S
E
C
T
O
R
#
B
Y
T
E
S
G A P
PR O GR A -
M A BLE
G A P
5 0 O F 
4 E
G A P
2 2 O F 
4 E
S Y N C
1 2 O F
0 0
S Y N C
1 2 O F
0 0
S Y N C
1 2 O F
0 0
IA M
3 O F
C 2*
3 O F
A1*
3 O F
A1*F C F E
F B
O R
F 8
A M A M D ATA G A P
D ATA FI ELD
R EP EAT ED FO R EAC H S EC T OR
AD D R E E F IELDIN D EX AD D R ESSF IELD
C 2 * = D a d o s C 2 c o m c lo ck 1 4
A 1 * = D a d o s A 1 co m c lo c k 0 A
Figura 2. Formato típico da unidade de disco. Formato
padrão IBM MFM.
O Algoritmo de Criptografia DES
DES é um algoritmo que criptografa blocos de
64 bits. Um bloco de dados de 64 bits como entrada
produz um bloco de 64 bits criptografado na saída
do DES. DES é um algoritmo simétrico, isto é, o
mesmo algoritmo e a mesma chave são usadas tanto
para criptografar como para decriptografar [4].
O comprimento da chave é de 56 bits.
Normalmente a chave é expressa em 64 bits,
contudo a cada conjunto de 8 bits é utilizado um bit
para checagem de paridade e este bit é ignorado
como parte da chave. Estes bits de paridade são
sempre o bit menos significativo dos bytes que
compõe a chave. A chave pode ser qualquer
combinação de 56 bits e pode ser trocada a qualquer
instante. Um conjunto pequeno de números é
considerado chave fraca, contudo pode ser
facilmente evitado.
Uma explicação simplificada do algoritmo seria
dizer que este combina duas técnicas básicas da
criptografia; confusão e difusão. O bloco
fundamental da arquitetura DES é uma combinação
destas técnicas, uma substituição seguida de uma
permutação, aplicada nos dados, levando como base
a chave. Este é chamado de etapa. O DES tem 16
etapas; isto é, aplica-se 16 vezes nos dados a ser
criptografado, a mesma combinação de técnicas
mencionadas anteriormente.
O algoritmo utiliza-se de aritmética básica e
operações lógicas básicas em números de 64 bits,
além de sua natureza repetitiva, o que torna este,
ideal para ser implementado em chips de aplicações
específicas (ASIC) [5].
Detalhamento do algoritmo.
O DES opera em blocos de 64 bits de dados.
Depois de uma permutação inicial, o bloco de dados
é dividido em duas partes, metade à esquerda e
metade à direita, cada parte com 32 bits de
comprimento. Logo após,há 16 etapas de operações
idênticas, chamadas de função F, no qual os dados
são combinados com a chave. Após o termino das 16
etapas, a parte da esquerda e da direita são juntadas e
uma permutação final (inverso da permutação
inicial) é aplicada, assim finalizando o algoritmo.
Veja Figura 3.
T e xto
IP
L 0 R 0
f K 1
L 1= R0 R 1= L 0+ f(R 0,K 1 )
f K 2
L 2= R 1 R2= L 1+ f(R1,K 2)
f K 1
R 15= L 14+ f(R 14,K 15) L 15= R 14
L 15= R14 R 15= L 14+ f(R 14,K 15 )
IP -1
Te xto c r ip to grafado
Figura 3. Diagrama de blocos DES.
Em cada etapa, a chave é deslocada e 48 bits
desta chave de 56 bits são escolhidos. A parte da
direta dos dados é expandido para 48 bits através de
uma permutação de expansão, combinado com
operador XOR com os 48 bits da chave já deslocada
e permutada, enviada através dos 8 blocos S,
produzindo 32 novos bits, e permutado novamente.
Estas 4 operações são chamadas de função F. O
resultado da função F é combinado com a parte da
esquerda utilizando-se novamente XOR para esta
operação como podemos observar na Figura 4. O
resultado destas operações torna-se a nova parte da
direita e a parte da direita anterior se torna a nova
parte da esquerda. Estas operações são repetidas por
16 vezes, compondo as 16 etapas do DES.
Se Bi é o resultado da interação número n, Li e
Ri são a parte da esquerda e a parte da direita de Bi,
5
Ki é a chave de 48 bits para a etapa i, e F é a função
que faz todas as substituições, permutações e XOR
com a chave, então a etapa seria como detalhado na
Figura 4
L i-1 Ri-1
Perm utação com Expansão
Subs tituiç ão Bloc o S
Perm utação Bl oco P
R iL i
Chave (key)
Perm utação com Expansão
Shi ft Shi ft
Chave (key)
Figura 4. Detalhamento etapa do DES.
Permutação Inicial
A permutação inicial ocorre antes da primeira
etapa, o embaralhamento dos bits dos dados de
entrada pode ser visto na Tabela 1. As tabelas
apresentadas a respeito do algoritmo do DES devem
ser lidas da esquerda para direita de cima para baixo.
Por exemplo, a permutação inicial move o bit 58 dos
dados de entrada para a posição 1, o bit 50 para
posição 2 e assim por diante.
A permutação inicial e a correspondente
permutação final não afetam na segurança do DES.
Tabela 1. Permutação Inicial (IP).
58 50 42 34 26 18 10 2
60 52 44 36 28 20 12 4
62 54 46 38 30 22 14 6
64 56 48 40 32 24 16 8
57 49 41 33 25 17 9 1
59 51 43 35 27 19 11 3
61 53 45 37 29 21 13 5
63 55 47 39 31 23 15 7
Transformação da chave
Inicialmente, a chave de 64 bits do DES é
reduzida para uma chave de 56 bits, isto é feito
ignorando-se o oitavo bit de cada byte, como pode
ser visto na Tabela 2. Estes bits ignorados podem
ser utilizados como checador de paridade para
garantir que a chave não está errada ou para outros
fins se necessário.
Tabela 2. Permutação da chave.
57 49 41 33 25 17 9
1 58 50 42 34 26 18
10 2 59 51 43 35 27
19 11 3 60 52 44 36
63 55 47 39 31 23 15
7 62 54 46 38 30 22
14 6 61 53 45 37 29
21 13 5 28 20 12 4
Após a chave de 56 bits ser extraída, uma
subchave diferente de 48 bits é gerada para cada
uma das 16 etapas do DES. Estas subchaves, Kn são
geradas da seguinte maneira.
Primeiramente os 56 bits da chave são divididos
em duas metades de 28 bits. Então as metades são
deslocadas circularmente para a esquerda de um ou
dois bits, dependendo da etapa. Este deslocamento
pode ser visto na Tabela 3.
Tabela 3. Número de bits da chave a ser deslocada para
esquerda pela interação.
Int. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Des 1 1 2 2 2 2 2 2 1 2 2 2 2 2 2 1
Após terem sido deslocados, 48 bits dos 56 bits
são selecionados. Devido a permutação dos bits
nesta operação como também na operação de
seleção dos 48 bits, este é chamado de permutação
com compressão (Compression permutation).
Devido ao deslocamento, um diferente conjunto
de bits da chave é utilizado para geração de cada
subchave. Cada bit é utilizado, aproximadamente,
nas 14 das 16 subchaves, contudo nem todos os bits
são utilizados exatamente o mesmo número de
vezes.
Tabela 4. Permutação com compressão.
14 17 11 24 1 5
3 28 15 6 21 10
23 19 12 4 26 8
16 7 27 20 13 2
41 52 31 37 47 55
30 40 51 45 33 48
44 49 39 56 34 53
46 42 50 36 29 32
6
Permutação com expansão
Esta operação expande a metade da direta dos
dados, Ri, de 32 bits para 48 bits. Esta operação é
chamada de permutação com expansão devido ao
fato desta mudar a ordem dos bits como também
repetir alguns dos bits.
Esta operação tem dois propósitos: fazer com
que a metade da direita tenha o mesmo tamanho da
chave para a operação com XOR e também produzir
um resultado maior que pode ser comprimido
durante a operação de substituição. Contudo nenhum
dos dois tem a finalidade de criptografia. Permitindo
que um bit afete duas substituições, a dependência
dos bits de saída nos bits de entrada cresce
rapidamente. Este é chamado de efeito avalanche.
DES é projetado para chegar a uma condição de que
todos os bits criptografados dependam de todos os
bits dos dados originais e de todos os bits da chave o
mais rápido possível.
 Este é chamado freqüentemente de bloco E. Para
cada 4 bits dos dados de entrada, o primeiro e o
quarto bit de cada, representam dois bits dos dados
de saída, enquanto que o segundo e o terceiro bit
representam um bit dos dados de saída. A Tabela 5
mostra qual das posições de saída corresponde a
qual das posições da entrada. Por exemplo, o bit de
posição 3 dos dados de entrada é movido para a
posição 4 dos dados de saída, e o bit na posição 21
dos dados de entrada é movido para a posição 30 e
32 dos dados de saída.
Apesar dos dados de saída serem maiores que os
dados de entrada, cada dado de entrada gera um
único dado de saída.
Tabela 5. Permutação com expansão (E).
32 1 2 3 4 5
4 5 6 7 8 9
8 9 10 11 12 13
12 13 14 15 16 17
16 17 18 19 20 21
20 21 22 23 24 25
24 25 26 27 28 29
28 29 30 31 32 1
O bloco S de substituição
Após a chave comprimida ter feito uma operação
de XOR com o bloco expandido, os 48 bits
resultantes vão para uma operação de substituição.
As substituições são feitas por 8 blocos de
substituição chamados de blocos S. Cada bloco S
tem 6 bits de entrada e 4 bits de saída, havendo 8
blocos S diferentes. Os 48 bits são divididos em 8
sub-blocos de 6 bits. Em cada sub-bloco é feita uma
operação de substituição com diferentes blocos S.
Cada bloco S é uma tabela de 4 linhas por 16
colunas. Cada entrada no bloco gera uma saída de 4
bits. Os 6 bits de entrada do bloco S especifica qual
das linhas e qual das colunas deve ser pego para a
saída. As Tabela 6 à Tabela 13, mostra todos os 8
blocos S.
Tabela 6. Substituição S[1].
14 4 13 1 2 15 11 8 3 10 6 12 5 9 0 7
0 15 7 4 14 2 13 1 10 6 12 11 9 5 3 8
4 1 14 8 13 6 2 11 15 12 9 7 3 10 5 0
15 12 8 2 4 9 1 7 5 11 3 14 10 0 6 13
Tabela 7. Substituição S[2].
15 1 8 14 6 11 3 4 9 7 2 13 12 0 5 10
3 13 4 7 15 2 8 14 12 0 1 10 6 9 11 5
0 14 7 11 10 4 13 1 5 8 12 6 9 3 2 15
13 8 10 1 3 15 4 2 11 6 7 12 0 5 14 9
Tabela 8. Substituição S[3].
10 0 9 14 6 3 15 5 1 13 12 7 11 4 2 8
13 7 0 9 3 4 6 10 2 8 5 14 12 11 15 1
13 6 4 9 8 15 3 0 11 1 2 12 5 10 14 7
1 10 13 0 6 9 8 7 4 15 14 3 11 5 2 12
Tabela 9. Substituição S[4].
7 13 14 3 0 6 9 10 1 2 8 5 11 12 4 15
13 8 11 5 6 15 0 3 4 7 2 12 1 10 14 9
10 6 9 0 12 11 7 13 15 1 3 14 5 2 8 4
3 15 0 6 10 1 13 8 9 4 5 11 12 7 2 14
Tabela 10. Substituição S[5].
2 12 4 1 7 10 11 6 8 5 3 15 13 0 14 9
14 11 2 12 4 7 13 1 5 0 15 10 3 9 8 6
4 2 1 11 10 13 7 8 15 9 12 5 6 3 0 14
11 8 12 7 1 14 2 13 6 15 0 9 10 4 5 3
Tabela 11. Substituição S[6].
12 1 10 15 9 2 6 8 0 13 3 4 14 7 5 11
10 15 4 2 7 12 9 5 6 1 13 14 0 11 3 8
9 14 15 5 2 8 12 3 7 0 4 10 1 13 11 6
4 3 2 12 9 5 15 10 11 14 1 7 6 0 8 13
7
Tabela 12. Substituição S[6].
4 11 2 14 15 0 8 13 3 12 9 7 5 10 6 1
13 0 11 7 4 9 1 10 14 3 5 12 2 15 8 6
1 4 11 13 12 3 7 14 10 15 6 8 0 5 9 2
6 11 13 8 1 4 10 7 9 5 0 15 14 2 3 12
Tabela 13. Substituição S[8].
13 2 8 4 6 15 11 1 10 9 3 14 5 0 12 7
1 15 13 8 10 3 7 4 12 5 6 11 0 14 9 2
7 11 4 1 9 12 14 2 0 6 10 13 15 3 5 8
2 1 14 7 4 10 8 13 15 12 9 0 3 5 6 11Os bits de entrada especificam uma entrada no
bloco S em uma maneira muito particular. Considere
um bloco S com só 6 bits de entrada, b1, b2, b3, b4,
b5 e b6. Os bits b1 e b6 são combinados para formar
um número de 2 bits, o qual corresponde à linha da
tabela. Os 4 bits do meio, b2 até b5 são combinados
para formar um número de 4 bits, o qual
corresponde à coluna da tabela.
Por exemplo, imagine que as entradas do sexto
bloco S sejam 110011. O primeiro e o último bit
combinado são 11, o qual corresponde a linha 3 do
sexto bloco S (lembrando de contar as linhas de 0 a
3 e colunas de 0 a 15). Os quatro bits do meio
combinados são 1001, o qual corresponde à coluna 9
do bloco S. O número na tabela correspondente é o
14. Assim podemos dizer que o número 110011 será
substituído por 1110 (14 decimal).
Para uma implementação em software podemos
re-arranjar os blocos S em uma matriz de 64
entradas. Contudo nunca se deve rearranjar a
indexação sem rearranjar as entradas. Os blocos S
foram projetados com muito cuidado.
As substituições dos blocos S são um passo
crítico do DES. Os algoritmos das outras operações
são lineares e fáceis de analisar. Os blocos S são
não-lineares e mais que tudo dão ao DES a
segurança.
O resultado desta fase de substituição formam 8
blocos de 4 bits os quais combinados formam um
bloco de 32 bits. Este bloco é então a entrada do
bloco de permutação (bloco P).
Bloco P permutação
Os 32 bits de saída do bloco de substituição são
permutados de acordo com o bloco P. A Tabela 14
mostra a posição a qual cada bit é permutado. Por
exemplo, o bit 21 é movido para o bit 4, enquanto o
bit 4 move para o bit 31.
Finalmente o resultado do bloco P é feito um
XOR com a metade da esquerda dos 64 bits iniciais.
Após esta operação a parte da direita é trocada com
a parte da esquerda e inicia-se uma nova etapa.
Tabela 14. Permutação (P).
16 7 20 21
29 12 28 17
1 15 23 26
5 18 31 10
2 8 24 14
32 27 3 9
19 13 30 6
22 11 4 25
Permutação final
A permutação final é o inverso da permutação
inicial e está descrita na Tabela 15. Note que a
metade da esquerda e a metade da direita não são
trocadas após a última etapa do DES, os blocos R16
e L16 são concatenados e utilizados como entrada
do bloco de permutação final. Não ocorre nada nesta
fase, trocando-se as metades e deslocando-se na
permutação levaria a exatamente o mesmo resultado.
Isto é verdade, pois o algoritmo pode ser utilizado
tanto para criptografar como para decriptografar.
Tabela 15. Permutação final
40 8 48 16 56 24 64 32
39 7 47 15 55 23 63 31
38 6 46 14 54 22 62 30
37 5 45 13 53 21 61 29
36 4 44 12 52 20 60 28
35 3 43 11 51 19 59 27
34 2 42 10 50 18 58 26
33 1 41 9 49 17 57 25
Decriptografando o DES
Após todas as substituições, permutações, XOR e
deslocamentos, podemos pensar que a decriptografia
seja alguma coisa complexa como o algoritmo de
criptografia. Ao contrário as várias operações foram
escolhidas para produzir uma propriedade
específica. O mesmo algoritmo funciona como
criptografador e decriptogrador.
Com o DES é possível utilizar as mesmas
funções para criptografar e decriptografar um dado.
A única diferença é que as chaves devem ser usadas
em uma ordem reversa, isto é se na criptografia as
chaves para cada etapa foram k1, k2, k3,..., k16,
então para decriptografar devem ser utilizadas k16,
8
k15, k14, ...., k1. O algoritmo utilizado para se criar
as chaves para as etapas é circular. O deslocamento
da chave é um deslocamento para a direita e o
número de bits a ser deslocado é 1, 1, 2, 2, 2, 2, 2, 2,
1, 2, 2, 2, 2, 2, 2 e 1.
Abordagem
A partir dos dados disponíveis foi feito um
modelamento do sistema como um todo, sendo nesta
etapa divididos em 4 macroblocos.
O sistema foi dividido de tal forma que
facilitasse no projeto dos circuitos. Um dos pontos
mais considerados foi à possibilidade de reutilização
de cada macrobloco em um projeto futuro, como
também a possibilidade de simulação de cada
macrobloco separadamente. Assim pudemos dividir
cada parte do sistema em macroblocos
independentes que em conjunto podem ser utilizados
com o sistema de segurança aqui abordado. Veja
Figura 5 com mais detalhes.
O primeiro macrobloco chamado de
Decodificador e Controle é componsto dos seguintes
blocos:
• Separador de dados e clock.
• Detector de fase.
• Máquina de estado de controle
• Multiplexador.
• Codificador MFM
O separador de dados e clock é um módulo onde
é feita toda a decodificação dos dados vindos no
formato MFM do floppy disk e convertidos para
sinais de níveis lógicos 0s e 1s, esta etapa é
necessária devido a dificuldade em trabalharmos
com dados codificados em MFM, assim este módulo
se encarrega de decodificar este sinal em um sinal de
dados e um sinal de relógio. É importante notarmos
que neste estágio de decodificação dos dados MFM,
não temos ainda informações suficientes sobre a fase
de captura dos dados pois a fase do sinal de relógio
restaurado pode estar invertido.
Uma vez passado este bloco podemos então
detectar a fase correta do sinal de relógio, isto é feito
no bloco de detector de fase.
O bloco detector de fase observa características
específicas dos dados gravados no floppy disk, os
quais são padronizadas para este fim, chamado de
preâmbulo ou dados de sincronização, estes é
composta por uma seqüência de H00 e H4E. Uma
vez que estes dados são detectados o circuito deste
bloco tem a capacidade de identificar e fornecer na
saída o dado e o relógio recuperado na fase correta.
Podemos dizer que este bloco, máquina de estado
de controle, é o bloco mais importante para a
sincronização e o funcionamento em conjunto do
sistema todo.
O bloco multiplexador tem a função de substituir
os dados bem como o CRC quando estiver na região
de dados e na região de CRC onde serão substituídos
por dados decriptografados e seus respectivo CRC.
O codificador de MFM tem a função de gerar
novamente sinais MFM a partir dos dados
decriptografados e do sinal de relógio, ambos em
sinais de níveis lógicos 1 e 0. Este bloco é necessário
pois o controlador de floppy disk entende somente
dados vindos no formato MFM, é claro que se os
dados fossem utilizados em algum tipo diferente de
interface como por exemplo uma entrada serial, este
bloco não seria necessário.
Se pa ra dor de da d os
e c loc k D ete cto r d e fas e
D ados F lo p p y
C lo ck 1 6 M H z
D ados
C lo ck R
M aquina de
est ado de
co n t ro le
M ó dulo D E S
M o do C F B
 Mó dulo d e CRC
C o m p arado r
M ó dulo de
T ro ca de
C h ave
Chave 6 4
V eto r In icial 64
 Mó dulo I 2C
P / M e m ória c om
Cha ve
 Mó dulo d e CRC
x o rD ados sy c
D ados sy c
E st a no s D ado s
E st a no CR C
D ados D ecr ip t o gra fado s
C RC C h ecado
M ult ip lex ado r
C o dif icado r
M F M
C lo ck R
C lo ck R
C lo ck R
Sa ida M F M
Sina l p a ra c r ia r m issin g c lo ck
SC L
SD A
C lo ck 1 0 0 K H z
 M ó d u lo I2 C
T ro ca d e C h av eSC L
SD A
C lo ck 1 0 0 K H z
� � � � � � � � � � � � � � � 	 
 � 
 � � 	 � � � 
 � � � � � � �
� � � � � � � � � � � � � � � � � � � 	 � � � � � �
� � � � � � � � � � � 
 � � � �
� � � � � � � � � � � � � 	 � � � � � �
Figura 5. Diagrama de blocos detalhados do sistema de segurança.
9
O segundo Macrobloco chamado de Detector de
Erros é composto dos seguintes blocos:
• Módulo de CRC.
• Comparador.
• XOR.
No bloco módulo de CRC é calculado dois
CRC, um para os dados que estão chegando dos
floppy disk, o qual serve para uma verificação da
integridade dos dados decodificados pelo primeiro
macrobloco. Neste instante os dados ainda não
estão decriptografados, somente em estado digital,
dado e relógio.
Paralelamente o segundo gerador de CRC está
calculando o valor do CRC para os dados
decriptografados que estão vindos do terceiro
macrobloco.
Se houver algum erro na decodificação do
primeiro macro bloco, o primeiro gerador de CRC
resultará em um número errado.
Este CRC errado calculado pelo primeiro
gerador de CRC é comparado no bloco XOR com o
CRC que está gravado na trilha do floppydisk.
Uma vez detectado o erro, este bloco gera pulsos de
erro para que o CRC do segundo gerador seja
destruido.
Quando o controlador de floppy disk observar
os dados decriptografados e o CRC errado ira
enviar pulsos de controle para o floppy disk
avisando para que envie novamente os dados.
É importante ressaltar que a estrutura do bloco
XOR foi projetada para que este macro bloco não
gere nenhum atraso dos sinais, todo procedimento é
feito em tempo real para garantir o desempenho do
sistema.
O terceiro Macrobloco chamado Chave
componsto dos seguintes blocos:
• Módulo I2C para memória com chave.
• Módulo I2C de troca de chave.
• Módulo de troca de chave.
O módulo I2C para memória com chave tem a
função de fazer a interface no padrão I2C [6][7]
com a memória onde está guardado o valor da
chave utilizado pelo quarto bloco onde se concentra
o algoritmo de criptografia.
Existe o módulo de I2C de troca de chave tem a
função de interfacear com um módulo de
carregamento de chave onde este módulo utiliza-se
também do padrão de comunicação I2C.
For fim o módulo de troca de chave faz uma
checagem nos dados vindos do módulo I2C de troca
de chave e decide se a nova chave será aceita ou
não.
O quarto Macrobloco chamado de Módulo DES
é composto somente com um único bloco onde é
realizada a decriptografia propriamente dita. Este
bloco foi projetado para que faça somente a
decriptografia dos dados que entram serialmente,
sendo que a taxa de dados pode ser modificada de
taxas baixas até um valor máximo de 1M ciclos de
decriptografia por segundo, com uma inserção de
dados a uma taxa de 16 Mb/s.
Foi projetado para que em um futuro projeto
onde necessite de um bloco que faça tanto a
decriptografia como também a criptografia, este
bloco pode ser utilizado com mínimas alterações.
Estas alterações se referem à criptografia dos dados
visto que este bloco somente faz a decriptografia,
contudo, como o algoritmo DES descrito
anteriormente, seria necessária somente uma
mudança do sentido do deslocamento da chave.
Logicamente caso este bloco seja transformado
em um ASIC dedicado (Standard Cell ou gate
Array) a taxa de dados pode ser bem superior, hoje
este taxa está limitado à tecnologia da FPGA
utilizada neste sistema.
Na Figura 6 podemos observar a placa de
decriptografia desenvolvida neste trabalho e seu
posicionamento entre a unidade de floppy disk e a
controladora da unidade de floppy disk que esta
localizado na placa mãe.
Figura 6. Ilustração do sistema de segurança e seu
posicionamento.
Tanto na Figura 6 como na Figura 7 podemos
observar a existência de dois chips no centro da
placa de decriptografia, este é o componente FPGA
utilizado. Foram necessárias as utilizações destes
dois componentes para o primeiro momento,
devido ao tamanho do circuito desenvolvido.
Contudo, em uma segunda fase de minimização e
melhoramento da construção do circuito
propriamente dito, o tamanho do circuito foi
minimizado para caber em um único componente,
diminuindo o custo do sistema.
10
Figura 7. Detalhe da placa decriptografadora.
Conclusão
O sistema aqui proposto foi concluído
utilizando como componente final o FPGA da
Altera da família FLEX6000. A quantidade de
Gates utilizados foi de 35.000, em células dos
componentes da altera foi 1.500 células e a
ocupação do componente foi de 92%.
Foi notado que neste nível de ocupação podem
ser encontradas problema quanto a erros no circuito
causados pelos atrasos das interconexões dentro do
componente. Para minimizar estes tipos de
problemas devem ser sempre utilizadas estruturas
síncronas e estruturas bem definidas para confecção
de circuitos.
Agradecimentos
O projeto foi apoiado e financiado pela
Procomp Indústria Eletrônica LTDA. e LSI/PSI –
Escola Politécnica, Universidade de São Paulo.
Referência Bibliográfica
[1] D. J. Smith, ”HDL Chip Design: A Pratical
guide for Designing, Synthesizing, and
Simulation ASICs and FPGAs using VHDL”,
Doone Publications, 1996.
[2] AN-505, ”Floppy disk Data Separator Design
Guide”, National Semiconductor, Feb. 1989.
[3] DP8470, “Phase Locked Loop Data Sheet”,
National Semiconductor, 1986.
[4] ANSI X3.92, “American National Standard for
Data Encryption Algorithm (DEA),”American
Nationa Standard Institute, 1981.
[5] ANSI X3.105, “American National Standard
for Information System – Data Link
Encryption,”American National Standards
Institute, 1983.
[6] “The I2C bus And How to Use It,” Philips
Semiconductors, Jan. 1992.
[7] “The I2C-Bus Specification,” Philips
Semiconductors,Version 2.0, Dec. 1998.