Article Index

1°) Historique

code de césar
x = (x+3)%26
tableau -> études statistique

La cryptographie est l'art de caché des messages, rendre incompréhenssibles les messages sans connaitre une manière non-ambigue de le déchiffrer. Par exemple on veut :

  • l'impossibilité de décrypté un message crypté
  • l'impossibilité de décrypté même si on dispose de plusieur messages cryptés
  • l'impossibilité de décrypté même si on dispose des messages en claires
  • l'impossibilité de décrypté même si on peut gnéré des messages cryptés

2°) Le bloc note à usage unique

C'est le seul code crypto sûre:
on ne réutilise pas les bits de la clé
clé: suite de bit aléatoires (long)
on xor le message avec la clé pour crypté
problème:
  • il faut transmettre la clée (physiquement au mieux)
  • la clé à la même taille que le message
  • la clé doit être aléatoire (pas de générateur pseudo-aléatoire)
certain générateur peuvent être utilisé et sont en pratique suffisament sûre (RC4)on initialise avec une clé de taille 255 (ou moin)
avantage: taille de la clé <= 255 octéts
c'est ce générateur qui est utilisé dans le codage WEP qui n'est pas sûre

3°) crytpographie symetrique

le seul secret partagé par Alice et Bob est une clé (secète) de petite taille
ex: générateur aléatoire + xor (RC4) = DES / AES (très rapide)
problème de transmission de la clé: échange de clés de Diffie-Hellman 1976
cette méthode permet l'échange de clé même si un attaquent écoute toutes les communications, il ne pourras pas craquer la clée

4°) crypto clé publique/privé, arithmétique

a°) rappels

def: m est multiple de n si n = n*a
on it aussi que n divise m, on note m|n
  • On note pgcd(n,m) pour le plus grand diviseur commun de n et m
  • si n et m sont des nombres entiers alors il existe un unique quotient et
    un unique r apartenant à [0,m] telque n = q*m + r

b°) euclide : pgcd

pgcd(0, n) = n ; pgcd(m, n) = pgcd(n%m, m) si m <= n, pgcd(m, n) = pgcd(m, n) sinon

exemple

pgcd(15, 12) = pgcd(12, 15) =
pgcd(15%12, 12) = pgcd(12%3, 3) =
pgcd(0, 3) = 3

c°) bézout : euclide étendue

theoreme: si a est le pgcd de n et m alors on peut trouver x et y telque m*x + n*y = a (x et y peuvent être négatif)

exemple

pgcd(14, 22)
= pgcd(8, 14) car 22 = 1*14 + 8 | x = -3 et y = 2
= pgcd(6, 08) car 14 = 1*08 + 6 | 2 = 2*(22-14) - 1*14 = -3*14 + 22*2
= pgcd(2, 06) car 08 = 1*06 + 2 | 2 = 8*1 - (14-1*8)*1 = 2*8 - 1*14
= pgcd(0, 02) car 06 = 3*02 + 0 | 2 = 8 - 6*1
= 2, on remonte: -------------------------/

d°) nombre premier

def: un nombre est premier si il a exactement 2 diviseur, 1 et lui même
theoreme: tout entier se décompose de manière unique en produit de nombres premier
theoreme: il y a une infinité de nombre premier pow(2, 43112609) et 43112609 sont premier
constation/conjecture: on ne sait pas trouver les facteurs premiers d'un nombre en temps raisonable
theoreme: la proportion de nombre premier entre 1 et n est environ n/ln(n)

e°) calcule modulo

on note a ≡ d%n quand m | (a-d), ou, a%m = b%m
theoreme: {a≡b%m ; a'≡b'%m} ⇒
a+a' ≡ (b+b')%m
a*a' ≡ (b*b')%m
a-a' ≡ (b-b')%m
pow(a, k) ≡ pow(b, k)%m
⇒ pow(a, a') ≢ pow(b, b')%m (en général)
remarque: division modulo, si a et m sont premier entre eux alors on peut diviser par a%m

methode

on cherche x et y telque ax+my=1
on a ax+bm ≡ 1%m ⇒ ax ≡ 1%m
on dit que x est l'inversse de a%m, la division est donc la multiplication par l'inversse de a : x
si m est un nombre premier, on peut diviser par 1..m-1 ; on dit que {0, ..., n-1} forme on corp, noté ℤ/nℤ
theoreme euleur: si p est premier alors pow(a, p-1) ≡ 1%p
si p et q sont premier alors pow(a, (p-1)*(q-1)) ≡ 1%p

f°) problème du logarithme discret

si p est premier alors un élément générateur est un nombre a telque
{a⁰=1, a¹=a, ..., a^(p-2)} = {1, 2, ..., p-1} c à d les puissances de a engendre tout les nombres %p sauf 0
Si a est générateur, la fonction n➝pow(a,n)%p est facile à calculer, mais on ne sait pas faire l'inversse en temps raisonable
c'est le problème du logarithme discret⎡ X1 = ( aX + c)%m
⎢ X2 = (aX1 + c)%m
⎣ X3 = (aX2 + c)%m
a = (X3-X2) / (X2-X1)
c = X2 - aX1

5°) implémentation

/**********************************************************************
 * teste un vecteur d'initialisation :                                *
 *   - "o_rc4" est le premier octet généré par RC4 avec "IV"          *
 *   - "n" est l'octet de la clé que l'on recherche                   *
 *   - "cle" contient les morceaux de la clé que l'on a déjà calculée *
 *                                                                    *
 * La fonction renvoie 1 si la clé était faible, et dans ce cas,      *
 * la prédiction correspondante se trouve dans le dernier paramètre   *
 * "prediction".                                                      *
 * Si la clé n'était pas faible, cette fonction renvoie 1 et le       *
 * paramètre n'est pas modifié.                                       *
 **********************************************************************/
 
int predit_octet_simple(octet o_rc4, int n, octet *cle, octet *prediction)
{
    unsigned char P[256];
    unsigned char s_1;
    unsigned char tmp_key[8];
    int i, j;
    
    memcpy(tmp_key, cle, 8);
    j = s_1 = 0;
    
    for(i=0; i<256; i++)
        P[i] = i;
      
    for(i=0; i<n+3; i++)
    {
        j = (unsigned char)(j+P[i]+tmp_key[i%8]);
        echange(&P[i], &P[j]);
    }
    
    for (i=0; i<256; i++)
    {
        if(P[i] == *prediction)
            s_1 = i;
    }
    
    if(P[0] != n+3 || P[1] != 0)
        return -1;
      
    *prediction = (s_1-j-P[n+3]);
    
    return 1;
}



/**********************************************************************
 * devine le "n"-ième octet de la clé (en supposant qu'on connaît les *
 * n-1 octets précédents) en essayant tous les vecteurs               *
 * d'initialisations faibles.                                         *
 * L'argument "cle_WEP_partielle" contient le début de la clé (octets *
 * 0 à "n"-1, non compris).                                           *
 * La fonction ne modifie pas les "n"-1 premières valeurs de          *
 * "cle_WEP_partielle".                                               *
 *                                                                    *
 * L'argument "nb_IV_faibles" est le nombre de vecteurs faibles à     *
 * considérer.                                                        *
 * L'argument "nb_IV_total" est le nombre total de vecteurs à tester. *
 *                                                                    *
 * La fonction s'arrête quand l'une des deux bornes est atteinte.     *
 *                                                                    *
 * Si les 2 bornes sont nulles, on utilise alors uniquement la        *
 * famille de vecteurs (n+3, 255, ...). ATTENTION, ça n'est possible  *
 * que si "taille_IV = 3".                                            *
 *                                                                    *
 * La fonction positionne le n-ème octet de "cle_WEP_partielle" en    *
 * utilisant la prédiction faite.                                     *
 **********************************************************************/
void predit_octet_multiple(int n, octet *cle_WEP_partielle, int nb_IV_faibles_total, int nb_IV_total)
{
  int i;
  int faible;

  /* la prédiction finale */
  octet prediction = 0;
  int resultat = -1;

  /* le vecteur d'initialisation courant */
  octet IV[taille_IV];

  /* la clé RC4 que l'on essaie de compléter :
   * les premiers octets sont variables et contiennent le vecteur
   * d'initialisation,
   * les derniers octets contiennent le morceau de la clé WEP que l'on a déjà
   * craquée*/
  octet cle_partielle[taille_cle_RC4];


  for (i = 0; i < taille_cle_RC4 - taille_IV; i++)
    cle_partielle[i + taille_IV] = cle_WEP_partielle[i];  /* cette partie de la clé est constante : c'est le morceau de la clé WEP déjà craqué */

  if (verbose > 2)
    printf("Pour l'octet n=%d :  ", n); fflush(NULL);

  /* nb de vecteurs et de vecteurs faibles rencontrés */
  int nb_IV = 0;
  int nb_IV_faibles = 0;


  while (1) { // on boucle jusqu'à avoir tester suffisamment de vecteurs d'initialisation

    /* si nb_IV_total et nb_IV_faibles_total sont négatifs, on choisit un
     * nouveau vecteur d'initialisation dans la famille (n+3, 255, ...) */
    if (nb_IV_total < 1 && nb_IV_faibles_total < 1) {
      if (nb_IV > 255) break;  //on a testé tous les vecteurs de la forme (n+3, 255, ...)
      IV[0] = n + taille_IV;
      IV[1] = 255;
      IV[2] = nb_IV;
    } else {
    /* sinon, on tire un vecteur d'initialisation aléatoirement */
      if ((nb_IV_total > 0) && (nb_IV > nb_IV_total)) break;  // on a testé suffisamment de vecteurs
      if ((nb_IV_faibles_total > 0) && (nb_IV_faibles > nb_IV_faibles_total)) break; // idem
      for (i=0; i < taille_IV; i++) IV[i] = rand() % 256;
    }

    nb_IV++;

    /* on initialise RC4 avec le vecteur d'initialisation courant,
     * puis on demande le premier octet */
    init_WEP_RC4(IV);
    octet o_rc4 = RC4_PRGA();

    /* On initialize la clé partielle */
    /* on recopie le vecteur d'initialisation dans la clé (le reste de la clé
     * est constant : c'est ce qu'on cherche) */
    for (int k = 0; k < taille_IV; k++)
        cle_partielle[k] = IV[k];

    /***
     * on appelle la fonction "predit_octet_simple" pour vérifier si "IV" est
     * un vecteur d'initialisation faible (et calculer la prédiction)
     ***/
    faible = predit_octet_simple(o_rc4, n, cle_partielle, &prediction);

    /* si le vecteur IV était faible, on prend en compte la prediction */
    if (1 == faible) {
        nb_IV_faibles++;
        resultat = prediction;
    }
  }

  cle_WEP_partielle[n] = resultat;
}