Signaturverfahren

FALCON mathematisch erklärt

Wie eine McGesund-Bewertung mit FN-DSA (FALCON) unterschrieben wird — und warum ein geändertes Zeichen die Unterschrift bricht.

Stand: 2026-09-07

1. Worum es hier geht

Eine Bewertung bei McGesund ist kein Textfeld in einer Datenbank, dem man glauben muss. Sie wird beim Absenden digital signiert, und jeder Besucher kann diese Signatur später im eigenen Browser nachrechnen.

Für einen Teil dieser Signaturen verwenden wir FALCON — genauer FN-DSA-512 und FN-DSA-1024. Dieser Beitrag erklärt, was dabei mathematisch passiert.

Wichtig vorweg:

FALCON ist keine Verschlüsselung. Der Bewertungstext soll ja gelesen werden. FALCON beweist nicht Geheimhaltung, sondern Herkunft und Unversehrtheit.

2. Was genau unterschrieben wird

Signiert wird nicht der Fließtext, sondern ein kompaktes Datenobjekt, das den Text eindeutig festnagelt:

{
  "v":   1,
  "typ": "rev-comment",
  "f":   "<Firmen-ID>",
  "c":   "<Bewertungs-ID>",
  "h":   "<SHA-256 des Bewertungstexts>",
  "rh":  "<SHA-256 des ganzen Abgabe-Datensatzes>",
  "rv":  1,
  "qh":  "<SHA-256 des QR-Envelopes, nur bei QR-Bewertungen>",
  "iat": 1757203200
}

Das ist unsere Nachricht mm. Sie bindet zusammen:

  1. zu welchem Unternehmen die Bewertung gehört (f),
  2. um welche Bewertung es geht (c),
  3. welcher Text dahinterstand — als Hashwert (h),
  4. welcher Datensatz insgesamt abgegeben wurde (rh): Text, Herzen, Geo-Status und Anlass-Angaben, kanonisch serialisiert und gehasht, in der Schema-Version rv,
  5. aus welchem QR-Code die Bewertung stammt (qh) — bei einer Bewertung ohne QR entfällt das Feld,
  6. wann signiert wurde (iat).

Ein geändertes Zeichen im Bewertungstext bricht diese Kette. Genau das ist der Zweck — und seit rh gilt dasselbe für ein nachträglich verschobenes Herz oder einen geänderten Geo-Status.

3. Das Grundproblem

Ein Leser, der auf ein Unternehmensprofil kommt, steht vor zwei Fragen:

  1. Stammt diese Bewertung wirklich aus dem McGesund-System?
  2. Wurde sie nachträglich verändert?

Dafür gibt es ein Schlüsselpaar:

  • einen privaten Schlüssel — bleibt im Signaturdienst
  • einen öffentlichen Schlüssel — darf jeder haben

Signiert wird mit dem privaten, geprüft mit dem öffentlichen Schlüssel. Und zwar auf dem Gerät des Lesers, nicht auf unserem Server.

4. Warum FALCON?

Viele heutige Signaturverfahren beruhen auf Problemen, die für klassische Rechner schwer sind, für hinreichend große Quantencomputer aber deutlich leichter werden könnten.

Bei einer Bewertung ist das relevanter als bei einer flüchtigen Nachricht: Eine Bewertung soll in fünf oder zehn Jahren noch überprüfbar sein. Wer heute unterschreibt, unterschreibt für die gesamte Lebensdauer des Eintrags.

FALCON beruht deshalb auf Gitterkryptografie:

Man baut ein mathematisch einfach beschreibbares Gitter, in dem eine bestimmte Suchaufgabe extrem schwer ist.

5. Was ist ein mathematisches Gitter?

Zwei Vektoren:

v1=(2,0),v2=(1,2).v_1=(2,0), \qquad v_2=(1,2).

Alle ganzzahligen Kombinationen

a v1+b v2,a,b∈Za\,v_1+b\,v_2, \qquad a,b\in\mathbb{Z}

ergeben ein Gitter aus Punkten. Zum Beispiel:

2v1+3v2=(4,0)+(3,6)=(7,6).2v_1+3v_2=(4,0)+(3,6)=(7,6).
v₁ = (2,0)v₂ = (1,2)(7,6)0
Zwei Vektoren spannen ein Gitter auf. Jeder Punkt ist eine ganzzahlige Kombination der beiden — der markierte entsteht aus zweimal v₁ und dreimal v₂.

Entscheidend ist:

Das Gitter selbst ist leicht zu beschreiben. Bestimmte Eigenschaften darin zu finden, ist sehr schwer.

6. Das Geheimnis sind kurze Vektoren

