Como o DES pode ter caixas S 6x4 e ainda ser reversível?

12

Os dados não seriam perdidos ao mapear valores de 6 bits para valores de 4 bits nas S-Boxes do DES? Se sim, como podemos revertê-lo para que a saída correta apareça?


fonte
3
Essa é provavelmente uma pergunta muito interessante, mas eu tentaria torná-la mais independente para que você possa obter uma resposta decente. Tente fornecer mais informações básicas.
Dave Clarke
2
Embora o Sadeq tenha uma resposta, ainda assim seria útil esclarecer a questão. Em primeiro lugar, o que é uma S-Box no DES?
Suresh Venkat
5
Uma cifra baseada em Feistel divide a entrada em duas cadeias de bits de comprimento igual e R (32 bits em DES) e aplica repetidamente a operação que Sadeq descreve abaixo (em DES, é repetida 16 vezes). Em DES, uma S -Box é uma função de 6 bits para 4 bits que é um componente da aplicação de M . As caixas S tinham algumas propriedades estatísticas interessantes, cujo objetivo permaneceu obscuro por quinze anos. Muitas pessoas suspeitavam que tornavam o DES mais fácil de quebrar. Eventualmente, foram descobertas essas propriedades das caixas S, tornando o DES resistente à criptoanálise diferencial. LRSFS
quer
3
@Suresh: as cifras clássicas são divididas em dois tipos: cifras de substituição (como César) e cifras de permutação (como transposição colunar). Mais tarde, tornou-se evidente que nenhum dos tipos fornecia segurança suficiente. As cifras de bloco modernas fazem uso de ambas as transformações. Em particular, eles têm caixas P (= caixas de Permutação) e caixas S (= caixas de Substituição).
MS Dousti 30/10/10
3
@ Suresh: Eu concordo absolutamente com você. Embora as S-Boxes sejam famosas pelos criptografadores, acredito que o OP deve fazer a pergunta de uma maneira que beneficie a todos, e não uma pequena parte da comunidade.
MS Dousti 30/10/10

Respostas:

25

DES é uma cifra baseada em Feistel . Em tais cifras, a função não precisa ser invertível. Aqui está o motivo:F

Em cada rodada, a seguinte operação é aplicada:

Para i=0,1,,n

Li+1=Ri

Ri+1=LiF(Ri,Ki)

A descriptografia é realizada da seguinte maneira:

Ri=Li+1

Li=Ri+1F(Li+1,Ki)

Como você pode ver, a descriptografia não precisa que seja invertível. (Como a descriptografia não precisa calcular F - 1 .)FF1

MS Dousti
fonte
4

Veja o capítulo 5 do livro "Introdução à criptografia moderna", de Katz e Lindell.

user686
fonte
1

Sem entrar em todo o mumbo-jumbo matemático sobre Feistel (que ainda não entendo 100%), se você olhar esta imagem da Wikipedia:

Etapa de criptografia DES

Você pode ver que, embora as 8 s-boxes estejam realmente comprimindo 48 bits para 32, apenas 32 bits de entropia são provenientes do texto simples ; portanto, você pode obter os outros 16 bits da chave ao descriptografar, que é a mágica executada por funções Feistel mencionadas anteriormente.

Sophistifunk
fonte