2. DSA and ECDSA Notations (DSA- und ECDSA-Notationen)

In diesem Abschnitt beschreiben wir kurz DSA und ECDSA und definieren unsere Notationen. Die vollständigen Spezifikationen für DSA und ECDSA können in [FIPS-186-4] bzw. [X9.62] gefunden werden.

2.1. Key Parameters (Schlüsselparameter)

DSA und ECDSA arbeiten über einer großen Gruppe von Primzahlgröße, in der die Gruppenoperation einfach zu berechnen ist, aber der diskrete Logarithmus mit existierender und absehbarer Technologie rechnerisch nicht durchführbar ist. Die Definition der Gruppe wird als "Schlüsselparameter" bezeichnet. Schlüsselparameter können zwischen verschiedenen Schlüsselpaaren ohne negative Auswirkungen auf die Sicherheit geteilt werden, dies ist insbesondere bei ECDSA der übliche Fall.

DSA verwendet die folgenden Schlüsselparameter:

p - eine große Primzahl (mindestens 1024 Bits)

q - eine ausreichend große Primzahl (mindestens 160 Bits), die auch ein Teiler von p-1 ist

g - ein Generator für die multiplikative Untergruppe der Ordnung q von Ganzzahlen modulo p

Die Gruppe, über der DSA berechnet wird, besteht aus den Werten 'g^j mod p', wobei '^' Potenzierung bezeichnet und j von 0 bis q-1 (einschließlich) reicht. Die Größe der Gruppe ist q.

ECDSA verwendet die folgenden Schlüsselparameter:

E - eine elliptische Kurve, definiert über einem gegebenen endlichen Körper

q - eine ausreichend große Primzahl (mindestens 160 Bits), die ein Teiler der Kurvenordnung ist

G - ein Punkt von E mit der Ordnung q

Die Gruppe, über der ECDSA berechnet wird, besteht aus den Kurvenpunkten jG (Multiplikation des Punktes G mit der Ganzzahl j), wobei j von 0 bis q-1 reicht. G ist so, dass qG = 0 (der "Punkt im Unendlichen" auf der Kurve E). Die Größe der Gruppe ist q. Beachten Sie, dass diese Notationen sich geringfügig von denen in [X9.62] unterscheiden, wir verwenden sie, um mit denen für DSA übereinzustimmen.

2.2. Key Pairs (Schlüsselpaare)

Ein DSA- oder ECDSA-privater Schlüssel ist eine Ganzzahl x modulo q. Die relevanten Standards schreiben vor, dass x nicht 0 sein soll, daher ist x eine Ganzzahl im Bereich [1, q-1].

Ein DSA- oder ECDSA-öffentlicher Schlüssel wird aus dem privaten Schlüssel x und den Schlüsselparametern berechnet:

Für DSA ist der öffentliche Schlüssel die Ganzzahl: y = g^x mod p
Für ECDSA ist der öffentliche Schlüssel der Kurvenpunkt: U = xG

2.3. Integer Conversions (Ganzzahlkonvertierungen)

Sei qlen die binäre Länge von q. qlen ist die kleinste Ganzzahl, sodass q kleiner als 2^qlen ist. Dies ist die Größe der binären Darstellung von q ohne ein Vorzeichenbit (beachten Sie, dass q, da es eine große Primzahl ist, ungerade ist und somit jede Mehrdeutigkeit über die Länge einer Ganzzahl gleich einer Potenz von 2 vermieden wird). Wir definieren fünf Konvertierungsfunktionen, die mit Zeichenfolgen von Bits, Oktetten und Ganzzahlen modulo q arbeiten. qlen ist der Hauptparameter für diese Konvertierungen.

In den folgenden Unterabschnitten verwenden wir zwei andere Längen, genannt blen und rlen. rlen ist gleich qlen, aufgerundet auf das nächste Vielfache von 8 (wenn qlen bereits ein Vielfaches von 8 ist, dann ist rlen gleich qlen, andernfalls ist rlen etwas größer, bis zu qlen+7). Beachten Sie, dass rlen nicht mit dem Wert r zusammenhängt, der ersten Hälfte einer erzeugten Signatur. blen ist die Länge (in Bits) einer Eingabesequenz von Bits und kann zwischen Aufrufen variieren. blen kann kleiner, gleich oder größer als qlen sein.

2.3.1. Bits and Octets (Bits und Oktette)

Formal sind alle Operationen auf Sequenzen von Bits definiert. Eine Sequenz ist geordnet, das erste Bit wird als das am weitesten links stehende bezeichnet, während das letzte Bit das am weitesten rechts stehende ist.

