Wie kann man feststellen, ob ein öffentlicher Schlüsselpunkt y negativ oder positiv, ungerade oder gerade ist?

Nehmen Sie einen öffentlichen Bitcoin-Schlüssel (x, y) und sein additives Inverses (x, -y). Wie erkennen Sie, was der positive Punkt und was der negative Punkt ist?

Beispiel

Privater Schlüssel 1 -> (x, y)

x = 0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798L

y = 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8L

-y = 0xb7c52588d95c3b9aa25b0403f1eef75702e84bb7597aabe663b82f6f04ef2777L

Privater Schlüssel 2 -> (x, y)

x = 0xc6047f9441ed7d6d3045406e95c07cd85c778e4b8cef3ca7abac09b95c709ee5L

y = 0x1ae168fea63dc339a3c58419466ceaeef7f632653266d0e1236431a950cfe52aL

-y = 0xe51e970159c23cc65c3a7be6b99315110809cd9acd992f1edc9bce55af301705L

Privater Schlüssel 3 -> (x, y)

x = 0xf9308a019258c31049344f85f89d5229b531c845836f99b08601f113bce036f9L

y = 0x388f7b0f632de8140fe337e62a37f3566500a99934c2231b6cb9fd7584b8e672L

-y = 0xc77084f09cd217ebf01cc819d5c80ca99aff5666cb3ddce4934602897b4715bdL

Wie können Sie außerdem feststellen, welcher Pub-Schlüssel ungerade und welcher gerade ist?

Beispiel: privater Schlüssel 1 x,y ist ungerade, privater Schlüssel 2 x,y ist gerade

Ich verstehe die Frage nicht. x und y sind dabei Elemente des endlichen Körpers F_p, bei dem es im Allgemeinen keine eindeutige Bedeutung von „ungerade“ und „gerade“ gibt – jede Zahl ist bezüglich der Körpermultiplikation durch 2 teilbar. Es gibt ein ähnliches Problem mit "positiv" und "negativ", da F_p kein geordnetes Feld ist.
@NateEldredge, ich denke, Prabu möchte wissen, ob der Punkt aus einem ungeraden/gerade privaten Schlüssel generiert wurde oder nicht, und nicht, ob die resultierenden Koordinaten ungerade/gerade sind.

Antworten (2)

Es gibt keine konkrete Bestimmung, die einen 'y'-Wert in einem EC-Punkt negativ macht oder nicht. Fühlen Sie sich frei, Ihre eigene Konvention zu treffen, wie z. B. y-Werte <= als die Hälfte von p negativ und > die Hälfte von p positiv sind. Das ist aber nur eine Konvention.

Verwandt:

Wie können Sie außerdem feststellen, welcher Pub-Schlüssel ungerade und welcher gerade ist?

Beispiel: privater Schlüssel 1 x,y ist ungerade, privater Schlüssel 2 x,y ist gerade

Du kannst nicht! Nicht ohne den privaten Schlüssel selbst zu kennen. Wenn Sie könnten, wären Sie ein Teil des Weges zur Lösung des diskreten Protokollproblems .

Hallo StephenM347, y-Werte <= als die Hälfte von p sind negativ und > die Hälfte von p sind positiv. Bitte können Sie dies anhand eines Beispiels klar erläutern
Wie würde man das Problem des diskreten Logarithmus lösen, wenn man wüsste, ob Y positiv, negativ, ungerade oder gerade ist? Würde es die Kryptographie absolut brechen oder nur die Feldsuche einschränken, um einen privaten Schlüssel zu finden?
@PedroGonçalves Zu wissen, ob die Y-Koordinate ungerade oder gerade ist, ist natürlich keine Unterbrechung, da es sich um öffentliche Informationen handelt. Zu wissen, ob die Y-Koordinate "positiv oder negativ" ist, hängt davon ab, wie Sie positiv oder negativ definieren (wie in dieser Antwort angegeben, können Sie Ihre eigene Konvention erstellen). WENN Sie es als "der entsprechende private Schlüssel ist gerade/ungerade" definieren, ist das Wissen, ob Y positiv oder negativ ist, tatsächlich eine Sicherheitslücke (Sie sollten keine Informationen über den privaten Schlüssel ableiten können).

Sehen wir uns das etwas formaler an.

Angenommen, es gibt eine Funktion lsbPriv(P), die das LSB des privaten Schlüssels kvom öffentlichen Schlüssel zurückgibt, P = [k]Gwo Gder Basispunkt ist.

Nun können wir diese Funktion verwenden, um alle Bits des privaten Schlüssels kwie folgt zu bestimmen;

func DlogbyLSB(P)
  for i in range(1..256)
    x = lsbPriv(P)
    secretKey.append(x)
    if x == 0 then    ; test the bit
      P = [2^-1]P     ; i.e. we can divide `k` by `2` since the last bit is `0`
   else 
      P = [1]G        ; i.e. we substructed the bit `1` from the `k` and 
      P = [2^-1]P    ; now it is again divisible by `2`
   return secretKey

Dies ist fast wie die Umkehrung des Double-and-Add- Algorithmus, der die Skalarmultiplikation auf den elliptischen Kurven berechnet.

Mit Hilfe von lsbPrivkönnen wir also jedes Bit des privaten Schlüssels lernen k. In der Kryptographie bezeichnen wir dies lsb bitals Hardcore-Prädikat . Wie wir sehen können, lsbPriventhüllt das nach den 256 Aufrufen den Schlüssel. Es ist also lsbprivso schwierig, alle Bits wiederherzustellen.

Dies impliziert auch, dass eine solche lsbPrivFunktion, wenn sie existiert, gleichbedeutend mit der Lösung des DlogProblems auf der Kurve ist Secp256k. Derzeit wissen wir, dass dies schwierig ist, daher gibt es keine solche lsbPrivFunktion.

Wie kann man feststellen, ob ein öffentlicher Schlüsselpunkt y negativ oder positiv, ungerade oder gerade ist?
AntwortenHierDatenschutz-Bestimmungen1y, 0v