Die klassische schwere Aufgabe lautet:

min⁡v∈L,  v≠0∥v∥.\min_{v\in L,\;v\neq0}\|v\|.

Das ist das Shortest Vector Problem. In zwei Dimensionen kann man es durchprobieren. FALCON arbeitet in Dimension 512 oder 1024 — dort ist es aussichtslos.

lange Basisfast parallelkürzester Vektor
Dasselbe Gitter, zwei Beschreibungen. Die grauen Vektoren erzeugen es ebenfalls, sind aber lang und fast parallel — eine schlechte Basis. Der kurze Vektor ist das, was schwer zu finden ist.

FALCON braucht allerdings nicht den kürzesten Vektor schlechthin, sondern etwas Verwandtes: zu einem vorgegebenen Zielpunkt einen nahen Gitterpunkt zu finden. Auch das ist ohne die richtige Zusatzinformation schwer.

Zielpunkt aus der Bewertungnaher Gitterpunktweit entfernt
Der Zielpunkt aus der Bewertung (hohler Kreis) liegt nicht im Gitter. Gesucht ist ein Gitterpunkt dicht daneben — der gestrichelte Weg zu einem weit entfernten Punkt ist ebenfalls eine Lösung der ersten Bedingung, aber eben keine kurze.

7. Polynome statt Zahlen

FALCON verwendet ein NTRU-Gitter und rechnet mit Polynomen. Statt einzelner Zahlen also mit Koeffizientenlisten:

f=(1,0,1,0,0,1)⟷f(x)=1+x2+x5.f=(1,0,1,0,0,1) \quad\longleftrightarrow\quad f(x)=1+x^2+x^5.

Gerechnet wird im Ring

Rq=Zq[x]/(xn+1).R_q=\mathbb{Z}_q[x]/(x^n+1).

Das bedeutet:

  • Zq\mathbb{Z}_q: Rechnen modulo qq. Bei q=7q=7 etwa 10≡310\equiv3, denn 10−7=310-7=3.
  • xn=−1x^n=-1: hält die Polynome auf fester Länge.

FALCON verwendet konkret:

q=12289,n=512  oder  1024.q=12289, \qquad n=512 \;\text{oder}\; 1024.

8. Der zentrale Trick

Der private Schlüssel besteht aus vier kleinen Polynomen

f,  g,  F,  Gf,\;g,\;F,\;G

mit der NTRU-Gleichung

fG−gF=q.fG-gF=q.

Diese vier bilden zusammen eine geheime, gutartige Gitterbasis — eine Beschreibung des Gitters aus kurzen Vektoren.

Der öffentliche Schlüssel ist im Wesentlichen ein einziges Polynom:

h=gf(modq).h=\frac{g}{f}\pmod q.

Aus hh ergibt sich dasselbe Gitter, aber in einer unhandlichen Basis aus langen Vektoren:

L={(s1,s2)  :  s1+s2 h≡0(modq)}.L=\{(s_1,s_2)\;:\;s_1+s_2\,h\equiv0 \pmod q\}.

Das ist der ganze Kern von FALCON. Beide Basen beschreiben dasselbe Gitter. Nur ist die eine zum Rechnen brauchbar und die andere nicht.

Man kann sich das wie einen Stadtplan vorstellen: Öffentlich ist die vollständige Karte. Geheim ist die Kenntnis der Abkürzungen.

9. Die Bewertung wird zu einem Punkt

Bevor signiert wird, geht das Payload-Objekt durch eine Hash-Funktion. FALCON nutzt dafür Hash-to-Point: Aus der Nachricht wird kein Zahlenwert, sondern direkt ein Punkt im Ring.

Zusätzlich zieht der Signaturdienst ein zufälliges Salt rr (320 Bit) und hasht es mit:

c=HashToPoint(r ∥ m).c=\mathrm{HashToPoint}(r \,\|\, m).

Das Salt ist kein Beiwerk. Ohne es würde dieselbe Bewertung immer dieselbe Signatur ergeben, und aus vielen Signaturen ließe sich die geheime Basis rekonstruieren. Es wandert deshalb mit in die Signatur.

10. Was eine gültige Signatur ist

Gesucht ist ein Paar

(s1,s2)(s_1,s_2)

mit zwei Eigenschaften:

s1+s2 h≡c(modq)und∥(s1,s2)∥  klein.s_1+s_2\,h\equiv c \pmod q \qquad\text{und}\qquad \|(s_1,s_2)\|\;\text{klein}.

Die erste Bedingung allein ist trivial zu erfüllen — man setzt s2=0s_2=0 und s1=cs_1=c. Die zweite Bedingung macht die Aufgabe schwer.

