Réseaux et cryptographie¶
Définition¶
Définition
Un réseau est un sous-groupe de \(\R^n\) engendré par une base de \(\R^n\).
Comme groupe, un réseau est isomorphe à \(\Z^n\), mais il a une structure géométrique supplémentaire héritée de l’espace ambiant \(\R^n\) : distance, volume.
Exemple
le réseau \(\Z^n\subset\R^n\). Comme on le verra, il faut avoir conscience que ce réseau n’est pas du tout le réseau typique, il est beaucoup trop régulier et symétrique.
réseau hexagonal \(\Z[j]\subset\C=\R^2\)
\(\Z[\sqrt 2]\subset \R^2\) n’est pas un réseau (sous-groupe dense de \(\R\))
toute matrice \(A\in\Gl_n(\R)\) définit le réseau \(A\Z^n\) engendré par les colonnes de \(A\).
Définition
Soit \(V=(v_1,\dots v_n)\) une base d’un réseau \(\Lambda\). Le domaine fondamental relativement à \(V\) est l’ensemble
L’espace est pavé par les translatés du domaine par le réseau
Définition
Soit \(\Lambda=A\Z^n\subset\R^n\) un réseau. Le volume de \(\Lambda\) est le volume d’un domaine fondamental
En crypto, on s’intéresse surtout aux réseaux entiers, c’est-à-dire aux sous-groupes de \(\Z^n\) de rang \(n\). Dans ce cas, le volume est le cardinal du groupe quotient
\(\Z^n/\Lambda\).
Une construction courante, le réseau du noyau modulo \(N\) d’une application linéaire :
Exemple
Soit \(p\) un nombre premier et \(\lambda\in\F_p^\times\), on pose \(\Lambda=\set{(x,y), x=\lambda y\bmod p}\subset\Z^2\).
Une base est donnée par les vecteurs \((p,0)\) et \((\lambda,1)\), le réseau est de volume \(p\) (ce qui correspond au fait qu’une proportion \(1/p\) des vecteurs de \(\Z^2\) est dans le réseau).
Courts vecteurs¶
Trouver le plus petit vecteur d’un réseau est problème difficile, NP-dur en général https://people.csail.mit.edu/vinodv/6876-Fall2015/L10.pdf.
Pourtant, il est facile de démontrer qu’il existe nécessairement des vecteurs courts
Minkowski
Soit \(\Lambda\subset\R^n\) un réseau, on note \(V_n\) le volume de la boule unité. Si \(V_n R^n\geq \Vol(\Lambda)\), alors \(\Lambda\) contient un vecteur non nul de norme \(\leq 2R\).
Démonstration
La projection de la boule de rayon \(R\) sur \(\R^n/\Lambda\) ne peut pas être injective, deux vecteurs \(x,y\) de même image fournissent un vecteur \(x-y\) du réseau, de norme inférieure à \(2R\).
Corollaire
En notant \(\norm{v_1}\) le plus petit vecteur non nul, on a \(\norm{v_1}\leq 2\left(\frac{\Vol(\Lambda)}{V_n}\right)^{\frac 1n}\), où le volume de la boule
tend vers \(0\) pour \(n\to\infty\).
Exemple
Avec l’exemple précédent, le volume de la boule est \(V_2=\pi\), donc il existe un vecteur de norme \(x^2+y^2\leq (2\sqrt{\frac{p}{\pi}}^2< 2p\).
Si \(p\equiv -1\bmod 4\), on peut choisir \(\lambda\) tel que \(\lambda^2=-1\), alors le vecteur court est de norme \(x^2+y^2\equiv 0\bmod p\), on a donc \(x^2+y^2=p\).
Exemples de problèmes résolus à l’aide de vecteurs courts¶
Approximations rationnelles¶
Une approximation \(\pi\approx\frac ab\), \(b\leq B\), correspond à une petite valeur \(b\pi - a\). Pour se ramener à des valeurs entières, si l’on multiplie par la borne \(B\) et que l’on arrondit, les bonnes approximations correspondent à de petites valeurs entières de \(\delta_{a,b}=b\round{B\pi}-Ba\).
Par exemple pour \(B=10^4\), on pose le réseau
A = [ -10^4, round(10^4*Pi) ; 0 , 1 ]
La fonction qflll renvoie les coordonnées de vecteurs courts,
qflll(A)
et l’on retrouve effectivement les approximations usuelles de \(\pi\) : \(\tfrac{22}7\) et \(\tfrac{355}{113}\).
De manière générale, on a le résultat suivant.
Proposition
Soit \(\alpha\in\R\), et \(B>0\). Alors le réseau
est de volume \(B\), il contient un vecteur \(v=av_1+b_2\) de norme \(\norm{v}\leq \sqrt{3}2\sqrt{B}\), et pour lequel on a l’approximation
Démonstration
En dimension 2, une base réduite \(v,v'\) vérifie \(\Vol(\lambda)\geq \frac{\sqrt3}2\norm{v}^2\), donc ici \(\norm{v}\leq \frac{2}{\sqrt 3}\sqrt{B}\).
Notons \(r=b\round{B\alpha}-aB\) de sorte que \(v=av_1+bv_2=(r,b)\), alors
Relations de dépendance linéaires¶
P = 1+3*x-7*x^2+3*x^4+x^5 r = polrootsreal(P)[1]
Supposons qu’on ne connaisse pas \(P(x)\), comment retrouver ce polynôme à partir d’une approximation d’une racine ?
B=10^3; A = matconcat([matid(5),0;vector(5,k,round(B*r^(k-1))),round(B*r^5)])
Le réseau obtenu contient déjà de petits vecteurs, car \(r<1\). Si on fait le même jeu avec \(-1/r>1\), on obtient de grandes valeurs en dernière coordonnée, ce qui force un petit vecteur (dont on sait qu’il existe) à l’annuler.
r = -1/r; B=10^3; A = matconcat([matid(5),0;vector(5,k,round(B*r^(k-1))),round(B*r^5)])
qflll(A)
On reconnaît bien le polynôme (réciproque) comme plus court vecteur.
gp > lindep([1,Pi,Pi^2,Pi^3],5) %6 = [19, -15, -16, 6]~ gp > 19 - 15*Pi-16*Pi^2+6*Pi^3 %7 = 9.9860522284574566383655397409785263529 E-5
Attaque de Wiener¶
La relation \(ed-k\varphi(n)=1\) implique que \(ed-kn = 1 - k (n-\varphi(n)) = O(k\sqrt n)\), avec \(k<d\).
On considère le réseau engendré par \(v_1=(e,\sqrt n)\) et \(v_2=(n,0)\), alors le vecteur \(w=dv_1-kv_2=(O(k\sqrt n),d\sqrt n)\) est de norme \(\norm{w}=O(d\sqrt n)\), et le réseau de volume \(n^{\frac 32}\).
Si \(d=O(n^{\frac14})\), alors \(w\) est un petit vecteur du réseau.
Bases¶
L’espace des réseaux de \(\R^n\) est donc le groupe \(\Gl_n(\R)/\Gl_n(\Z)\) (bases modulo changement de base).
Définition
Si \(\Lambda\subset\Z^n\) est un réseau entier, la forme normale de Hermite est une base bien définie du réseau.
On a unicité de cette base, mais d’un point de vue géométrique elle est catastrophique : le domaine fondamental est complètement applati, les vecteurs de la base sont gigantesques.
Il existe toujours une base dont le premier vecteur est le plus court vecteur, et il existe des bases
SVP, CVP¶
Définition
On appelle Shortest Vector Problem le problème de déterminer le plus court vecteur d’un réseau, et Closest Vector Problem celui de déterminer le vecteur du réseau le plus proche d’un point de \(\R^n\).
Ce sont deux problèmes très durs dès que le réseau n’a pas de structure particulière et que la dimension augmente.
Voir par exemple le jeu Cryptris https://cryptris.nl/index_fr.html pour se convaincre qu’obtenir de petits vecteurs à partir d’une mauvaise base est très compliqué.
Pour résoudre le CVP, on a besoin d’une base la plus orthogonale possible.
Soit \(v_1\) le plus court vecteur du réseau, alors on peut disposer des boules de diamètre \(\norm{v_1}\) aux points du réseau qui sont tangentes : un réseau donne un empilement de sphères.
Réduction¶
Définition
Une base d’un réseau est une base en tant que \(\Z\)-module. Deux bases d’un réseau diffèrent par un élément de \(Gl_n(\Z)\).
Exemple
Le réseau \(\Z^2\) a pour base \(v_1=(4,3)\) et \(v_2=(3,2)\).
La réduction consiste à obtenir la base la plus agréable possible pour un réseau. Une «bonne base» est
formées de vecteurs courts
qui sont aussi orthogonaux que possible, (c’est-à-dire que les angles sont minorés).
L’intérêt de ce second critère est que les courts vecteurs du réseau aient de petits coefficients sur la base, et que le domaine fondamental contienne la plus grande boule possible.
Attention, quand la dimension augmente la géométrie est pleine de surprises :
la famille libre des plus courts vecteurs n’est pas toujours une base
la plus petite base pour l’ordre lexicographique sur les normes (base de Hermite) est en général loin d’être orthogonale.
Cas de la dimension 2¶
Par exemple, pour un réseau de \(\R^2\), si l’on prend pour \(v_1\) le plus petit vecteur et qu’on renormalise en posant \(v_1=(0,1)\), \(v_2\) est en dehors du cercle unité, et par translations de \(v_1\) on peut le choisir dans la bande \(-1/2,1/2\).
Cela signifie que
le projeté orthogonal \(v_2^\bot\) de \(v_2\) sur \(\prodscal{v_1}^\bot\) est de norme supérieure à \(\frac{\sqrt 3}2=\frac{\sqrt 3}2\norm{v_1}\)
la composante de \(v_2\) sur \(v_1\), c’est-à-dire le coefficient \(\mu\) de l’égalité \(v_2=v_2^\bot+\mu v_1\), est inférieure à \(1/2\).
Réduction de Hermite¶
En généralisant on obtient la définition suivante
Définition
Une base \((\alpha,\beta)\)-réduite d’un réseau \(\Lambda\) est une base \(v_1,\dots v_n\) telle que pour tout \(i\), si on note \(v_i^\bot\) la projection de \(v_i\) sur \(\prodscal{v_{i+1},\dots v_{i+n}}^\bot\), alors
\(\norm{v_{i+1}^\bot}\geq \alpha \norm{v_{i}^\bot}\)
en écrivant \(v_i = v_i^\bot + \sum_{j<i} \mu_{i,j} v_j^\bot\) on a \(\abs{\mu_{i,j}}\leq\beta\).
La traduction en termes de matrices est plus simple à comprendre : soit \(v_1,\dots v_n\) une base et \((v_1^\bot,\dots v_n^\bot)\) son orthogonalisée de Gram-Schmidt.
En disposant les vecteurs en colonne, le procédé d’ortogonalisation de Gram-Schmidt s’écrit
où les coefficients \(\star\) de la matrice de droite sont les composantes de projection \(\frac{\prodscal{v_i^\bot,v_j}}{\norm{v_i^\bot}_2^2}\).
Le critère de \(\beta\)-reduction consiste simplement à prendre les coefficients \(\abs{\star}\leq\frac12\), ce qui est trivial par opérations sur les colonnes.
Par ailleurs, en notant \(D\) la matrice diagonale \((\norm{v_i^\bot})_i\), la matrice des \(v_i^\bot\) s’écrit \(KD\), où \(K\in O_n(\R)\) est la matrice de la base orthonormale \(\frac{v_i^\bot}{d_i}\).
Le critère de réduction \(\alpha\) consiste à imposer que la diagonale \(D\) soit «pseudo-croissante» de raison au moins \(\alpha\).
On obtient donc le théorème de Hermite d’existence d’une base réduite
Hermite, Siegel
Soit
l’ensemble des matrices triangulaires supérieures bornées par \(\beta\), et
l’ensemble des matrices diagonales \(\alpha\)-échelonnées.
Si \(\alpha\leq\frac{\sqrt3}2\) et \(\beta\geq\frac12\), alors
En d’autres termes, tout réseau possède une base \(\alpha,\beta\)-réduite.
Démonstration
La démonstration, dans les premiers paragraphes de [Borel-IntroGroupesArithmetiques], est celle que l’on va donner de l’algorithme LLL ci-dessous,
Une base réduite au sens de Hermite n’est pas unique, mais elle se calcule en temps polynomial : c’est l’algorithme appelé LLL.
algorithme LLL
Soit \(V=(v_1,\dots v_n)\) une base de \(\R^n\), on considère la procédure suivante :
calculer la base orthogonale \(v_1^\bot,\dots v_n^\bot\)
ajuster chaque \(v_j\) par une combinaison entière des \(v_i,i<j\) pour que \(-\beta < \star = \frac{\prodscal{v_i^\bot,v_j}}{\norm{v_i^\bot}^2}\leq \beta\)
vérifier pour \(i=1,\dots n-1\) que \(\norm{v_{i+1}^\bot}\geq \alpha\norm{v_i^\bot}\), sinon échanger \(v_i\) et \(v_{i+1}\) et reprendre au début.
Si \(\alpha\leq\frac{\sqrt{3}}2-\epsilon\) et \(\beta\geq\frac12\), cette procédure termine en un nombre d’opérations polynomial en \(n,\frac1\epsilon\) et produit une base \(\alpha,\beta\) réduite.
Démonstration
Il suffit de que l’on réalise un nombre polynomial d’échanges \((i,i+1)\), on le montre en considérant le volume du réseau engendré par les \(i\) premiers vecteurs \(v_1,\dots v_i\).
Après échange des vecteurs \(i,i+1\), les vecteurs orthogonaux \(v_1^\bot,\dots v_{i-1}^\bot\) ne changent pas, tandis que l’on a désormais au rang \(i\) le vecteur \(\tilde v_{i}^\bot = v_{i+1}^\bot+a_{i,i+1}v_i^\bot\) (\(v_{i+1}^\bot\) était réduit par rapport à l’ancien \(v_i^\bot\), ce n’est plus le cas).
Le volume du réseau engendré par les \(i\) premiers vecteurs est \(\prod_{j\leq i}\norm{v_j^\bot}\). Lors de l’échange, le carré du volume décroît d’un facteur \(\frac{\norm{\tilde{v_{i}^\bot}}^2}{\norm{v_{i}^\bot}^2} \leq \alpha^2+\frac14 < 1\) (on utilise l’orthogonalité pour développer la norme).
Puisque le réseau est discret, il ne peut y avoir qu’un nombre logarithmique d’échange sur chaque indice \(i\), d’où la terminaison et la complexité.
La traduction matricielle est la suivante
on part d’une matrice \(V\in\Gl_n(\R)\)
calculer l’orthogonalisation \(V = V^\bot A\), \(A\) triangulaire supérieure, ainsi que \(d=(\norm{v_i^\bot})\).
calculer \(U\in\Gl_n(\Z)\) telle que \(AU\) ait des coefficients \(\abs{\star}\leq \beta\)
si il existe \(i\) tel que \(d_{i+1}\leq \alpha d_i\), échanger les colonnes \(i\) et \(i+1\) de \(U\) recommencer en remplaçant \(V\) par \(VU\).
Retourner la base \(VU\).
Pour \(\alpha<\frac{\sqrt3}2\) et \(\beta>\frac12\) on a un algorithme de calcul polynomial.
Démonstration
Le principe : Si \(v_1,\dots v_n\) est une base, on considère son orthogonalisée de Gram-Schmidt \(\overline{v_1},\dots \overline{v_n}\) et on se ramène en décalant \(v_i\) d’une combinaison de \(v_j, j<i\) à des coordonnées \(a_i,j=\prodscal{v_i,\overline{v_j}}\leq \beta\). On vérifie la condition \(\alpha\), s’il existe \(i\) tel que \(\norm{\overline{v_i+1}}<\alpha\norm{\overline{v_i}}\) on échange les deux vecteurs et on recommence depuis le début.
Théorème : l’algorithme termine en temps polynomial.
En pratique, rendre l’algorithme efficace est un sujet de recherche complexe.
Théorème
Les bases réduites satisfont
en particulier
à comparer avec la borne de Minkowski
Un des buts de la théorie est d’écrire des
Cryptographie et réseaux¶
Les cryptosystèmes construits à partir de réseaux : utilisent en général un problème CVP, facile à résoudre si on a une bonne base (clef privée) et impossible avec une mauvaise base (clef publique).
Un message est un petit vecteur. Il est dans le domaine fondamental d’une bonne base, mais pas dans celui d’une mauvaise. On chiffre et déchiffre en transmettant l’image du vecteur dans le domaine fondamental.
Les cryptosystèmes attaqués via les réseaux : sac à dos, Coppersmith
Le cryptosystème Sac à Dos¶
On appelle sac à dos le problème combinatoire suivant : soit \(c\) un entier, la capacité du sac, et \(a_1,\dots a_n\) des entiers positifs. On cherche à écrire \(c=\sum e_ia_i\) pour des coefficients \(e_i\in\set{0,1}\).
C’est-à-dire que l’on veut sélectionner des objets dans un ensemble qui permettent de remplir exactement le sac-à-dos.
C’est un problème NP-complet.
Cryptosystème de Merkle-Hellman¶
On prend une suite \(a_i\) dite supercroissante, c’est-à-dire telle que pour tout \(i\), \(a_i>\sum_{j<i}a_j\).
Dans ce cas le problème de sac-à-dos se résout trivialement par approche gloutonne (on a \(m_n=1\Leftrightarrow c\geq a_n\), puis \(m_{n-1}=1\Leftrightarrow c-m_na_n \geq a_{n-1}\), etc.)
On mélange cette suite de poids \(a_i\) comme suit : on choisit un module \(N>\sum a_i\), un élément aléatoire \(K\in(\Z/N\Z)^\times\), et on pose \(b_i=K a_i\bmod N\).
La clef publique est la suite de poids modifiés \(b_i\), de longueur \(n\).
On chiffre un message \(m\in\set{0,1}^n\) par l’entier \(c=\sum m_i b_i\).
La clef privée est la suite supercroissante \(a_i\), et les entiers \(N,K\).
Pour déchiffrer, on se ramène au problème facile en posant \(K^{-1}c\bmod N = \sum m_i a_i\bmod N\), ce qui permet de retrouver les \(m_i\).
Attaque LLL¶
La stratégie habituelle est de trouver le vecteur \(m_i\) comme vecteur court \((m_0,\dots m_n,0)\) du réseau engendré par les colonnes de
Toutefois, il est probable que ce réseau contienne beaucoup d’autres vecteurs \((x_1,\dots x_n,\epsilon)\) avec \(\sum x_ib_i = c+\epsilon\). Pour ne sélectionner que des solutions atteignant l’égalité \(\sum x_ib_i=c\) on met un grand poids \(B\approx\sqrt n\) à la dernière ligne, de sorte qu’un vecteur ne satisfaisant pas l’égalité est automatiquement grand.
Un autre problème est que contrairement à la solution du sac à dos, les courts vecteurs s’autorisent à prendre indifféremment des coefficients positifs et négatifs.
Une astuce pour privilégier les coefficients \(0\) et \(1\) consiste à considérer le réseau
Le vecteur correspondant à la combinaison de colonnes \((m_1,\dots m_n,1)\) d désormais pour composantes \((m_1-\frac12,\dots m_n-\frac12,0)\) de norme \(\sqrt{n}/2\) puisque chaque composante vaut \(\pm\frac12\).
On obtient un résultat similaire en prenant le réseau
et une constante \(B > n\).
On appelle densité du problème la quantité
Algorithme de Coppersmith¶
Cet algorithme permet de déterminer les «petites racines» de polynômes de «petit degré» modulo un entier \(n\) non premier.
Remarque
Il est facile de trouver les racines modulo \(p\) d’un polynôme, en calculant d’abord \(f_0 = \pgcd(f,x^p-x)\) pour isoler le facteur scindé modulo \(p\), puis si ce facteur est de degré \(>1\) on le décompose en calculant \(\pgcd(f_0,(x+a)^{\frac{p-1}2}-1)\) pour des valeurs aléatoires de \(a\), ce qui sépare les racines \(x\) telles que \(x+a\) est un carré (technique de Cantor-Zassenhaus).
Tout algorithme permettant de trouver une racine d’un polynôme modulo \(n\) permet de factoriser \(n\) (on obtient en particulier les racines carrées).
La première étape est de montrer qu’il est facile de calculer les petites racines de polynômes à petits coefficients, puisque ce sont en réalité des racines dans \(\Z\).
Lemme
Soit \(f(x)\in\Z[x]\) de degré \(n\), si
\(f(x_0)\equiv 0\bmod b^m\) avec \(\abs{x_0}\leq X\)
\(\norm{f(xX)}_2 < \frac{b^m}{\sqrt(n)}\)
alors \(f(x_0)=0\) dans \(\Z\).
Démonstration
On applique Cauchy-Schwartz \(\abs{f(x_0)}=\abs{\sum a_ix_0^i}\leq\sum \abs{a_iX^i}\leq \sqrt n\norm{f(xX)}_2<n\) donc la congruence à \(0\) est en réalité une égalité.
Soient maintenant \(f(x)\) un polynôme dont on sait qu’il a une racine \(f(x_0)\equiv 0\bmod b\), où \(x\leq X\) et \(b\) est un diviseur de \(N\), avec \(b\geq N^\beta\).
\(b\) et \(x_0\) sont les inconnues, tandis que les paramètres \(X,N,\beta\) sont connus. Il suffit de déterminer \(x_0\), puisqu’on retrouve ensuite \(b\) en calculant \(\pgcd(f(x_0),N)\).
On se ramène au lemme en déterminant un polynôme \(g(x)\) dont \(x_0\) est racine, et qui a de petits coefficients : la stratégie est de construire un réseau de tels polynômes pour obtenir une combinaison linéaire petite.
Si \(f(x_0)\equiv 0\bmod b\), alors \(N^ix_0^jf(x_0)^k\equiv 0\bmod b^{i+k}\), de sorte que les polynômes \(g_{i,j}(x) = N^{m-i}x^jf^i(x)\) vérifient \(g_{i,j}(x_0)\equiv 0\bmod b^m\), ainsi que toute combinaison linéaire.
On considère le réseau engendré par les coefficients des \(g_{i,j}(xX)\), s’il possède un vecteur de norme \(\norm{g}_2\leq \frac{b^m}{\sqrt n}\), on a gagné. On choisit \(X\) le plus grand possible pour que les bornes LLL permettent d’obtenir un tel \(g\).
Coppersmith
Soit \(N\) un entier composé possédant un diviseur \(b\geq N^\beta\). Soit \(f(x)\in\Z[x]\) un polynôme unitaire de degré \(\delta\). Alors on peut trouver toutes les solutions \(x_0\) de l’équation \(f(x)\equiv 0\bmod b\) telles que
en temps polynomial en \(\log(N),\delta,\frac1\epsilon\).
Démonstration
voir May [MayRSA].
L’attaque ROCA¶
Autrement dit, «Coppersmith, le retour», 2016-2017.
La société Infineon est un poids lourd des semiconducteurs embarqués. Elle commercialise des solutions cryptographiques, par exemple des cartes d’identité numériques sécurisées. À ce titre, elle a sa propre bibliothèque de cryptographie RSA, très largement utilisée dans ce contexte.
En 2016 des analystes ont repéré des anomalies statistiques sur les clefs publiques commercialisées par cette société et découvert une faille majeure permettant de factoriser les clefs publiques.
La seule publication du fait que les clefs n’étaient pas robustes a permis à d’autres cryptographes de découvrir la faille et reconstituer l’attaque en quelques jours.
Reconstitution¶
Quand on génère des premiers RSA, la stratégie est de tirer des entiers au hasard et de tester leur composition. Pour gagner du temps, on peut se restreindre à tirer des entiers impairs, puis non divisibles par \(3\), etc.
Une stratégie acceptable est de tirer au hasard des entiers \(a_i\neq 0\bmod p_i\) et d’imposer que \(p\) soit congru à \(a_i\) modulo \(p_i\), ie à une valeur \(A\) modulo \(M=\prod p_i\).
En effet, le choix a priori de congruences indépendantes ne modifie par la distribution finale, si l’on choisit ces congruences de manière uniforme et indépendante pour chaque choix de premier.
En revanche, des versions erronées de cette stratégie seraient de
conserver la valeur \(A\) entre tirages de premiers distincts
choisir \(A\) directement modulo \(M\) par une méthode qui n’assure pas une distribution uniforme sur \((\Z/M\Z)^\times\).
En observant les clefs Infineon, les cryptographes se sont rendus compte qu’elles n’étaient pas du tout distribuées uniformément modulo les petits premiers, ce qui correspond à la seconde erreur.
La démarche adoptée par les programmeurs d’Infineon est la suivante : ils prennent un très grand produit de premiers successifs \(M\), et cherchent \(p\) congru à \(A=e^a\bmod M\) où \(e=65537=2^{16}+1\) est l’exposant de chiffrement, et \(a\) est un exposant tiré aléatoirement avant le choix de \(p\).
De cette manière on évite de considérer les entiers divisibles par de petits nombres premiers, ainsi que ceux qui sont congrus à \(1\) modulo \(e\).
Concrètement, pour un premier \(p=kM+(e^a\bmod M)\) de 256 bits, le module \(M\) est de \(219\) bits (produit des 39 premiers inférieurs à 167), ainsi que l’exposant \(a\), et le multiplicateur \(k\) de \(37\) bits.
On a bien l’impression que le double choix de \(k\) et \(a\) se fait dans un espace de \(219+37=256\) bits, mais en réalité le sous-groupe \(\prodscal{e}\bmod M\) engendré par \(e\) est de taille au plus \(\ppcm_{p\leq 167}(p-1) \approx 2^{61}\) dans \((\Z/M\Z)^\times\) qui n’est pas du tout cyclique. On choisit donc \(p\) dans un sous-ensemble minuscule.
Comment factoriser ? si l’on connaît \(a\) c’est facile, on connaît alors \(p\bmod M\) avec \(M>\sqrt N\), ce qui permet d’appliquer l’attaque de Coppersmith sur les bits de poids faible de \(p\).
On ne connaît pas \(a\), et l’attaque sur \(a\) est de type force brute, mais avec quelques astuce.
D’abord l’espace de recherche (60 bits) est grand, mais puisqu’on peut appliquer Coppersmith tant que \(M>\sqrt N\), on peut artificiellement prendre pour \(M\) un produit minimal de premier, ce qui diminue la taille du groupe \(\prodscal{e\bmod M}\).
Par exemple, \(M'=\prod_{p\leq 103}p\) a plus de 128 bits, et \(e\) est d’ordre \(\lambda<2^{39}\) modulo \(M'\). Cela vaut aussi la peine de chercher un sous-produit différent \(\prod_{i\in I}p_i>\sqrt N\) qui minimise l’ordre du groupe \(\ppcm_{i\in I}(p_i-1)\).
Ensuite, puisque les deux facteurs \(p\equiv e^a\bmod M'\) et \(q\equiv e^b\bmod M'\) sont construits de la même manière, il suffit de déterminer \(a\) ou \(b\) modulo \(\lambda\), sachant que l’on connaît la somme \(a+b\) puisque \(N\equiv e^{a+b}\bmod M'\). L’intervalle \([\frac{a+b}2,\frac{a+b+\lambda}2]\) contient \(a\) ou \(b\).
https://crocs.fi.muni.cz/_media/public/papers/nemec_roca_ccs17_preprint.pdf