Sintesi Tecnica: Una Nuova Crittografia a Chiave Pubblica Basata su Matrici di Lucas Generalizzate

Definizione del Problema

Il documento affronta la necessità di schemi di crittografia a chiave pubblica potenziati che offrano spazi di chiavi più ampi, una riduzione della complessità di trasmissione e una sicurezza robusta basata sulla teoria dei numeri e l'algebra lineare. Mentre la teoria delle matrici e le sequenze ricorsive (come le sequenze di Fibonacci e di Lucas) sono state utilizzate nella crittografia (ad esempio, Hill Cipher, ElGamal), i metodi esistenti spesso comportano lo scambio di grandi matrici di chiavi o si affidano alle proprietà standard delle sequenze. Gli autori propongono un sistema che minimizza i dati scambiati durante l'accordo sulle chiavi, massimizzando al contempo la complessità dello spazio delle chiavi di cifratura attraverso l'uso di matrici ricorsive generalizzate.

Metodologia

1. Fondamenti Matematici

Il nucleo dello schema proposto si basa sulla costruzione di Matrici di Lucas Generalizzate (GLM) derivate da Matrici di Fibonacci Generalizzate (GFM).

• Matrici di Fibonacci Generalizzate (GFM): Gli autori utilizzano la sequenza di Fibonacci generalizzata di ordine $k$ $\{f_{k,n}\}$ e la sua corrispondente rappresentazione matriciale $Q^k_n$. Queste matrici soddisfano proprietà standard come $Q^n_k Q^l_k = Q^{n+l}_k$ e regole specifiche del determinante basate sull'ordine $k$.
• Sequenze di Lucas Generalizzate: Viene definita una nuova sequenza $\{l_{k,n}\}$ dove i valori iniziali sono derivati dalla traccia delle prime $k$ matrici GFM ($l_{k,r} = \text{trace}(Q^r_k)$). La relazione di ricorrenza rispecchia la sequenza di Fibonacci generalizzata: $l_{k,k+n} = \sum_{i=0}^{k-1} l_{k,k+n-1-i}$.
• Matrici di Lucas Generalizzate (GLM): Una matrice ricorsiva $L^{(n)}_k$ è costruita utilizzando combinazioni lineari di termini della sequenza di Lucas generalizzata:
  $$L^{(n)}_k = Q^n_k L^{(0)}_k = L^{(0)}_k Q^n_k$$
  dove $L^{(0)}_k$ è la matrice di Lucas iniziale.

2. Schema Crittografico

Il sistema proposto integra queste matrici in un Cifrario Affine-Hill modificato combinato con l'infrastruttura a chiave pubblica ElGamal.

• Scambio di Chiavi (basato su ElGamal):

  • Ricevitore (Bob): Seleziona un numero primo $p$, una radice primitiva $\alpha$ e un intero segreto $D$. Pubblica $E_1 = \alpha$ ed $E_2 = \alpha^D \pmod p$.
  • Mittente (Alice): Sceglie un intero casuale $e$. Calcola una firma $s = E_1^e \pmod p$ e un segreto condiviso $\lambda = E_2^e \pmod p$.
  • Trasmissione: Alice invia il testo cifrato e la firma $s$ a Bob. Lei non invia la matrice di chiave completa o il segreto $\lambda$.

• Cifratura (Affine-Hill con GLM):

  • Utilizzando il segreto condiviso $\lambda$ (ordine della matrice) e la firma $s$ (esponente), Alice costruisce la matrice di chiave di cifratura $K = L^{(s)}_\lambda \pmod p$.
  • Un vettore di spostamento $B$ viene generato utilizzando i termini della sequenza di Lucas: $B = [l_{\lambda,\lambda}, l_{\lambda,\lambda+1}, \dots, l_{\lambda,2\lambda-1}]$.
  • I blocchi di testo in chiaro $P$ vengono cifrati come $C = (P \cdot K + B) \pmod p$.

