Cifra Feistel - Feistel cipher

Em criptografia , uma cifra de Feistel (também conhecido como bloco cifra Luby-Rackoff ) é uma estrutura simétrica usada na construção de cifras de bloco , em homenagem ao alemão -born físico e criptógrafo Horst Feistel que fez pesquisas pioneiras enquanto trabalhava para a IBM (EUA) ; também é comumente conhecido como rede Feistel . Uma grande proporção das cifras de bloco usa o esquema, incluindo o US Data Encryption Standard , o GOST soviético / russo e as cifras Blowfish e Twofish mais recentes . Em uma cifra Feistel, a criptografia e a descriptografia são operações muito semelhantes e ambas consistem na execução iterativa de uma função chamada "função circular" um número fixo de vezes.

História

Muitas cifras de bloco simétricas modernas são baseadas em redes Feistel. As redes Feistel foram vistas comercialmente pela primeira vez na cifra Lucifer da IBM , projetada por Horst Feistel e Don Coppersmith em 1973. As redes Feistel ganharam respeitabilidade quando o governo federal dos Estados Unidos adotou o DES (uma cifra baseada em Lúcifer, com alterações feitas pela NSA ) em 1976. Como outros componentes do DES, a natureza iterativa da construção Feistel torna a implementação do criptossistema no hardware mais fácil (particularmente no hardware disponível no momento do design do DES).

Projeto

Uma rede Feistel usa uma função redonda , uma função que recebe duas entradas, um bloco de dados e uma subchave, e retorna uma saída do mesmo tamanho que o bloco de dados. Em cada rodada, a função de rodada é executada em metade dos dados a serem criptografados e sua saída é XORed com a outra metade dos dados. Isso é repetido um número fixo de vezes e a saída final são os dados criptografados. Uma vantagem importante das redes Feistel em comparação com outros designs de criptografia, como redes de substituição-permutação, é que toda a operação pode ser invertida (ou seja, os dados criptografados podem ser descriptografados), mesmo se a função de arredondamento não for invertível. A função de arredondamento pode ser arbitrariamente complicada, uma vez que não precisa ser projetada para ser invertida. Além disso, as operações de criptografia e descriptografia são muito semelhantes, até idênticas em alguns casos, exigindo apenas uma reversão da programação da chave . Portanto, o tamanho do código ou circuito necessário para implementar tal cifra é quase reduzido pela metade.

Trabalho teórico

A estrutura e as propriedades das cifras Feistel foram extensivamente analisadas por criptógrafos .

Michael Luby e Charles Rackoff analisaram a construção da cifra Feistel e provaram que se a função de rodada for uma função pseudo-aleatória criptograficamente segura , com K _i usado como semente, então 3 rodadas são suficientes para tornar a cifra de bloco uma permutação pseudo - aleatória , enquanto 4 rodadas são suficientes para torná-la uma permutação pseudo-aleatória "forte" (o que significa que ela permanece pseudo-aleatória mesmo para um adversário que obtém acesso oráculo à sua permutação inversa). Por causa desse resultado muito importante de Luby e Rackoff, as cifras de Feistel são às vezes chamadas de cifras de bloco Luby – Rackoff.

O trabalho teórico posterior generalizou um pouco a construção e deu limites mais precisos para a segurança.

Detalhes de construção

Let ser a função round e deixe ser as sub-chaves para os rounds respectivamente. ${\ displaystyle {\ rm {F}}}$ ${\ displaystyle K_ {0}, K_ {1}, \ ldots, K_ {n}}$ ${\ displaystyle 0,1, \ ldots, n}$

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

Divida o bloco de texto simples em duas partes iguais, ( , ) ${\ displaystyle L_ {0}}$ ${\ displaystyle R_ {0}}$

Para cada rodada , calcule ${\ displaystyle i = 0,1, \ dots, n}$

{\ displaystyle L_ {i + 1} = R_ {i} \,}

{\ displaystyle R_ {i + 1} = L_ {i} \ oplus {\ rm {F}} (R_ {i}, K_ {i}).}

Onde significa XOR . Então o texto cifrado é . ${\ displaystyle \ oplus}$ ${\ displaystyle (R_ {n + 1}, L_ {n + 1})}$

A descriptografia de um texto cifrado é realizada por computação para ${\ displaystyle (R_ {n + 1}, L_ {n + 1})}$ ${\ displaystyle i = n, n-1, \ ldots, 0}$

{\ displaystyle R_ {i} = L_ {i + 1} \,}

{\ displaystyle L_ {i} = R_ {i + 1} \ oplus \ operatorname {F} (L_ {i + 1}, K_ {i}).}

Então é o texto simples novamente. ${\ displaystyle (L_ {0}, R_ {0})}$

O diagrama ilustra a criptografia e a descriptografia. Observe a reversão da ordem da subchave para descriptografia; esta é a única diferença entre criptografia e descriptografia.

Cifra de Feistel não balanceada

As cifras de Feistel não balanceadas usam uma estrutura modificada onde e não são de comprimentos iguais. A cifra Skipjack é um exemplo dessa cifra. O transponder de assinatura digital da Texas Instruments usa uma cifra Feistel proprietária não balanceada para realizar autenticação de desafio-resposta . ${\ displaystyle L_ {0}}$ ${\ displaystyle R_ {0}}$

O Thorp shuffle é um caso extremo de cifra Feistel desequilibrada em que um lado é um único bit. Isso tem melhor segurança comprovável do que uma cifra Feistel balanceada, mas requer mais rodadas.

Outros usos

A construção Feistel também é usada em algoritmos criptográficos diferentes de cifras de bloco. Por exemplo, o esquema ideal de preenchimento de criptografia assimétrica (OAEP) usa uma rede Feistel simples para randomizar textos criptografados em certos esquemas de criptografia de chave assimétrica .

Um algoritmo Feistel generalizado pode ser usado para criar permutações fortes em pequenos domínios de tamanho, não uma potência de dois (consulte criptografia com preservação de formato ).

Redes Feistel como um componente de design

Quer a cifra inteira seja uma cifra Feistel ou não, as redes do tipo Feistel podem ser usadas como um componente do design de uma cifra. Por exemplo, MISTY1 é uma cifra Feistel que usa uma rede Feistel de três rodadas em sua função redonda, Skipjack é uma cifra Feistel modificada que usa uma rede Feistel em sua permutação G e Threefish (parte de Skein ) é uma cifra de bloco não Feistel que usa uma função MIX do tipo Feistel.

Lista de cifras Feistel

Feistel ou Feistel modificado:

Feistel generalizado:

Veja também

Criptografia
Cifra de fluxo
Rede de substituição-permutação
O esquema de levantamento para a transformação wavelet discreta tem praticamente a mesma estrutura
Criptografia com preservação de formato
Esquema Lai-Massey

Languages

In other projects