YooGoo

 
 
Bienvenue sur YooGoo
  
 

 
 
News

Description du Projet
Avancement du Projet
L'équipe
Photos du Projet et du reste
 
 

 
 
Téléchargement

Le Client
Le Serveur
Les Sources Serveur
Les Sources Client
Cahiers des Charges
Soutenance 1
Soutenance 2
Soutenance 3
Soutenance Finale
 
 

 
 
Contacts

Franck Tetzlaff CV Tessari Marco CV Bouhelier Stéphane CV Pouiller Jérôme CV		 
 
 
 

Le cryptage des données

YooGoo est crypté, donc, toute la première phase de la connexion se compose de la génération et de l'échange des clés de cryptage. Dans la suite, le cryptage est totalement transparent. Lorsque nous appelons la fonction permettant l'envoie de donnée, celle-ci crypte les données avant de les envoyer.

Récapitulatif

Il existe plusieurs algorithmes de cryptage. Les plus simples et les plus anciens sont les algorithmes secrets. Ce sont des algorithmes dont on ne connaît pas le procédé de cryptage. Il est tenu secret. Cette méthode ne nous convient pas, car les sources de notre projet sont disponibles pour tous les utilisateurs, donc l'algorithme de cryptage ne sera pas secret. Il existe alors des algorithmes à clé. L'algorithme est alors connu de tous mais la clé doit rester secrète car c'est d'elle que dépend la sécurité du message. Ceci permet de pouvoir utiliser un même algorithme autant de fois que l'on veut, car la sécurité ne dépend pas du procédé mais de la clé. C'est donc cette méthode qui a été retenue pour YooGoo. On distingue alors deux types de cryptage à clé. Les algorithmes symétriques et asymétriques.

Le cryptage symétrique, et en particulier le DES (Data Encryption Standard) que nous utiliserons, a besoin d'une seule clé pourcrypter et décrypter le message. Cette clé doit alors être tenue secrète et les deux parties communicantes doivent derenir la clé. L'avantage est que ces algorithmes sont assez rapides et permettent le cryptage d'un grand nombre de données. Mais l'inconvénient est que les deux parties doivent detenir la clé. Dans notre cas cela implique l'échange de la clé entre le client et le serveur. Il faut donc trouver une autre méthode pour cet échange. De plus le DES est devenu peu sûr à cause des machines très puissantes actuelles. Nous utiliserons alors un triple-DES qui revient à crypter 3 fois le message (et donc avoir 2 ou 3 clés). Dans YooGoo on utilisera donc le DES pour crypter les messages entre les clients et le serveur.

Le cryptage asymétrique, et en particulier le RSA, fonctionne sur un principe de clé publique et de clé privée. On appelle clé publique la clé qui est accessible à tout le monde et qui permet de crypter les messages. La clé privée, qui elle doit être tenue secrète, sert à décrypter le message. On s'aperçoit alors que tout le monde peut crypter un message et que seulement une personne peut le décrypter. Ainsi, il est parfois impossible de savoir de qui provient le message. De plus le RSA se base sur des propriétés arithmétiques qui exigent des calculs sur de très grands nombres (pour que l'algorithme soit suffisamment sûr), ce qui fait que le temps de cryptage est beaucoup plus long que des algorithmes tels que le DES. Par conséquand le RSA sera seulement utilisé pour l'échange de la clé entre le serveur et les clients.

Le DES

Principe:

DES est un chiffrement par bloc, ce qui signifie qu'il traite les données en sections de taille fixe, appelées blocs. La taille d'un bloc DES est de 64 bits ; si le volume de données à chiffrer n'est pas un multiple pair de 64 bits, les données sont complétées d'une façon dépendante de l'application (par des '$\backslash$0' dans YooGoo).

