A Aldeia Numaboa ancestral ainda está disponível para visitação. É a versão mais antiga da Aldeia que eu não quis simplesmente descartar depois de mais de 10 milhões de pageviews. Como diz a Sirley, nossa cozinheira e filósofa de plantão: "Misericórdia, ai que dó!"

Se você tiver curiosidade, o endereço é numaboa.net.br.

Leia mais...

Laboratórios

O Cifrário SHJ

Seg

10

Abr

2006


20:37

(2 votos, média 5.00 de 5) 


1.2 Sobre o cálculo de sub-chaves

As sub-chaves do sistema são calculadas a partir da chave mestre que tem 256 bits. Inicialmente temos uma tabela de rotação com 32 elementos. Ela é denominada TABROT e é apresentada a seguir:

1° - 8° 02 04 15 13 12 06 14 00
9° - 16° 07 01 11 08 03 09 05 10
17° - 24° 07 01 04 11 02 08 05 13
25° - 32° 03 15 06 12 10 14 09 00

A tabela TABROT (a tabela TABROT é fixa!) é utilizada como um índice de rotação em uma rotina interna da geração de sub-chaves que veremos logo mais.

O parâmetro da entrada da função de geração de sub-chaves é uma chave de 256 bits. Ela pode ser dividida em um vetor de 32 elementos onde esses elementos obedecem à sentença 0 <= X <= 255, sendo X um elemento deste vetor. De fato cada elemento X indica uma entrada em uma SBOX (o sistema possui 4 SBOX’s, veja em anexos). Assim podemos formar mais 4 vetores de 32 elementos Y, onde Y representa a saída correspondente do elemento X na SBOX em uso. Veja abaixo (CHAVE = chave inicial de 256 bits, 32 bytes):

For ct := 1 to 32 step 1
C1[ct] = (C1[ct] + CAIXA1[CHAVE[ct] + 1]) MOD 256
C2[ct] = (C2[ct] + CAIXA2[CHAVE[ct] + 1]) MOD 256
C3[ct] = (C3[ct] + CAIXA3[CHAVE[ct] + 1]) MOD 256
C4[ct] = (C4[ct] + CAIXA4[CHAVE[ct] + 1]) MOD 256
Next

De acordo com este processo temos 4 vetores C1, C2, C3 e C4. Eles nada mais são do que a própria chave inicial que passou pelas SBOX's 1, 2, 3 e 4, respectivamente. Também são criadas duas variáveis V1 e V2 ambas com valor inicial zero. A variável SUBCHAVE é iniciada com o conteúdo da chave inicial de 256 bits.

Neste ponto temos o início da estrutura mestre de geração de sub-chaves, rotulado de estrutura Z1. No princípio desta estrutura os vetores C1, C2, C3 e C4 se alteram através de uma rotação de elementos (não confundir com rotação de bits!). As rotações são de 1, 3, 5 e 7 elementos em relação à C1, C2, C3 e C4, respectivamente. Isto significa que o primeiro elemento de C1 passa a ser o último e os outros são deslocados uma posição para cima; em C2 temos que o primeiro elemento é o 4° visto que os 3 primeiros foram deslocados para as últimas posições e assim sucessivamente. Veja:

C1 = Substr(C1,2) + Substr(C1,1,1)
C2 = Substr(C2,4) + Substr(C2,1,3)
C3 = Substr(C3,6) + Substr(C3,1,5)
C4 = Substr(C4,8) + Substr(C4,1,7)

Neste ponto abre-se uma nova estrutura rotulada de sub-estrutura Z1.1. Esta sub-estrutura é um laço de 32 voltas onde a mesma rotina é executada 32 vezes. Inicialmente vamos considerar a pseudovariável ct como o número da volta em questão. Assim temos que:

V1 = (V1 + ((C1[ct] * 256) + C3[ct])) MOD 65536
V2 = (V2 + ((C2[ct] * 256) + C4[ct])) MOD 65536
V1 = (ROT(V1,9) + (V1 XOR ROT(V2,TABROT[ct]))) MOD 65536

Nesta nomenclatura MOD representa módulo e ROT representa rotação para a esquerda; XOR é o ou-exclusivo bit a bit; * representa multiplicação.

