Como sabes, el procesador no proporciona matemáticas para números largos. Actualmente, los procesadores trabajan con números de 64 bits de longitud. En C esto corresponde al tipo largo largo. En criptografía es necesario trabajar con números de longitud mucho mayor. Hay dos formas de resolver este problema: utilizar bibliotecas de terceros existentes o escribir todo usted mismo. Extra Systems en este producto (como hacemos habitualmente) eligió la segunda opción. El sistema de cifrado Cypher Net de Extra Systems solo ejecuta código escrito por nosotros.
Para procesar números largos, Extra Systems Cypher Net utiliza matrices de caracteres sin firmar de tal longitud que pueden acomodar números del tamaño requerido. Hay dos formatos de almacenamiento: regular y empaquetado. El formato empaquetado utiliza todos los bits, mientras que el formato normal utiliza sólo la mitad. Por tanto, en formato normal, cada byte contiene un dígito hexadecimal: cuatro bits. La longitud de los números empaquetados está determinada por la constante PACKED_VALUE_LENTH. Si estamos trabajando con claves de 1024 bits, entonces la matemática debe ser de 2048 bits (ya que el producto puede contener el doble de dígitos que los factores). Un byte contiene 8 bits, por lo que el valor del parámetro PACKED_VALUE_LENTH es 256 (2048 dividido por 8). Y VALUE_LENTH será el doble, es decir, 512.
El empaquetado y descomprimido de números largos se realiza mediante los procedimientos pack_value y 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;
}
}
También damos un ejemplo del procedimiento para restar números largos:
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;
}
}
}
No presentamos aquí otros procedimientos (multiplicación, división, etc.), ya que ellos (así como el procedimiento de resta publicado anteriormente) no tienen nada que ver con la criptografía.
Por supuesto, los algoritmos dados anteriormente están relacionados con la implementación de un sistema sin utilizar inserciones en lenguaje ensamblador. Cuando se utilizan tales inserciones, la situación cambia radicalmente. En la implementación en lenguaje ensamblador, las operaciones de empaque y desempaquetado se reducen a una transformación 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); }
Y las constantes VALUE_LENTH y PACKED_VALUE_LENTH en nuestra implementación de matemáticas largas en lenguaje ensamblador tienen el mismo valor (256 con claves de 1024 bits). Esto se debe al hecho de que los módulos ensambladores no utilizan ninguna "rarefacción" de bits y la información se almacena densamente utilizando todos los bits.
Actualmente utilizamos código de 64 bits, por lo que la unidad para procesar números largos es un objeto de 8 bytes. De hecho, nuestra aritmética en lenguaje ensamblador utiliza registros de 64 bits como dígitos, por lo que la "base" en nuestro lenguaje ensamblador es 2 elevado a 64. Como ejemplo, mostremos nuestro código fuente ensamblador para el procedimiento para incrementar un número largo. (la dirección del operando se pasa aquí en el registro 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
;======================================================
Así, en el ensamblador, en el caso de claves RSA de 1024 bits, se procesan números de sólo 32 (parámetro LONG_INT_LENTH) "caracteres" (cada uno de los cuales, para una arquitectura determinada, es una palabra de máquina de 64 bits de longitud). Esto, por supuesto, proporciona un aumento significativo del rendimiento en comparación con los módulos matemáticos largos en C (que funcionan con palabras de sólo 4 bits de longitud y, a diferencia del ensamblador, no tienen soporte de hardware para control de desbordamiento).
El contenido de esta página también está disponible en inglés, francés, alemán, portugués, ucraniano y ruso.
| © Extra Systems, 2024 |
|