Zum Hauptinhalt springen

3. Deterministisches DSA und ECDSA

Deterministisches (EC)DSA ist der Prozess der Erzeugung einer (EC)DSA-Signatur über einer Eingabenachricht m durch Verwendung des standardmäßigen (EC)DSA-Signaturerzeugungsprozesses (diskutiert im vorherigen Abschnitt), außer dass der Wert k, anstatt zufällig erzeugt zu werden, durch den in diesem Abschnitt beschriebenen Prozess erhalten wird.

Wir verwenden die in Abschnitt 2 beschriebenen Notationen.

3.1. Bausteine​

3.1.1. HMAC​

HMAC [RFC2104] ist eine Konstruktion eines Message Authentication Code unter Verwendung einer Hash-Funktion und eines geheimen Schlüssels. Hier verwenden wir HMAC mit derselben Hash-Funktion H wie derjenigen, die zur Verarbeitung der Eingabenachricht vor der Signaturerzeugung oder -verifizierung verwendet wird.

Wir bezeichnen den Prozess der Anwendung von HMAC mit Schlüssel K auf Daten V durch:

HMAC_K(V)

was eine Sequenz von Bits der Länge hlen zurückgibt (die Ausgabelänge der zugrunde liegenden Hash-Funktion H).

3.2. Erzeugung von k​

Bei der Eingabenachricht m wird der folgende Prozess angewendet:

a. Verarbeite m durch die Hash-Funktion H, was ergibt:

h1 = H(m)

(h1 ist eine Sequenz von hlen Bits).

b. Setze:

V = 0x01 0x01 0x01 ... 0x01

sodass die Länge von V in Bits gleich 8*ceil(hlen/8) ist. Zum Beispiel wird auf einem oktetbasierten System, wenn H SHA-256 ist, V auf eine Sequenz von 32 Oktetten mit dem Wert 1 gesetzt. Beachten Sie, dass wir in diesem Schritt und allen folgenden Schritten dieselbe H-Funktion wie die in Schritt 'a' zur Verarbeitung der Eingabenachricht verwendete verwenden. Diese Wahl wird in Abschnitt 3.6 ausführlicher diskutiert.

c. Setze:

K = 0x00 0x00 0x00 ... 0x00

sodass die Länge von K in Bits gleich 8*ceil(hlen/8) ist.

d. Setze:

K = HMAC_K(V || 0x00 || int2octets(x) || bits2octets(h1))

wobei '||' Verkettung bezeichnet. Mit anderen Worten, wir berechnen HMAC mit Schlüssel K über die Verkettung des Folgenden in dieser Reihenfolge: der aktuelle Wert von V, eine Sequenz von acht Bits mit dem Wert 0, die Kodierung des (EC)DSA-privaten Schlüssels x und die gehashte Nachricht (möglicherweise gekürzt und erweitert wie durch die bits2octets-Transformation spezifiziert). Das HMAC-Ergebnis ist der neue Wert von K. Beachten Sie, dass der private Schlüssel x im Bereich [1, q-1] liegt, daher eine korrekte Eingabe für int2octets ist, was rlen Bits Ausgabe ergibt, d.h. eine ganzzahlige Anzahl von Oktetten (rlen ist ein Vielfaches von 8).

e. Setze:

V = HMAC_K(V)

f. Setze:

K = HMAC_K(V || 0x01 || int2octets(x) || bits2octets(h1))

Beachten Sie, dass das "interne Oktett" diesmal 0x01 ist.

g. Setze:

V = HMAC_K(V)

h. Wende den folgenden Algorithmus an, bis ein geeigneter Wert für k gefunden wird:

  1. Setze T auf die leere Sequenz. Die Länge von T (in Bits) wird als tlen bezeichnet, somit ist an diesem Punkt tlen = 0.

  2. Solange tlen < qlen, führe das Folgende aus:

    V = HMAC_K(V)
    T = T || V

  3. Berechne:

    k = bits2int(T)

    Wenn dieser Wert für k geeignet ist (d.h. wenn k im Bereich [1, q-1] liegt und für DSA oder ECDSA geeignet ist), dann wird dieser Wert von k verwendet.

  4. Andernfalls berechne:

    K = HMAC_K(V || 0x00)
    V = HMAC_K(V)

    und kehre zu Schritt h.1 zurück, wobei versucht wird, einen neuen Wert für k zu erzeugen.

