cifra de Feistel

Autor: Leandro Alegsa Data de criação: 26 de janeiro de 2021

Na criptografia, uma cifra de Feistel é uma estrutura simétrica utilizada na construção de cifras de blocos, nomeada em homenagem ao criptógrafo alemão da IBM Horst Feistel; também é comumente conhecida como uma rede Feistel. Um grande conjunto de cifras de bloco utiliza o esquema, incluindo o padrão de criptografia de dados

A estrutura Feistel tem a vantagem de que as operações de encriptação e decriptação são muito semelhantes, mesmo idênticas em alguns casos, exigindo apenas uma inversão do cronograma de chaves. Portanto, o tamanho do código ou circuito necessário para implementar tal cifra é reduzido quase pela metade.

A construção Feistel é iterativa por natureza, o que facilita a implementação do criptosistema em hardware.

As redes Feistel e construções similares são cifras de produtos, e assim combinam múltiplas rodadas de operações repetidas, como por exemplo:

Bit-shuffling (muitas vezes chamadas caixas de permutação ou P-boxes)
Funções simples não lineares (muitas vezes chamadas de caixas de substituição ou S-boxes)
Mistura linear (no sentido de álgebra modular) usando XOR para produzir uma função com grandes quantidades do que Claude Shannon descreveu como "confusão e difusão".

O embaralhamento de bits cria o efeito de difusão, enquanto a substituição é usada para confusão.

Trabalho teórico

Muitas cifras modernas de blocos simétricos usam redes de Feistel, e a estrutura e propriedades das cifras de Feistel foram amplamente exploradas por criptografos. Especificamente, Michael Luby e Charles Rackoff analisaram a construção da cifra de bloco de Feistel, e provaram que se a função redonda é uma função pseudo-aleatória criptográfica segura, com _Ki usado como semente, então 3 redondas são suficientes para fazer da cifra de bloco uma permutação pseudo-aleatória, enquanto 4 redondas são suficientes para torná-la uma permutação pseudo-aleatória "forte" (o que significa que ela permanece pseudo-aleatória até mesmo para um adversário que obtém acesso oráculo a sua permutação inversa). Devido a este resultado muito importante de Luby e Rackoff, as cifras de Feistel são às vezes chamadas de cifras de bloco de Luby-Rackoff. Outros estudos teóricos generalizaram a construção, e definiram limites mais precisos para a segurança.

Construção

Que F ${\rm F}$ seja o estilo de jogo F seja a função redonda e que K 1 , K 2 , ... , K n estilo de jogo K_{1},K_2,ldots ,K_n $K_1,K_2,\ldots,K_{n}$ sejam as subchaves para as rodadas 1 , 2 , ... , n estilo de jogo 1,2,ldots ,n $1,2,\ldots,n$ respectivamente.

Então a operação básica é a seguinte:

Dividir o bloco de texto em duas partes iguais, ( L 1 {{\i1} L_1 , R 1 {\i1}displaystyle R_{\i}} R_1 )

Para cada rodada i = 1 , 2 , ... , n {\i1,2,}displaystyle i=1,2,{\i}dots ,n $i =1,2,\dots,n$ calcular (calcular)

L i + 1 = R i {\i+1}=R_{\i},} $L_{i+1} = R_i\,$

R i + 1 = L i ⊕ F ( R i , K i ) R_{\i+1}=L_{\i}}oplus {\rm {F}}(R_{i},K_{i})} $R_{i+1}= L_i \oplus {\rm F}(R_i, K_i)$ .

Então o texto cifrado é ( R n + 1 , L n + 1 ) $(R_{n+1}, L_{n+1})$ {\i1} {\i1}. (Geralmente as duas peças R n {\i1}, R_{n+1} R_n e L n {\i1} L_n não são trocadas após a última rodada).

A descodificação de um texto cifrado ( R n , L n ) {\i1} (R_n, L_n) é realizada através da computação para i = n , n - 1 , ... , 1 {\i1}displaystyle i=n,n-1,{\i}ldots ,1 $i=n,n-1,\ldots,1$

