Technische Samenvatting: Een Nieuwe Publieke Sleutel Cryptografie Gebaseerd op Gegeneraliseerde Lucas-matrices

Probleemstelling

Het artikel adresseert de behoefte aan verbeterde publieke sleutel cryptografische schema's die grotere sleutelruimtes bieden, de transmissiecomplexiteit verminderen en een robuuste beveiliging bieden op basis van getaltheorie en lineaire algebra. Hoewel matrix-theorie en recursieve reeksen (zoals Fibonacci- en Lucas-reeksen) zijn toegepast in de cryptografie (bijv. Hill-cijfer, ElGamal), maken bestaande methoden vaak gebruik van het uitwisselen van grote sleutelmatrices of vertrouwen ze op standaard eigenschappen van reeksen. De auteurs stellen een systeem voor dat de uitgewisselde data tijdens sleutelovereenkomst minimaliseert terwijl de complexiteit van de encryptiesleutelruimte wordt gemaximaliseerd door het gebruik van gegeneraliseerde recursieve matrices.

Methodologie

1. Wiskundige Fundamenten

De kern van het voorgestelde schema rust op de constructie van Gegeneraliseerde Lucas-matrices (GLM) afgeleid van Gegeneraliseerde Fibonacci-matrices (GFM).

• Gegeneraliseerde Fibonacci-matrices (GFM): De auteurs maken gebruik van de $k$-de orde gegeneraliseerde Fibonacci-reeks $\{f_{k,n}\}$ en de bijbehorende matrixrepresentatie $Q^k_n$. Deze matrices voldoen aan standaard eigenschappen zoals $Q^n_k Q^l_k = Q^{n+l}_k$ en specifieke determinantregels gebaseerd op de orde $k$.
• Gegeneraliseerde Lucas-reeksen: Een nieuwe reeks $\{l_{k,n}\}$ wordt gedefinieerd waarbij de beginwaarden worden afgeleid van de trace van de eerste $k$ GFM-matrices ($l_{k,r} = \text{trace}(Q^r_k)$). De recessieve relatie weerspiegelt de gegeneraliseerde Fibonacci-reeks: $l_{k,k+n} = \sum_{i=0}^{k-1} l_{k,k+n-1-i}$.
• Gegeneraliseerde Lucas-matrices (GLM): Een recursieve matrix $L^{(n)}_k$ wordt geconstrueerd met behulp van lineaire combinaties van termen uit de gegeneraliseerde Lucas-reeks. De auteurs stellen een fundamentele relatie tussen GLM en GFM vast:
  $$L^{(n)}_k = Q^n_k L^{(0)}_k = L^{(0)}_k Q^n_k$$
  waarbij $L^{(0)}_k$ de initiële Lucas-matrix is.

2. Cryptografisch Schema

Het voorgestelde systeem integreert deze matrices in een aangepast Affine-Hill-cijfer gecombineerd met de ElGamal publieke sleutel-infrastructuur.

• Sleuteluitwisseling (gebaseerd op ElGamal):

  • Ontvanger (Bob): Selecteert een priemgetal $p$, een primitieve wortel $\alpha$, en een geheim geheel getal $D$. Hij publiceert $E_1 = \alpha$ en $E_2 = \alpha^D \pmod p$.
  • Verzender (Alice): Kiest een willekeurig geheel getal $e$. Zij berekent een handtekening $s = E_1^e \pmod p$ en een gedeeld geheim $\lambda = E_2^e \pmod p$.
  • Transmissie: Alice stuurt het cijfertekstblok en de handtekening $s$ naar Bob. Zij stuurt niet de volledige sleutelmatrix of het geheime $\lambda$.

• Encryptie (Affine-Hill met GLM):

  • Met behulp van het gedeelde geheim $\lambda$ (orde van de matrix) en de handtekening $s$ (exponent) construeert Alice de encryptiesleutelmatrix $K = L^{(s)}_\lambda \pmod p$.
  • Een verschuivingsvector $B$ wordt gegenereerd met behulp van termen uit de Lucas-reeks: $B = [l_{\lambda,\lambda}, l_{\lambda,\lambda+1}, \dots, l_{\lambda,2\lambda-1}]$.
  • Plaintekstblokken $P$ worden versleuteld als $C = (P \cdot K + B) \pmod p$.