• Decifrazione:

  • Bob recupera $\lambda$ utilizzando la sua chiave privata: $\lambda = s^D \pmod p$.
  • Egli costruisce la matrice inversa $K^* = L^{(-s)}_\lambda H^{-1} \pmod p$, dove $H = (L^{(0)}_\lambda)^2$. Il documento prova che $L^{(s)}_\lambda L^{(-s)}_\lambda = H$, garantendo l'esistenza di un inverso.
  • La decifrazione viene eseguita come $P = (C - B) \cdot K^* \pmod p$.

Contributi Principali

1. Definizione delle Matrici di Lucas Generalizzate: Il documento definisce formalmente le GLM di ordine $k$ ed stabilisce le loro proprietà algebriche, inclusi i formulari del determinante, le regole di prodotto ($L^{(m)}_k L^{(n)}_k = L^{(m+n)}_k L^{(0)}_k$) e la costruzione esplicita dei loro inversi.
2. Generazione della Chiave Basata su Parametri: A differenza delle tradizionali cifre basate su matrici dove l'intera matrice deve essere condivisa o generata da un grande seme, questo schema permette alla chiave di essere ricostruita da entrambe le parti utilizzando solo due parametri: $\lambda$ (derivato dal problema del logaritmo discreto) e $s$ (la firma).
3. Integrazione con Affine-Hill ed ElGamal: Gli autori propongono uno schema ibrido che utilizza l'efficienza del cifrario Affine-Hill (cifratura a blocchi con un vettore di spostamento) protetto dalla difficoltà del problema del logaritmo discreto inerente alla configurazione ElGamal.
4. Costruzione dell'Inverso: Il documento fornisce un metodo specifico per calcolare l'inverso della GLM senza fare affidamento sulla standard eliminazione gaussiana, utilizzando la relazione $Inv(L^{(n)}_k) = L^{(-n)}_k H^{-1}$.

Risultati e Analisi

• Esempio di Implementazione: Gli autori dimostrano lo schema con $p=37$, ordine $k=3$ e valori interi specifici per $D$ ed $e$. Riescono a cifrare il testo in chiaro "NOBLE2022" in blocchi di testo cifrato e recuperano il messaggio originale, verificando la correttezza matematica delle operazioni matriciali e dell'aritmetica modulare.
• Riduzione della Complessità: Lo schema dichiara di ridurre la complessità temporale e spaziale per la trasmissione della chiave. Inveve di trasmettere una matrice $n \times n$, viene scambiata solo la coppia $(\lambda, s)$.
• Analisi della Sicurezza:
  • Logaritmo Discreto: Recuperare $\lambda$ da $s$ richiede la risoluzione del problema del logaritmo discreto, che è computazionalmente intrattabile per numeri primi di grandi dimensioni.
  • Spazio delle Chiavi: La sicurezza contro gli attacchi brute-force dipende dalla dimensione del Gruppo Lineare Generale $|GL(\lambda)|$. Gli autori calcolano che per $p=37$ e $\lambda=50$, lo spazio delle chiavi è circa $3.105 \times 10^{3920}$, un valore esponenzialmente grande.
  • Indipendenza della Firma: L'analisi suggerisce che la firma $s$ non compromette la sicurezza anche se nota, poiché la sicurezza dipende principalmente dalla difficoltà di determinare $\lambda$ e dall'immensità dello spazio matriciale definito da $\lambda$.

Significato e Rivendicazioni

Il documento conclude che il metodo proposto offre un quadro crittografico matematicamente semplice ma forte per le parti autorizzate, presentando al contempo una barriera significativa per gli intrusi. Il significato risiede in:

• Spazio delle Chiavi Ampliato: L'uso delle matrici di Lucas generalizzate espande significativamente lo spazio delle chiavi disponibile rispetto alle implementazioni standard.
• Efficienza: Riducendo la trasmissione della chiave a una coppia di numeri, lo schema migliora l'efficienza in termini di larghezza di banda e archiviazione.
• Robustezza: La combinazione del problema del logaritmo discreto (per l'accordo sulle chiavi) e della complessità della struttura matriciale (per la cifratura) crea una difesa multistrato.

Gli autori affermano che il metodo è "matematicamente semplice per la parte autorizzata e tedioso per un intruso", basandosi sulla difficoltà stabilita del problema del logaritmo discreto e sul vasto spazio combinatorio delle matrici di Lucas generalizzate.