3.3. Alternative Beschreibung der Erzeugung von k​

Der im vorherigen Abschnitt beschriebene Prozess ist tatsächlich vom "HMAC_DRBG"-Pseudozufallszahlengenerator abgeleitet, der in [SP800-90A] und Anhang D von [X9.62] beschrieben ist. Unter Verwendung der Terminologie aus [SP800-90A] kann die Erzeugung von k wie folgt beschrieben werden:

a. Instantiiere HMAC_DRBG unter Verwendung von HMAC, parametrisiert mit derselben Hash-Funktion H wie derjenigen, die zur Verarbeitung der zu signierenden Nachricht verwendet wird. Instantiierungsparameter sind:

requested_instantiation_security_strength Setze diesen Parameter auf einen beliebigen Wert, den die HMAC_DRBG-Implementierung akzeptiert, wenn H als Basis-Hash-Funktion verwendet wird.

prediction_resistance_flag Setze diesen Parameter auf "false".

personalization_string Setze diesen Parameter auf "Null" (die leere Bit-Sequenz).

entropy_input Verwende int2octets(x) als Entropie-String.

nonce Verwende bits2octets(H(m)) als Nonce.

Beachte, dass die letzten beiden Parameter keine Parameter für die HMAC_DRBG-Instantiierungsfunktion an sich sind. Stattdessen werden diese Werte von der internen Get_entropy_input-Funktion während der Instantiierung angefordert. Für deterministisches (EC)DSA möchten wir, dass HMAC_DRBG mit dem Entropie-String und der Nonce läuft, die wir spezifizieren, ohne auf eine tatsächliche Entropiequelle zuzugreifen.

b. Erzeuge einen Kandidatenwert für k, indem qlen Bits von HMAC_DRBG angefordert werden und die resultierenden Bits mit der bits2int-Transformation in eine Ganzzahl umgewandelt werden. Wiederhole diesen Schritt, bis ein Wert erhalten wird, der nicht null ist, kleiner als q ist und für (EC)DSA geeignet ist (siehe Abschnitt 3.4).

Beachte, dass wir für jeden Signaturerzeugungsprozess eine neue HMAC_DRBG-Instanz instantiieren. Es gibt keinen "personalization string" und keine "additional input" beim Erzeugen von Bits. Die Reseed-Funktion von HMAC_DRBG wird niemals aufgerufen, weder extern noch als Folge der internen HMAC_DRBG-Verarbeitung.

Wie oben gezeigt, verwenden wir die Kodierung des privaten Schlüssels als "entropy string" und die gehashte Nachricht (gekürzt und erweitert durch bits2octets) als "nonce". In HMAC_DRBG werden der Entropie-String und die Nonce einfach in den initialen Seed verkettet, daher ist die Aufteilung zwischen "Entropie" und "Nonce" ziemlich willkürlich. Die Verwendung von qlen Bits für jeden sollte mit den meisten Eingabeanforderungen der HMAC_DRBG-Implementierung kompatibel sein.

3.4. Verwendungshinweise​

Bei DSA oder ECDSA wird der Wert k zur Berechnung der ersten Hälfte der Signatur verwendet, genannt r (siehe Abschnitt 2.4). Die Standards DSA und ECDSA verlangen, dass falls r null ist, ein neuer Wert für k ausgewählt werden muss. In dieser Situation gibt dieses Dokument an, dass der Wert k "ungeeignet" ist und der Erzeugungsprozess weiter schleifen sollte.

Dieses Ereignis ist äußerst unwahrscheinlich. Tatsächlich würde es erheblichen rechnerischen Aufwand erfordern (ähnlich dem Brechen der Preimage-Resistenz der Hash-Funktion), um einen privaten Schlüssel und eine Nachricht zu finden, die zu einem Null-Wert für r führen. Rein zufällig auf einen solchen Fall zu stoßen, wird daher als unmöglich betrachtet, und ein Angreifer kann es nicht mit sorgfältig gestalteten Nachrichten erzwingen. In der Praxis wird ein solcher Code-Pfad nicht ausgelöst und kann daher mit minimalen Optimierungen implementiert werden.

3.5. Begründung​