La sécurité du DES repose sur le même principe qu'un écran de fumée ou, en jargon cryptographique, sur les principes de confusion et de diffusion. Le but de la confusion est de cacher toute relation existante entre le texte clair, le texte chiffré et la clé. Le but de la diffusion est de répartir les effets conjugués du texte clair et de la clé sur la plus grande longueur possible de texte chiffré. Ces deux principes rendent l'analyse cryptographique très difficile.

Avec DES, on chiffre un bloc de texte clair en réalisant une série de permutations et de substitutions sur celui-ci. Leur conséquence sur le texte clair est essentiellement fonction des 16 sous-clés, $K_1$, $K_2$, ... , $K_{16}$, dérivées d'une clé de départ, $K_0$ qui est celle que l'on fournit. Pour chiffrer un bloc de texte clair, les sous clés sont appliquées tour à tour ($K_1$, $K_2$, ..., $K_{16}$) sur les données à l'aide d'une suite d'opérations répétées 16 fois par clé. Chaque itération s'appelle un round. Le déchiffrement d'un bloc crypté s'effectue de la même façon, mais en appliquant les clés en sens inverse ($K_{16}$, $K_{15}$, ..., $K_1$).

Tous les tableaux utilisés lors des décalages, permutations, transformations et rotations, sont établis par une norme DES pour que l'algorithme ai une confusion et une dispersion maximum. La description de l'algorithme est très fastidieuse car les opérations effectuées peuvent sembler sorties de nulle part (c'est d'ailleurs un peu le cas).

Calcul des sous-clés

La première étape consiste à calculer les sous-clés à partir de la clé de départ. DES utilise une clé de 56 bits, mais nous en fournissons une de 64 bits car, car les 8 bits restants sont utilisés dans les implémentations matérielles du DES. Pour obtenir la clé de 56 bits, on effectue une transformation de clé selon le tableau Des_Transform[]. 

        // Correspondances pour la transformation de la clé
        static const int Des_Transform[56] =
        {
            57, 49, 41, 33, 25, 17,  9,  1, 58, 50, 42, 34, 26, 18,
            10,  2, 59, 51, 43, 35, 27, 19, 11,  3, 60, 52, 44, 36,
            63, 55, 47, 39, 31, 23, 15,  7, 62, 54, 46, 38, 30, 22,
            14,  6, 61, 53, 45, 37, 29, 21, 13,  5, 28, 20, 12,  4
        };

Chaque position $p$ du tableau contient la position du bit de la clé de départ occupant la position $p$ de la clé transformée. Le bit 57 de la clé de départ, devient par exemple le bit 1 de la clé transformée ; de même, le bit 49 devient le bit 2, et ainsi de suite. La convention est de numéroter les bits de gauche à droite, en commençant à 1.

Après avoir transformé la clé en 56 bits, on calcule les sous-clés en divisant d'abord la clé en deux blocs de 28 bits. Puis, pour chaque sous-clé, on effectue une rotation des deux blocs d'un nombre de fois dépendant du round dans lequel on utilisera la sous-clé selon le tableau Des_Rotations[], puis on réunit les blocs. 

        // Nombre de rotations pour le calcul des sous-clés
        static const int Des_Rotations[16] =
        {
        1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1
        };

Après cela on réduit les sous-clés de 56 bits, formées des blocs réunis, à 48 bits en les permutant selon le tableau Des_Permute[]. 

        // Correspondances pour le choix permuté des sous-clés
        static const int Des_Permute[48] =
        {
        14, 17, 11, 24,  1,  5,  3, 28, 15,  6, 21, 10,
        23, 19, 12,  4, 26,  8, 16,  7, 27, 20, 13,  2,
        41, 52, 31, 37, 47, 55, 30, 40, 51, 45, 33, 48,
        44, 49, 39, 56, 34, 53, 46, 42, 50, 36, 29, 32
        };
Cette permutation s'appelle "choix permuté". Ce traitement est répété pour chacune des 16 sous-clés. Le but de tout cela est de s'assurer que l'ont peut appliquer, dans chaque round, les différents bits de la clé de départ aux données.

