5. The X25519 and X448 Functions (Die X25519- und X448-Funktionen)

Die Funktionen »X25519« und »X448« führen Skalarmultiplikationen auf der Montgomery-Form der obigen Kurven aus. (Dies wird bei der Implementierung von Diffie-Hellman verwendet.) Die Funktionen nehmen einen Skalar und eine u-Koordinate als Eingaben und liefern eine u-Koordinate als Ausgabe. Obwohl die Funktionen intern mit ganzen Zahlen arbeiten, sind die Ein- und Ausgaben 32-Byte-Zeichenketten (für X25519) bzw. 56-Byte-Zeichenketten (für X448), und diese Spezifikation definiert deren Kodierung.

Die u-Koordinaten sind Elemente des zugrunde liegenden Körpers GF(2^255 - 19) bzw. GF(2^448 - 2^224 - 1) und werden als Byte-Array u in Little-Endian-Reihenfolge kodiert, sodass u[0] + 256u[1] + 256^2u[2] + ... + 256^(n-1)*u[n-1] dem Wert modulo p kongruent ist und u[n-1] minimal ist. Beim Empfang eines solchen Arrays MÜSSEN Implementierungen von X25519 (nicht jedoch X448) das höchstwertige Bit im letzten Byte maskieren. Dies geschieht, um die Kompatibilität mit Punktformaten zu wahren, die das Vorzeichenbit für andere Protokolle reservieren, und um die Widerstandsfähigkeit gegen Implementierungs-Fingerprinting zu erhöhen.

Implementierungen MÜSSEN nicht-kanonische Werte akzeptieren und so verarbeiten, als wären sie modulo der Körperprimzahl reduziert worden. Die nicht-kanonischen Werte sind 2^255 - 19 bis 2^255 - 1 für X25519 und 2^448 - 2^224 - 1 bis 2^448 - 1 für X448.

Die folgenden Funktionen implementieren dies in Python, wobei der Python-Code weder leistungsorientiert noch seitenkanalfrei sein soll. Hier ist der Parameter »bits« für X25519 auf 255 und für X448 auf 448 zu setzen:

def decodeLittleEndian(b, bits):
    return sum([b[i] << 8*i for i in range((bits+7)/8)])

def decodeUCoordinate(u, bits):
    u_list = [ord(b) for b in u]
    # Ignore any unused bits.
    if bits % 8:
        u_list[-1] &= (1<<(bits%8))-1
    return decodeLittleEndian(u_list, bits)

def encodeUCoordinate(u, bits):
    u = u % p
    return ''.join([chr((u >> 8*i) & 0xff)
                    for i in range((bits+7)/8)])

Skalare werden als zufällig erzeugte Bytes angenommen. Für X25519 setzt man, um 32 Zufallsbytes als ganzzahligen Skalar zu dekodieren, die drei niederwertigsten Bits des ersten Bytes und das höchstwertige Bit des letzten Bytes auf null, das zweithöchstwertige Bit des letzten Bytes auf 1 und dekodiert anschließend als Little-Endian. Das bedeutet, dass die resultierende ganze Zahl von der Form 2^254 plus dem Achtfachen eines Werts zwischen 0 und 2^251 - 1 (einschließlich) ist. Entsprechend setzt man für X448 die zwei niederwertigsten Bits des ersten Bytes auf 0 und das höchstwertige Bit des letzten Bytes auf 1. Das bedeutet, dass die resultierende ganze Zahl von der Form 2^447 plus dem Vierfachen eines Werts zwischen 0 und 2^445 - 1 (einschließlich) ist.

def decodeScalar25519(k):
    k_list = [ord(b) for b in k]
    k_list[0] &= 248
    k_list[31] &= 127
    k_list[31] |= 64
    return decodeLittleEndian(k_list, 255)

def decodeScalar448(k):
    k_list = [ord(b) for b in k]
    k_list[0] &= 252
    k_list[55] |= 128
    return decodeLittleEndian(k_list, 448)

Zur Implementierung der Funktionen X25519(k, u) und X448(k, u) (wobei k der Skalar und u die u-Koordinate ist) dekodiert man zuerst k und u und führt dann das folgende Verfahren aus, das aus [curve25519] stammt und auf Formeln aus [montgomery] basiert. Alle Berechnungen erfolgen in GF(p), d. h. sie werden modulo p ausgeführt. Die Konstante a24 ist (486662 - 2) / 4 = 121665 für curve25519/X25519 und (156326 - 2) / 4 = 39081 für curve448/X448.