Die Ku¨rze ist die Signatur.\boxed{\text{Die Kürze ist die Signatur.}}

11. Ein vollständig durchgerechnetes Mini-Beispiel

Wir schrumpfen alles auf Spielzeuggröße: Polynome mit nur einem Koeffizienten, also gewöhnliche Zahlen, und

q=97.q=97.

Der geheime Schlüssel. Zwei kleine Zahlen:

f=3,g=5.f=3, \qquad g=5.

Der öffentliche Schlüssel. Es ist 3−1≡65(mod97)3^{-1}\equiv65 \pmod{97}, denn 3⋅65=195=2⋅97+13\cdot65=195=2\cdot97+1. Also:

h=g⋅f−1=5⋅65=325≡34(mod97).h=g\cdot f^{-1}=5\cdot65=325\equiv \boxed{34} \pmod{97}.

Das Gitter. L={(s1,s2):s1+34 s2≡0(mod97)}L=\{(s_1,s_2): s_1+34\,s_2\equiv0 \pmod{97}\}.

Die öffentliche Basis ergibt sich direkt aus hh:

(97,0)und(−34,1).(97,0) \quad\text{und}\quad (-34,1).

Beide liegen in LL — und beide sind lang.

Die geheime Basis kennt nur der Signaturdienst:

(−g,f)=(−5,3)und(−G,F)=(−9,−14),(-g,f)=(-5,3) \quad\text{und}\quad (-G,F)=(-9,-14),

denn −5+34⋅3=97≡0-5+34\cdot3=97\equiv0 und −9+34⋅(−14)=−485=−5⋅97≡0-9+34\cdot(-14)=-485=-5\cdot97\equiv0. Die Determinante ist

(−5)(−14)−(3)(−9)=70+27=97=q,(-5)(-14)-(3)(-9)=70+27=97=q,

die NTRU-Gleichung geht also auf. Beide Vektoren sind kurz.

Schritt 1: Die Bewertung hashen

Nehmen wir an, das Payload-Objekt der Bewertung ergibt

c=71.c=71.

Schritt 2: Eine erste, schlechte Lösung

(s1,s2)=(71,0)(s_1,s_2)=(71,0)

erfüllt 71+34⋅0=71≡c71+34\cdot0=71\equiv c. Aber die Länge ist 7171 — viel zu lang.

Schritt 3: Mit der geheimen Basis kürzen

Der Signaturdienst drückt den Zielpunkt in seiner kurzen Basis aus:

(71,0)=a (−5,3)+b (−9,−14).(71,0)=a\,(-5,3)+b\,(-9,-14).

Das führt auf a≈−10,25a\approx-10{,}25 und b≈−2,20b\approx-2{,}20. Gerundet auf a=−10a=-10, b=−2b=-2 ergibt sich der Gitterpunkt

−10 (−5,3)−2 (−9,−14)=(50,−30)+(18,28)=(68,−2).-10\,(-5,3)-2\,(-9,-14)=(50,-30)+(18,28)=(68,-2).

Kontrolle: 68+34⋅(−2)=68−68=068+34\cdot(-2)=68-68=0, also tatsächlich in LL. Abziehen:

(71,0)−(68,−2)=(3,2)(71,0)-(68,-2)=\boxed{(3,2)}

Länge:

∥(3,2)∥=9+4=13≈3,61.\|(3,2)\|=\sqrt{9+4}=\sqrt{13}\approx3{,}61.

Das ist die Signatur.

Schritt 4: Dasselbe Verfahren mit der öffentlichen Basis

Wer nur h=34h=34 kennt, hat die Basis {(97,0),(−34,1)}\{(97,0),(-34,1)\}. Dieselbe Rundungsrechnung liefert dort den Gitterpunkt (97,0)(97,0) und damit

(71,0)−(97,0)=(−26,0),∥(−26,0)∥=26.(71,0)-(97,0)=(-26,0), \qquad \|(-26,0)\|=26.

Ebenfalls eine gültige Lösung der Gleichung — aber siebenmal länger. Wird die Annahmeschranke unterhalb von 26 gesetzt, ist sie wertlos.

Gleicher Algorithmus, gleiches Gitter, gleicher Zielpunkt.Nur die Basis unterscheidet sich — und damit das Ergebnis.\boxed{ \begin{array}{c} \text{Gleicher Algorithmus, gleiches Gitter, gleicher Zielpunkt.}\\ \text{Nur die Basis unterscheidet sich — und damit das Ergebnis.} \end{array}}

Das ist die Falltür von FALCON in einer Zeile.

