3 DES
O Data Encryption Standard (DES) é um algoritmo de criptografia simétrica de bloco com chave de 56-bits baseado na cifra de Feistel desenvolvido pela IBM e adotado pela NSA como protocolo de criptografia padrão dos EUA na década de 70.
O DES foi deprecado e substituído pelo 4 AES (AES) no começo da década de 2000, quando sua criptanálise se tornou comercialmente viável.
História
O DES foi desenvolvido a partir da cifra Lucifer pela IBM e foi publicado em 1975, e foi logo padronizado pela NSA e adotado pelo NIST (National Institute of Standards and Technology) como criptografia padrão para informação não-classificada.
O tamanho de chave original pretendido pela IBM foi de 64 bits, mas a NSA decidiu por reduzir o tamanho para 56 bits, tornando cada bit final de um byte da chave em um bit de paridade. Isso consequentemente fez com que a criptografia DES fosse quebrável pelo governo dos EUA com a tecnologia da época. Além disso, o governo dos EUA exigia que o DES fosse usado com chaves de
Criptografia
Apresentação
O DES pode ser separado em algumas partes:
Geração das subchaves: a chave de 56 bits é expandida e permutada em duas metades de 48 bits e uma mistura de permutações de left shifts é realizado para gerar 16 sub-chaves.
Inicialização: o bloco de texto legível é permutado e separado em duas metades.
Rounds: os próximos passos são realizados 16 vezes, uma com cada sub-chave:
- Função \(f\): o bloco direito é expandido, permutado e combinado com a sub-chave correspondente. Então, cada palavra de 6 bits sofre uma transformação não-linear e não-inversível chamada S-Box, sendo substituída por uma outra palavra de 4 bits. O resultado é permutado.
- Combinação: o resultado da função \(f\) é combinado (XOR) com o bloco esquerdo, tornando-se o novo bloco direito. O bloco direito antigo se torna o novo bloco esquerdo sem alterações.
Finalização: os blocos direito e esquerdo são trocados e então sofrem a permutação inversa da inicial.
Geração das subchaves
A chave inserida de 56 bits (com bits de paridade desprezados) é expandida e permutada em duas metades de 48 bits através de uma permutação denominada PC-1 (Permutation Choice 1). Após isso, o resultado da permutação é separado em duas metades de 24 bits
Cada uma é submetida a um número de left shifts determinado pelo número da iteração e então combinada, contraída e permutada com uma permutação denominada PC-2 (Permutation Choice 2), que resulta numa sub-chave. Por conta da contração, PC-2 é uma função não-linear.
Esse processo é feito 16 vezes, resultando em 16 subchaves.
Inicialização
O bloco de texto legível inicial é permutado de acordo com uma permutação IP (Initial Permutation) e então separado em dois blocos. Esta permutação não tem valor criptográfico e é desfeita no fim do algoritmo. Ela existe por questões de compatibilidade legacy, pois facilitava a implementação do algoritmo em circuitos integrados.
Rounds
Os dois blocos de texto (esquerdo e direito) são submetidos a 16 rounds de transformações, um para cada sub-chave. Os rounds do DES formam um exemplo clássico de uma cifra de Feistel.
Função \(f\)
A função \(f\) é onde se encontra o maior valor criptográfico do algoritmo, ou seja, é a parte onde se encontra toda a inteligência.
O bloco direito de 32 bits é primeiramente permutado e expandido pela transformação E, se tornando um bloco de 48 bits, que é por sua vez combinado (XOR) com a sub-chave correspondente à iteração, de mesmo tamanho. Então, cada uma das 8 palavras de 6 bits são substituidas pelas S-Boxes.
S-Boxes
Uma S-Box (Substitution Box) é uma tabela de substituição de palavras binárias. No DES, são utilizadas 8 S-Boxes, denominadas S1 a S8, cada uma com 4 fileiras e 16 colunas. Cada entrada é uma palavra de 4 bits.
Para o processo de substituição, primeiramente o bloco de 48 bits é separado em 8 palavras de 6 bits. Os dois bits externos de cada palavra são juntados para formar um valor binário entre 0 e 4; esse é o índice das fileiras da saída da S-Box. Os quatro bits internos restantes são juntados para formar um valor binário entre 0 e 15; esse é o índice das colunas da saída da S-Box.
As S-Boxes do DES formam uma função booleana não-linear1 e não-inversível, e é onde se encontra a maior parte da inteligência do DES. Estas tabelas foram ajustadas para que seu resultado fosse o mais homogêneo possível, enquanto evita ataques de criptanálise diferencial. Um exemplo da homogeneidade das S-Boxes é a distribuição de números pares em cada lado das tabelas.
Após a passagem pelas S-Boxes, as palavras são concatenadas, formando um bloco de 32 bits, e passam pela permutação P.
Combinação e troca de lados
Após a aplicação da função \(f\) ao lado direito, a saída da função é combinada (XOR) com o bloco esquerdo, dando origem ao novo bloco direito. O bloco direito original de antes da função \(f\) se torna o novo lado esquerdo.
Troca de lados e permutação final
Após os 16 rounds de transformações, os dois blocos são trocados de lado e passam por uma última permutação, a inversa da IP. Essa última permutação da origem ao bloco de texto ilegível final.
Decriptografia
Para decriptografar um criptotexto do DES, basta passar o criptotexto pelo DES novamente, usando a mesma chave. A única diferença é que as sub-chaves devem ser utilizadas em ordem reversa.
Assim, temos: - \(IP\) desfaz \(IP^{-1}\); - Cada round desfaz um round da seguinte maneira: Suponha que, durante a criptografia, os blocos \(E_i\) e \(D_i\) foram inseridos no round. Dessa maneira, temos \[ \begin{gather} D_{i+1} = E_i \oplus f_{K_i}(D_i) \\ E_{i+1} = D_i \end{gather} \] Agora, para decriptografar, recebemos os blocos \(E_{i+1}\) e \(D_{i+1}\). Então, fazemos \[ \begin{gather} \underbrace{ D_{i+1} }_{ = E_i \oplus f(D_i) } \oplus f_{K_i}(\underbrace{ E_{i+1} }_{ = D_i }) = E_i \oplus f_{K_i}(D_i) \oplus f_{K_i}(D_i) = E_i \\ E_{i+1} = D_i \end{gather} \] Afinal, \(A \oplus A = 0\) e \(B \oplus 0 = B\), para quaisquer strings binárias \(A\) e \(B\). - A troca de lados desfaz a troca de lados final. - \(IP^{-1}\) defaz \(IP\).
Código
Implementação em Python do DES:
'''
Luã Jaz
15/03/2025
Implementação do algoritmo básico do DES.
'''
# PERMUTAÇÕES
PC1_l = [56, 48, 40, 32, 24, 16, 8, 0, 57, 49, 41, 33, 25, 17, 9, 1, 58, 50, 42, 34, 26, 18, 10, 2, 59, 51, 43, 35]
PC1_r = [62, 54, 46, 38, 30, 22, 14, 6, 61, 53, 45, 37, 29, 21, 13, 5, 60, 52, 44, 36, 28, 20, 12, 4, 27, 19, 11, 3]
PC2 = [13, 16, 10, 23, 0, 4, 2, 27, 14, 5, 20, 9, 22, 18, 11, 3, 25, 7, 15, 6, 26, 19, 12, 1, 40, 51, 30, 36, 46, 54, 29, 39, 50, 44, 32, 47, 43, 48, 38, 55, 33, 52, 45, 41, 49, 35, 28, 31]
IP = [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, 56, 48, 40, 32, 24, 16, 8, 0, 58, 50, 42, 34, 26, 18, 10, 2, 60, 52, 44, 36, 28, 20, 12, 4, 62, 54, 46, 38, 30, 22, 14, 6]
IP_inv = [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, 32, 0, 40, 8, 48, 16, 56, 24]
E = [31, 0, 1, 2, 3, 4, 3, 4, 5, 6, 7, 8, 7, 8, 9, 10, 11, 12, 11, 12, 13, 14, 15, 16, 15, 16, 17, 18, 19, 20, 19, 20, 21, 22, 23, 24, 23, 24, 25, 26, 27, 28, 27, 28, 29, 30, 31, 0]
P = [15, 6, 19, 20, 28, 11, 27, 16, 0, 14, 22, 25, 4, 17, 30, 9, 1, 7, 23, 13, 31, 26, 2, 8, 18, 12, 29, 5, 21, 10, 3, 24]
# S-BOXES
S1 = [ [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] ]
S2 = [ [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] ]
S3 = [ [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] ]
S4 = [ [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] ]
S5 = [ [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] ]
S6 = [ [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] ]
S7 = [ [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] ]
S8 = [ [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, 11] ]
S_BOXES = [S1, S2, S3, S4, S5, S6, S7, S8]
# RELAÇÃO ROUND - LEFT SHIFT
LEFT_SHIFTS = [1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1]
# FUNÇÕES
def perm(input, key):
'''
str, array -> str
Recebe uma string binária e um array de permutação e retorna
a permutação em questão, ou seja, retorna uma string de tamanho
igual ao do array que contém em cada posição o bit indicado pela
mesma posição do array.
'''
output = ''
for i in key:
output += input[i]
return output
def left_shift(input, n):
'''
str, int -> str
Recebe uma string e um int n e retorna a string binária com
n left shifts realizados. I.e., left_shift('abcde', 1) = 'bcdea',
left_shift('abcde', 2) = 'cdeab', etc.
'''
output = input[n:] + input[:n]
return output
def xor(a, b):
'''
str, str -> str
Recebe duas strings binárias e retorna o xor entre elas.
'''
output = ''
for i in range(len(a)):
if a[i] == b[i]:
output += '0'
else:
output += '1'
return output
def add_parity_bits(key):
'''
str -> str
Recebe uma string de 56 bits chave e retorna uma string de 64 bits com
bits de paridade inseridos para cada byte. Ou seja, se os primeiros 7 bits
da chave são 0110100, como há 3 bits valendo 1, um número impar, o bit de
paridade é 1 (seria 0 se fosse par), e o primeiro byte da saída será 01101001.
O mesmo é feito para todos os outros conjuntos de 7 bits.
'''
output = ''
for i in range(8):
sub_string = key[7*i : 7*(i+1)]
sum = 0
for i in sub_string:
sum += int(i)
sub_string += str(sum % 2)
output += sub_string
return output
def subkey_gen(key):
'''
str -> array(str)
Recebe uma string binária de 64 bits e retorna um array com
as 16 subchaves de 48 bits especificadas no algoritmo do DES.
'''
subkeys = []
# PC1
b_l = perm(key, PC1_l)
b_r = perm(key, PC1_r)
# rounds
for i in range(16):
b_l = left_shift(b_l, LEFT_SHIFTS[i])
b_r = left_shift(b_r, LEFT_SHIFTS[i])
subkeys.append(perm(b_l + b_r, PC2))
return subkeys
def f_func(block, subkey):
'''
str, str -> str
Recebe uma string binária de 32 bits bock e uma string binária de
48 bits subkey e retorna a função f do algoritmo DES aplicada sobre
block usando a key como chave.
'''
block = perm(block, E)
block = xor(block, subkey)
# S-BOXES
output = ''
for i in range(8):
sub_string = block[6*i: 6*(i+1)]
row = 2*int(sub_string[0]) + int(sub_string[5])
col = 8*int(sub_string[1]) + 4*int(sub_string[2]) + 2* int(sub_string[3]) + int(sub_string[4])
output += bin(S_BOXES[i][row][col])[2:].rjust(4, '0')
return perm(output, P)
def DES(block, key, mode=0):
'''
str, str, int -> str
Recebe duas string binárias, block (64-bit) e key (56-bit), e retorna a string
block encriptografada com o algoritmo DES usando a chave key.
Para encriptar, usamos mode=0, para decriptar usamos mode=1.
'''
# bits de paridade da chave
key = add_parity_bits(key)
# gerar subchaves
subkeys = subkey_gen(key)
# início do algoritmo
block = perm(block, IP)
b_l = block[:32]
b_r = block[32:]
# inverter chaves caso decriptar
if mode == 1:
subkeys = subkeys[::-1]
# iteração
for i in range(16):
f_r = f_func(b_r, subkeys[i])
buffer = b_r
b_r = xor(b_l, f_r)
b_l = buffer
b_l, b_r = b_r, b_l
return perm(b_l + b_r, IP_inv)Triple DES
O algoritmo do DES pode ser aplicado multiplas vezes para aumentar sua segurança. Os procedimentos mais comuns nesse caso são o Triple DES de 2 chaves (2TDES) e o Triple DES de 3 chaves (3TDES)
Triple DES de 2 chaves
No Triple DES de 2 chaves (2TDES), duas chaves distintas e independentes são escolhidas. Então, o bloco de dados é passado pelo DES com a primeira chave, então pelo DES inverso (modo decriptografar) com a segunda chave, e finalmente pelo DES com a primeira chave novamente.
Triple DES de 3 chaves
No Triple DES de 3 chaves (3TDES), três chaves distintas e independentes são escolhidas. Então, o bloco de dados é passado pelo DES com a primeira chave, então pelo DES inverso (modo decriptografar) com a segunda chave, e finalmente pelo DES com a terceira chave.
Aproximadamente metade das entradas das S-Boxes formam funções booleanas não-lineares.↩︎