x_1 = u
x_2 = 1
z_2 = 0
x_3 = u
z_3 = 1
swap = 0

For t = bits-1 down to 0:
    k_t = (k >> t) & 1
    swap ^= k_t
    // Conditional swap; see text below.
    (x_2, x_3) = cswap(swap, x_2, x_3)
    (z_2, z_3) = cswap(swap, z_2, z_3)
    swap = k_t

    A = x_2 + z_2
    AA = A^2
    B = x_2 - z_2
    BB = B^2
    E = AA - BB
    C = x_3 + z_3
    D = x_3 - z_3
    DA = D * A
    CB = C * B
    x_3 = (DA + CB)^2
    z_3 = x_1 * (DA - CB)^2
    x_2 = AA * BB
    z_2 = E * (AA + a24 * E)

// Conditional swap; see text below.
(x_2, x_3) = cswap(swap, x_2, x_3)
(z_2, z_3) = cswap(swap, z_2, z_3)
Return x_2 * (z_2^(p - 2))

(Hinweis: Diese Formeln weichen geringfügig von Montgomerys Originalarbeit ab. Implementierungen dürfen beliebige korrekte Formeln verwenden.)

Schließlich kodiert man den resultierenden Wert als 32 bzw. 56 Bytes in Little-Endian-Reihenfolge. Für X25519 MUSS das ungenutzte höchstwertige Bit null sein.

Die Funktion cswap SOLLTE in konstanter Zeit implementiert werden (d. h. unabhängig vom Argument swap). Beispielsweise kann dies wie folgt geschehen:

cswap(swap, x_2, x_3):
      dummy = mask(swap) AND (x_2 XOR x_3)
      x_2 = x_2 XOR dummy
      x_3 = x_3 XOR dummy
      Return (x_2, x_3)

Dabei ist mask(swap) das nur aus Einsen oder nur aus Nullen bestehende Wort gleicher Länge wie x_2 und x_3, berechnet z. B. als mask(swap) = 0 - swap.

5.1. Side-Channel Considerations (Seitenkanalüberlegungen)

X25519 und X448 sind so ausgelegt, dass sich schnelle, zeitkonstante Implementierungen leichter erzeugen lassen. Das obige Verfahren stellt sicher, dass für alle Werte des Geheimnisschlüssels dieselbe Folge von Körperoperationen ausgeführt wird und damit eine häufige Quelle von Seitenkanal-Leckagen beseitigt wird. Allein dadurch werden jedoch nicht alle Seitenkanäle verhindert. Es ist wichtig, dass das Muster von Speicherzugriffen und Sprüngen nicht von den Werten der Bits von k abhängt. Ebenso wichtig ist, dass die verwendete Arithmetik keine Information über die ganzen Zahlen modulo p verrät, etwa indem sich bc von cc unterscheiden lässt. Auf manchen Architekturen können selbst elementare Maschinenbefehle, etwa ein Wort-Divisionsbefehl, je nach Eingaben variable Laufzeiten haben.

Seitenkanalangriffe sind ein aktives Forschungsfeld mit weiterhin vielen neuen Ergebnissen. Implementierer sollten dieser Forschung engmaschig folgen.

5.2. Test Vectors (Testvektoren)

Es werden zwei Arten von Tests bereitgestellt. Die erste ist ein Paar von Testvektoren für jede Funktion, das aus den erwarteten Ausgaben für die gegebenen Eingaben besteht. Die Eingaben sind im Allgemeinen als 64 bzw. 112 hexadezimale Ziffern angegeben, die vor der Verarbeitung als 32 bzw. 56 binäre Bytes zu dekodieren sind.

X25519:

Eingabeskalar:

a546e36bf0527c9d3b16154b82465edd62144c0ac1fc5a18506a2244ba449ac4

Eingabeskalar als Zahl (Basis 10):

31029842492115040904895560451863089656472772604678260265531221036453811406496

Eingabe-u-Koordinate:

e6db6867583030db3594c1a424b15f7c726624ec26b3353b10a903a6d0ab1c4c

Eingabe-u-Koordinate als Zahl (Basis 10):

34426434033919594451155107781188821651316167215306631574996226621102155684838

Ausgabe-u-Koordinate:

c3da55379de9c6908e94ea4df28d084f32eccf03491c71f754b4075577a28552

Eingabeskalar:

4b66e9d4d1b4673c5ad22691957d6af5c11b6421e0ea01d42ca4169e7918ba0d

Eingabeskalar als Zahl (Basis 10):

35156891815674817266734212754503633747128614016119564763269015315466259359304

Eingabe-u-Koordinate:

e5210f12786811d3f4b7959d0538ae2c31dbe7106fc03c3efc4cd549c715a493

Eingabe-u-Koordinate als Zahl (Basis 10):

8883857351183929894090759386610649319417338800022198945255395922347792736741

Ausgabe-u-Koordinate:

95cbde9476e8907d7aade45cb4b873f88b595a68799fa152e6f8f7647aac7957

X448:

Eingabeskalar:

3d262fddf9ec8e88495266fea19a34d28882acef045104d0d1aae121700a779c984c24f8cdd78fbff44943eba368f54b29259a4f1c600ad3

Eingabeskalar als Zahl (Basis 10):

599189175373896402783756016145213256157230856085026129926891459468622403380588640249457727683869421921443004045221642549886377526240828

Eingabe-u-Koordinate:

06fce640fa3487bfda5f6cf2d5263f8aad88334cbd07437f020f08f9814dc031ddbdc38c19c6da2583fa5429db94ada18aa7a7fb4ef8a086

Eingabe-u-Koordinate als Zahl (Basis 10):

382239910814107330116229961234899377031416365240571325148346555922438025162094455820962429142971339584360034337310079791515452463053830

Ausgabe-u-Koordinate:

ce3e4ff95a60dc6697da1db1d85e6afbdf79b50a2412d7546d5f239fe14fbaadeb445fc66a01b0779d98223961111e21766282f73dd96b6f

Eingabeskalar:

203d494428b8399352665ddca42f9de8fef600908e0d461cb021f8c538345dd77c3e4806e25f46d3315c44e0a5b4371282dd2c8d5be3095f

Eingabeskalar als Zahl (Basis 10):

633254335906970592779259481534862372382525155252028961056404001332122152890562527156973881968934311400345568203929409663925541994577184

Eingabe-u-Koordinate:

0fbcc2f993cd56d3305b0b7d9e55d4c1a8fb5dbb52f8e9a1e9b6201b165d015894e56c4d3570bee52fe205e28a78b91cdfbde71ce8d157db

Eingabe-u-Koordinate als Zahl (Basis 10):

622761797758325444462922068431234180649590390024811299761625153767228042600197997696167956134770744996690267634159427999832340166786063

Ausgabe-u-Koordinate:

884a02576239ff7a2f2f63b2db6a9ff37047ac13568e1e30fe63c4a7ad1b3ee3a5700df34321d62077e63633c575c1c954514e99da7c179d

Die zweite Art von Testvektor besteht aus dem Ergebnis wiederholter Aufrufe der jeweiligen Funktion. Zunächst setzt man k und u auf die folgenden Werte:

Für X25519:

0900000000000000000000000000000000000000000000000000000000000000

Für X448:

050000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

In jeder Iteration setzt man k auf das Ergebnis des Funktionsaufrufs und u auf den alten Wert von k. Das Endergebnis ist der verbleibende Wert in k.

X25519:

Nach einer Iteration:

422c8e7a6227d7bca1350b3e2bb7279f7897b87bb6854b783c60e80311ae3079

Nach 1.000 Iterationen:

684cf59ba83309552800ef566f2f4d3c1c3887c49360e3875f2eb94d99532c51

Nach 1.000.000 Iterationen:

7c3911e0ab2586fd864497297e575e6f3bc601c0883c30df5f4dd2d24f665424

X448:

Nach einer Iteration:

3f482c8a9f19b01e6c46ee9711d9dc14fd4bf67af30765c2ae2b846a4d23a8cd0db897086239492caf350b51f833868b9bc2b3bca9cf4113

Nach 1.000 Iterationen:

aa3b4749d55b9daf1e5b00288826c467274ce3ebbdd5c17b975e09d4af6c67cf10d087202db88286e2b79fceea3ec353ef54faa26e219f38

Nach 1.000.000 Iterationen:

077f453681caca3693198420bbe515cae0002472519b3e67661a7e89cab94695c8f4bcd66e61b9b9c946da8d524de3d69bd9d9d66b997e37