Auf den meisten Softwaresystemen werden Bits in Oktetten (Sequenzen von acht Bits) gruppiert. Binärdaten, z.B. die Ausgabe einer Hash-Funktion, sind als eine Sequenz von Oktetten verfügbar. Wo anwendbar, betrachten wir, dass Bits innerhalb eines Oktetts vom höchstwertigen zum niedrigstwertigen geordnet sind: Das erste (am weitesten links stehende) Bit innerhalb eines Oktetts hat den numerischen Wert 128, während das letzte (am weitesten rechts stehende) den numerischen Wert 1 hat.

2.3.2. Bit String to Integer (Bit-Zeichenfolge zu Ganzzahl)

Die bits2int-Transformation nimmt als Eingabe eine Sequenz von blen Bits und gibt eine nicht-negative Ganzzahl aus, die kleiner als 2^qlen ist. Sie besteht aus den folgenden Schritten:

Die Sequenz wird zuerst auf die Länge qlen gekürzt oder erweitert:
- wenn qlen < blen, dann werden die qlen am weitesten links stehenden Bits behalten und nachfolgende Bits werden verworfen;
- andernfalls werden qlen-blen Bits (mit dem Wert null) links von der Sequenz hinzugefügt (d.h. vor den Eingabebits in der Sequenzordnung).
Die resultierende Sequenz wird dann unter Verwendung der Big-Endian-Konvention in einen Ganzzahlwert konvertiert: Wenn die Eingabebits b_0 (am weitesten links) bis b_(qlen-1) (am weitesten rechts) genannt werden, dann ist der resultierende Wert:
```
b_0*2^(qlen-1) + b_1*2^(qlen-2) + ... + b_(qlen-1)*2^0
```

Die bits2int-Transformation kann auch auf folgende Weise beschrieben werden: Die Eingabebitsequenz (der Länge blen) wird unter Verwendung der Big-Endian-Konvention in eine Ganzzahl transformiert. Wenn dann blen größer als qlen ist, wird die resultierende Ganzzahl durch zwei hoch blen-qlen geteilt (Euklidische Division: Der Rest wird verworfen). In vielen Softwareimplementierungen der Arithmetik für große Ganzzahlen entspricht diese Division einem "Rechtsshift" um blen-qlen Bits.

2.3.3. Integer to Octet String (Ganzzahl zu Oktett-Zeichenfolge)

Ein Ganzzahlwert x kleiner als q (und insbesondere ein Wert, der modulo q genommen wurde) kann in eine Sequenz von rlen Bits konvertiert werden, wobei rlen = 8*ceil(qlen/8). Dies ist die Sequenz von Bits, die durch Big-Endian-Kodierung erhalten wird. Mit anderen Worten, die Sequenzbits x_i (für i im Bereich von 0 bis rlen-1) sind so, dass:

x = x_0*2^(rlen-1) + x_1*2^(rlen-2) + ... + x_(rlen-1)

Wir nennen diese Transformation int2octets. Da rlen ein Vielfaches von 8 ist (das kleinste Vielfache von 8, das nicht kleiner als qlen ist), ist die resultierende Sequenz von Bits auch eine Sequenz von Oktetten, daher der Name.

2.3.4. Bit String to Octet String (Bit-Zeichenfolge zu Oktett-Zeichenfolge)

Die bits2octets-Transformation nimmt als Eingabe eine Sequenz von blen Bits und gibt eine Sequenz von rlen Bits aus. Sie besteht aus den folgenden Schritten:

Die Eingabesequenz b wird durch die bits2int-Transformation in einen Ganzzahlwert z1 konvertiert:
```
z1 = bits2int(b)
```
z1 wird modulo q reduziert, was z2 ergibt (eine Ganzzahl zwischen 0 und q-1, einschließlich):
```
z2 = z1 mod q
```
Beachten Sie, dass diese modulare Reduktion, da z1 kleiner als 2^qlen ist, mit einer einfachen bedingten Subtraktion implementiert werden kann: z2 = z1-q, wenn dieser Wert nicht-negativ ist, andernfalls z2 = z1.
z2 wird durch Anwendung von int2octets in eine Sequenz von Oktetten (eine Sequenz von rlen Bits) transformiert.

2.3.5. Usage (Verwendung)

Es ist bemerkenswert, dass int2octets nicht die Umkehrung von bits2int ist, da int2octets die Reduktion modulo q einschließt.