A Totient Function Associated with Variants of Groups

1. Problème et Contexte

L'article s'inscrit dans le domaine de la cryptographie moderne, spécifiquement autour du problème du logarithme discret (DLP) dans les groupes finis. L'auteur s'intéresse à l'utilisation des variants de groupes (une notion issue de la théorie des semi-groupes) pour concevoir de nouveaux schémas de chiffrement.

Le problème central abordé est le suivant : lorsqu'on tente de casser un système cryptographique basé sur un variant de groupe par une attaque par force brute, le nombre de paires de clés candidates à tester est de l'ordre de $O(n^2)$ (où $n$ est l'ordre du groupe). Cependant, une vulnérabilité potentielle existe : il peut exister de nombreuses « fausses positives », c'est-à-dire des paires $(y, f)$ différentes de la clé réelle $(x, e)$ qui produisent le même texte chiffré.

L'objectif de l'article est d'introduire et d'analyser une nouvelle fonction arithmétique, notée $T(n)$, qui compte le nombre de telles fausses solutions. La sécurité du système dépend de la capacité à rendre $T(n)$ suffisamment grand par rapport à $n$, augmentant ainsi la difficulté de l'attaque par force brute en créant un « tas de foin » de solutions incorrectes parmi lesquelles trouver la « aiguille » correcte.

2. Méthodologie

L'approche de l'auteur combine la théorie des groupes, la théorie des semi-groupes et l'analyse numérique (théorie des nombres).

• Définition de la fonction $T(n)$ :
  La fonction est définie pour un entier $n \ge 1$ comme le nombre d'unités impaires $m \in \mathbb{Z}_n$ (c'est-à-dire $\gcd(m, n)=1$) telles que $(m-1)/2$ soit également une unité dans $\mathbb{Z}_n$.
  $$T(n) = |\{1 \le m \le n \mid \gcd(m, n) = 1 \text{ et } \gcd((m-1)/2, n) = 1\}|$$
  (Note : $T(1)$ est défini comme 0).

• Lien avec les fonctions totient existantes :
  L'auteur établit des liens avec la fonction d'Euler $\phi(n)$ et la fonction de Schemmel $S_r(n)$ (qui compte les suites de $r$ unités consécutives). Une fonction auxiliaire clé est $S(n) = S_2(n)$, qui compte les paires d'unités consécutives $(m, m+1)$ dans $\mathbb{Z}_n$.
  $$S(n) = n \prod_{p|n} \left(1 - \frac{2}{p}\right)$$

• Analyse par cas et principe d'inclusion-exclusion :
  La méthodologie principale consiste à décomposer le calcul de $T(n)$ selon la parité de $n$ et sa factorisation en nombres premiers.

  • Pour $n$ impair, l'auteur utilise le principe d'inclusion-exclusion sur les ensembles d'entiers partageant des facteurs communs avec $n$ ou ayant une forme spécifique ($1+2k$).
  • Pour $n$ pair, une analyse plus fine est menée en distinguant les cas $n=2^k$, $n=2^k m$ (avec $m$ impair), et en étudiant les résidus modulo 4.
  • Des lemmes techniques (Lemmes 4 à 12) sont développés pour estimer les intersections d'ensembles définis par des congruences linéaires et des conditions de parité, en utilisant des algorithmes comme celui d'Euclide pour résoudre des équations diophantiennes.

3. Contributions Clés

Les principales contributions de l'article sont :

1. Introduction d'une nouvelle fonction arithmétique : Définition rigoureuse de $T(n)$, une généralisation liée aux variants de groupes, distincte des fonctions totient classiques.
2. Établissement de bornes et de formules exactes :
   • Cas des puissances de nombres premiers impairs : Pour $n=p^e$, une formule exacte est donnée : $T(p^e) = (p^e - 2p^{e-1} - 1)/2$.
   • Cas des nombres pairs : Des formules exactes sont dérivées pour $T(2^e)$ et $T(2^e n)$ (avec $n$ impair). Par exemple, $T(2^e n) = 2^{e-2}S(n)$ pour $e \ge 2$.
   • Bornes pour les nombres composés : Pour un entier $n$ impair avec $\omega$ facteurs premiers distincts, l'article établit une borne d'erreur pour l'approximation de $T(n)$ par rapport à $S(n)$ :
     $$|T(n) - \frac{S(n)-1}{2}| \le \frac{3^\omega - 2^{\omega+1} + 1}{2}$$
