GoupillWiki

Cette page est en lecture seule. Vous pouvez afficher le texte source, mais ne pourrez pas le modifier. Contactez votre administrateur si vous pensez qu'il s'agit d'une erreur.
====== Générer un nombre premier de n bits ======

<WRAP tip>Si vous voulez tentez ce TD en C, vous trouverez de l'aide sur [[nsi:tds:c:get_n_bits_prime|cette page]].</WRAP>

J'écris cette fiche en me basant sur cette [[https://www.geeksforgeeks.org/how-to-generate-large-prime-numbers-for-rsa-algorithm/|source]].

====== Clé de N bits =====

Dans le cadre de [[nsi:terminales:securite:rsa|RSA]], on veut une clé $N = p_1 \times p_2$ avec $p_1$ et $p_2$ premiers. Pour un niveau de sécurité donné, c'est le nombre de bits de $N$ que l'on veut fixer. On demande par exemple $n = 1024$ bits pour $N$.

Cela signifie que $N$ est dans l'intervalle $[2^{n-1}\,;\,2^n[$.

Pour garantir que $N$ sera dans cet intervalle, on choisit $p_1$ et $p_2$ dans $\left[\sqrt{2}\cdot 2^{\frac{n}{2}-1}\,;\,2^{\frac{n}{2}}\right[$

Par exemple, pour $n = 1024$, on cherche $p_1$ et $p_2$ dans $\left[\sqrt{2}\cdot 2^{511}\,;\,2^{512}\right[$ et on sait qu'on peut en trouver jusque $10^{151}$ donc il y a le choix !

===== premier à n bits =====

Demandons nous maintenant comment on choisit $p_1$ -- idem pour $p_2$.

Voici la procédure :
  * on choisit $p$ à la taille voulue, au hasard\\ On peut choisir $p$ dans $\left[\sqrt{2}\cdot 2^{n-1}\,;\,2^n\right[$
  * on s'assure que $p$ n'est pas divisible par les plus petits nombres premiers. On peut en essayer quelques centaines, voire quelques milliers. On peut facilement garder en mémoire quelques milliers de nombres premiers.\\ Si on trouve un diviseur, on essaie un autre $p$.
  * on lance des tests de //Rabin - Miller//.\\ Si au moins un de ces tests échoue, on recommence au début.\\ Si tous les tests passent, on peut utiliser $p$, on est quasiment certain qu'il est premier.

==== Tests de Rabin - Miller ====

Des détails sur la [[https://fr.wikipedia.org/wiki/Test_de_primalit%C3%A9_de_Miller-Rabin|page Wikipedia]].

C'est une approche probabiliste : trouver un très grand $p$ dont on est certain qu'il est premier demande trop de temps de calcul. On se contente d'être raisonnablement certain que $p$ est premier.

Si $p$ réussit un passage de test Rabin - Miller, la probabilité qu'il soit premier est de 75 %. Autrement dit, le risque qu'il ne soit pas premier est $\frac{1}{4}$.

Si $p$ passe $k$ passage de test, alors la probabilité qu'il **ne soit pas premier** est de $\frac{1}{4^k}$. Dans les applications commerciales, on se contente de diminuer ce risque à $\frac{1}{2^{128}}$. Il suffit donc de réussir $k = 64$ passages de tests.

==== Principe mathématique du test ====

<WRAP important>Je résume ce que je trouve sur Wikipedia, je ne maîtrise pas les détails :-/

Vous pouvez sauter si ça vous paraît trop compliqué/</WRAP>

<wrap tip>On note $a \equiv b [c]$ ou $a \overset{c}{\equiv} b$ si $a \mod c = b$.</wrap>

Soit $p$ un nombre premier. Le [[https://fr.wikipedia.org/wiki/Petit_th%C3%A9or%C3%A8me_de_Fermat|petit théorème de Fermat]] nous dit que pour $2 \leqslant a < p$, on a $a^{p-1} = 1 [p]$.

On sait aussi que si $X^2 \overset{p}{\equiv} 1$ alors $X \overset{p}{\equiv} 1$ ou $X \overset{p}{\equiv} -1 \overset{p}{\equiv} p - 1$.

L'idée est donc de chercher les racines carrés modulo des $p-1$ et de vérifier que le résultat est toujours $1$ ou $-1$.

Pour cela on détermine $d$ et $s$ tels que $p - 1 = d \times 2^s$, avec $d$ impair. Ainsi, pour un nombre $a$ comme précédemment, $a^{d\times 2^{s-1}}$ est la racine de $a^{d \times 2^s} = a^{p-1}$ et donc $a^{d\times 2^{s-1}} \overset{p}{\equiv} 1 \text{ ou } -1$. Et si c'est $1$ alors on peut poursuivre avec la racine suivante, c'est à dire $a^{d\times 2^{s-2}}$. Et ainsi de suite jusque $a^{d}$.

Donc, soit tous les $a^{d\times 2^{s-i}}$ sont égaux à 1 modulo $p$, soit il y en a qui est égal à $-1$ modulo $p$, c'est à dire à $p-1$.

Tout cela nous permet d'énoncer la propriété suivante.

<WRAP box>Si $p$ premier, soit $d$ impair et $s$ tels que $p - 1 = d \times 2^s$, alors on a :
\[a^d \overset{p}{\equiv} 1 \quad \text{ou} \quad \exists i \text{ tel que } 0 \leqslant i \leqslant s - 1, a^{d\times 2^i} \overset{p}{\equiv} p - 1\]

Si on trouve $a$ qui ne vérifie pas cette propriété, il prouve que $p$ n'est pas premier. On qualifie un tel nombre de **témoin de Miller**. Il peut aussi arriver que $p$ ne soit pas premier et que l'on choisisse $a$ vérifiant la propriété. Ce $a$ nous fait croire à tort que $p$ est premier. C'est un **menteur**.

On sait que les menteurs représentent moins de $\frac{1}{4}$ des choix possibles. Si on choisit $a$ au hasard, on a donc une probabilité de $\frac{1}{4}$ d'être trompés. Il suffit de répéter l'opération pour abaisser cette probabilité autant que l'on veut.
</WRAP>

==== Fonctionnement des tests ====

<WRAP important>Je ne connais pas les mathématiques mises en œuvre. Je vous donne juste le fonctionnement...</WRAP>

Pour $p$ donné, dont on veut savoir s'il est premier,
  * on cherche $d$ impair et $s$ tels que $p - 1 = d \times 2^s$.
  * Un passage de test consiste à :
    * choisir au hasard un nombre $a$ entier dans $[2 ; p[$
    * si $a^{d} \mod p = 1$, on peut arrêter, ce passage de test est validé
    * pour $i$ allant de $0$ à $s-1$, si on trouve $a^{d\times 2^i} \mod p = p - 1$, le test réussit également, pas besoin d'aller plus loin
    * sinon le test échoue, $p$ n'est pas premier.
  * Tant que les tests réussissent, on peut recommencer avec un autre $a$ choisit au hasard. On détermine le nombre de tests à faire pour atteindre la probabilité voulue.

==== Implémentation ====

  * Pour le choix de $p$ au hasard, ''random.randrange'' fait l'affaire,
  * vous devez constituer une base de quelques milliers de nombres premiers,
  * pour le calcul de $a^b \mod p$, vous pouvez utiliser une fonction native de Python : ''pow(a, b, p)''.

<WRAP box>**À faire :** implémentez une fonction ''get_prime(n:int) -> int'' qui renvoie un nombre premier à ''n'' bits, ou mieux, appartenant à $\left[\sqrt{2}\cdot 2^{n-1}\,;\,2^n\right[$. Il nous suffit que $p$ soit probablement un nombre premier avec une probabilité de $1 - \frac{1}{2^{128}}$, soit 64 passages de Rabin Miller.</WRAP>