Comme vous le savez, le processeur ne fournit pas de calcul pour les nombres longs. Actuellement, les processeurs fonctionnent avec des nombres de 64 bits. En C, cela correspond au type long long. En cryptographie, il est nécessaire de travailler avec des nombres de longueur beaucoup plus grande. Il existe deux manières de résoudre ce problème: utiliser des bibliothèques tierces existantes ou tout écrire vous-même. Les systèmes supplémentaires de ce produit (comme nous le faisons habituellement) ont choisi la deuxième option. Le système de cryptage Extra Systems Cypher Net exécute uniquement le code écrit par nos soins.
Pour traiter les nombres longs, Extra Systems Cypher Net utilise des tableaux de caractères non signés d'une longueur telle qu'ils peuvent accueillir des nombres de la taille requise. Il existe deux formats de stockage: régulier et emballé. Le format compressé utilise tous les bits, tandis que le format normal n'en utilise que la moitié. Ainsi, au format normal, chaque octet contient un chiffre hexadécimal – quatre bits. La longueur des nombres compressés est déterminée par la constante PACKED_VALUE_LENTH. Si nous travaillons avec des clés de 1024 bits, le calcul doit alors être de 2048 bits (puisque le produit peut contenir deux fois plus de chiffres que les facteurs). Un octet contient 8 bits, donc la valeur du paramètre PACKED_VALUE_LENTH est 256 (2048 divisé par 8). Et VALUE_LENTH sera deux fois plus grande, soit 512.
Le compactage et le décompression des nombres longs sont effectués par les procédures pack_value et 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;
}
}
Nous donnons également un exemple de la procédure de soustraction de nombres longs:
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;
}
}
}
Nous ne présentons pas ici d’autres procédures (multiplication, division, etc.), car elles (ainsi que la procédure de soustraction publiée ci-dessus) n’ont rien à voir avec la cryptographie.
Bien entendu, les algorithmes donnés ci-dessus sont liés à l'implémentation d'un système sans utiliser d'inserts en langage assembleur. Lors de l'utilisation de tels inserts, la situation change radicalement. Dans l'implémentation du langage assembleur, les opérations de packaging et de déballage se réduisent à une transformation identique:
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); }
Et les constantes VALUE_LENTH et PACKED_VALUE_LENTH dans notre implémentation de mathématiques longues en langage assembleur ont la même valeur (256 avec des clés de 1024 bits). Cela est dû au fait que les modules assembleurs n'utilisent aucune «raréfaction» de bits et que les informations sont stockées de manière dense, en utilisant tous les bits.
Nous utilisons actuellement du code 64 bits, donc l'unité de traitement des nombres longs est un objet de 8 octets. En fait, l'arithmétique de notre langage assembleur utilise des registres de 64 bits comme chiffres, donc la «base» dans notre langage assembleur est 2 à la puissance 64. À titre d'exemple, montrons notre code source assembleur pour la procédure d'incrémentation d'un nombre long. (l'adresse de l'opérande est passée ici dans le registre 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
;======================================================
Ainsi, dans l'assembleur, dans le cas de clés RSA de 1024 bits, des nombres de seulement 32 (paramètre LONG_INT_LENTH) «caractères» sont traités (dont chacun pour une architecture donnée est un mot machine de 64 bits de long). Ceci, bien sûr, donne une augmentation significative des performances par rapport aux longs modules mathématiques en C (qui fonctionnent avec des mots de seulement 4 bits de longueur et, contrairement à l'assembleur, ne disposent pas de support matériel pour le contrôle de débordement).
Le contenu de cette page est également disponible en anglais, allemand, ukrainien et en russe.
| © Extra Systems, 2024 |
|