Résumé Technique : Une Nouvelle Cryptographie à Clé Publique Basée sur les Matrices de Lucas Généralisées

Énoncé du Problème

L'article traite de la nécessité de schémas de cryptographie à clé publique améliorés offrant des espaces de clés plus larges, une complexité de transmission réduite et une sécurité robuste basée sur la théorie des nombres et l'algèbre linéaire. Bien que la théorie des matrices et les séquences récursives (telles que les séquences de Fibonacci et de Lucas) aient été utilisées en cryptographie (par exemple, le chiffre de Hill, ElGamal), les méthodes existantes impliquent souvent l'échange de grandes matrices de clés ou reposent sur les propriétés de séquences standards. Les auteurs proposent un système qui minimise les données échangées lors de l'accord de clé tout en maximisant la complexité de l'espace de clé de chiffrement grâce à l'utilisation de matrices récursives généralisées.

Méthodologie

1. Fondements Mathématiques

Le cœur du schéma proposé repose sur la construction de Matrices de Lucas Généralisées (MLG) dérivées de Matrices de Fibonacci Généralisées (MFG).

• Matrices de Fibonacci Généralisées (MFG) : Les auteurs utilisent la séquence de Fibonacci généralisée d'ordre $k$, $\{f_{k,n}\}$, et sa représentation matricielle correspondante $Q^k_n$. Ces matrices satisfont des propriétés standards telles que $Q^n_k Q^l_k = Q^{n+l}_k$ et des règles de déterminant spécifiques basées sur l'ordre $k$.
• Séquences de Lucas Généralisées : Une nouvelle séquence $\{l_{k,n}\}$ est définie où les valeurs initiales sont dérivées de la trace des $k$ premières matrices MFG ($l_{k,r} = \text{trace}(Q^r_k)$). La relation de récurrence reflète la séquence de Fibonacci généralisée : $l_{k,k+n} = \sum_{i=0}^{k-1} l_{k,k+n-1-i}$.
• Matrices de Lucas Généralisées (MLG) : Une matrice récursive $L^{(n)}_k$ est construite en utilisant des combinaisons linéaires de termes de la séquence de Lucas généralisée. Les auteurs établissent une relation fondamentale entre la MLG et la MFG :
  $$L^{(n)}_k = Q^n_k L^{(0)}_k = L^{(0)}_k Q^n_k$$
  où $L^{(0)}_k$ est la matrice de Lucas initiale.

2. Schéma Cryptographique

Le système proposé intègre ces matrices dans un chiffre Affine-Hill modifié combiné à l'infrastructure à clé publique ElGamal.

• Échange de Clés (basé sur ElGamal) :

  • Le Récepteur (Bob) : Sélectionne un nombre premier $p$, une racine primitive $\alpha$, et un entier secret $D$. Il publie $E_1 = \alpha$ et $E_2 = \alpha^D \pmod p$.
  • L'Émetteur (Alice) : Choisit un entier aléatoire $e$. Elle calcule une signature $s = E_1^e \pmod p$ et un secret partagé $\lambda = E_2^e \pmod p$.
  • Transmission : Alice envoie le texte chiffré et la signature $s$ à Bob. Elle ne transmet pas la matrice de clé complète ni le secret $\lambda$.

• Chiffrement (Affine-Hill avec MLG) :

  • En utilisant le secret partagé $\lambda$ (ordre de la matrice) et la signature $s$ (exposant), Alice construit la matrice de clé de chiffrement $K = L^{(s)}_\lambda \pmod p$.
  • Un vecteur de décalage $B$ est généré en utilisant des termes de la séquence de Lucas : $B = [l_{\lambda,\lambda}, l_{\lambda,\lambda+1}, \dots, l_{\lambda,2\lambda-1}]$.
  • Les blocs de texte en clair $P$ sont chiffrés comme $C = (P \cdot K + B) \pmod p$.

