Як відомо, процесор не забезпечує математики довгих чисел. На даний момент, процесори працюють з числами завдовжки 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 |
|