Detalhes

Categoria: Laboratório de Criptografia

Atualização: Terça, 16 Fevereiro 2010 18:37

Autor: Yugi

Acessos: 12633

A procura do criptógrafo por um sistema perfeito é sem dúvida uma das empreitadas mais difíceis que podemos imaginar. No começo a seguinte pergunta já nos atormenta: Será que existe realmente um criptossistema perfeito ou apenas não temos poder computacional suficiente para poder enfrentá-lo? Infelizmente não posso responder aos leitores deste artigo.

Introdução

Alguns criptoanalistas dizem que não há lógica alguma que o ser humano possa criar, que ele mesmo, com a aplicação e competência necessária, não possa elucidar. Esta pode ser uma verdade, contudo ainda não foi provada ou refutada.

Isto nos leva a refletir sobre o futuro da criptografia e da criptoanálise (na realidade falamos do futuro da Criptologia). Os sistemas especialistas que se baseiam nos conhecimentos da Inteligência Artificial e utilizam técnicas de busca de soluções - em profundidade (depth-first), em nível (breadth-first), através de técnicas heurísticas (Hill-climbing, least-cost) – com o objetivo de resolver o problema da explosão combinatória podem realmente criar "problemas" para os criptógrafos da nova geração. E a computação quântica que promete tornar os supercomputadores atuais em peças de um museu pré-histórico!

Vemos que hoje a criptoanálise evoluiu e geralmente as técnicas que são normalmente divulgadas (criptoanálise diferencial, linear, integral, etc...) representam apenas uma mínima parte do que realmente se conhece. É que a criptoanálise é a parte mais secreta da criptologia. Imagine que descobrimos uma técnica criptoanalítica eficiente contra o AES. É preferível, neste caso, fazer com que todos pensem que o AES é extremamente seguro e que não existe a mínima possibilidade de quebrá-lo, a não ser por força bruta. E realmente, ao contrário do que pensam os leigos, a quebra de criptossistemas importantes não é divulgada. Basta girar a roda da história pra trás e veremos que a máquina nazista Enigma (que já fora criptoanalisada com sucesso pelo matemático polonês Marian Rejewski, antes da Segunda Guerra Mundial) foi utilizada por vários países, principalmente as ex-colônias da Grã-Bretanha após o término da Guerra (os britânicos tinham capturado milhares de máquinas Enigma e as distribuíra para as ex-colônias que acreditavam que a cifra era inviolável!). Naturalmente, os britânicos decifraram rotineiramente as comunicações secretas destas ex-colônias durante anos. Somente em 1974 é que os britânicos revelaram que a Enigma havia sido decifrada (graças à insistência do capitão F. W. Winterbotham).

Exemplos como este podem nos assombrar. Será que o AES já foi quebrado e temos uma idéia ilusória de segurança? E a cifra RSA? Será que o problema da fatoração já pode ser solucionado? Quem nos responderá estas questões? Meu objetivo é fazer com que o leitor destas breves linhas possa pensar um pouco sobre isto.

Enquanto não chega a criptografia perfeita eu vos apresento mais um simples trabalho: O Criptossistema SHJ. Espero que gostem.

CRIPTOSSISTEMA SHJ

O cifrário SHJ é muito simples: todavia ele pode proteger informações em nível de segurança satisfatório. O criptossistema SHJ não é indicado para proteger informações extremamente sigilosas (militares ou governamentais), mas pode ser usado onde o AES é também utilizado.

Vamos ao descritivo do criptossistema SHJ.

1.0 Sobre as chaves do sistema

O cifrário SHJ trabalha com uma chave de 256 bits e cifra o texto claro em blocos de 64 bits. O algoritmo utiliza, numa estrutura de 20 voltas, 4 caixas de substituição não-lineares com entradas e saídas de 8 bits.

As operações utilizadas para cifrar os dados são simples: XOR, adição em módulo 2¹⁶ e rotação dependente de dados (rotação para a esquerda).

1.1 Sobre a divisão dos dados

O bloco claro é dividido em 4 words de 16 bits, normalmente rotuladas de A, B, C e D. As words interagem com a chave e entre si em cada uma das voltas do processo de cifragem.

O bloco cifrado é formado pela concatenação das words após a 20 volta de processamento do sistema.

A chave inicial de 256 bits gera 84 sub-chaves de 16 bits que são utilizadas nas 20 voltas do processamento.

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:

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.

2.0 Sobre o processo de cifragem

A cifragem do sistema SHJ é muito simples. A estrutura de cifragem tem 20 voltas e inicia com a adição de 4 palavras chaves nas words A, B, C e D que representam um bloco de texto claro com 64 bits. As palavras chaves são inseridas através de soma e XOR (N = 1, índice das sub-chaves e KEY é o vetor com 84 sub-chaves):

A = (A + KEY[N + 0]) MOD 65536
B = B XOR KEY[N + 1]
C = C XOR KEY[N + 2]
D = (D + KEY[N + 3]) MOD 65536

O próximo passo representa a estrutura de difusão do sistema SHJ. Neste passo procurou-se fazer com que a interação entre as 4 words que representam o bloco em processamento seja o mais confusa possível (sem complicar demais o código de cifragem!). Vejam:

X1 = A XOR B
X2 = (A + B) MOD 65536
X1 = X1 XOR ROT(X2,3)
X2 = (X1 * X2) MOD 65536
X1 = X1 XOR ROT(C,9)

C = C XOR X2
D = D XOR X1

