Come sai, il processore non fornisce matematica per numeri lunghi. Attualmente, i processori funzionano con numeri lunghi 64 bit. In C corrisponde al tipo long long. In crittografia è necessario lavorare con numeri di lunghezza molto maggiore. Esistono due modi per risolvere questo problema: utilizzare le librerie di terze parti esistenti o scrivere tutto da soli. Extra Systems in questo prodotto (come facciamo di solito) hanno scelto la seconda opzione. Il sistema di crittografia Extra Systems Cypher Net esegue solo codice scritto da noi.
Per elaborare numeri lunghi, Extra Systems Cypher Net utilizza array di caratteri senza segno di lunghezza tale da poter contenere numeri della dimensione richiesta. Esistono due formati di archiviazione: normale e in pacchetto. Il formato compresso utilizza tutti i bit, mentre il formato normale ne utilizza solo la metà. Pertanto, nel formato normale, ogni byte contiene una cifra esadecimale, ovvero quattro bit. La lunghezza dei numeri compressi è determinata dalla costante PACKED_VALUE_LENTH. Se lavoriamo con chiavi a 1024 bit, la matematica deve essere a 2048 bit (poiché il prodotto può contenere il doppio delle cifre dei fattori). Un byte contiene 8 bit, quindi il valore del parametro PACKED_VALUE_LENTH è 256 (2048 diviso 8). E VALUE_LENTH sarà due volte più grande, ovvero 512.
L'imballaggio e l'estrazione dei numeri lunghi viene eseguito dalle procedure 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;
}
}
Diamo anche un esempio della procedura per sottrarre i numeri lunghi:
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;
}
}
}
Non presentiamo qui altre procedure (moltiplicazione, divisione, ecc.), poiché esse (così come la procedura di sottrazione pubblicata sopra) non hanno nulla a che fare con la crittografia.
Naturalmente gli algoritmi sopra riportati si riferiscono all'implementazione di un sistema senza l'utilizzo di inserti in linguaggio assembly. Quando si utilizzano tali inserti, la situazione cambia radicalmente. Nell'implementazione del linguaggio assembly, le operazioni di imballaggio e spacchettamento si riducono a una trasformazione identica:
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 le costanti VALUE_LENTH e PACKED_VALUE_LENTH nella nostra implementazione della matematica lunga in linguaggio assembly hanno lo stesso valore (256 con chiavi a 1024 bit). Ciò è dovuto al fatto che i moduli assembler non utilizzano alcuna “rarefazione” di bit e le informazioni vengono archiviate densamente, utilizzando tutti i bit.
Attualmente utilizziamo codice a 64 bit, quindi l'unità per l'elaborazione dei numeri lunghi è un oggetto a 8 byte. Infatti, l'aritmetica del nostro linguaggio assembly utilizza registri a 64 bit come cifre, quindi la "radice" nel nostro linguaggio assembly è 2 alla potenza di 64. Ad esempio, mostriamo il nostro codice sorgente assembler per la procedura per incrementare un numero lungo (l'indirizzo dell'operando viene passato qui nel 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
;======================================================
Pertanto, nell'assemblatore, nel caso di chiavi RSA a 1024 bit, vengono elaborati numeri di soli 32 (parametro LONG_INT_LENTH) “caratteri” (ognuno dei quali per una data architettura è una parola macchina lunga 64 bit). Ciò, ovviamente, fornisce un significativo aumento delle prestazioni rispetto ai lunghi moduli matematici in C (che funzionano con parole di soli 4 bit di lunghezza e, a differenza dell'assemblatore, non hanno supporto hardware per il controllo dell'overflow).
Il contenuto di questa pagina è disponibile anche in inglese, francese, tedesco, portoghese, spagnolo, ucraino e russo.
| © Extra Systems, 2024 |
|