Pour gagner en rapidité d'exécution, lorsqu'on ne passe pas de clé en paramètre à la fonction de cryptage, c'est alors la clé utilisée lors de l'appel précédent qui est utilisée. Les sous-clés sont déclarées en "static", et ne sont alors pas recalculées.

Chiffrement et déchiffrement des blocs de données

Lorsque l'on a préparé les sous-clés, on est prêt à chiffrer ou déchiffrer des blocs de données. On commence par permuter les blocs de données de 64 bits selon le tableau Des_Initial[]. 

        // Correspondances pour la permutation initiale des blocs
        static const int Des_Initial[64] =
        {
        58, 50, 42, 34, 26, 18, 10,  2, 60, 52, 44, 36, 28, 20, 12, 4,
        62, 54, 46, 38, 30, 22, 14,  6, 64, 56, 48, 40, 32, 24, 16, 8,
        57, 49, 41, 33, 25, 17,  9,  1, 59, 51, 43, 35, 27, 19, 11, 3,
        61, 53, 45, 37, 29, 21, 13,  5, 63, 55, 47, 39, 31, 23, 15, 7
        };
Cette permutation porte, fort à propos, le nom de permutation initiale. Elle n'améliore pas la sécurité du DES, mais elle doit être effectuée pour être conforme à la norme DES. Après la permutation initiale, le bloc de 64 bits de données est divisé en deux blocs de 32 bits, $L_0$ et $R_0$.

Après la permutation initiale le bloc de données passe par une série d'opérations répétées pendant 16 rounds. Le but de chaque round $i$ est de calculer $L_i$ et $R_i$, utilisés par le round suivant, jusqu'à obtenir finalement le bloc de données $R_{16}L_{16}$. On commence chaque round avec $L_{i-1}$ et $R_{i-1}$ et on étend $R_{i-1}$ de 32 à 48 bits à l'aide d'une fonction d'expansion, selon le tableau Des_Expansion[]. 

        // Correspondances pour la fonction d'expansion des blocs
        static const int Des_Expansion[48] =
        {
            32,  1,  2,  3,  4,  5,  4,  5,  6,  7,  8,  9,
            8,  9, 10, 11, 12, 13, 12, 13, 14, 15, 16, 17,
            16, 17, 18, 19, 20, 21, 20, 21, 22, 23, 24, 25,
            24, 25, 26, 27, 28, 29, 28, 29, 30, 31, 32,  1
        };
Le but principal de cette fonction est de créer un effet d'avalanche lors du chiffrement des données : un seul bit du bloc de données affecte plus de bits à l'étape suivante, ce qui provoque donc une diffusion. Après cette étape, on calcule le OU exclusif (note $\oplus$) du résultat de 48 bits et de $K_i$, la sous-clé du round : cela donne un résultat intermédiaire de 48 bits, appelé $R_{int}$. Soit $E$, la fonction d'expansion, les opérations réalisées jusqu'à maintenant dans le round peuvent s'exprimer comme suit:

\begin{displaymath}R_{int} = E(R_{i-1}) \oplus K_i\end{displaymath}


Puis, $R{int}$ subit huit substitutions réalisées a l'aide de huit boîte-S. Chaque boîte-S j prend un bloc de 6 bits, de la position $6j$ à $6j+6$ dans $R_{int}$ et recherche une valeur de 4 bits pour lui dans la table Des_SBox[]. Cette valeur est écrite dans le tampon à la position $4j$. 

        // Tableaux pour les substitutions par boîtes-S sur les blocs
        static const int Des_SBox[8][4][16] =
        {
        {
        {14,  4, 13,  1,  2, 15, 11,  8,  3, 10,  6, 12,  5,  9,  0,  7},
        { 0, 15,  7,  4, 14,  2, 13,  1, 10,  6, 12, 11,  9,  5,  3,  8},
        { 4,  1, 14,  8, 13,  6,  2, 11, 15, 12,  9,  7,  3, 10,  5,  0},
        {15, 12,  8,  2,  4,  9,  1,  7,  5, 11,  3, 14, 10,  0,  6, 13},
        },
                ...
        {
        {13,  2,  8,  4,  6, 15, 11,  1, 10,  9,  3, 14,  5,  0, 12,  7},
        { 1, 15, 13,  8, 10,  3,  7,  4, 12,  5,  6, 11,  0, 14,  9,  2},
        { 7, 11,  4,  1,  9, 12, 14,  2,  0,  6, 10, 13, 15,  3,  5,  8},
        { 2,  1, 14,  7,  4, 10,  8, 13, 15, 12,  9,  0,  3,  5,  6, 11},
        },
        };