O código acima altera as palavras C e D com X2 e X1. Este representa uma fusão entre A, B e C; aquele representa fusão entre A e B.

O próximo passo é a alteração da palavra B:

B = (B + ((CAIXA1[(C MOD 256) + 1] * 256) + (CAIXA2[(D DIV 256) + 1]))) MOD 65536

CAIXA1 e CAIXA2 são SBOX’s do sistema. MOD representa módulo e DIV representa a parte inteira de uma operação de divisão; * = multiplicação.

O próximo passo é a alteração da palavra A. A alteração processa-se como segue:

X = ROT(B,(C + D) MOD 16)
X = (CAIXA3[(X DIV 256) + 1] * 256) + CAIXA4[(X MOD 256) + 1]
A = A XOR X

Uma pequena observação deve ser feita em relação ao código acima. Ele é executado em 19 das 20 voltas da estrutura de cifragem. Na volta de número 13 a palavra A fica inalterada (esta rotina é desprezada na 13ª volta).

Para finalizar a estrutura de cifragem temos a inversão das palavras A e C; B e D. Veja:

TMP = A
A = C
C = TMP

TMP = B
B = D
D = TMP

A última instrução antes de começar a próxima volta é incrementar o índice de sub-chaves N. Neste caso N = N + 4. Depois voltamos ao início da estrutura de cifragem e começamos a 2ª volta. Faremos o mesmo para as voltas restantes até que se complete a 20ª volta.

Após a 20ª volta inserimos mais 4 sub-chaves nas words e terminamos a cifragem:

A = (A + KEY[N + 0]) MOD 65536
B = B XOR KEY[N + 1]
C = C XOR KEY[N + 2]
D = (D + KEY[N + 3]) MOD 65536

O bloco cifrado é a concatenação das words A, B, C e D.

2.1 Sobre o processo de decifragem

O processo de decifragem com o algoritmo SHJ é quase idêntico ao processo de cifragem. Ele pode ser condensado no pseudocódigo abaixo:

* Passo 1: Inverso do passo final:

A = (A - KEY[81] + 65536) MOD 65536
B = B XOR KEY[82]
C = C XOR KEY[83]
D = (D - KEY[84] + 65536) MOD 65536

N := 77		//	INDICE DE SUB-CHAVES

FOR CONT := 20 TO 1 STEP -1

    * DECIFRAGEM DA INVERSÃO:

    TMP = A
    A = C
    C = TMP

    TMP = B
    B = D
    D = TMP

    * Passo 2: DECIFRAGEM DA ESTRUTURA DE DIFUSÃO:

    X = ROT(B,(C + D) MOD 16)
    X = CAIXA3[(X DIV 256) + 1] * 256) + CAIXA4[(X MOD 256) + 1]
    A = A XOR X
    B = (B - ((CAIXA1[(C MOD 256) + 1] * 256) + (CAIXA2[(D DIV 256) + 1] )) + 65536) MOD 65536

    X1 = A XOR B
    X2 = (A + B) MOD 65536
    X1 = X1 XOR ROT(X2,3)
    X2 = (X1 * X2) MOD 65536


    C = C XOR X2
    X1 = X1 XOR ROT(C,9)
    D = D XOR X1

    * Passo 1: Inverso do passo inicial 


    A = (A - KEY[N + 0] + 65536) MOD 65536

    B = B XOR KEY[N + 1]
    C = C XOR KEY[N + 2]
    D = (D - KEY[N + 3] + 65536) MOD 65536

    N = N - 4
NEXT

3.0 Sobre as SBOX’S do cifrário SHJ

O criptossistema SHJ trabalha com 5 SBOX’s de 8 bits com 256 entradas e saídas cada uma. Estas são chamadas de CAIXA1, CAIXA2, CAIXA3, CAIXA4 e VETINC. As 4 primeiras são utilizadas na cifragem, decifragem e geração de sub-chaves. A última (VETINC) é usada somente na geração de sub-chaves do sistema.

Caixa 1

Caixa 2

Caixa 3

Caixa 4

Estas caixas de substituição são utilizadas na cifragem, decifragem e geração de sub-chaves do sistema.

A ordem de leitura da SBOX é a linha e depois a coluna. Logo, o primeiro elemento da CAIXA4 é 242, o 2º 82, o 16º 33, o 17º elemento é 78 e assim sucessivamente.

A próxima SBOX é VETINC que somente é usada na geração de sub-chaves do sistema. Vejam a seguir.

Caixa VETINC

4.0 Conclusão final

O Criptossistema SHJ é de uma estrutura muito simples; contudo apresenta algumas características criptográficas muito interessantes (a difusão, por exemplo). A chave tem um tamanho muito bom (256 bits) e é suficiente para garantir a segurança nos dias de hoje.

Espero que os leitores tenham gostado deste breviário criptográfico sobre o SHJ. Que estas informações lhes sejam úteis.

Download

Recado da vovó Vicki:

Juntamente com este texto de apresentação, o Yugi enviou um aplicativo que permite cifrar e decifrar arquivos usando o Cifrário SHJ. Você encontra o software para download aqui e na Seção de Downloads da Aldeia. Procure por Laboratórios da Aldeia | Laboratório de Criptografia.

Gostaria de aproveitar esta oportunidade para agradecer a colaboração e o empenho do Yugi, um dos colaboradores mais antigos da Aldeia Numaboa. É isso aí, Yugi! Obrigada por escolher a Aldeia para publicar seu trabalho.