Schritt 5: Der Browser prüft

Der Browser bekommt die Bewertung, das Salt und s2=2s_2=2. Er berechnet den Hash neu, erhält c=71c=71, rekonstruiert

s1=c−s2 h=71−68=3,s_1=c-s_2\,h=71-68=3,

und prüft die Länge:

∥(3,2)∥=13  ≤  β⟹Signatur gu¨ltig\|(3,2)\|=\sqrt{13}\;\leq\;\beta \quad\Longrightarrow\quad \boxed{\text{Signatur gültig}}

Schritt 6: Jemand ändert den Bewertungstext

Wird der Text nachträglich geändert, ändert sich der Content-Hash und damit der Punkt, sagen wir

c′=40.c'=40.

Die alte Signatur bleibt (3,2)(3,2), aber

3+34⋅2=71≠40⟹Signatur ungu¨ltig3+34\cdot2=71\neq40 \quad\Longrightarrow\quad \boxed{\text{Signatur ungültig}}

Wir können eine Bewertung löschen. Verändern können wir sie nicht, ohne dass es auffällt.

Ehrlichkeitshinweis zum Beispiel

In zwei Dimensionen kann ein Angreifer kurze Lösungen einfach durchprobieren — für c′=40c'=40 etwa (6,1)(6,1). Das Beispiel ist nicht sicher; es zeigt nur den Mechanismus. Bei FALCON-1024 hat der Vektor 2048 Koeffizienten, und dort führt Durchprobieren nirgendwohin.

12. Warum wird nicht einfach gerundet?

Das Verfahren aus Schritt 3 heißt Babai-Rundung. Für ein Lehrbeispiel genügt es — für ein echtes Signaturverfahren nicht.

Der Grund: Die gerundeten Signaturen liegen nicht gleichmäßig verteilt. Ihre Form hängt von der Geometrie der geheimen Basis ab. Aus genügend vielen Signaturen ließe sich diese Geometrie rekonstruieren — und damit der private Schlüssel. Genau daran sind frühere gitterbasierte Signaturverfahren gescheitert.

FALCON zieht die kurzen Vektoren deshalb aus einer diskreten Gaußverteilung über dem Gitter:

P(x)∝e−∥x−c∥2/(2σ2).P(x)\propto e^{-\|x-c\|^2/(2\sigma^2)}.

Werte nahe am Zielpunkt sind wahrscheinlicher, aber welcher genau gewählt wird, ist zufällig. Das Ergebnis ist eine Verteilung, die nichts über die verwendete Basis verrät — mathematisch: Sie ist nicht von einer Verteilung unterscheidbar, die nur vom Gitter selbst abhängt.

Dieser Sampler ist der anspruchsvollste Teil von FALCON. Er läuft rekursiv über eine Baumstruktur und arbeitet mit Fließkommazahlen — was die Implementierung heikel macht und der Hauptgrund dafür ist, dass FALCON schwerer korrekt umzusetzen ist als ML-DSA.

13. Was tatsächlich übertragen wird

Die Signatur besteht aus

σ=(r,  s2).\sigma=(r,\;s_2).

Nur s2s_2 — nicht das Paar. s1s_1 rechnet der Prüfer selbst aus:

s1=c−s2 h(modq).s_1=c-s_2\,h \pmod q.

Da die Koeffizienten von s2s_2 klein sind und um null streuen, lassen sie sich stark komprimieren. Das ist der Grund für FALCONs auffällig kompakte Signaturen:

öffentlicher SchlüsselSignatur
FALCON-512897 B~666 B
FALCON-10241.793 B~1.280 B

Zum Vergleich: ML-DSA-87 braucht 4.627 Byte. Bei McGesund steckt allerdings keine dieser Signaturen im QR-Code selbst — der Aufkleber trägt nur den Ed25519-Envelope; die PQ-Stempel liegen am Datensatz und werden beim Prüfen nachgeladen. Die Größe entscheidet hier also nicht über die Druckbarkeit, sondern über Speicher und Übertragung: Ein FALCON-Stempel ist gut ein Viertel so groß wie ein ML-DSA-Stempel.

14. Warum FALCON schnell prüft

Polynommultiplikation naiv kostet

O(n2).O(n^2).

Mit der schnellen Fourier-Transformation sinkt das auf ungefähr

O(nlog⁡n).O(n\log n).

Bei n=1024n=1024 ist das der Unterschied zwischen einer Million und rund zehntausend Operationen. Deshalb läuft die Prüfung im Browser eines Besuchers in Millisekunden — und deshalb steckt das F im Namen:

FAst Fourier Lattice-based COmpact signatures over NTRU.