Ao final da estrutura os nomes dos vetores C1, C2, C3 e C4 são alterados de acordo com o esquema:

TEMP = C1
C1 = C2
C2 = C3
C3 = C4
C4 = TEMP

A sub-estrutura acima (Z1.1) repete 32 vezes estes 2 trechos de pseudocódigo. A tabela TABROT faz com que V2 seja rotacionada a cada volta com um índice diferente. Ao final de cada volta os vetores são trocados: na primeira volta V1 interage com C1 e C3; na 2ª volta com C2 e C4, e assim sucessivamente.

Abre-se a nova estrutura Z2 (com 8 voltas) que mistura os 4 vetores C1, C2, C3 e C4. Primeiramente temos que os vetores C1, C2, C3 e C4 tem os seus elementos deslocados em 9, 11, 13 e 17 posições, respectivamente. Isto significa que C1 tem início com o seu 10º elemento, C2 com o seu 12º elemento, etc.

Em seguida invertem-se os últimos 16 elementos de C1 e C2. Os que pertenciam a este passam a pertencer àquele. O mesmo é feito com C3 e C4. Finalmente invertemos C1 e C3. O vetor C1 é agora C3 e este é C1.

O pseudocódigo a seguir explica este processo:

C1 = Substr(C1,10) + Substr(C1,1,09)
C2 = Substr(C2,12) + Substr(C2,1,11)
C3 = Substr(C3,14) + Substr(C3,1,13)
C4 = Substr(C4,18) + Substr(C4,1,17)

cx = c1
C1 = Substr(c1,1,16) + substr(c2,17)
C2 = Substr(c2,1,16) + substr(cx,17)

cx = c3
c3 = Substr(c3,1,16) + substr(c4,17)
C4 = Substr(c4,1,16) + substr(cx,17)

cx = c1
C1 = c3
C3 = cx

Em seguida os vetores C1, C2, C3 e C4 passam por 4 caixas de substituição do sistema rotuladas de CAIXA1, CAIXA2, CAIXA3 e CAIXA4. Cada elemento de cada vetor (C1, C2, C3 e C4) passa por uma destas SBOX’s.

Nas voltas de números 1, 2, 3 e 4 são utilizadas as SBOX’s de números 2, 3, 4 e 1; 3, 4, 1 e 2; 4, 1, 2 e 3; 1, 2, 3 e 4 respectivamente. Nas voltas de 5 a 8 repete-se esta mesma ordem de uso das SBOX’s. Veja:

i = 1
FOR CT := 1 TO 32 STEP 1
C1[CT] = CAIXAi[C1[CT] + 1]
C2[CT] = CAIXAi+1[C2[CT] + 1]
C3[CT] = CAIXAi+2[C3[CT] + 1]
C4[CT] = CAIXAi+3[C4[CT] + 1]
i = i + 1
NEXT

A nomenclatura CAIXAi representa uma das 4 caixas possíveis: para a volta 1 temos as caixas 2, 3, 4 e 5 para C1, C2, C3 e C4, respectivamente.

Finalizando a estrutura Z2 temos que Cx = C1. Cada elemento de C1 deve ser alterado por um XOR com o elemento correspondente de C2 em passagem pela SBOX VetInc. Cada elemento de C2 é alterado por XOR com o correspondente em C3 em passagem pela SBOX VetInc; cada elemento de C3 é alterado por XOR com o correspondente em C4 em passagem pela SBOX VetInc; Finalmente cada elemento de C4 é alterado por XOR seu o seu correspondente do vetor temporário Cx em passagem pela SBOX VetInc. Veja:

for ct := 1 to 32
Cx = C1
C1[ct] = C1[ct] XOR VETINC[C2[ct] + 1]
C2[ct] = C2[ct] XOR VETINC[C3[ct] + 1]
C3[ct] = C3[ct] XOR VETINC[C4[ct] + 1]
C4[ct] = C4[ct] XOR VETINC[Cx[ct] + 1]
Next

A função XOR é apenas uma simples operação de ou-exclusivo. VetInc é uma SBOX de 8 bits com 256 entradas. As entradas da SBOX VetInc são endereçadas de 1 até 256 e os elementos de C1, C2, C3 e C4 são endereçados de 0 até 255; isto explica o acréscimo da unidade no pseudocódigo acima que faz referência à SBOX VetInc. Fecha-se aqui a estrutura Z2.