Der in den vorherigen Abschnitten beschriebene Prozess ahmt das "Approved"-Verfahren zur Erzeugung von k nach, das in Anhang D von [X9.62] mit dem "HMAC_DRBG"-Pseudozufallszahlengenerator beschrieben ist. Der Hauptunterschied besteht darin, dass wir die Verkettung des privaten Schlüssels x und der gehashten Nachricht H(m) als Seed für den Pseudozufallszahlengenerator (PRNG) verwenden. Bei Verwendung einer "Sicherheitsstufe" von n Bits sollte HMAC_DRBG mit einer Seed-Entropie von mindestens n+64 Bits verwendet werden. Der Schlüssel x sollte jedoch ebenfalls mit dieser Entropie erzeugt worden sein, und die Länge von x ist qlen, die mindestens gleich 2*n und somit größer als n+64 ist (DSA und ECDSA, wie von den Standards spezifiziert, erfordern qlen >= 160). Es kann daher argumentiert werden, dass deterministisches ECDSA die Entropieanforderungen von Anhang D von [X9.62] erfüllt.

Wir verwenden bits2octets(H(m)) anstelle von H(m), um die Integration zu erleichtern. Tatsächlich lagern viele bestehende Signatursysteme das Nachrichten-Hashing aus. Die Signatur-Engine (die Zugriff auf den privaten Schlüssel hat) erhält nur H(m). In einigen Anwendungen, wo die Datenbandbreite eingeschränkt ist, werden nur die ersten qlen Bits von H(m) zur Signatur-Engine übertragen, auf der Grundlage, dass die bits2int-Transformation nachfolgende Bits ohnehin ignoriert. Möglicherweise könnte in einigen Systemen das gekürzte H(m) extern modulo q reduziert werden, da dies das Erste ist, was (EC)DSA mit der gehashten Nachricht durchführt. Mit der Definition von bits2octets kann deterministisches (EC)DSA mit derselben Eingabe angewendet werden.

3.6. Varianten​

Viele Teile der Spezifikation von deterministischem (EC)DSA sind ziemlich willkürlich, aber die Wahl wurde aus Interoperabilitätsgründen getroffen. Dieser Abschnitt diskutiert einige mögliche Varianten.

Die verwendete Hash-Funktion H wird im Signaturerzeugungsprozess für zwei verschiedene Zwecke verwendet: erstens zur Verarbeitung der Eingabenachricht und zweitens als Basis für HMAC (das selbst auch eine Hash-Funktion ist). In diesem Dokument spezifizieren wir die Verwendung derselben Hash-Funktion für beide Zwecke. Dies ist jedoch nicht zwingend erforderlich; es ist möglich, unterschiedliche Funktionen für diese beiden Rollen zu verwenden. Der Hauptnachteil besteht darin, dass Testvektoren nicht alle Kombinationen abdecken können; die Verwendung einer einzigen Hash-Funktion vereinfacht Interoperabilitätstests.

Die Definitionen von int2octets und bits2octets führen zu einer Ausgabe von rlen Bits (d.h. qlen aufgerundet auf das nächste Vielfache von 8), und sie erzeugen bei ihrer Verwendung tatsächlich höchstens qlen Bits Entropie. Es wäre möglich, dieselben Funktionen so zu definieren, dass sie genau qlen Bits ausgeben; dies würde jedoch die Implementierung etwas komplizierter machen, da viele Programmiersprachen und Frameworks dazu neigen, mit Sequenzen von Oktetten statt mit Bit-Sequenzen zu arbeiten. Andererseits erhöht das Aufrunden von qlen höchstens 7 Bits, was im Kontext eines PRNG-Seeds vernachlässigbar ist.

In dieser Spezifikation geben wir einen Prozess an, der in Sonderfällen schleift, in denen k (erhalten aus T durch bits2int) nicht im geeigneten Bereich liegt oder zur Erzeugung eines Null-Werts für r führen würde. Beide Fälle treten jedoch praktisch nie auf. Der letztere Fall (ein berechnetes r von Null) kann nur aufgrund eines Software-Fehlers auftreten (z.B. Elliptic-Curve-Parameter werden während der Programmlaufzeit beschädigt). Implementierungen können daher wählen, solche Fälle einfach als nicht behebbare Fehler zu behandeln und die Signaturberechnung einfach abzubrechen, anstatt zu schleifen.