Как известно, процессор не обеспечивает математику длинных чисел. На данный момент, процессоры работают с числами длиной 64 бита. В языке C это соответствует типу long long. В криптографии необходимо работать с числами намного большей длины. Имеется два способа решения данной проблемы: использовать существующие сторонние библиотеки, либо написать все самому. Компания Extra Systems в данном продукте (как обычно мы это и делаем) выбрала второй вариант. В системе шифросвязи Extra Systems Cypher Net работает только код, написанный нами.
Для обработки длинных чисел Extra Systems Cypher Net использует массивы типа unsigned char такой длины, чтобы в них помещались числа необходимого размера. Существует два формата хранения: обычный и упакованный. В упакованном формате используются все биты, а в обычном - только половина. Таким образом, в обычном формате каждый байт содержит одну шестнадцатиричную цифру - четыре бита. Длина упакованных чисел определяется константой PACKED_VALUE_LENTH. Если мы работаем с 1024-битными ключами, то математика должна быть 2048-битная (поскольку произведение может содержать в два раза больше цифр, чем сомножители). В байте содержится 8 бит, следовательно значение параметра PACKED_VALUE_LENTH равно 256 (2048 делить на 8). А VALUE_LENTH будет в два раза больше, то есть 512.
Упаковку и распаковку длинных чисел производят процедуры pack_value и 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;
}
}
Также приведем в качестве примера процедуру вычитания длинных чисел:
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;
}
}
}
Другие процедуры (умножение, деление и т.п.) мы здесь не приводим, поскольку к криптографии они (равно как и опубликованная выше процедура вычитания) никакого отношения не имеют.
Разумеется, приводимые выше алгоритмы имеют отношение к реализации системы без использования вставок на ассемблере. При использовании таких вставок положение дел меняется радикальным образом. В ассемблерной реализации операции упаковки и распаковки сводятся к тождественному преобразованию:
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); }
А константы VALUE_LENTH и PACKED_VALUE_LENTH в нашей реализации длинной математики на языке ассемблера имеют одно и то же значение (256 при 1024-битных ключах). Это связано с тем, что ассемблерные модули не используют никакого "разрежения" битов, а хранение информации производится плотно, с использованием всех бит.
В настоящее время мы используем 64-битный код, поэтому единицей обработки длинных чисел является объект размером 8 байт. Фактически, наша ассемблерная арифметика использует 64-битные регистры в качестве цифр, так что "основание системы исчисления" у нас в ассемблере равно 2 в степени 64. В качестве примера продемонстрируем наш исходный код на ассемблере процедуры инкремента длинного числа (адрес операнда передается сюда в регистре 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
;======================================================
Таким образом, на ассемблере, в случае 1024-битных ключей RSA, обрабатываются числа всего лишь из 32-х (параметр LONG_INT_LENTH) "знаков" (каждый из которых для данной архитектуры представляет собой машинное слово длиной 64 бита). Это, конечно, дает существенный прирост производительности по сравнению с модулями длинной математики на языке C (которые работают со словами длиной всего лишь 4 бита, и не имея при этом к тому же, в отличие от ассемблера, аппаратной поддержки контроля переполнения).
| © Extra Systems, 2024 |
|