Technisches Resümee: Eine neuartige Public-Key-Kryptographie basierend auf verallgemeinerten Lucas-Matrizen

Problemstellung

Die Arbeit adressiert das Bedürfnis nach verbesserten Public-Key-Kryptographie-Verfahren, die größere Schlüsselräume, reduzierte Übertragungskomplexität sowie eine robuste Sicherheit basierend auf Zahlentheorie und linearer Algebra bieten. Während Matrizentheorie und rekursive Folgen (wie Fibonacci- und Lucas-Folgen) bereits in der Kryptographie eingesetzt wurden (z. B. Hill-Chiffre, ElGamal), verwenden bestehende Methoden oft den Austausch großer Schlüsselmatrizen oder verlassen sich auf Standard-Folgeneigenschaften. Die Autoren schlagen ein System vor, das den auszutauschenden Datenumfang während der Schlüsselvereinbarung minimiert und gleichzeitig die Komplexität des Verschlüsselungsschlüsselraums durch den Einsatz verallgemeinerter rekursiver Matrizen maximiert.

Methodik

1. Mathematische Grundlagen

Der Kern des vorgeschlagenen Schemas beruht auf der Konstruktion von verallgemeinerten Lucas-Matrizen (GLM), die aus verallgemeinerten Fibonacci-Matrizen (GFM) abgeleitet werden.

• Verallgemeerte Fibonacci-Matrizen (GFM): Die Autoren nutzen die $k$-te Ordnung der verallgemeinerten Fibonacci-Folge $\{f_{k,n}\}$ und deren entsprechende Matrizendarstellung $Q^k_n$. Diese Matrizen erfüllen Standardeigenschaften wie $Q^n_k Q^l_k = Q^{n+l}_k$ sowie spezifische Determinantenregeln basierend auf der Ordnung $k$.
• Verallgemeerte Lucas-Folgen: Es wird eine neue Sequenz $\{l_{k,n}\}$ definiert, bei der die Anfangswerte aus der Spur der ersten $k$ GFM-Matrizen abgeleitet werden ($l_{k,r} = \text{trace}(Q^r_k)$). Die Rekursionsrelation spiegelt die verallgemeinerte Fibonacci-Folge wider: $l_{k,k+n} = \sum_{i=0}^{k-1} l_{k,k+n-1-i}$.
• Verallgemeerte Lucas-Matrizen (GLM): Eine rekursive Matrix $L^{(n)}_k$ wird unter Verwendung linearer Kombinationen von Termen aus der verallgemeinerten Lucas-Folge konstruiert. Die Autoren stellen eine fundamentale Beziehung zwischen GLM und GFM her:
  $$L^{(n)}_k = Q^n_k L^{(0)}_k = L^{(0)}_k Q^n_k$$
  wobei $L^{(0)}_k$ die initiale Lucas-Matrix ist.

2. Kryptographisches Schema

Das vorgeschlagene System integriert diese Matrizen in eine modifizierte Affine-Hill-Chiffre in Kombination mit der ElGamal-Public-Key-Infrastruktur.

• Schlüsselvereinbarung (ElGamal-basiert):

  • Empfänger (Bob): Wählt eine Primzahl $p$, eine primitive Wurzel $\alpha$ und eine geheime Ganzzahl $D$. Er veröffentlicht $E_1 = \alpha$ und $E_2 = \alpha^D \pmod p$.
  • Sender (Alice): Wählt eine Zufallszahl $e$. Sie berechnet eine Signatur $s = E_1^e \pmod p$ und ein gemeinsames Geheimnis $\lambda = E_2^e \pmod p$.
  • Übertragung: Alice sendet den Geheimtext und die Signatur $s$ an Bob. Sie sendet nicht die vollständige Schlüsselmatrix oder das geheime $\lambda$.

• Verschlüsselung (Affine-Hill mit GLM):

  • Unter Verwendung des gemeinsamen Geheimnisses $\lambda$ (Ordnung der Matrix) und der Signatur $s$ (Exponent) konstruiert Alice die Verschlüsselungs-Schlüsselmatrix $K = L^{(s)}_\lambda \pmod p$.
  • Ein Verschiebevektor $B$ wird mithilfe von Termen der Lucas-Folge generiert: $B = [l_{\lambda,\lambda}, l_{\lambda,\lambda+1}, \dots, l_{\lambda,2\lambda-1}]$.
  • Klartextblöcke $P$ werden verschlüsselt als $C = (P \cdot K + B) \pmod p$.

• Entschlüsselung:

  • Bob stellt $\lambda$ mithilfe seines privaten Schlüssels wieder her: $\lambda = s^D \pmod p$.
  • Er konstruiert die inverse Matrix $K^* = L^{(-s)}_\lambda H^{-1} \pmod p$, wobei $H = (L^{(0)}_\lambda)^2$. Das Paper beweist, dass $L^{(s)}_\lambda L^{(-s)}_\lambda = H$ gilt, was die Existenz einer Inversen sicherstellt.
  • Die Entschlüsselung erfolgt als $P = (C - B) \cdot K^* \pmod p$.

