Transaktionen signieren und verifizieren

Hallo zusammen,

ich arbeite gegenwärtig ich Buch zum Thema Blockchain-Entwicklung durch und bin mittlerweile beim letzten Kapitel angekommen allerdings ist mir hier das ein oder andere nicht ganz verständlich, vielleicht kann mir hier ja wer weiterhelfen.

Im letzten Kapitel geht es darum u.A. Transaktionen zu signieren und anschießend zu verifizieren aber ich tu mich noch etwas schwer das ganze zu verstehen. Ich poste euch unten die entsprechenden Seiten im Buch damit ihr mir besser folgen könnt.

Und zwar ausgangssituation ist folgende: Ich habe einen Block Explorer erstellt über den es möglich ist die Blockchain zu durchsuchen und auch Transaktionen zu versenden. Um das versenden zu ermöglichen muss der User unter Anderem seinen privaten und öffentlichen Schlüssel eingeben. Diese werden dann im Frontend mittels JavaScript benutzt um die Transaktion zu signieren.

Im Backend soll das ganze dann mittels der Methoden „verify()“ verifiziert werden. Im Buch heißt es das Frontend und das Backend müssen die exakt gleiche Repräsentation einer Transaktionen verwenden. Ist damit die JSON Repräsentation gemeint oder der Hash oder beides?

Ebenfalls heißt es dann bei der Methode verify dass die Signatur selbst nur aus den Punkten R und S besteht. Diese „sind im ASN1 Format codiert und müssen aus dem Hex-String der Signatur ermittelt werden. Anschließend kann mit der Library von Bouncy Castle die Transaktion verifiziert werden“. Kann mir bitte wer in eigenen Worten erklären wie ich mit diesen 2 Punkten (und dem Hash der Transaktionen und dem Public Key) die Transaktion verifizieren soll?

Ich habe den gestrigen Tag bereits damit verbracht mich mit elliptischen Kurven auseinanderzusetzen, einige Uni-Vorlesungen dazu angesehen usw. Also mit dem Grundlegenden Prinzip davon bin ich vertraut, auch mit Gruppenoperationen usw. Aber wirklich verstehen tu ich diesen Schritt im Buch trotzdem noch nicht, villeicht kann mit ja wer helfen :blush:

//Methoden
	public static boolean verify(byte[] hash, byte[] signature, byte[] publicKey) {
		boolean result;
		try(ASN1InputStream asn1 = new ASN1InputStream(signature)) {
			ECDSASigner signer = new ECDSASigner();
			signer.init(false, new ECPublicKeyParameters(CURVE.getCurve().decodePoint(publicKey), DOMAIN));
			
			DLSequence seq = (DLSequence) asn1.readObject();
			BigInteger r = ((ASN1Integer) seq.getObjectAt(0)).getPositiveValue();
			BigInteger s =  ((ASN1Integer) seq.getObjectAt(1)).getPositiveValue();
			result = signer.verifySignature(hash, r, s);
			
		} catch (Exception e) {
			result = false;
		}		
		
		return result;
	}

Buchseiten:

Ich habe ECDSA unter anderem mithilfe dieses Videos verstanden:

Beachte jedoch dass hinter ECDSA keine simple Vektormultiplikation steckt. Es ist deutlich komplexer.

Ansonsten kann uns bestimmt @skyrmion jede Menge über ECDSA erzählen :wink:

2 „Gefällt mir“

Mir ist ehrlich gesagt noch nicht klar, was du genau wissen möchtest.

Auf den fünf Buchseiten geht es nicht um die hintergründige Mathematik. Stattdessen wird gezeigt wie man Signatur und Verifikation mittels der hier verwendeten Bibliothek praktisch implementiert. Ein großer Teil des Codes besteht aus Hin- und Her-Geschiebe und Konvertieren verschiedener Codierungen der verwendeten Variablen.

Auch in deiner Methode verify findet die eigentliche Verifikation nur verdeckt innerhalb von signer.verifySignature(hash, r, s) statt. Vorher passiert im Prinzip nichts.

Hast du nun Schwierigkeiten mit den Codierungen, mit der Implementierung der einzelnen Schritte oder mit der zugrundeliegenden Kryptographie?

Falls du wissen möchtest, was bei der Verifikation mathematisch passiert, kannst du z.B. einfach mal in den Wikipedia-Artikel schauen: Elliptic Curve DSA – Wikipedia

→ Unter dem Punkt Überprüfung einer Signatur stehen die Schritte, wie du anhand von Public Key, Hash, r und s die Verifikation durchführst.

Solltest du Fragen zu den konkreten rechnerischen Schritten haben, kann ich gerne versuchen dir zu helfen.

Solltest du eher Fragen zur Implementierung haben, wäre ich der falsche. :slight_smile:

Das kann ich dir nicht sagen, da es eine Frage der Implementierung ist, mit der ich mich nicht auskenne.

Allerdings ist logisch, dass der Hash, den du für die Verifikation verwendest, derselbe sein muss wie der Hash, der für die Berechnung der Signatur (r,s) verwendet wurde. Der Hash repräsentiert schließlich die Transaktion.

Ansonsten würdest du bei der Verifkation prüfen, ob die Signatur für eine andere Transaktion (Hash) gültig ist.

2 „Gefällt mir“

@lerpy: Vielen Dank für das Video, da wird das ganze wirklich schonmal sehr gut erklärt! :)
@skyrmion Mir geht es tatsächlich erstmal eher um die Mathematik weil ich das ganze erst verstehen will bevor ich mich an die Implementierung mach :) Also ich hab mir das Video von lerpy mal angesehen und die Stelle worum es mir geht ist die folgende:


Also wenn ich das ganze richtig verstanden habe signiert Alice die Nachricht (bei BTC etc die Transaktion) folgendermaßen: Sie multipliziert den Generator Point (also den Punkt der die gesamte Kurve generieren kann) mit einer zufallszahl k. Worum genau handelt es sich dabei bzw. ist das wirklich einfach nur irgendeine zufällige Nummer? Dann bekommt sie den Punkt R und davon relevant ist nur der x wert. S berechnet sie indem sie dann die inverse von k mit dem Hash der Transaktion + d * r rechnet. „d“ stellt hier wiederum den privateKey dar wenn also die Anzahl an Multiplikationen mit dem GeneratorPoint die gebraucht werden um auf den Publik Key zu kommen oder?
Ich glaub es macht am meisten Sinn erstmal den Part zu klären bevor wir zur Verifikation gehen :sweat_smile: Vielen Dank schonmal für deine bzw. eure Hilfe!

Soweit richtig.

Wobei der Generator-Punkt G natürlich nicht einfach mit der Zahl k multipliziert werden kann. Stattdessen ist k die Anzahl, wie oft G nach den Regeln der Elliptischen Kurve aufaddiert werden soll. Für k=4 also beispielsweise k\cdot G=G+G+G+G.

Nein, der private Schlüssel von Alice im Video heißt d. Im Wikipedia-Artikel heißt er d_A.

k ist tatsächlich eine Zufallszahl im Bereich 1, 2, …, n-1. Dabei ist die Primzahl n die Ordnung des Generators G, also die Ordnung der von G erzeugten zyklischen Gruppe.
Das ist zwar der gleiche Wertebereich wie bei den Private Keys, aber für jede einzelne Signatur muss immer wieder eine neue solche Zufallszahl k generiert werden, s.a. den Wiki-Artikel:

Es ist entscheidend, dass für verschiedene Signaturen auch verschiedene k-Werte verwendet werden, ansonsten kann die Gleichung im Schritt 4 nach dem geheimen Schlüssel d_A aufgelöst werden

Die Zufallszahl k ist einfach Teil des Algorithmus und hat erst einmal nichts mit den Schlüsseln zu tun.

Auch richtig, also s = k^{-1} \cdot (Hash\_as\_integer + r \cdot d) mod n.

Den Hash der Transaktion musst du natürlich vor der Addition von einem Byte String in eine ganze Zahl (Integer) konvertieren.

Und dein „rechnet“ bedeutet hier Multiplikation modulo n.

Kurz zum Inversen von k: Es handelt sich hier um das multiplikative Inverse von k innerhalb des Restklassenkörpers mit Ordnung n. Also diejenige ganze Zahl im Bereich 1, 2, …, n-1, die multipliziert mit k gleich 1 ist (mod n). Bestimmen kann man diese z.B. mit dem erweiterten euklidischen Algorithmus.

Richtig.

Wenn du die Rechnungen verstehen und selbst durchführen können möchtest, solltest du dich mit dem Rechnen in Restklassenringen bzw. -körpern (Modulo-Rechnen, ggT, euklidischer Algorithmus, Square-and-Multiply etc.), sowie auf der Elliptischen Kurve vertraut machen.

Es gibt allerdings gerade in der Kryptographie einen guten Grund, für finale Anwendungen auf bewährte Bibliotheken zu setzen. :wink:

Im Endeffekt musst du bei der Geschichte zwei Hürden überwinden. Als erstes die Mathematik und als zweites die ganzen verschiedenen Datenformate und -codierungen. Beides ist kein Hexenwerk, braucht aber etwas Zeit.

Das Video ist nicht schlecht, aber an der ein oder anderen Stelle etwas unsauber und inkonsistent bei den Bezeichnungen.

Ich würde mich eher an die einfachen Schritte bei Wikipedia halten, oder etwas umfangreicher an das hier, was eigentlich auch sehr schön geschrieben ist:

Technical Guideline BSI TR-03111 - Elliptic Curve Cryptography

3 „Gefällt mir“

Also erstmal vielen lieben Dank für die ausführliche Antwort, darf ich fragen woher du das alles so genau weißt? :smiley:
Ich denke das mit dem verifizieren ist eigentlich soweit klar jetzt da die variablen alle geklärt sind.
Was ich aber noch nicht so genau verstehe ist was es genau mit der „Domain“ der Kurve aufsich hat. Die Domain wird ja scheinbar benötigt um die Kurve zu bilden oder? Aber reicht dafür nicht einfach der GeneratorPoint? Bei mir im Buch werden ja für die Domain die Punkte G, N und H verwendet das versteh ich nicht sorecht.

private static final ECDomainParameters DOMAIN =
		new ECDomainParameters( CURVE.getCurve( ), CURVE.getG( ), CURVE.getN( ), CURVE.getH( ) );

	//Methoden
	public static boolean verify(byte[] hash, byte[] signature, byte[] publicKey) {
		boolean result;
		try(ASN1InputStream asn1 = new ASN1InputStream(signature)) {
			ECDSASigner signer = new ECDSASigner();
			signer.init(false, new ECPublicKeyParameters(CURVE.getCurve().decodePoint(publicKey), DOMAIN));

Und letzte Sache die mir unklar ist wofür ich jetzt eigentlich den publicKey in der Methode brauche (in der theorie die wir eben besprochen ist es mir natürlich klar, da er zur Verifikation in der Formal gebraucht wird). Dieser wird ja irgendwie encodiert aber in der „verifySignature“ Methode garnicht übergeben.
Aber ich fürchte das ganze bezieht sich jetzt zu sehr auf die implementierung oder? :slight_smile:

lg.~

1 „Gefällt mir“

Sagen wir so, die ein oder andere Mathematik-Vorlesung wie z.B. Algebra (Gruppen/Ringe/Körper) oder Kryptographie ist sehr hilfreich für das Grundverständnis. Das wiederum hilft einem mit der passenden Lektüre schneller in solch ein Thema reinzukommen.

Allerdings erhält man nur einen groben Überblick. Wirklich gut kennt man sich nur aus, wenn man auf einem Gebiet arbeitet. Deshalb meine Aussagen bitte auch wirklich nicht als absolut verlässlich ansehen!

Die Domain Parameter definieren wie und mit welcher elliptische Kurve du rechnest.

Fest steht im Allgemeinen nur die Gleichung einer Elliptischen Kurve: y^²=x^³+ax+b

Es ist erst einmal nicht festgelegt mit welchen Zahlen x, y, a und b aus welchem Körper überhaupt gerechnet werden soll (z.B. ganze, rationale oder reelle Zahlen; endlicher oder unendlicher Körper). Oder welche Kurve verwendet wird, also die Parameter a und b, und welchen Generator G man wählt.

Der Generator alleine reicht nicht. Konkret muss man in unserem Kontext mindestens vorgeben:

p - Ordnung des zugrundeliegenden endlichen Zahlenkörpers (hier eine Primzahl)
a,b - Parameter, welche die Gleichung der Elliptischen Kurve definieren
G - Generatorpunkt, der auf der definierten Kurve liegt

Die folgenden Parameter bräuchte man streng genommen nicht mit angeben, da sie durch die oben genannten eindeutig bestimmt sind:

n - Ordnung der durch G erzeugten Untergruppe
h - Kofaktor, definiert durch n und die Kurvengruppenordnung

Hier die Domain Parameter der für Bitcoin verwendeten Kurve: Secp256k1 - Bitcoin Wiki

Die Parameter p,a,b legen alle Punkte (x,y) fest, die auf der Kurve liegen, deren Koordinaten also die Gleichung der Elliptischen Kurve erfüllen. Als zugrundeliegenden Zahlenraum für die Punkt-Koordinaten x und y verwendet man hier den endlichen Restklassenkörper \mathbb{F}_p mit Primzahlordnung p (Ganze Zahlen modulo p). Bei der Verknüpfung („Addition") von zwei Kurven-Punkten nach einer definierten Vorschrift wird entsprechend mit den Koordinaten modulo p gerechnet.

Durch diese Verknüpfung zweier Punkte erhält man wieder einen Punkt, der auf der Kurve liegt. Außerdem ist die definierte Verknüpfung assoziativ (man darf umklammern) und kommutativ (man darf vertauschen), es existiert ein neutrales Element (Point at Infinity), sowie zu jedem Punkt ein inverses Element.
Alle Punkte auf der Kurve zusammen bilden also bzgl. dieser Verknüpfung eine abelsche (kommutative) Gruppe. In kommutativen Gruppen nennt man die Vernüpfung zwischen den Elementen so wie hier auch gerne „Addition“ und verwendet das „+“-Zeichen.

Die Punkte auf der Kurve, welche durch die Vielfachen des Generators erreicht werden können (G+G+G+G+ …), bilden eine zyklische Untergruppe der Ordnung n und werden als Schlüsselraum für die Public Keys verwendet. n ist also die Anzahl dieser Untergruppenelemente bzw. Punkte.

Der Kofaktor h entspricht dem Quotienten aus der Anzahl aller Kurvenpunkte und der Anzahl n der Kurvenpunkte in der durch den Generator erzeugten Untergruppe. Bei secp256k1 ist h=1, d.h. mit den Vielfachen des Generators erreicht man alle Punkte auf der Kurve.

So wie ich das verstehe, wird der Public Key dem Objekt signer schon bei der Initialisierung signer.init(...) übergeben und wahrscheinlich als Attribut von signer gespeichert.

Nachher werden dann in signer.verifySignature(...) noch zusätzlich Hash, r und s übergeben.

3 „Gefällt mir“

Nochmals vielen Dank für die ausführliche Antwort du hast mir wirklich ungemein weitergeholfen! Ich hätte jetzt nur noch eine letzte Grundlagenfrage dann geh ich dir nichtmehr auf die Nerven :smiley:

Und zwar geht es mir noch um die Key-Erstellung an sich: Also wenn der privateKey die Anzahl an Multiplikationen mit G ist um auf den publicKey zu kommen (P = d * G ) dann frag ich mich nur noch was war als erstes da? Rein logisch natürlich der privateKey oder weil man kann ja praktisch nicht vom publicKey auf den privateKey zurückrechnen weil sonst ja die ganze Verschlüsselung keinen Sinn machen würde oder? Also gibt der privateKey den publicKey vor und der kpriv wäre dann wiederum aber eine reine Zufallszahl… Verstehst du was ich meine? :sweat_smile:

1 „Gefällt mir“

Genau, du wählst zufällig eine natürliche Zahl d (die kleiner als Ordnung n sein muss) und das ist dein privater Schlüssel (wie oben schon erwähnt nicht verwechseln mit den temporären Schlüsseln).

Der ist dann „zuerst“ da, wobei natürlich auch die anderen Parameter (Modul, Koeffizienten, der Punkt der die zyklische Gruppe erzeugt und dessen Ordnung) teil des öffentlichen Schlüssels sind bzw. zu den öffentlichen Informationen gehören.

Ich weiß nicht welches Buch du genutzt hast, aber falls du was theoretischeres suchst, dass auch ausführlicher auf die Mathematik eingeht (und sie einführt) dann schau dir mal Paar und Pelzl (Kryptographie verständlich) an. Das ist dann der komplette Wahnsinn von Stromchiffre bis Hashfunktionen.

Das machst du aber nur zu Testzwecken für dich selbst, oder? :slight_smile:

1 „Gefällt mir“

@sutterseba Perfekt, dann hab ich das soweit mal einigermaßen verstanden ( die zahlreichen Details mal außen vor) :sweat_smile:

Das Buch steht tatsächlich schon auf meiner Liste für die nächste Urlaubslektüre da ich mir von dem Professor ein paar Vorlesungen auf Youtube zu dem Thema angesehen habe und der das ganze wirklich auch sehr gut erklären kann :+1: :sweat_smile:

Und ja das mache ich nur zu Testzwecken, du meinst weil der PublicKey normalerweise aus dem Privaten errrechnet werden sollte damit der User ihn nicht auch noch extra angeben muss oder? Ich glaub die Autoren haben diese zusätzliche Berechnung aus Vereinfachungsgründen wohl weggelassen.

lg.~
PS: Das Buch das ich durcharbeite heißt Blockchain für Entwickler
Wobei ich mich noch eher als Anfänger bezeichnen würde, hab zuvor ein halbes Jahr ca Java gelernt aber wollte mich nachdem ich mit meinen Anfängerkursen (Java, JavaFX und SQL) dazu ferig war gleich auf das Thema Blockchain spezialisieren weil mich das am meisten interessiert :sweat_smile:

Joah, das auch. Aber mir ging es darum dass ein solches Tool aus Sicherheitsgründen (und aus rein praktischen Gründen – Endnutzer haben gar keinen Kontakt zu rohen Schlüssel) natürlich nicht für tatsächliche Nutzer empfehlenswert ist.

Aber für Lernzwecke ist sowas natürlich optimal, nicht falsch verstehen! :smiley:

Für einen Block Explorer üblich wäre eine einfache Broadcast Funktion die fertige Transaktionen nur veröffentlicht. Beispiel.

Ah okay danke für den Tipp, wenn ich in Zukunft mal ein „richtiges“ Projekt angehe werde ich das natürlich so machen :slight_smile: