Cryptographie RSA

Chiffrement RSA

Principe :

Si Bob désire que l’on puisse communiquer avec lui de façon secrète, il procède de la manière suivante :

  1. Bob engendre deux grands nombres premiers p et q (test de primalité).
  2. Bob calcule n = p q donc ɸ(n) = (p-1)(q-1), ɸ indicateur d’Euler.
  3. Bob choisit un nombre aléatoire b avec 1 b ɸ(n) tel que pgcd(b, ɸ(n) ) = 1.
  4. Bob calcule l’inverse de p modulo ɸ(n), noté e, c’est-à-dire : b*e ≡ 1 mod ɸ(n) (Algorithme d’Euclide généralisé).
  5. Bob publie (n, b) (clef public) et garde e qui forme la clef secrète.

Fantasio veut envoyer un message M (M < n) à Bob, il calcule :

C = M^b mod n et envoi C à Bob.

Bob reçoit C et calcule : C^e mod n =M

 

Notions mathématiques :

Considérons l’ensemble suivant : En = {0, 1, 2, …, n-1}.

Théorème :

Soit a appartient à En, alors a est inversible ssi pgcd(a,n) = 1, c’est-à-dire, a et n sont premiers entre eux. Ainsi, si n est premier, alors chaque élément de En est inversible, sauf 0 .

Définition : Indicateur d’Euler noté ɸ.

Il indique le nombre d’élément inversible de En.

Propriétés de ɸ(n) :

  1.  Si n est premier, alors ɸ(n) = n-1.
  2. Si m et n sont premiers entre eux, ɸ(m*n) = ɸ(m)* ɸ(n).
  3. Si m et n sont premiers, alors ɸ(m*n) = (m-1)*(n-1).
  4. Si a est inversible de En, alors a^ ɸ(n) 1 mod n.

Nombre premier: test de primalité

Comme annoncé dans mon dernier article, concernant l’algorithme de recherche des nombres premiers, nous allons nous pencher sur différents tests de primalité d’un point de vue plus mathématique. Néanmoins, cela devrait rester abordable, nul besoin de la connaissance des espaces vectoriels pour comprendre :D.

 

Méthode naïve:

Il suffit de diviser le nombre n dont on veut tester la primalité par tous les nombres de 2 à √n, car si n = p * q et dans ce cas, on a: p <= √n et q<= √n. En effet, supposons que        p >= q > √n; p > √n, q > √n; p*q > √n   -> absurde car n = p*q. On peut encore améliorer le test et ne tester que les nombres impairs une fois que la division par 2 a échoué. La complexité de ce test est exp( 1/2 * log n ).

 

Test de Fermat:

Rappel: Si n est premier et si a < n, alors a^(n-1) ≡ 1 mod n.                                 Conséquences:                                                                                                                       Soit a < n,  Si a ^(n-1) ≠ 1 mod n alors n n’est pas premier.                                                 Ce test élimine mais ne confirme pas. Il est possible de déterminer si le nombre n’est pas premier. La réciproque est fausse.

 

Test de Lucas-Lehmer:

Si p est premier, le nombre de Mersenne Mp d’indice p est défini par: Mp = 2^p  –  1  .       On définit une suite Sn par S2 = 4 et Sn = (S(n-1))² – 2.                                                        Alors, Mp est premier ssi Mp divise Sp, c’est-à-dire: Sp ≡ 0 mod p.

Algorithme de recherche des nombres premiers

Aujourd’hui, nous nous intéressons aux nombres premiers et à la façon de les trouver. Pour cela, voilà un algorithme assez simple qui permet de trouver un nombre n de nombre premier. Dans sa première version, l’algorithme recommençait à calculer à partir de 5 (si ma mémoire est bonne ;) ) à chaque exécution. Dans sa version actuelle, nous pouvons maintenant reprendre les calculs à partir du dernier nombre premier trouvé. Quelques améliorations pourront néanmoins être apporter comme la possibilité d’interrompre le programme alors qu’il teste des nombres et de le relancer sans avoir à repartir du dernier nombre premier, la gestion des grands nombres pourrait être à revoir. Nous pouvons également envisager la division du fichier contenant les nombres premiers en plusieurs autres fichiers tous les x nombres.

L’algorithme est présenté en code C et repose sur ce que mon professeur de sécurité désignait il y a quelques jours comme la « méthode naïve »; puisqu’il existe d’autres méthodes, permettant de s’assurer qu’un nombre n’est pas premier entre autres (mais pas d’équivalence ici, si le nombre n’est pas premier, le théorème ne permet pas de monter qu’il l’est) et dont je parlerais certainement dans un autre article.

Au jour d’aujourd’hui, notre fichier fait 969 376 620 octets et est trop grand pour être ouvert par certains éditeur de texte :D.  Pour déterminer si un nombre est premier, l’algorithme va regarder le résultat de la division du nombre testé par les nombres premiers déjà présent dans le fichier. Si le reste vaut 0, le nombre testé est divisible par un autre nombre que 1 ou lui-même, il n’est donc pas premier. On peut arrêter ce test, lorsque le nombre premier utilisé dans la division euclidienne est supérieur à la racine carré du nombre testé et ainsi gagner du temps. De même, l’incrémentation des nombres testés de 2 en 2 à partir d’un entier impair permet de ne jamais tester les nombres pairs puisque nous les savons tous divisibles par 2. Le lien vers un dossier contenant le code et les fichiers qu’il utilise: Algorithme Nombres Premiers. Place maintenant au programme:

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int premier(int test);

int main(void)
{
    /*VARIABLE:
      recherche: le nombre de nombre premier à rechercher
      dernier: le dernier nombre testé
        lors de l'appel précédent au programme,
        contenu dans dernier.txt*/

    int recherche, dernier;
    FILE *fichier_dernier_nbr;
    FILE  *fichier;
    recherche=100;
    dernier=0;

    /*Initialisation du dernier nombre testé
      dernier est obligatoirement impair*/
    fichier=NULL;
    fichier_dernier_nbr = NULL;
    fichier_dernier_nbr = fopen("dernier.txt", "r+");

    if (fichier_dernier_nbr != NULL)
    {
        fscanf(fichier_dernier_nbr, "%d", &dernier);
        fclose(fichier_dernier_nbr);
    }

    /*On recherche autant de nombre premier
       que le contenu de recherche*/
    while(recherche>0)
    {
        if(premier(dernier))
        {
            /*Le nombre testé est premier*/
            /*printf("%d:Premier\n", dernier);*/
            /*On enregistre le nombre à la fin du fichier*/
            fichier = fopen("test.txt", "r+");
            fseek(fichier, 0, SEEK_END);
            fprintf(fichier, "%d\n", dernier);
            fclose(fichier);
            /*On décrémente le nombre de nombre premier
              encore à trouver*/
            recherche--;
        }
        dernier=dernier+2;
    }
    /*On enregistre le dernier à la fin du fichier*/
    fichier = fopen("dernier.txt", "w+");
    fseek(fichier, 0, SEEK_SET);
    fprintf(fichier, "%d", dernier);
    fclose(fichier);

    printf("Operation effectuee avec succes.\n");

    return EXIT_SUCCESS;
}

/*Renvoi 1 si le nombre est un nombre premier*/
int premier(int test)
{
    int nb_premier;
    int borne=0;

    FILE* fichier = NULL;
    fichier = fopen("test.txt", "r+");

    if (fichier != NULL)
    {

        while(feof(fichier)==0 && borne==0)
        {    
            fscanf(fichier, "%d", &nb_premier);
            /*printf("%d\n", nb_premier);*/
            /*Nombre divisible par un nombre premier,
              premier(test)=0*/
            if(test%nb_premier==0)
            {
                fclose(fichier);
                return 0;
                }
            /*Si la racine carré du nombre testé est inférieure au
              nombre premier actuel,inutile de continuer le test*/
            if(nb_premier>sqrt(test))
            {borne=1;}
        }

        fclose(fichier);
        if(borne==1)
        {return 1;}
    }
    return 0;
}

Illustration: illustrer.fr

11 Mars 2011, une année après le drame !

Séisme Japonais

Source visuelle: « Kanpai.fr »

Il y a un an jour pour jour, au Japon. Une petite pensée pour tout ceux qui l’ont vécu ! Le tremblement de terre qui nous fait tous trembler !

Mais que pouvons-nous faire contre la nature..

Cette catastrophe tant naturelle qu’humaine (nucléaire) pousse nos gouvernements à penser à d’autres solutions viables de production d’énergie, même s’ils ne semblent pas pressés d’en trouver !

Dans un monde où l’or noir est devenu indispensable, que pouvons nous dire de l’électricité, pouvons nous nous en passer ? Sûrement pas ! Alors quelle sera l’évolution qui permettra d’en produire sans risquer la vie de milliers de personnes et de milliers de kilomètres carrés de terrains fertiles et habitables ?

Sécurité Informatique: Intro et Théorie

Principes fondamentaux

La sécurité informatique est un ensemble de moyens techniques, juridiques, organisationnels et humains pour garantir la sécurité des systèmes d’information (SI). Les critères de la sécurité des SI sont :

  • La disponibilité : Consiste à assurer l’accessibilité de la ressource informatique (utilisable en un temps de réponse acceptable) et la possibilité de mener à terme une session de travail.
  • L’intégrité : Consiste à pouvoir confirmer que les données, les traitements et les serveurs n’ont pas été altérés, modifiés ou détruits de façon intentionnelle ou accidentelle.
  • La confidentialité : Consiste en le maintien du secret des informations, à savoir que l’information est seulement accessible à ceux qui ont droits.

Remarque :

Bien que la sécurité des SI repose sur ces trois critères, le poids donné à chaque critère dépend de l’institution.

Exemple :

Banque → Intégrité

Militaire → Confidentialité

Fournisseur d’accès internet → Disponibilité

 

Deux critères s’ajoutent aux trois premiers :

  • Traçabilité : Consiste à s’assurer qu’un événement a eu lieu et que seuls les entités identifiées sont à l’origine de l’événement. On parle alors de : authentification, non-reproduction, compatibilité, journalisation.
  • Auditabilité : Consiste en la capacité du système à garantir la présence des informations nécessaires à une analyse ultérieure.

 

Périmètre de sécurité 

La sécurité des SI se décline en plusieurs périmètres de sécurité. Nous parlerons donc de :

  • Sécurité physique : Elle concerne l’environnement dans lequel se situent les systèmes et leurs moyens de maîtrise.
  • Sécurité de l’exploitation : Concerne la grande partie des aspects organisationnels, de gestion et de surveillance, qui touchent au bon fonctionnement des SI.
  • Sécurité logique : Elle concerne l’ensemble des mécanismes de sécurité par logiciel.
  • Sécurité applicative : Elle concerne la sécurité des applications installées ou en phase de réalisation.

On peut ajouter la sécurité des télécommunications et la sécurité juridique.

Exemple :

Programmer proprement ->Sécurité applicative

Configuration d’un pare-feu ->Sécurité des télécommunications

Création de configuration et des mises à jour ->Sécurité de l’exploitation

Installation d’antivirus ->Sécurité logique

Protection d’accès ( porte à code) ->Sécurité physique

Analyse des logs ->Sécurité de l’exploitation

Redondance du matériel ->Sécurité physique

 

Les 7 principes de base de sécurité

  1. Moindre privilège : Ce principe stipule que chaque utilisateur et chaque module d’un système ne doit posséder que les droits minimaux pour effectuer ses tâches.
  2. Goulet d’étranglement : Ce principe consiste à éviter tout moyen possible de contourner les points d’accessibilité.
  3. Défense en profondeur : Elle est réalisée en utilisant plusieurs mécanismes de protection redondants.
  4. Maillon le plus faible : Un système de protection n’est jamais plus efficace que son élément le plus faible.
  5. Déni par défaut : Consiste de partir du principe qui consiste à tout interdire sauf ce qui est explicitement permis.
  6. Simplicité : Plus le système de protection est simple, plus il a de chances d’être configuré et maintenu. Il est ainsi capable de fournir une sécurité presque sans faille car il est plus facile à documenter et à valider.
  7. Participation des utilisateurs : Un système de sécurité n’est efficace que si tous les utilisateurs adhèrent à ses principes.