Pour lire la table Des_SBox[], on trouve la boîte-S $j$, on recherche le numéro de ligne ayant la valeur de deux bits, formée par le premier et le dernier bit du bloc de six bits, et le numéro de colonne ayant la valeur de quatre bits formés des bits du milieu de ce même bloc (les numéros de lignes et colonnes commencent à 0). Les boîtes-S ajoutent de la confusion aux données, et font, plus que tout autre chose, la sécurité de DES : elles ont donc été longtemps l'objet d'examens minutieux.

Lorsque les substitutions par boîtes-S sont terminées, le résultat est une valeur de 32 bits que l'on permute à l'aide d'une boîte-P, selon le tableau Des_PBox[]. 

        // Correspondances pour la permutation-P
        static const int Des_Pbox[32] =
        {
        16,  7, 20, 21, 29, 12, 28, 17,  1, 15, 23, 26,  5, 18, 31, 10,
        2,  8, 24, 14, 32, 27,  3,  9, 19, 13, 30,  6, 22, 11,  4, 25
        };

A cette étape, il est pratique de considérer les opérations du round comme une fonction $f$. Si $b_j$ est $j^e$ bloc de six bits de $R_{int}$, $S_j$ la $j^e$ boîte-S, et P la permutation-P, cette fonction se définit par :

\begin{displaymath}f = P(S_1(b_1),S_2(b_2),\cdot,S_8(b_8))\end{displaymath}

La dernière opération de chaque round consiste à calculer le OU exclusif du résultat de $f$, sur 32 bits, et du bloc gauche original passé au round, $L_{i-1}$. Lorsque cela est fait, on échange les blocs gauche et droit et on commence le round suivant. Au dernier round, cependant, on n'effectue pas cet échange. Mis ensembles, les calculs des $L_i$ et $R_i$ de chaque round peuvent être ainsi énoncés:

\begin{displaymath}L_i = R_{i-1}\end{displaymath}


\begin{displaymath}R_i = L_{i-1} \oplus f(R_{i-1},K_1)\end{displaymath}

Lorsque les 16 rounds sont terminés, on concatène le bloc droit final, $R_{16}$, avec le bloc gauche final, $L_{16}$, pour produire le bloc de 64 bits, $R_{16}L_{16}$ (le bloc droit et le bloc gauche ne sont pas échangés dans le round final : le dernier bloc droit est donc à gauche et le dernier bloc gauche à droite). L'étape finale consiste à permuter $R_{16}L_{16}$ selon le tableau Des_Final[]. 

        // Correspondances pour la permutation finale des blocs
        static const int Des_Final[64] =
        {
        40,  8, 48, 16, 56, 24, 64, 32, 39,  7, 47, 15, 55, 23, 63, 31,
        38,  6, 46, 14, 54, 22, 62, 30, 37,  5, 45, 13, 53, 21, 61, 29,
        36,  4, 44, 12, 52, 20, 60, 28, 35,  3, 43, 11, 51, 19, 59, 27,
        34,  2, 42, 10, 50, 18, 58, 26, 33,  1, 41,  9, 49, 17, 57, 25
        };
Cette permutation s'appelle évidemment "permutation finale"; elle annule simplement ce que la permutation initiale avait fait plus tôt. Lorsque l'on chiffre les données, le résultat est un bloc de 64 bits de texte chiffré ; lorsque l'on déchiffre, c'est le bloc de 64 bits de texte clair.