15. Der Ablauf im Bild

SIGNATURDIENST (MCGESUND)BROWSER DES BESUCHERSprivater Schlüssel (f, g, F, G — kurze Basis)Payload m = {Firma, Bewertung, h, rh, iat}Salt r + HashToPoint(r ‖ m) = cGauß-Sampling: kurzer Vektor (s₁, s₂)Signatur σ = (r, s₂) + kidBewertung + σ + öffentlicher Schlüssel hc neu berechnen, s₁ = c − s₂·h‖(s₁, s₂)‖ ≤ β ?gültigungültig
Vom Payload bis zum Häkchen im Browser. Alles oberhalb der Trennlinie passiert einmal beim Absenden, alles darunter bei jedem Besucher neu — auf seinem Gerät, mit dem öffentlichen Schlüssel.

16. Warum ein Angreifer scheitert

Er kennt hh und damit das gesamte Gitter. Er kennt auch den Zielpunkt cc, sobald die Bewertung öffentlich ist. Was ihm fehlt, ist die kurze Basis.

Um eine Bewertung zu fälschen, müsste er zu einem selbst gewählten cc einen kurzen Vektor finden — allein aus der öffentlichen Beschreibung. Das ist die Aufgabe, die Schritt 4 des Beispiels illustriert hat: Ohne die guten Vektoren landet dieselbe Rechnung bei einer viel zu langen Lösung.

In Dimension 1024 sind die besten bekannten Verfahren — klassisch wie quantenbasiert — davon weit entfernt.

Signieren: schnellPru¨fen: schnellFa¨lschen: schwer\boxed{\text{Signieren: schnell}\quad \text{Prüfen: schnell}\quad \text{Fälschen: schwer}}

17. Was McGesund konkret damit macht

Der Envelope. Jede signierte Bewertung trägt eine Ed25519-Signatur. Das ist die Pflichtvariante — klassisch, sehr klein, in jedem Browser nativ prüfbar.

Die Post-Quanten-Stempel. Daneben liegen ein oder zwei quantenresistente Signaturen. Welche, hängt am Tarif:

Tarifverfügbare Signaturstufen
BasisEd25519, FN-DSA-512
KlassikEd25519, FN-DSA-512, FN-DSA-1024
ProEd25519, FN-DSA-1024, ML-DSA-87
PremiumEd25519, FN-DSA-1024, ML-DSA-87, beide parallel

Die parallele Variante ist bewusst redundant. FALCON steht auf NTRU-Gittern, ML-DSA auf Module-Gittern. Sollte eine der beiden Familien schwächer sein als heute angenommen, trägt die andere weiter.

Der Zeitanker. Der Fingerabdruck des Signaturschlüssels wird über OpenTimestamps in einem Bitcoin-Block verankert. Damit ist nicht nur belegt, dass die Signatur echt ist, sondern auch, dass sie zu einem bestimmten Zeitpunkt schon existierte — ohne dass jemand unserem Zeitstempel glauben müsste.

Gerechnet wird all das im Browser des Lesers, über ein WASM-Modul. Wir liefern die Daten; die Prüfung läuft auf dem Gerät des Besuchers. Gingen wir morgen vom Netz, bliebe eine einmal geladene Bewertung überprüfbar.

Zur Einordnung der Namen: FALCON wird derzeit als FN-DSA standardisiert; der Entwurf ist als FIPS 206 vorgesehen, aber noch nicht abgeschlossen. Deshalb heißen die Stufen im McGesund-Code FN-DSA-512 und FN-DSA-1024, auch wenn im Sprachgebrauch weiterhin von FALCON die Rede ist.

18. Die wichtigste Intuition

Der öffentliche Schlüssel ist die vollständige Beschreibung eines Labyrinths. Jeder darf sie ansehen.

Die Signatur ist der Nachweis: „Ich habe für genau diese Bewertung einen sehr kurzen Weg gefunden."

Der private Schlüssel ist die Kenntnis der Abkürzungen.

Der Leser muss die Abkürzungen nicht kennen. Er misst nur nach, ob der vorgelegte Weg tatsächlich kurz ist und tatsächlich zu dieser Bewertung gehört. Beides kann er ohne uns.

FALCON verwandelt eine Bewertung in einen Punkt in einem Gitterund die Unterschrift in einen kurzen Weg dorthin.\boxed{ \begin{array}{c} \text{FALCON verwandelt eine Bewertung in einen Punkt in einem Gitter}\\ \text{und die Unterschrift in einen kurzen Weg dorthin.} \end{array}}

Wer den Text ändert, verschiebt den Punkt — und der alte Weg führt ins Leere.