• Decryptie:

  • Bob herstelt $\lambda$ met behulp van zijn privésleutel: $\lambda = s^D \pmod p$.
  • Hij construeert de inverse matrix $K^* = L^{(-s)}_\lambda H^{-1} \pmod p$, waarbij $H = (L^{(0)}_\lambda)^2$. Het artikel bewijst dat $L^{(s)}_\lambda L^{(-s)}_\lambda = H$, wat het bestaan van een inverse garandeert.
  • Decryptie wordt uitgevoerd als $P = (C - B) \cdot K^* \pmod p$.

Belangrijkste Bijdragen

1. Definitie van Gegeneraliseerde Lucas-matrices: Het artikel definieert formeel GLM van orde $k$ en stelt hun algebraïsche eigenschappen vast, inclusief determinantformules, productregels ($L^{(m)}_k L^{(n)}_k = L^{(m+n)}_k L^{(0)}_k$) en de expliciete constructie van hun inversen.
2. Parameter-gebaseerde Sleutelgeneratie: In tegenstelling tot traditionele matrix-gebaseerde ciphers waarbij de volledige matrix moet worden gedeeld of gegenereerd vanuit een grote seed, staat dit schema beide partijen toe de sleutelmatrix te reconstrueren met slechts twee parameters: $\lambda$ (afgeleid van het discrete logaritme probleem) en $s$ (de handtekening).
3. Integratie met Affine-Hill en ElGamal: De auteurs stellen een hybride schema voor dat het efficiënte Affine-Hill-cijfer (blokversleuteling met een verschuivingsvector) combineert met de beveiliging van het discrete logaritme probleem dat inherent is aan de ElGamal-opzet.
4. Constructie van de Inverse: Het artikel biedt een specifieke methode voor het berekenen van de inverse van de GLM zonder terug te vallen op standaard Gaussische eliminatie, gebruikmakend van de relatie $Inv(L^{(n)}_k) = L^{(-n)}_k H^{-1}$.

Resultaten en Analyse

• Implementatievoorbeeld: De auteurs demonstreren het schema met $p=37$, orde $k=3$, en specifieke gehele waarden voor $D$ en $e$. Zij versleutelen succesvol de plaintekst "NOBLE2022" naar cijfertekstblokken en herstellen de originele boodschap, waarmee de wiskundige correctheid van de matrixoperaties en modulaire rekenkunde wordt geverifieerd.
• Complexiteitsreductie: Het schema beweert de tijd- en ruimtecomplexiteit voor sleuteltransmissie te verminderen. In plaats van een $n \times n$ matrix te verzenden, wordt alleen het paar $(\lambda, s)$ uitgewisseld.
• Beveiligingsanalyse:
  • Discreet Logaritme: Het herstellen van $\lambda$ uit $s$ vereist het oplossen van het discrete logaritme probleem, wat computationeel onhaalbaar is voor grote priemgetallen.
  • Sleutelruimte: De beveiliging tegen brute-force aanvallen hangt af van de grootte van de algemene lineaire groep $|GL(\lambda)|$. De auteurs berekenen dat voor $p=37$ en $\lambda=50$, de sleutelruimte ongeveer $3.105 \times 10^{3920}$ is, wat exponentieel groot is.
  • Onafhankelijkheid van de Handtekening: De analyse suggereert dat de handtekening $s$ de beveiliging niet in gevaar brengt, zelfs als deze bekend is, aangezien de beveiliging primair rust op de moeilijkheid van het bepalen van $\lambda$ en de enorme omvang van de matrixruimte gedefinieerd door $\lambda$.

Betekenis en Claims

Het artikel concludeert dat de voorgestelde methode een wiskundig eenvoudige maar sterke cryptografische structuur biedt voor geautoriseerde partijen, terwijl het een significante barrière vormt voor indringers. De betekenis ligt in:

• Vergroting van de Sleutelruimte: Het gebruik van gegeneraliseerde Lucas-matrices breidt de beschikbare sleutelruimte aanzienlijk uit vergeleken met standaard implementaties.
• Efficiëntie: Door de sleuteltransmissie te reduceren tot een paar getallen, verbetert het schema de efficiëntie in termen van bandbreedte en opslag.
• Robuustheid: De combinatie van het discrete logaritme probleem (voor sleutelovereenkomst) en de complexiteit van de matrixstructuur (voor encryptie) creëert een meerlaagse verdediging.

De auteurs beweren dat de methode "wiskundig eenvoudig is voor de geautoriseerde partij en moeizaam voor een indringer", leunend op de gevestigde moeilijkheid van het discrete logaritme probleem en de grote combinatorische ruimte van de gegeneraliseerde Lucas-matrices.