Kernbeiträge

1. Definition von verallgemeerten Lucas-Matrizen: Das Paper definiert formal die GLM der Ordnung $k$ und etabliert deren algebraische Eigenschaften, einschließlich Determinantenformeln, Produktregeln ($L^{(m)}_k L^{(n)}_k = L^{(m+n)}_k L^{(0)}_k$) und die explizite Konstruktion ihrer Inversen.
2. Parameterbasierte Schlüsselgenerierung: Im Gegensatz zu traditionellen matrixbasierten Chiffren, bei denen die gesamte Matrix geteilt oder aus einem großen Seed generiert werden muss, ermöglicht dieses Schema beiden Parteien die Rekonstruktion der Schlüsselmatrix unter Verwendung von nur zwei Parametern: $\lambda$ (abgeleitet aus dem Problem des diskreten Logarithmus) und $s$ (die Signatur).
3. Integration von Affine-Hill und ElGamal: Die Autoren schlagen ein Hybridschema vor, das die Effizienz der Affine-Hill-Chiffre (Blockverschlüsselung mit Verschiebevektor) nutzt, welche durch die Schwierigkeit des diskreten Logarithmus-Problems im ElGamal-Setup abgesichert ist.
4. Konstruktion der Inversen: Das Paper liefert eine spezifische Methode zur Berechnung der Inversen der GLM, ohne auf das Standardverfahren der Gaußschen Elimination zurückzugreifen, indem die Beziehung $Inv(L^{(n)}_k) = L^{(-n)}_k H^{-1}$ genutzt wird.

Ergebnisse und Analyse

• Implementierungsbeispiel: Die Autoren demonstrieren das Schema mit $p=37$, Ordnung $k=3$ und spezifischen Ganzzahlwerten für $D$ und $e$. Sie verschlüsseln den Klartext "NOBLE2022" erfolgreich in Geheimtextblöcke und stellen die ursprüngliche Nachricht wieder her, wodurch die mathematische Korrektheit der Matrixoperationen und der modularen Arithmetik verifiziert wird.
• Reduktion der Komplexität: Das Schema beansprucht, die Zeit- und Speicherkomplexität für die Schlüsselübertragung zu reduzieren. Anstatt eine $n \times n$ Matrix zu übertragen, wird lediglich das Paar $(\lambda, s)$ ausgetauscht.
• Sicherheitsanalyse:
  • Diskreter Logarithmus: Die Rekonstruktion von $\lambda$ aus $s$ erfordert das Lösen des Problems des diskreten Logarithmus, was für große Primzahlen rechnerisch unmöglich ist.
  • Schlüsselraum: Die Sicherheit gegen Brute-Force-Angriffe hängt von der Größe der allgemeinen linearen Gruppe $|GL(\lambda)|$ ab. Die Autoren berechnen, dass für $p=37$ und $\lambda=50$ der Schlüsselraum etwa $3,105 \times 10^{3920}$ beträgt, was exponentiell groß ist.
  • Signatur-Unabhängigkeit: Die Analyse deutet darauf hin, dass die Signatur $s$ die Sicherheit nicht gefährdet, selbst wenn sie bekannt ist, da die Sicherheit primär auf der Schwierigkeit beruht, $\lambda$ zu bestimmen, und der enormen Weite des durch $\lambda$ definierten Matrixraums.

Bedeutung und Behauptungen

Das Paper kommt zu dem Schluss, dass die vorgeschlagene Methode ein mathematisch einfaches, aber starkes kryptographisches Framework für autorisierte Parteien bietet und gleichzeitig eine signifikante Barriere für Eindringlinge darstellt. Die Bedeutung liegt in:

• Vergrößerter Schlüsselraum: Die Verwendung verallgemeinerter Lucas-Matrizen erweitert den verfügbaren Schlüsselraum im Vergleich zu Standardimplementierungen erheblich.
• Effizienz: Durch die Reduktion der Schlüsselübertragung auf ein Paar von Zahlen verbessert das Schema die Effizienz in Bezug auf Bandbreite und Speicherplatz.
• Robustheit: Die Kombination aus dem Problem des diskreten Logarithmus (für die Schlüsselvereinbarung) und der Komplexität der Matrixstruktur (für die Verschlüsselung) schafft eine mehrschichtige Verteidigung.

Die Autoren behaupten, dass die Methode "mathematisch einfach für die autorisierte Partei und mühsam für einen Eindringling" ist, wobei sie auf der etablierten Schwierigkeit des diskreten Logarithmus-Problems und dem großen kombinatorischen Raum der verallgemeinerten Lucas-Matrizen basiert.