Aula 22 –> 8-1-01
Nesta aula foram
feitas revisões sobre o algoritmo do fluxo máximo – Ford Fulkerson e
continuamos a estudar o algoritmo Bebé - DES.
Índice
O objectivo do algoritmo Ford-Fulkerson é
obter o fluxo máximo de um grafo.
Os passos para obtermos o fluxo máximo de
um grafo são:
1.
Introduz-se
um fluxo arbitrário compatível (fluxo de cada arco não exceda a capacidade)
2.
Obtém-se um
fluxo completo (todos os caminhos contenham pelo menos um arco saturado)
3.
Obtém-se o
fluxo máximo
o
3.1.Marca-se
a fonte com sinal +
o
3.2.Um
vértice Xi estando marcado:
§
a) marcar
com + Xi todo vértice Xj não marcado tal que existe um arco (Xi,Xj) não
saturado
§
b) marcar
com - Xi todo vértice Xj não marcado tal que exista um arco (Xj, Xi) percorrido
por um fluxo não nulo
o
3.3. Se o
fluxo não for máximo, considera-se a seqüência de vértices marcados (+ ou -)
indo da fonte ao sumidouro; se um arco desta seqüência é orientado no sentido
da seqüência soma-se, em caso contrário subtrai-se uma unidade ao fluxo desse
arco;
o
3.4.Apaga-se
as marcas e retorna-se ao passo 3.1 até que não seja possível marcar o
sumidouro (passo 3.3)
Dada o seguinte grafo:
Depois de introduzirmos um fluxo arbitrário compatível (passo 1):
Obtêm-se um fluxo completo (todos os caminhos contenham pelo menos um arco
saturado) (passo 2):
Depois de marcarmos (passos 3.1 e 3.2)
A sequência de um caminho que pode ser optimizado (passos 3.3)
Depois da optimização do caminho anterior (passo 3.3):
O grafo depois de mais uma tentativa de marcação (passos 3.4, 3.1 e 3.2):
Como a anti-raiz não foi marcada, o fluxo nesta rede é maximo.
O fluxo máximo é:24.
O "Data Encryption Standard" é um
algoritmo simétrico, de blocos, que surgiu a partir de um outro algoritmo
LUCIFER, desenvolvido pela IBM. Foi adoptado, em 1976, como um
"standard" nos EUA sob o patrocínio do NBS (National Bureau of
Standards) e tem tido, desde então, uma grande utilização, inclusivamente em
empresas privadas. Apesar da sua divulgação generalizada em todo o mundo, a lei
dos EUA não permite a exportação de qualquer implementação do algoritmo.
Numa descrição simplificada, o algoritmo pode ser
visto como uma sequência de 16 passos, cada um composto por uma operação de
substituição e outra de transposição (ver fig. 1).
Fig. 1 - Esquema de funcionamento do DES
O DES manipula blocos de 64 bits e utiliza
uma chave de 56 bits (na realidade a chave é normalmente designada por um
número de 64 bits, mas em cada 8 bits um é usado apenas para verificação
paridade). O algoritmo de cifragem e de decifragem é o mesmo, excepto pela
sequência em que a chave é usada (K16 a K1, em vez de K1 a K16).
Num passo prévio, cada bloco T é transposto
usando uma permutação inicial IP, que produz T0 = IP(T). Depois de passar pelas 16
iterações, o bloco resultante T16 é
novamente transposto, com a permutação inicial inversa IP-1, para obter o bloco de saída Tc.
Se Ti denotar o
resultado da iteração i e Li e Ri designarem, respectivamente, a metade
esquerda e a metade direita desse bloco (Ti = LiRi, com Li = t1…t32 e Ri = t33…t64), então:
em que ‰ é o OU exclusivo e Ki designa chaves intermédias, de 48 bits,
obtidas a partir da chave original. A função f consiste em permutar e
expandir a metade direita dos blocos, de 32 para 48 bits, fazer um OU exclusivo
com a chave intermédia respectiva, fazer uma substituição para 32 bits e
finalmente uma outra permutação.
A distância
de unicidade do DES é facilmente calculável, usando a expressão (26). A
entropia da chave H(K) é 56 bits e, em inglês, com a razão de 1,2
bits/letra, temos que, num caracter ASCII (um "byte"), D = 6,8
bits/letra, ou seja, temos 6,8 bits redundantes. Onde a distância de unicidade
é:
· N
= H(K)/D = 56/6,8 = 8,2 letras
o que equivale
a dizer que, tipicamente, um bloco de criptograma (64 bits) é suficiente para
se determinar a chave.
Descrição mais pormenorizada do algoritmo DES
Descrevendo
a função f:
A função f
constitui a parte fundamental do algoritmo, consta em 16 iterações onde combina
operações de substituição, transposição e somas exclusivas.
A parte de
entrada da iteração i, é representada assim:
R(i-1) =
r1(i-1), r2(i-2), ... , r32(I-1)
Formado por
uma cadeia de 32 bits, constitui o 1º argumento da função f. O 2º argumento da
função é o k(i), é uma cadeia de bits de longitude 48 y representa a chave em
cada iteração. O resultado desta função é uma cadeia de 32 bits.
Os passos
necessários para realizar esta função são os seguintes:
1- O primeiro argumento r(i-1), expande-se em
48 bits mediante a tabela E de expansão de bits que está indicado na tabela 1,
onde permutam-se os 32 bits de r(i-1) e alguns y duplicam-se.
|
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 |
Tabela 1: Tabela de expansão de bits.
2 - Uma vez gerado E (r(i-1)), soma-se o modulo 2 com
k(i) y, representa o resultado como a concatenação de 8 cadeias de 6 bits:
S1
((b1b6),(b2b3b4b5))=S1(01,1110)=S1(1,14)=3=0100
Figura 2: Função de permutação S-Casos
onde 01 corresponde á fila 1 (começando
pela fila 0) y 1110 corresponde á coluna 14. Assim , no caso S1 o
resultado que obtemos é o valor 3, que em binário se representa com o valor
0100.
A permutação P, que se mostra na figura 3,
toma como entrada a concatenação da saída dos S-Casos, formando uma cadeia de
32 bits y obtendo como saída outra cadeia de 32 bits.
|
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 |
Figura 3: Função de permutação P
A cadeia de
saída obtida dos S-Casos será a soma do módulo posteriormente com o
vector L(i - l). Na figura 4 mostra-se o esquema do processo aplicado
pela funcão f.
Figura 4: Cálculo de f(R(i-1), K(i))
Todavia, a
segurança prática deste algoritmo não é tão baixa quanto a sua segurança
teórica (i.e. o valor da distância de unicidade). De facto, o tempo e a
quantidade de recursos necessários para quebrar esta cifra são muito elevados.
Numa abordagem de força bruta, com 1000 computadores pessoais trabalhando em
paralelo, cada um capaz de realizar 100.000 cifragens por segundo, são, ainda
assim, necessários quase 23 anos para pesquisar todo o espaço de chaves.
Há que ter
em atenção que estes valores são obtidos em máquinas de uso geral. Em 1993 foi
apresentada uma comunicação (na Crypto Conference realizada na Universidade da
Califórnia em Santa Barbara), por Michael Wiener, em que se descreve o projecto
de uma máquina, baseada num circuito integrado específico para quebrar o DES. A
máquina é capaz de realizar 50 milhões de cifragens por segundo e, a um custo
que Wiener estimou em 1.600$00 por integrado, será possível, investindo 15
milhões de contos numa máquina desse tipo, quebrar criptogramas DES em apenas 2
minutos! É muito dinheiro, mas há certamente várias instituições que estarão
dispostas a investi-lo para saber os segredos da concorrência, que podem
facilmente valer mais do que essa verba…
Por outro
lado, existem processos bem mais rápidos do que a força bruta. Na conferência
Crypto ‘94, M. Matsui apresentou uma técnica de quebra do DES, denominada
"criptanálise linear", que usando 243 criptogramas conhecidos, lhe permitiu
quebrar uma chave DES em 50 dias, usando uma estação de trabalho pessoal.