3. Théorèmes de sécurité cryptographique :
   • Théorème 1 : Établit que pour un groupe fini $G$ d'ordre pair $n$, le nombre de paires $(y, f)$ produisant un même texte chiffré est d'au moins $T(n)$.
   • Théorème 14 : Généralise ce résultat. Si $n$ est impair, le nombre de solutions est d'au moins $S(n)$ ; si $n$ est pair, il est d'au moins $T(n)$.
4. Analyse des primes sûres : Pour un groupe $G = \mathbb{Z}_p^*$ où $p=2q+1$ est une prime sûre, l'article montre que le nombre de solutions est exactement $p-5$, ce qui est significativement plus grand que la seule solution correcte.

4. Résultats Principaux

• Non-multiplicativité : Contrairement à la fonction d'Euler $\phi$ et à celle de Schemmel $S$, la fonction $T$ n'est pas multiplicative (c'est-à-dire que $T(nm) \neq T(n)T(m)$ même si $\gcd(n,m)=1$).
• Comportement asymptotique : Pour les grands entiers $n$, $T(n)$ est approximativement proportionnel à $S(n)/2$. Puisque $S(n)$ est de l'ordre de $n \prod (1-2/p)$, $T(n)$ reste une fraction significative de $n$.
• Implication cryptographique : L'utilisation de variants de groupes double la complexité de l'attaque par force brute (passant de $O(n)$ à $O(n^2)$ paires à tester). De plus, la présence de $T(n)$ (ou $S(n)$) fausses solutions rend l'identification de la clé réelle extrêmement difficile, car l'attaquant ne peut pas distinguer la solution correcte des nombreuses solutions incorrectes sans information supplémentaire.
• Cas des primes sûres : Dans le cas spécifique des primes sûres ($p=2q+1$), le nombre de collisions est très élevé ($\approx p/4$), rendant le système particulièrement robuste contre les attaques par texte clair connu si la clé $x$ est changée aléatoirement à chaque chiffrement.

5. Signification et Perspectives

L'article démontre que l'application des variants de semi-groupes à la cryptographie offre une nouvelle voie pour renforcer la sécurité du problème du logarithme discret. La fonction $T(n)$ fournit une mesure quantitative de la « résistance » d'un tel système aux attaques par force brute en quantifiant le bruit (les fausses solutions) généré par la structure algébrique du variant.

Signification :

• Théorique : L'article enrichit la théorie des nombres en introduisant une nouvelle fonction arithmétique avec des propriétés de distribution intéressantes et des liens non triviaux avec les fonctions totient classiques.
• Pratique : Il propose un mécanisme cryptographique où la sécurité ne repose pas seulement sur la difficulté de calcul du logarithme discret, mais aussi sur l'ambiguïté structurelle introduite par le variant de groupe.

Perspectives :
L'auteur suggère plusieurs pistes pour de futures recherches :

1. L'étude de généralisations $T_r(n)$ comptant les unités $m$ telles que $(m-1)/r$ soit une unité.
2. L'analyse de la parité des solutions des équations diophantiennes $ap - bq = 1$ (Lemme 4), qui pourrait permettre de prédire le comportement de $T(n)$ pour des composantes spécifiques.
3. L'optimisation des paramètres (choix de $n$ et de la structure du groupe) pour maximiser le rapport entre le nombre de fausses solutions et la taille de l'espace de recherche.

En conclusion, ce travail établit un pont solide entre l'algèbre abstraite (variants de groupes) et la théorie des nombres appliquée à la cryptographie, offrant une nouvelle perspective sur la conception de systèmes résistants aux attaques par force brute.