R i = L i + 1 R_{\i}=L_{i+1},} $R_{i} = L_{i+1}\,$

L i = R i + 1 ⊕ F ( L i + 1 , K i ) {\i} {\i}=R_{\i+1}oplus {\i}(L_{\i+1},K_{i})} $L_{i} = R_{i+1} \oplus {\rm F}(L_{i+1}, K_{i})$ .

Então ( L 1 , R 1 ) {\i1} é novamente o texto em quadratura (L_{1},R_{1})} (L_1,R_1) .

Uma vantagem deste modelo é que a função redonda F {\i} ${\rm F}$ não tem que ser invertível, e pode ser muito complexa.

O diagrama ilustra o processo de criptografia. A decriptação requer apenas a inversão da ordem da sub-chave K n , K n - 1 , ... , K 1 {\displaystyle K_{n},K_{n-1},{\ldots ,K_{1}} $K_{n},K_{n-1},\ldots,K_1$ usando o mesmo processo; esta é a única diferença entre criptografia e decriptação:

As cifras Feistel desequilibradas usam uma estrutura modificada onde L 1 {\i1} L_1 e R 1 {\i1} R_1 não são de comprimento igual. A cifra MacGuffin é um exemplo experimental de tal cifra.

A construção Feistel também é utilizada em algoritmos criptográficos que não sejam cifras de bloco. Por exemplo, o esquema Optimal Asymmetric Encryption Padding (OAEP) usa uma rede Feistel simples para randomizar os textos criptográficos em certos esquemas de criptografia de chaves assimétricas.

Operação da rede Feistel em cifra de bloco, onde P é o texto plaquetário e C é o texto cifrado

Lista de cifras de Feistel

Feistel ou Feistel modificado: Blowfish, Camellia, CAST-128, DES, FEAL, ICE, KASUMI, LOKI97, Lucifer, MARS, MAGENTA, MISTY1, RC5, TEA, Triple DES, Twofish, XTEA, GOST 28147-89

Feistel generalizado: CAST-256, MacGuffin, RC2, RC6, Skipjack

Perguntas e Respostas

P: O que é uma cifra de Feistel?

R: Uma cifra Feistel é uma estrutura simétrica usada na construção de cifras de blocos, com o nome do criptógrafo alemão da IBM Horst Feistel. É também comumente conhecida como uma rede Feistel.

P: Quais são algumas vantagens do uso de uma estrutura Feistel?

R: A principal vantagem de usar uma estrutura Feistel é que as operações de encriptação e decriptação são muito semelhantes, mesmo idênticas em alguns casos, exigindo apenas uma inversão do horário das chaves. Isso reduz pela metade o tamanho do código ou circuito necessário para implementar uma cifra desse tipo. Além disso, sua natureza iterativa facilita a implementação do sistema de criptografia em hardware.

P: Como Claude Shannon descreve "confusão e difusão"?

R: Claude Shannon descreveu "confusão e difusão" como tendo grandes quantidades dos dois elementos presentes, a fim de tornar difícil para um atacante decifrar uma mensagem criptografada.

P: Que técnicas são usadas para criar confusão e difusão?

R: Confusão e difusão são criadas através de embaralhamento de bits (muitas vezes chamadas caixas de permutação ou P-boxes) e funções simples não lineares (muitas vezes chamadas caixas de substituição ou S-boxes), bem como mistura linear (no sentido de álgebra modular) usando XOR. O embaralhamento de bits cria o efeito de difusão, enquanto a substituição é usada para confusão.

P: Que tipo de cifra é uma rede Feistel?

R: Uma rede Feistel é um tipo de cifra de produto que combina múltiplas rodadas de operações repetidas, a fim de criptografar os dados com segurança.

P: Quem desenvolveu esse tipo de criptografia?

R: A estrutura Feistel foi desenvolvida pelo criptógrafo alemão Horst Feistel, da IBM.

P: O padrão de criptografia de dados é baseado nesse tipo de criptografia?

R: Sim, o Data Encryption Standard usa esse tipo de criptografia que usa os mesmos princípios delineados acima para criar confusão e difusão dentro de uma mensagem criptografada.