CRYSTALS-Dilithium- und Falcon-Signaturen

RSA- und ECDSA-Signaturen werden durch Shors Algorithmus gebrochen. Post-Quanten-Signaturen müssen sie in folgenden Bereichen ersetzen: TLS-Zertifikate, Codesignierung, E-Mail-Signierung (S/MIME, PGP) und Authentifizierung von Softwareupdates. Das NIST hat zwei gitterbasierte Verfahren standardisiert: ML-DSA und FN-DSA.

Dilithium basiert auf der Schwierigkeit von Module-LWE und Module-SIS (Short Integer Solution). Der Sicherheitsnachweis gilt im QROM (Quantum Random Oracle Model). Es gibt drei Varianten: Dilithium2 (etwa 128 Bit), Dilithium3 (etwa 192 Bit) und Dilithium5 (etwa 256 Bit). Der Signaturpfad ist einfach und kommt ohne Rejection Sampling aus.

Privater Schlüssel: geheime Matrizen s1, s2. Öffentlicher Schlüssel: t = As1 + s2. Signieren: Ziehen Sie ein zufälliges y; berechnen Sie w = Ay; berechnen Sie die Challenge c = H(mu || w1), wobei w1 = HighBits(w); berechnen Sie z = y + cs1; falls ||z|| oder ||r0|| zu groß ist, verwerfen Sie den Versuch und starten Sie erneut. Ausgabe (z, c, hint).

Verifizieren Sie (z, c, hint): Prüfen Sie, ob ||z|| klein ist; berechnen Sie w' = Az - ct; verwenden Sie hint, um w1 wiederherzustellen; prüfen Sie c == H(mu || w1). Der Hinweis besteht aus einer kleinen Anzahl von Bits aus MakeHint(). Die Ablehnung stellt sicher, dass s1 nicht aus z preisgegeben wird – das Sicherheitsargument ist ein „aborts-then-uniform“-Argument.

ML-DSA-65 (Dilithium3, 192-Bit-Sicherheit): öffentlicher Schlüssel 1952 Byte, privater Schlüssel 4000 Byte, Signatur 3293 Byte. Zum Vergleich: ECDSA-P256: öffentlicher Schlüssel 64 Byte, Signatur 64 Byte. Dilithium-Signaturen sind etwa 40- bis 50-mal größer, aber quantensicher.

Falcon basiert auf NTRU-Gittern und verwendet einen Gauß-Sampler über dem NTRU-Gitter. Die Signaturen sind deutlich kleiner als bei Dilithium, aber zum Signieren ist ein G​​auß-Sampler mit Gleitkommaarithmetik erforderlich – dadurch ist eine Implementierung in konstanter Zeit schwieriger und eine sichere Programmierung komplexer.

Falcon-512 (128-Bit-Sicherheit): öffentlicher Schlüssel 897 Byte, Signatur 666 Byte – deutlich kleiner als bei Dilithium. Der Nachteil: Falcon ist schwieriger sicher zu implementieren (Gauß-Sampling ist anfällig für Timing-Angriffe). Das Verfahren eignet sich für Umgebungen mit begrenzter Bandbreite, erfordert aber eine sorgfältige Implementierung.

SPHINCS+ ist ein hashbasiertes Signaturverfahren – eine konservative Wahl ohne strukturelle algebraische Annahmen. Die Sicherheit beruht ausschließlich auf der Sicherheit der Hashfunktion. Signaturgröße: etwa 8–50 KB (groß). Langsames Signieren. Wird eingesetzt, wenn langfristiges Vertrauen entscheidend ist und Leistung eine nachrangige Rolle spielt.

ML-DSA (Dilithium): universell einsetzbar, einfache Implementierung, gut geeignet für TLS-Zertifikate und Codesignierung. FN-DSA (Falcon): Umgebungen mit begrenzter Bandbreite (IoT, LPWAN). SLH-DSA (SPHINCS+): äußerst konservativ, für langlebige Vertrauensanker (offline gehaltene CA-Schlüssel, Software-Root of Trust).

Dilithium: Rejection Sampling kann die Verzweigungsdauer preisgeben – verwenden Sie Vergleiche in konstanter Zeit. Falcon: Der Gauß-Sampler verwendet Gleitkommaarithmetik – stellen Sie die Deterministik der Gleitkommaarithmetik sicher. Für beide Verfahren gilt: Vermeiden Sie Seitenkanäle in der Polynom-Arithmetik. Verwenden Sie Referenzimplementierungen aus den NIST-Einreichungspaketen.

NIST FIPS 204: ML-DSA (Dilithium). NIST FIPS 205: SLH-DSA (SPHINCS+). NIST FIPS 206: FN-DSA (Falcon). Alle wurden im August 2024 veröffentlicht. Bibliotheken wie OpenSSL 3.x, BoringSSL und liboqs (Open Quantum Safe project) implementieren alle drei Verfahren.

ML-DSA (Dilithium): gitterbasiert, einfach, Signaturen von etwa 3 KB. FN-DSA (Falcon): NTRU-basiert, Signaturen von etwa 700 Byte, komplexe Implementierung. SLH-DSA (SPHINCS+): hashbasiert, konservativ, groß. Alle sind in FIPS 204/205/206 standardisiert. Als Nächstes: die Migration zu PQC mit hybriden Ansätzen.