Signaturen

4.2 Signaturen

4.2.1 Einleitung

Elektronische Signaturen dienen der Authentifizierung – im Sinne dessen daß sie (vgl. Signaturgesetz):

dem Inhaber eines Signaturschlüssels eindeutig zugeordnet sind bzw. ihn identifizieren;
eine nachträgliche Änderung der Daten (Nachricht), mit denen sie verknüpft sind, sicher erkennbar machen.

Man unterscheidet Signaturen mit „Message Recovery” (siehe z. B. [ISO02a] oder [MvV92]) und Signaturen mit „Appendix”. In der Praxis werden Signaturen mit Anhang nach [IEE00, PKC02, NIS09, ANS05] wohl am häufigsten verwendet. Ihre Bildungsvorschrift kann man wiefolgt skizzieren (siehe auch Abbildung 4.4):

H(ash): Berechne den Hash (bzw. Message Digest) der Nachricht $M$ .
C(oding): Kodiere das Ergebnis nach einem dem Kryptoalgorithmus (siehe nächster Punkt) angepaßten Schema.
E(ncrypt): Verschlüssele den so strukturierten Hash mit dem privaten Teil $Kpriv$ des Signaturschlüssels.

Abbildung 4.4:

Signatur mit Anhang

Die Integrität der empfangenen (und möglicherweise veränderten) Nachricht $M′$ kann im weiteren mit Hilfe der Signatur verifiziert werden. Dazu sind auf der Empfängerseite folgende Schritte nötig:

Berechne $H (M ′)$ in gleicher Art und Weise wie beim Herausgeber.
Entschlüssele die Signatur mit Hilfe des öffentlichen Teils $Kpub$ des Signaturschlüssels und dekodiere $H (M )$ .
Vergleiche $H (M )$ mit $′ H (M )$ um die Integrität $′ M = M$ zu verifizieren.

4.2.2 RSA-Signaturen nach PKCS #1

Die RSA-Signatur über eine Nachricht $m$ wird berechnet, indem der Hash-Wert von $m$ mit dem privaten RSA-Schlüssel (vgl. Abschnitt 3.1) verschlüsselt wird. Auf der Empfangsseite muß der, mit dem öffentlichen Schlüssel entschlüsselte Hash, mit dem berechneten Wert für die Nachricht übereinstimmen.

RSA hat die für digitale Signaturen wichtige Eigenschaft, daß Ver- und Entschlüsselung vertauschbar sind.

4.2.3 Digital Signature Algorithm

Der Digital Signature Algorithm (DSA) wurde ursprünglich in [NIS94] standardisiert (dessen Nomenklatur hier beibehalten wurde), ist mittlerweile aber in überarbeiteten Fassungen, z. B. [NIS13, 4] und [IEE00] zu finden. Auch hierbei wird das Problem des diskreten Logarithmus genutzt, um einen öffentlichen und privaten Schlüssel zu definieren und mit dessen Hilfe eine Signatur zu berechnen bzw. zu verifizieren. Wie bei Signaturen üblich wird der Hash (Digest, Fingerprint) $h(m )$ einer Message $m$ signiert bzw. verifiziert.

Ansatz Wir wählen im Gegensatz zu der gewohnten Literatur einen etwas universelleren Ansatz, welcher den ECDSA nach [NIS13, ANS05, IEE00] gleich mit abdeckt.⁴⁹ Dazu sei die jeweils typische Einweg-Funktionen $Ψ (⋅)$ folgendermaßen definiert:

wobei $e$ ein Element aus dem jeweiligen Körper $K$ ( $K := Fp$ für DSA bzw. $K := E$ für ECDSA) und $n$ einen Skalar (mit $n < |K|$ ) darstellt.

In beiden Fällen kann man bezüglich einer Operation $◇$ , mit

Ψ (e,n )◇ Ψ(e,n )= Ψ (e,n + n ) 1 2 1 2

(4.2)

die Eigenschaft der Linearität festhalten. Konkret soll die Operation $◇$ folgendes bezeichnen:

beim diskreten Logarithmus (DSA) die Multiplikation im Körper $Fp$ (wozu natürlich auch die finale Modulo-Division durch $p$ gehört);
bei den elliptischen Kurven (ECDSA) die Punktaddition.

Außerdem wollen wir noch eine hilfreiche Abbildungsfunktion $Λ (e)$ definieren, welche aus einem Element $e$ der jeweiligen Domäne (DLC/ECC) und dem Domain-Parameter $q< |K |$ eine Langzahl ableitet.

Das Ergebnis kann dann als eine Komponente der Signatur verwendet werden (Details dazu folgen).

Schlüsselgenerierung Zuerst wird ein privater Schlüssel $x$ als Zufallszahl bestimmt. Aus diesem wird dann ein öffentlicher Schlüssel $y$ mit Hilfe der Einweg-Funktion $Ψ(⋅)$ berechnet:

y = Ψ(g,x).

(4.3)

Dabei sei $g$ ein Basiselement aus dem jeweiligen Körper, dessen Ordnung $q$ eine Primzahl sein muß.⁵⁰ Der private Schlüssel $x$ muß im Intervall $0< x < q$ liegen, d. h. $x$ entstammt der multiplikativen Gruppe $∗ F q$ .⁵¹

Interessanterweise gilt für den öffentlichen Schlüssel folgende Relation:

Ψ(y,n)= Ψ (g,nx)

(4.4)

welche eine wichtige Grundvoraussetzung für die Wirkungsweise des Algorithmus darstellt. Wir wollen Sie schnell noch überprüfen.

Signieren Zum Signieren wählt man eine Zufallszahl $0 < k< q$ , den privaten „Einmal-Schlüssel” und berechnet damit zwei Zahlen $(r,s)$ nach folgender Vorschrift:⁵²

Die Komponenten $(r,s)$ stellen eine DSA/ECDSA Signatur dar, welche später vom Empfänger verifiziert wird.

Durch die Wahl des Basiselements $g$ bzw. die Größe von $q$ kann man sehr gut die Länge der Signatur beeinflussen.

Zur Bestimmung des inversen $k$ ist das Lösen der Kongruenz $k−1k≡ 1 (mod q)$ notwendig. Vorteilhaft können sowohl Gleichung 4.5 als auch $k−1$ im Voraus (off-line) berechnet werden, falls erlaubt⁵³ .

k = s−1(h+ xr) mod q = s−1h mod q+ s−1r mod q x (mod q) ◟---◝◜---◞ ◟---◝◜--◞ u1 u2

und mit den beiden schon angedeuteten Variablen $u1$ und $u2$ entsprechend [NIS13]:

k = u + u x mod q 1 2

(4.7)

Verifizieren Abgesehen von den Wertebereichsprüfungen $0 < ^r < q$ und $0 < ^s< q$ erfolgt das Verifizieren vor allem mit Hilfe der Formeln 4.3 und 4.4. Dies geschieht (siehe z. B. auch [NIS13, Appendix E]) indem zuerst aus der übermittelten Signatur $(^r,^s)$ die Variablen $^u 1$ und $^u 2$ berechnet werden.

Im nächsten großen Schritt wird dann $v= Ψ(g, ^u )◇Ψ (y,u^) 1 2$ berechnet, was nur im Fall $^u = u 1 1$ und $u^2 = u2$ (bzw. $^r = r$ und $^s= s$ ) sowie bei passenden Schlüsseln und Domain-Parametern zu $Λ (v) = r$ führt.

In den Einzelschritten wurden dabei die Formeln 4.4, 4.2, 4.7 und 4.5 angewendet (in genau dieser Reihenfolge).