Como sabe, o processador não fornece matemática para números longos. Atualmente, os processadores trabalham com números de 64 bits. Em C, este corresponde ao tipo long long. Na criptografia, é necessário trabalhar com números de comprimento muito maior. Existem duas formas de resolver este problema: utilizar bibliotecas existentes de terceiros ou escrever tudo sozinho. Os Sistemas Extra neste produto (como costumamos fazer) escolheram a segunda opção. O sistema de encriptação Extra Systems Cypher Net apenas executa código escrito por nós.
Para processar números longos, o Extra Systems Cypher Net utiliza matrizes de caracteres não assinados de tamanho tal que podem acomodar números do tamanho necessário. Existem dois formatos de armazenamento: normal e embalado. O formato comprimido utiliza todos os bits, enquanto o formato normal utiliza apenas metade. Assim, no formato normal, cada byte contém um dígito hexadecimal – quatro bits. O comprimento dos números comprimidos é determinado pela constante PACKED_VALUE_LENTH. Se estivermos a trabalhar com chaves de 1024 bits, a matemática deverá ser de 2048 bits (uma vez que o produto pode conter o dobro dos dígitos que os factores). Um byte contém 8 bits, pelo que o valor do parâmetro PACKED_VALUE_LENTH é 256 (2048 dividido por 8). E VALUE_LENTH será duas vezes maior, ou seja, 512.
A compressão e descompressão de números longos é realizada pelos procedimentos pack_value e unpack_value:
void pack_value(unsigned char *value, unsigned char *packed_value)
{
unsigned char x, y;
unsigned int i = 0, j = 0;
memset(packed_value, 0, PACKED_VALUE_LENTH);
while (i < PACKED_VALUE_LENTH)
{
x = value[j++];
y = value[j++];
packed_value[i++] = x | (y << 4);
}
}
void unpack_value(unsigned char *packed_value, unsigned char *value)
{
unsigned char cur_char;
unsigned int i = 0, j = 0;
clear_value(value);
while (i < PACKED_VALUE_LENTH)
{
cur_char = packed_value[i++];
value[j++] = cur_char & 0xF;
value[j++] = cur_char >> 4;
}
}
Damos também um exemplo do procedimento para subtrair números longos:
void value_sub(signed char *operand1, signed char *operand2)
{ //operand1 -= operand2
int i;
for (i = 0; i < VALUE_LENTH; i++)
{
*(operand1 + i) -= *(operand2 + i);
if (*(operand1 + i) < 0)
{
*(operand1 + i) += RADIX;
if ((i + 1) < VALUE_LENTH) *(operand1 + i + 1) -= 1;
}
}
}
Não apresentamos aqui outros procedimentos (multiplicação, divisão, etc.), pois eles (bem como o procedimento de subtração publicado acima) nada têm a ver com criptografia.
É claro que os algoritmos fornecidos acima estão relacionados com a implementação de um sistema sem o uso de inserções em linguagem assembly. Ao utilizar tais inserções, a situação muda radicalmente. Na implementação da linguagem assembly, as operações de empacotamento e descompactação são reduzidas a uma transformação idêntica:
void pack_value(void *value, void *packed_value) { memcpy(packed_value, value, VALUE_LENTH); }
void unpack_value(void *packed_value, void *value) { memcpy(value, packed_value, VALUE_LENTH); }
E as constantes VALUE_LENTH e PACKED_VALUE_LENTH na nossa implementação de matemática longa em linguagem assembly têm o mesmo valor (256 com chaves de 1024 bits). Isto deve-se ao facto dos módulos assembler não utilizarem qualquer “rarefação” de bits, e a informação ser armazenada de forma densa, utilizando todos os bits.
Atualmente estamos a utilizar código de 64 bits, pelo que a unidade para processar números longos é um objeto de 8 bytes. De facto, a nossa aritmética em linguagem assembly utiliza registos de 64 bits como dígitos, pelo que a "raiz" na nossa linguagem assembly é 2 elevado a 64. Como exemplo, vamos mostrar o nosso código fonte em assembler para o procedimento incrementar um número longo (o endereço do operando é passado aqui no registo rsi):
;======================================================
WORD_SIZE EQU 8
LONG_INT_LENTH EQU VALUE_LENTH / WORD_SIZE
;======================================================
SECTION .text
;======================================================
ii_inc_long_int: mov rcx,LONG_INT_LENTH
mov rax,1
mov rdx,0
.m10: add [rsi+rdx*WORD_SIZE],rax
jnc .fin
inc rdx
loop .m10
.fin: ret
;======================================================
Assim, no assembler, no caso das chaves RSA de 1024 bits, são processados números de apenas 32 (parâmetro LONG_INT_LENTH) “caracteres” (cada um dos quais para uma determinada arquitetura é uma palavra de máquina de 64 bits). Isto, claro, proporciona um aumento significativo de desempenho em comparação com os módulos matemáticos longos em C (que funcionam com palavras de apenas 4 bits de comprimento e, ao contrário do assembler, não têm suporte de hardware para controlo de overflow).
O conteúdo desta página está também disponível em inglês, francês, alemão, espanhol, ucraniano e russo.
| © Extra Systems, 2024 |
|