Rede de substituição-permutação - Substitution–permutation network

Um esboço de uma rede de substituição-permutação com 3 rodadas, criptografando um bloco de texto simples de 16 bits em um bloco de texto cifrado de 16 bits. As caixas S são as S i 's, as caixas P são as mesmas P e as chaves redondas são as K i ' s.

Na criptografia , uma rede SP , ou rede de substituição-permutação ( SPN ), é uma série de operações matemáticas vinculadas usadas em algoritmos de cifra de bloco , como AES (Rijndael) , 3-Way , Kalyna , Kuznyechik , PRESENT , SAFER , SHARK , e quadrado .

Tal rede pega um bloco de texto simples e a chave como entradas e aplica várias "rodadas" ou "camadas" alternadas de caixas de substituição (caixas S) e caixas de permutação (caixas P) para produzir o bloco de texto cifrado . As caixas S e P-caixas transformam (sub) blocos de bits de entrada em bits de saída. É comum que essas transformações sejam operações eficientes de serem executadas em hardware, como ou exclusivo (XOR) e rotação bit a bit . A chave é introduzida em cada rodada, geralmente na forma de "chaves redondas" derivadas dela. (Em alguns projetos, as próprias caixas S dependem da chave.)

A descriptografia é feita simplesmente invertendo o processo (usando os inversos das S-box e P-box e aplicando as teclas redondas na ordem inversa).

Componentes

Uma S-box substitui um pequeno bloco de bits (a entrada da S-box) por outro bloco de bits (a saída da S-box). Essa substituição deve ser um para um , para garantir a invertibilidade (portanto, a descriptografia). Em particular, o comprimento da saída deve ser igual ao comprimento da entrada (a imagem à direita tem S-boxes com 4 bits de entrada e 4 bits de saída), que é diferente das S-boxes em geral, que também podem mudar o comprimento, como no DES (Data Encryption Standard) , por exemplo. Um S-box geralmente não é simplesmente uma permutação dos bits. Em vez disso, um bom S-box terá a propriedade de que alterar um bit de entrada alterará cerca de metade dos bits de saída (ou um efeito de avalanche ). Ele também terá a propriedade de que cada bit de saída dependerá de cada bit de entrada.

Uma caixa P é uma permutação de todos os bits: ela pega as saídas de todas as caixas S de uma rodada, permuta os bits e os alimenta nas caixas S da próxima rodada. Uma boa P-box tem a propriedade de que os bits de saída de qualquer S-box sejam distribuídos para tantas entradas S-box quanto possível.

Em cada rodada, a chave redonda (obtida da chave com algumas operações simples, por exemplo, usando S-box e P-box) é combinada usando alguma operação de grupo, tipicamente XOR .

Propriedades

Um único S-box típico ou um único P-box sozinho não tem muita força criptográfica: um S-box pode ser pensado como uma cifra de substituição , enquanto um P-box pode ser pensado como uma cifra de transposição . No entanto, uma rede SP bem projetada com várias rodadas alternadas de caixas S e P já satisfaz as propriedades de difusão e confusão de Shannon :

  • A razão para a difusão é a seguinte: se alguém muda um bit do texto simples, então ele é alimentado em uma S-box, cuja saída irá mudar em vários bits, então todas essas mudanças são distribuídas pela P-box entre vários S- caixas, portanto, as saídas de todas essas caixas S são novamente alteradas em vários bits e assim por diante. Fazendo várias rodadas, cada bit muda várias vezes para frente e para trás, portanto, ao final, o texto cifrado mudou completamente, de forma pseudo - aleatória . Em particular, para um bloco de entrada escolhido aleatoriamente, se alguém inverter o i- ésimo bit, então a probabilidade de que o j- ésimo bit de saída mude é aproximadamente a metade, para qualquer i e j , que é o Critério de Avalanche Estrito . Vice-versa, se alguém alterar um bit do texto cifrado e depois tentar decifrá-lo, o resultado será uma mensagem completamente diferente do texto simples original - as cifras SP não são facilmente maleáveis .
  • O motivo da confusão é exatamente o mesmo que para a difusão: mudar um bit da chave muda várias das chaves redondas, e cada mudança em cada chave redonda se difunde por todos os bits, mudando o texto cifrado de uma maneira muito complexa.
  • Mesmo que um invasor obtenha de alguma forma um texto simples correspondente a um texto cifrado - um ataque de texto simples conhecido , ou pior, um texto simples escolhido ou ataque de texto cifrado escolhido - a confusão e a difusão tornam difícil para o invasor recuperar a chave.

Desempenho

Embora uma rede Feistel que usa S-boxes (como DES ) seja bastante semelhante às redes SP, existem algumas diferenças que tornam isso ou aquilo mais aplicável em certas situações. Para uma certa confusão e difusão , uma rede SP tem mais "paralelismo inerente" e então - dada uma CPU com muitas unidades de execução - pode ser calculada mais rápido do que uma rede Feistel. CPUs com poucas unidades de execução - como a maioria dos cartões inteligentes - não podem tirar vantagem desse paralelismo inerente. Além disso, as cifras SP exigem que as S-boxes sejam invertíveis (para realizar a descriptografia); As funções internas do Feistel não têm essa restrição e podem ser construídas como funções unilaterais .

Veja também

Referências

Leitura adicional

  • Katz, Jonathan; Lindell, Yehuda (2007). Introdução à Criptografia Moderna . CRC Press. ISBN   9781584885511 .
  • Stinson, Douglas R. (2006). Criptografia. Teoria e prática (terceira edição). Chapman & Hall / CRC. ISBN   1584885084 .