Chiffrement par blocs

Comme nous avons vu, le DES chiffre par blocs de 64 bits. Mais dans la plupart des cas l'information à chiffrer n'est pas égale à 64 bits. Si elle est inférieure on complète de façon à aboutir à une donnée de 64 bits. Si elle est supérieure a 64 bits comme dans la plupart des cas, on découpe la donnée en bloc de 64 bits. On invoque alors le DES plusieurs fois sur chacun de ces blocs, on parle alors de mode de chiffrement par blocs.

La façon la plus simple de traiter plusieurs blocs de données consiste à ajouter chaque bloc de texte chiffré généré à ceux qui ont été générés avant lui. Cette approche primitive s'appelle ECB, ou " Electronic Code Book ". Sa simplicité la rend très populaire, mais elle est relativement peu sûre : son problème principal est que, pour une clé donnée, un bloc de texte clair sera toujours chiffré par le même bloc de texte chiffré, où qu'il apparaisse dans les données. Cela signifie que si un quelqu'un arrive à briser ne serait-ce qu'une partie des données, il peut commencer à mettre en place un décodeur pour également briser les autres parties. CBC, ou " Cipher Block Chaining " constitue une meilleure approche. C'est donc cette méthode que nous avons décidé d'utiliser.

CBC évite les problèmes de ECB en augmentant un bloc chiffré à l'aide d'opérations simples et d'une rétroaction. La rétroaction fait que chaque bloc chiffré dépend, d'une certaine façon, d'actions réalisées auparavant. Dans le mode CBC, les blocs chiffrés précédents servent à alimenter la suite, afin q'un bloc de texte clair identique ait toutes les chances d'être chiffré différemment à chaque apparition.

Pour que les blocs chiffrés précédemment puissent servir à la rétroaction, avant de chiffrer un bloc de texte clair , on fait un OU exclusif de celui-ci avec le bloc chiffré généré avant lui. Lorsque l'on déchiffre le texte, on fait un OU exclusif de chaque bloc déchiffré avec le bloc chiffré suivant. Exprimé simplement on a :

\begin{displaymath}C_i = E_K(P_i \oplus C_{i-1}\end{displaymath}


\begin{displaymath}P_i = C_{i-1} \oplus D_K(C_i)\end{displaymath}

où $C_i$ et $P_i$ et $E_K$ et $D_K$ sont, respectivement, les $i^e$ blocs de texte chiffré et clair des tampons $C$ et $P$, et $E_K$ et $D_K$ sont les opérations de chiffrement et de déchiffrement utilisant la clé $K$.

Le RSA

Principe

Comme le DES, le RSA est un chiffrement par bloc, mais la taille du bloc varie selon celle des clés. Dans YooGoo nous utilisons des clés de 256 bits, ce qui nous permet dans le cas d'un triple-DES d'envoyer 3 clés DES ($3*64 < 256$).

RSA est considéré très sûr, mais il est considérablement plus lent que DES. Comme pour ce dernier, la sécurité du RSA n'a jamais été prouvée, mais elle est liée au problème difficile de factoriser des grands nombres (des nombres contenant au moins 200 chiffres). Comme on ne connaît aucune solution efficace à ce problème, on suppose qu'il n'existe pas de moyen efficace de briser RSA.

RSA est fondé sur des principes moins obscurs que les permutations numériques et les substitutions utilisées par le DES. Le chiffrement et le déchiffrement des données dépendent d'une exponentiation modulaire, une opération de l'arithmétique des modulos.

Calcul des clés publiques et privées

Avec RSA, la clé publique et la clé privée fonctionnent ensemble comme une paire. La première sert à chiffrer un bloc de données, après quoi seule la clé privée correspondante peut permettre de le déchiffrer. Lorsque l'on génère les clés, on suit plusieurs étapes afin d'assurer que ce mariage fonctionne. Ces étapes vérifient également qu'il n'y a pas moyen de déterminer une des clés à partir de l'autre.

Pour commencer, on choisit deux grands nombres premiers, appelés $p$ et $q$. Etant donné les techniques de factorisation actuelles, ces nombres doivent posséder au moins 200 chiffres pour être considérés comme sûrs. Puis, on calcule $n$, le produit de ces nombres :

\begin{displaymath}n = pq\end{displaymath}

On choisit alors un petit entier impair, $e$, qui fera partie de la clé publique. Le critère le plus important dans le choix de $e$ est qu'il ne doit pas avoir de facteur commun avec $(p - 1)(q - 1)$ : en d'autres termes, $e$ et $(p - 1)(q - 1)$ sont premiers entre eux. Nous utilisons 17, car c'est un nombre premier, nous sommes alors sûr qu'il n'est pas de facteur commun. L'utilisation d'une valeur précise pour $e$ ne compromet pas la sécurité de RSA car le déchiffrement des données est fonction de la clé privée.

Ensuite, on calcule une valeur correspondante $d$ qui fera partie de la clé privée. Pour cela, on calcule l'inverse de $e$, modulo $(p - 1)(q - 1)$, de la façon suivante :


\begin{displaymath}d = e^{-1} mod(p - 1)(q - 1)\end{displaymath}

Maintenant que nous avons des valeurs pour $e$ et $d$, on publie $(e,n)$ comme étant la clé publique $P$ et on garde $(d,n)$ secret comme clé privée $S$ :


\begin{displaymath}P = (e,n)\end{displaymath}


\begin{displaymath}S = (d,n)\end{displaymath}

Ceux qui chiffrent les données utilisent $P$ et ceux qui déchiffrent, $S$. Pour s'assurer que quelqu'un connaissant $P$ ne puisse calculer $S$, les valeurs utilisées pour $p$ et $q$ ne doivent jamais être révélées.

La sécurité offerte par le couple $P$ et $S$ vient du fait que la multiplication est une fonction à sens unique, ce qui est fondamental en cryptographie. Exprimé simplement, une fonction à sens unique est une fonction relativement simple à calculer dans un sens, mais impossible à trouver dans l'autre. Dans RSA, par exemple, la multiplication de $p$ et $q$ est facile, mais la factorisation de $n$ en $p$ et $q$ est extrêmement lente si les valeurs choisis pour $p$ et $q$ sont suffisamment grandes.

Chiffrement et déchiffrement des blocs de données

Pour chiffrer et déchiffrer des données avec RSA, il faut d'abord choisir une taille de bloc en s'assurant que la plus grande taille que pourra contenir ce bloc sera inférieure à $n$. Si, par exemple, $p$ et $q$ sont des nombres premiers de 200 chiffres, n fera à peine moins de 400 chiffres. On doit donc choisir une taille de bloc suffisamment petite pour ne stocker que les nombres ayant moins de chiffres que cela. En pratique, on prend souvent une taille de bloc d'un nombre de bits égal à la plus grande puissance de 2 inférieure à $n$. Si $n = 209$, par exemple, on choisirait une taille de bloc de 7 bits car $2^7 = 128$ est inférieur à 209 et $2^8 = 256$ est supérieur.

Pour chiffrer un bloc de texte clair $M_i$, le ième bloc de données d'un tampon $M$, on utilise la clé publique $(e,n)$ pour prendre la valeur numérique de $M_i$, l'élever à la puissance $e$, et prendre le résultat modulo $n$. Cela donne un bloc de texte chiffré $C_i$. Le modulo $n$ garantit que $C_i$ tiendra dans la même taille de bloc que celle du texte clair. Ainsi, pour chiffrer un bloc de texte clair, on a :


\begin{displaymath}C_i = M_i^e mod n \end{displaymath}

Pour obtenir de nouveau le texte clair $M_i$ à partir de $C_i$, ième bloc de texte chiffré d'un tampon $C$, on utilise la clé privée $(d,n)$ pour prendre la valeur numérique de $C_i$, l'élever à la puissance $d$ et prendre le résultat modulo $n$. Ainsi pour déchiffrer un bloc de texte chiffré, on a :


\begin{displaymath}M_i = C_i^e mod n\end{displaymath}

Nombres infinis

Comme nous l'avons vu, RSA est sûr que si l'on travaille sur des nombres très grands (200 chiffres au moins). Il faut alors créer une classe de nombres infinis qui permet de réaliser toutes les opérations classiques (addition, soustraction, division, multiplication, modulo, exponentielle).

La première méthode qui a été réalisée est d'utilisé des chaînes de caractères pour stocker les nombres. Cette méthode permet d'afficher et de saisir des nombres très facilement. Mais que très peu de caractères sont utilisés ('0'-'9') et on gâche alors beaucoup d'espace. Les opérations sont effectuées comme si on les faisaient à la main, c'est à dire que pour chaque chiffre on effectue l'opération et on garde une éventuelle retenue pour l'inclure dans le calcul du chiffre suivant. La classe ainsi réalisée marche très bien mais est malheureusement très lente.

Nous avons alors décidé de reprendre une classe déjà réalisée, qui reprend un peu la même méthode mais au lieu d'utiliser les caractères '0'-'9', utilise des unsigned long int. On met alors côte à côte tous ces nombres et on obtient alors un nombre de la taille que l'on veut (dans notre cas 7). Le calcul des opérations est plus rapide car on calcul alors par paquet de 32 bits. Il suffit alors comme précédemment de garder la retenue à chaque fois.

Génération de nombres infinis

Les nombres $p$ et $q$ doivent être premiers. Pour pouvoir générer une clé aléatoirement il faut donc pouvoir générer un nombre premier aléatoirement. La méthode la plus évidente serait de générer un nombre quelconque et puis de tester s'il n'est pas multiple d'un nombre premier inférieur ou égal à sa racine carré. Cette méthode est très lente surtout lorsqu'on travaille sur des grands nombres, de plus il faut avoir précédemment calculé tous les nombres premiers plus petits que le nombre aléatoire. C'est quand même la seule méthode sûr à 100%.

Mais pour accélérer le test, on à mis au point des méthodes probabilistes qui sont fiables. La méthode de Rabin-Miller est considérée actuellement comme la plus efficace. Il faut l'effectuer 4 fois si on veut avoir une réponse quasiment exacte.

Le test de Miller-Rabin prend en entrée un entier impair $n > 1$ à tester. Il renvoie en sortie FAUX ou VRAI.

  1. Calculer $b$ où $b$ est le nombre de fois que 2 divise $n - 1$
  2. Poser $2^b * r = n - 1$ où $r$ est un entier impair.
  3. (A répéter 4 fois) 
                A = rand(n-1)       // 1 < a < n-1
            y = a^r mod n
            Si ( (y != 1) et (y != n - 1) ) alors
                j := 1
                Tant que ( (j < b) et (y != n - 1) ) faire
                    y := y^2 mod n
                    Si (y = 1) alors retourne (FAUX)
                    j := j + 1
                    Si (y != n - 1) alors retourne (FAUX)
                Fin fant que
            Sinon retourne  (VRAI)
 
 

 
 
Documentation

FAQ
Conception du Protocole
SDK en Ligne
Télécharger SDK
Cahiers des Charges
Soutenance 1
Soutenance 2
Soutenance 3
Soutenance Finale

Comment marche...
Les Canaux
Le Profile
L'administration
La Base de Données
La Cryptographie
Winsock
Le Multithreading
 
 

 
 
Liens

Epita
EpiTarget
Hallucinetik - Zone 42
poupouill.fr.st Minosis (Spé C2)
La Spé C1
La Sup C1 		 
 


 
 
made in Epita Powered by ApachePHP Scripting Language

All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2000 by YooGoo Team
Des remarques, des question, des choses pas claires? Hargos@ifrance.com