• Déchiffrement :

  • Bob récupère $\lambda$ en utilisant sa clé privée : $\lambda = s^D \pmod p$.
  • Il construit la matrice inverse $K^* = L^{(-s)}_\lambda H^{-1} \pmod p$, où $H = (L^{(0)}_\lambda)^2$. Le papier prouve que $L^{(s)}_\lambda L^{(-s)}_\lambda = H$, garantissant l'existence d'une inverse.
  • Le déchiffrement est effectué par $P = (C - B) \cdot K^* \pmod p$.

Contributions Clés

1. Définition des Matrices de Lucas Généralisées : L'article définit formellement la MLG d'ordre $k$ et établit ses propriétés algébriques, y compris les formules de déterminant, les règles de produit ($L^{(m)}_k L^{(n)}_k = L^{(m+n)}_k L^{(0)}_k$) et la construction explicite de leurs inverses.
2. Génération de Clé Basée sur des Paramètres : Contraques les chiffres matriciels traditionnels où la matrice entière doit être partagée ou générée à partir d'une grande graine, ce schéma permet de reconstruire la matrice de clé par les deux parties en utilisant uniquement deux paramètres : $\lambda$ (dérivé du problème du logarithme discret) et $s$ (la signature).
3. Intégration avec l'Affine-Hill et ElGamal : Les auteurs proposent un schéma hybride qui utilise l'efficacité du chiffre Affine-Hill (chiffrement par bloc avec un vecteur de décalage) sécurisé par la difficulté du problème du logarithme discret inhérente à la configuration ElGamal.
4. Construction de l'Inverse : L'article fournit une méthode spécifique pour calculer l'inverse de la MLG sans recourir à l'élimination de Gauss standard, en utilisant la relation $Inv(L^{(n)}_k) = L^{(-n)}_k H^{-1}$.

Résultats et Analyse

• Exemple d'Implémentation : Les auteurs démontrent le schéma avec $p=37$, l'ordre $k=3$, et des valeurs entières spécifiques pour $D$ et $e$. Ils parviennent à chiffrer le texte en clair "NOBLE2022" en blocs de texte chiffré et récupèrent le message original, vérifiant la correction mathématique des opérations matricielles et de l'arithmétique modulaire.
• Réduction de la Complexité : Le schéma prétend réduire la complexité temporelle et spatiale pour la transmission de la clé. Au lieu de transmettre une matrice $n \times n$, seul le couple $(\lambda, s)$ est échangé.
• Analyse de Sécurité :
  • Logarithme Discret : Récupérer $\lambda$ à partir de $s$ nécessite de résoudre le problème du logarithme discret, ce qui est informatiquement infaisable pour de grands nombres premiers.
  • Espace de Clé : La sécurité contre les attaques par force brute dépend de la taille du Groupe Linéaire Général $|GL(\lambda)|$. Les auteurs calculent que pour $p=37$ et $\lambda=50$, l'espace de clé est d'environ $3.105 \times 10^{3920}$, ce qui est exponentiellement grand.
  • Indépendance de la Signature : L'analyse suggère que la signature $s$ ne compromet pas la sécurité même si elle est connue, car la sécurité repose principalement sur la difficulté de déterminer $\lambda$ et l'immensité de l'espace matriciel défini par $\lambda$.

Signification et Revendications

L'article conclut que la méthode proposée offre un cadre cryptographique mathématiquement simple mais fort pour les parties autorisées, tout en présentant une barrière significative pour les intrus. La signification réside dans :

• Élargissement de l'Espace de Clé : L'utilisation des matrices de Lucas généralisées étend considérablement l'espace de clé disponible par rapport aux implémentations standards.
• Efficacité : En réduisant la transmission de la clé à une paire de nombres, le schéma améliore l'efficacité en termes de bande passante et de stockage.
• Robustesse : La combinaison du problème du logarithme discret (pour l'accord de clé) et de la complexité de la structure matricielle (pour le chiffrement) crée une défense multicouche.

Les auteurs affirment que la méthode est « mathématiquement simple pour la partie autorisée et fastidieuse pour un intrus », s'appuyant sur la difficulté établie du problème du logarithme discret et l'espace combinatoire vaste des matrices de Lucas généralisées.