5.2.3 Decoding (Dekodierung)

5.2.3 Decoding (Dekodierung)

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

1. Zuerst die Zeichenkette als Ganzzahl in Little-Endian-Darstellung interpretieren. Bit 455 dieser Zahl ist das niederwertigste Bit der x-Koordinate; dieser Wert sei x_0. Die y-Koordinate wird gewonnen, indem dieses Bit gelöscht wird. Ist der resultierende Wert >= p, schlägt die Dekodierung fehl.

2. Zur Wiederherstellung der x-Koordinate impliziert 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+1)/4). Mit folgendem Trick kann sowohl die Inversion von v als auch die Quadratwurzel in einer einzigen modularen Potenzierung erfolgen:

                         (p+1)/4    3            (p-3)/4
                x = (u/v)        = u  v (u^5 v^3)         (mod p)

3. Wenn v * x^2 = u, ist die wiederhergestellte x-Koordinate x. Andernfalls existiert keine Quadratwurzel, und die Dekodierung schlägt fehl.

4. Schließlich das Bit x_0 verwenden, um die richtige Quadratwurzel zu wählen. Wenn x = 0 und x_0 = 1, schlägt die Dekodierung fehl. Andernfalls, wenn x_0 != x mod 2, setze x <- p - x. Den dekodierten Punkt (x,y) zurückgeben.