Iniciamos a estrutura Z3 com 32 voltas onde cada elemento de C1, C2, C3 e C4 é alterado por uma operação de adição ou subtração com a SBOX VetInc (caixa de substituição de 8 bits). O parâmetro de endereçamento é representado pelas variáveis V1 e V2. Na realidade V1 e V2 são variáveis de 16 bits, logo é preciso dividi-las em 2 endereços de 8 bits para aplicar na SBOX VetInc. Existe ainda a variável Posic que controla a mudança cíclica dos vetores C1, C2, C3 e C4.

Veja a seguir todo o pseudocódigo desta rotina:

POSIC = 0
FOR CT := 1 TO 32 STEP 1
C1[CT] = (C1[CT] + VETINC[(V1 DIV 256) + 1]) MOD 256
C2[CT] = (C2[CT] - VETINC[(V1 MOD 256) + 1]) MOD 256
C3[CT] = (C3[CT] + VETINC[(V2 DIV 256) + 1]) MOD 256
C4[CT] = (C4[CT] - VETINC[(V2 MOD 256) + 1]) MOD 256

V1 = (ROT(V1,Tabrot[ct]) * VetInc[(V2 MOD 256) + 1]) MOD 65536
V2 = (V2 + (V1 XOR ROT(v2,tabrot[(V1 MOD 32) + 1]))) MOD 65536
V1 = (V1 - ROT(V2,Tabrot[(V1 MOD 32) + 1]) + 65536) MOD 65536
V2 = (ROT(V2,Tabrot[ct]) * VetInc[(V1 DIV 256) + 1]) MOD 65536

FOR XD := 0 TO POSIC
acl := c1
c1 := c2
c2 := c3
c3 := c4
c4 := acl
NEXT

POSIC = POSIC + 1
IF POSIC > 3
POSIC = 0
ENDIF
NEXT

O final da rotina é a geração da primeira sub-chave que é acrescida ao vetor SUBCHAVE. A sub-chave gerada é a própria variável V1. Neste ponto voltamos ao início da estrutura Z1 e repetimos todo o processo até que as 84 sub-chaves de 16 bits estejam geradas.

Todo o processo de geração de chaves pode ser resumido no se modelo:

  1. Criar as variáveis SUBCHAVE (com o conteúdo da chave inicial de 256 bits); criar também as variáveis V1 e V2 com valor zero.
  2. A partir da chave inicial criar 4 vetores de 32 elementos denominados C1, C2, C3, C4 que são realmente a própria chave inicial transformada pelas SBOX’s CAIXA1, CAIXA2, CAIXA3 e CAIXA4, respectivamente.
  3. Início da estrutura mestre de geração de sub-chaves. Rotação dos elementos dos vetores C1, C2, C3 e C4 em 1, 3, 5 e 7 bytes respectivamente.
  4. Início da sub-estrutura Z1.1. Alteração das variáveis V1 e V2. Ciclo de 32 voltas.
  5. Abre-se a sub-estrutura Z2 com 8 voltas. Iniciamos com rotação e inversão dos vetores C1, C2, C3 3 C4. Depois cada um destes vetores passa por uma SBOX’s que depende da variável POSIC. Posteriormente os vetores V1, V2, V3 e V4 interagem entre si e com a SBOX especial VETINC.
  6. Inicia-se a estrutura Z3 com 32 voltas. Interação geral entre V1, V2, C1, C2, C3, C4 e a SBOX VetInc.
  7. Acrescenta-se V1 ao Vetor SUBCHAVE.
  8. Verificar se já existem 84 sub-chaves de 16 bits. Em caso positivo terminar a rotina de geração de sub-chaves, caso contrário voltar ao passo 3.

É importante lembrar que o vetor SUBCHAVE já tem 16 sub-chaves antes da rotina de geração de sub-chaves ser executada. Estas sub-chaves são recolhidas da chave inicial de 256 bits.

Está finalizada a rotina de cálculo de sub-chaves do criptossistema SHJ. Resta explicar o processo de cifragem do texto claro e decifragem do criptograma.

Informações adicionais