Warum ist es nicht möglich, den privaten Schlüssel aus dem öffentlichen Schlüssel zu bekommen?

So wie ich es verstehe, ist die Gleichung für den öffentlichen Schlüssel wie folgt definiert:

K = k * G

Dabei ist K der öffentliche Schlüssel, k der private Schlüssel und G der Generatorpunkt.

  • Ist G eine Konstante? (Soweit ich gelesen habe, ist es eine Konstante.)
  • Wenn ja, wie ist es dann nicht möglich, einfach K/G = k zu machen?
  • Wenn nicht, wie wird er aus dem privaten Schlüssel erstellt?

Antworten (3)

Wie ich es verstanden habe, ist die Gleichung für den öffentlichen Schlüssel so definiert, K = k * Gdass K der öffentliche Schlüssel, k der private Schlüssel und G der Generatorpunkt ist.

Das ist richtig.

Nun meine erste Frage, ist G eine Konstante? (soweit ich gelesen habe, ist es eine Konstante)

Es ist. Es ist der Punkt mit den Koordinaten (55066263022277343669578718895168534326250603453777594175500187360389116729240, 32670510020758816978083085130507043184471273380659243275938904335757337482424). Sie können überprüfen, ob diese Koordinaten die Kurvengleichung erfüllen : Y^2 = X^3 + 7 (mod 115792089237316195423570985008687907853269984665640564039457584007908834671663).

Und wenn ja, wie ist es dann nicht möglich, einfach K/G = k zu machen?

Die Antwort ist einfach, dass wir keinen effizienten Weg kennen, um elliptische Kurven zu "dividieren" (was als Problem des diskreten Logarithmus bezeichnet wird), und es wird angenommen, dass kein solcher Weg gefunden werden kann. Der bekannteste Algorithmus dafür benötigt für diese spezielle Kurve etwa 2 128 Iterationen, eine unglaublich große Menge.

Sie müssen sich darüber im Klaren sein, dass das *in, k * Gwährend Sie es schreiben, keine gewöhnliche Multiplikation ist (was würde das überhaupt für Punkte bedeuten?). Es ist eine ziemlich komplizierte Operation , und die Leute haben nützliche Eigenschaften davon herausgefunden, die der Multiplikation etwas ähnlich sind (es bildet eine zyklische Gruppe , also wird dasselbe Symbol verwendet). Aber niemand hat jemals einen Weg gefunden, die umgekehrte Operation durchzuführen, und dies wurde die Grundlage für die Kryptografie mit elliptischen Kurven .

Dadurch hat sich für mich einiges aufgeklärt. Danke für die Erklärung und Links!

Mathematiker mögen ihre Analogien, manchmal können diese Analogien hilfreich sein, aber sie können auch verwirrend sein, besonders für diejenigen, die neu in einem Gebiet sind.

In der Mathematik besteht eine "Gruppe" aus einer Menge von Elementen und einem Operator, der einige Anforderungen erfüllt. Der Operator muss assoziativ sein, es muss ein Identitätselement existieren, und für jedes Element muss ein inverses Element unter dem Operator existieren.

Einige Gruppen werden analog zur Addition geschrieben, d. h. der Gruppenoperator wird durch ein „+“-Zeichen dargestellt, und das Identitätselement wird durch „0“ dargestellt. Andere Gruppen werden analog zur Multiplikation geschrieben, dh der Gruppenoperator wird als Multiplikationsoperation geschrieben (z. B. „*“, „.“ oder gar nichts) und das Identitätselement wird durch „1“ dargestellt. Elliptische Kurven werden traditionell in Analogie zur Addition geschrieben.

Wir können uns vorstellen, den Gruppenoperator wiederholt auf k Kopien von G anzuwenden. Wenn die Gruppe in Analogie zur Addition geschrieben wird, ist dies analog zur Multiplikation, wenn die Gruppe in Analogie zur Multiplikation geschrieben wird, dann ist dies analog zur Potenzierung.

Bezieht sich also k * Gnicht auf eine reguläre Multiplikation, sondern auf eine Operation, die der Multiplikation in gewisser Weise analog ist.

Sie könnten naiv denken, dass dies proportional zu k Zeit in Anspruch nehmen würde, aber dank der Assoziativität können wir die Zeit proportional zum Logarithmus von k berechnen. So können wir k * Gauch für sehr große k schnell rechnen.

Die Umkehrung des Vorgangs ist jedoch nicht so einfach. Das Problem ist als "Elliptische-Kurven-Diskreter-Logarithmus-Problem" bekannt, und die bekanntesten Methoden haben eine Komplexität, die ungefähr proportional zur Quadratwurzel der Anzahl der Elemente in der Gruppe ist.

Warum wird es als "Problem des diskreten Logarithmus bei elliptischen Kurven" bezeichnet, wenn es in der Notation, die normalerweise für elliptische Kurven verwendet wird, eher einer Division als einem Logarithmus entspricht? weil es eine Variante eines ähnlichen Problems ist, das für eine Gruppe untersucht wurde, die traditionell in Analogie zur Multiplikation geschrieben wird.

"Andere Gruppen werden in Analogie zur Multiplikation geschrieben, das heißt die . Elliptische Kurven werden traditionell in Analogie zur Addition geschrieben." Da sind wohl ein paar Worte gefressen worden. Außerdem schlage ich vor, den vollständigen Namen "diskreter Logarithmus" anstelle des abgekürzten "diskreten Logarithmus" zu verwenden, da es für einen Profanen nicht unbedingt offensichtlich ist, was dieser "Log" bedeutet.

k = K/G ist eine etwas irreführende Schreibweise. In vielerlei Hinsicht ist es besser, k = K * G^-1 zu schreiben. Dies betont, dass bei der "Division" zwei Operationen beteiligt sind : Multiplikation und Umkehrung (Außerdem macht es leichter zu erkennen, dass K * G^-1 und G^-1 * K unterschiedliche Konzepte sind und dass die Existenz von Es muss gezeigt werden, dass G^-1 existiert. Dies ist hier nicht so wichtig, da die Multiplikation mit elliptischen Kurven abelsch ist und immer eine Umkehrung hat, aber dies sind Überlegungen, die Sie berücksichtigen müssen, wenn Sie sich mit Gruppen und Ringen im Allgemeinen befassen. )

Elliptische-Kurven-Mathematik findet in einer abstrakten Gruppe statt, nicht innerhalb des reellen Zahlensystems, und die Verwendung der Notation reeller Zahlen fördert eine irreführende Intuition (und in der abstrakten Algebra wird der Schrägstrich für Quotientengruppen verwendet, nicht zum Teilen von Elementen einer Gruppe). Die Tatsache, dass es schwierig ist, in der Mathematik mit elliptischen Kurven die Inverse zu nehmen, macht es überhaupt erst zu einem kryptografischen System. Andernfalls könnte jeder, der den öffentlichen Schlüssel hatte, die Verschlüsselung ziemlich trivial umkehren. "Kryptografisches System" bezieht sich fast per Definition auf ein System mit einer Operation, bei der das Finden von a * b erheblich einfacher ist als das Finden von a ^ -1.

(Es gibt Möglichkeiten, K * G^-1 zu berechnen, ohne G^-1 explizit zu berechnen, aber sie sind immer noch so schwierig oder schwieriger als G^-1 zu finden.)

Und wenn nicht, wie wird er aus dem privaten Schlüssel erstellt?

Häh? Sie haben gerade die Gleichung für den öffentlichen Schlüssel angegeben: K = k * G.

Ich denke auch, dass Sie in den Hauptteil Ihres Textes aufnehmen sollten, dass Sie über secp256k1 sprechen, und nicht nur als Tag. Man könnte daraus schließen, dass es sich um Bitcoin SE handelt, aber es ist gut, wenn es explizit ist.

Ich finde diese Erklärung mehr Verwirrung, um ehrlich zu sein. G^-1 kann man nicht berechnen. Was wäre seine Art? Kein Punkt, denn dann wäre K G^-1 Punkt^2, der nicht existiert. Und kein Skalar, denn dann wäre K G^-1 ein Punkt. Sie müssten ein Konzept der "invertierten Punkte" einführen, das AFAIK nicht existiert und das auch nichts damit zu tun hat, wie K / G in Algorithmen wie Pollards Rho tatsächlich berechnet wird ... die tatsächlich K und G als Eingaben verwenden - nicht nur G - und Ausgabe k.
@PieterWuille: Sie wenden fälschlicherweise echte Arithmetik auf abstrakte Algebra an, genau wie Accumulation davor gewarnt hat. Der "Typ" eines Produkts über einer abstrakten Gruppe hat Einheiten, die das Produkt der Einheiten der beiden Eingaben sind, aber die Dimension ist nicht so einfach. Beispielsweise hat ein 3D-Vektor-Kreuzprodukt genau wie beide Eingaben 3D, und ein Vektor-Skalarprodukt ergibt einen Skalar, unabhängig von der Dimension der Eingaben. Ein weiteres Beispiel: Eine quadratische Matrix hat eine Inverse mit der gleichen Dimension wie sie selbst, und das bereitet keine Probleme, wenn man die invertierte Matrix mit Spaltenvektoren multipliziert.
Die Antwort lautet wörtlich "... aber sie sind immer noch so schwer oder schwieriger als G^-1 zu finden". Dies ist nach meinem besten Wissen eine falsche Aussage, da es keine bekannte Möglichkeit gibt, G^-1 zu berechnen (selbst wenn man die Frage ignoriert, was sein Typ wäre). Algorithmen zur Berechnung eines diskreten Logarithmus (= Division zweier Gruppenelemente) nehmen zwei Gruppenelemente als Eingabe. Sie berechnen nicht das Gegenteil von einem und multiplizieren es dann mit dem anderen. Sie könnten sicherlich "Inverse eines Gruppenelements mit Skalarmultiplikation" als ein abstraktes Objekt definieren, aber so würden Sie es nicht berechnen.
Hier ist noch mehr falsch. Die Umkehrung, über die wir sprechen, ist die Umkehrung der Skalarmultiplikation (Zahl mal Gruppenelement), nicht die Umkehrung der Gruppenoperation selbst (Gruppenelement plus Gruppenelement). Letztere existiert für jedes Element in jeder Gruppe (einschließlich nicht-abelscher Gruppen). Ersteres existiert jedoch, wenn man es definieren möchte, sicherlich nicht für jedes Element einer abelschen Gruppe; Dies gilt für jedes Element ungleich Null in secp, da es zyklisch mit Primzahlordnung ist, aber im Allgemeinen existiert es nicht für Elemente mit nicht maximaler Ordnung in der Gruppe.
Warum ist es nicht möglich, den privaten Schlüssel aus dem öffentlichen Schlüssel zu bekommen?
AntwortenHierDatenschutz-Bestimmungen1y, 0v