5.1.3 Decoding (Dekodierung)

5.1.3 Decoding (Dekodierung)

Die Dekodierung eines als 32-Oktett-Zeichenkette gegebenen Punkts ist etwas komplizierter.

1. Zuerst wird die Zeichenkette als Ganzzahl in Little-Endian-Darstellung interpretiert. Bit 255 dieser Zahl ist das niedrigstwertige Bit der x-Koordinate; dieser Wert heiße x_0. Die y-Koordinate erhält man einfach durch Löschen dieses Bits. Ist der resultierende Wert >= p, schlägt die Dekodierung fehl.

2. Zur Wiederherstellung der x-Koordinate liefert die Kurvengleichung x^2 = (y^2 - 1) / (d y^2 + 1) (mod p). Der Nenner ist modulo p stets ungleich null. Sei u = y^2 - 1 und v = d y^2 + 1. Um die Quadratwurzel von (u/v) zu berechnen, ist der erste Schritt die Kandidatenwurzel x = (u/v)^((p+3)/8). Dies lässt sich mit folgendem Trick mit einer einzigen modularen Potenzierung sowohl für die Inversion von v als auch für die Quadratwurzel erledigen:

                 (p+3)/8      3        (p-5)/8
        x = (u/v)        = u v  (u v^7)         (mod p)

3. Wiederum gibt es drei Fälle:

   1. Wenn v x^2 = u (mod p), ist x eine Quadratwurzel.

   2. Wenn v x^2 = -u (mod p), setze x <-- x * 2^((p-1)/4), was eine Quadratwurzel ist.

   3. Andernfalls existiert keine Quadratwurzel modulo p, und die Dekodierung schlägt fehl.

4. Schließlich wählt man mit dem Bit x_0 die richtige Quadratwurzel. Wenn x = 0 und x_0 = 1, schlägt die Dekodierung fehl. Andernfalls, wenn x_0 != x mod 2, setze x <-- p - x. Gib den dekodierten Punkt (x,y) zurück.