Wie Sie wissen, bietet der Prozessor keine Mathematik für lange Zahlen. Derzeit arbeiten Prozessoren mit Zahlen, die 64 Bit lang sind. In C entspricht dies dem Typ long long. In der Kryptographie ist es notwendig, mit Zahlen viel größerer Länge zu arbeiten. Es gibt zwei Möglichkeiten, dieses Problem zu lösen: Verwenden Sie vorhandene Bibliotheken von Drittanbietern oder schreiben Sie alles selbst. Extra Systems hat sich in diesem Produkt (wie wir es normalerweise tun) für die zweite Option entschieden. Das Extra Systems Cypher Net-Verschlüsselungssystem führt nur von uns geschriebenen Code aus.
Um lange Zahlen zu verarbeiten, verwendet Extra Systems Cypher Net vorzeichenlose Zeichenarrays mit einer solchen Länge, dass sie Zahlen der erforderlichen Größe aufnehmen können. Es gibt zwei Speicherformate: normal und verpackt. Das gepackte Format nutzt alle Bits, während das reguläre Format nur die Hälfte nutzt. Somit enthält im Normalformat jedes Byte eine hexadezimale Ziffer – vier Bits. Die Länge der gepackten Zahlen wird durch die Konstante PACKED_VALUE_LENTH bestimmt. Wenn wir mit 1024-Bit-Schlüsseln arbeiten, muss die Mathematik 2048-Bit sein (da das Produkt doppelt so viele Ziffern wie die Faktoren enthalten kann). Ein Byte enthält 8 Bits, daher beträgt der Wert des Parameters PACKED_VALUE_LENTH 256 (2048 geteilt durch 8). Und VALUE_LENTH wird doppelt so groß sein, also 512.
Das Packen und Entpacken langer Zahlen erfolgt durch die Prozeduren pack_value und 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;
}
}
Wir geben auch ein Beispiel für das Verfahren zum Subtrahieren langer Zahlen:
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;
}
}
}
Andere Verfahren (Multiplikation, Division usw.) stellen wir hier nicht vor, da sie (wie auch das oben veröffentlichte Subtraktionsverfahren) nichts mit Kryptographie zu tun haben.
Natürlich beziehen sich die oben angegebenen Algorithmen auf die Implementierung eines Systems ohne Verwendung von Einfügungen in Assembler. Bei der Verwendung solcher Einsätze ändert sich die Situation radikal. In der Assembler-Implementierung werden die Vorgänge des Packens und Entpackens auf eine identische Transformation reduziert:
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); }
Und die Konstanten VALUE_LENTH und PACKED_VALUE_LENTH in unserer Implementierung langer Mathematik in Assembler haben denselben Wert (256 mit 1024-Bit-Schlüsseln). Dies liegt daran, dass Assembler-Module keine „Verdünnung“ von Bits verwenden und Informationen dicht unter Verwendung aller Bits gespeichert werden.
Wir verwenden derzeit 64-Bit-Code, daher ist die Einheit zur Verarbeitung langer Zahlen ein 8-Byte-Objekt. Tatsächlich verwendet unsere Assembler-Arithmetik 64-Bit-Register als Ziffern, sodass die „Basis“ in unserer Assemblersprache 2 hoch 64 ist. Als Beispiel zeigen wir unseren Assembler-Quellcode für die Prozedur zum Erhöhen einer langen Zahl (Die Adresse des Operanden wird hier im RSI-Register übergeben):
;======================================================
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
;======================================================
Somit werden im Assembler bei 1024-Bit-RSA-Schlüsseln nur Zahlen von 32 (Parameter LONG_INT_LENTH) „Zeichen“ verarbeitet (von denen jedes für eine gegebene Architektur ein Maschinenwort mit einer Länge von 64 Bit ist). Dies führt natürlich zu einer erheblichen Leistungssteigerung im Vergleich zu langen Mathematikmodulen in C (die mit Wörtern von nur 4 Bit Länge arbeiten und im Gegensatz zu Assembler keine Hardwareunterstützung für die Überlaufkontrolle bieten).
Der Inhalt dieser Seite ist auch in Englisch, Französisch, Ukrainisch und Russisch verfügbar.
| © Extra Systems, 2024 |
|