Article Index

5°) échange de clé de Diffie-Hellman

Alice et Bob ne ce connaisse pas, il communique sur un canal compromis que Eve écoute, ils veulent partager une clé
Alice prend un nombre p premier et aleatoire qu'elle envoie a Bob
Alice prend un nombre g générateur de ℤ/pℤ qu'elle envoie a Bob
Bob choisit un nombre b aléatoire dans ℤ/pℤ
Bob calcule B = pow(g, b)%p
Alice choisit un nombre a aléatoire dans ℤ/pℤ
Alice calcule A = pow(g, a)%p
A et B sont envoyerrespectivement à Bob et Alice
Alice calcule K = pow(B, a)%p
Bob calcule K' = pow(A, b)%p
theoreme: K = K'
preuve: K = B%p = pow(pow(g, b), a)%p = pow(g, a*b)%p = pow(pow(g, a), b) = pow(A, b)%p = K'
comment Eve peut-elle retrouver K ?
  • elle connait p, g, A, B
  • seul solution connue : logarithme discret
problème: n'y Alice n'y Bob ne choisit la clé

6°) crypto, clé publique (RSA, ElGranal)

idée: une clé secrète pour décrypter, une clé publique pour crypté (asymétrique)
plus besoin d'échange de clés: Alice met à disposition la clé publique à tout le monde
il faut que l'on ne puisse pas retrouver la clé secrète à partir de la clé publique

example du système El Granal

Alice choisit p,g avec g: gnérateur de ℤ/pℤ
  • elle choisit une clé secrete k<p< li="">
  • elle calcule K = pow(g,k)%p
  • la clé publique est p,g,K qui est envoyer à Bob
  • elle reçoit une messages crypter de Bob
  • elle calcule pow(T,k)%p = pow(pow(g,k),b) = pow(K,b)%p
  • elle calcule M/pow(k,b)%p = m, le message
Bob veut envoyer un message qu'il découpe en bloques representer par des entier dans ℤ/pℤ
chaque bloques en crypter et tranmit à Alice
  • choisit une clé temporaire b (différente à chaque bloques)
  • il calcule pow(g,b)%p = T
  • il calcule m*pow(K,b)%p = M
  • il envoie T et M

7°) signature electronique

  • Alice est la seul à pouvoir signer -> clé privée
  • tout le monde peut verifier -> clé publique
  • (clé privée / clé publique sont inversé)
  • Alice crypte M avec ça clé privée : S pour verifier la signature
  • Bob decrypte S avec la clé publique de Alice et compare le resultate avec M

8°) RC4

Générateur pseudo-aléatorie qui produit des nombre entre 0 et 255
Inventer par R.Rivest en 1987
En 1994, le fonctionement est dévoilé sur le groupe usenet 'cyberpunk' (ARC4)
remarque:
  • on ne sait pas craquer RC4 en pratique
  • on sait distinguer RC4 d'une vrai suite aléatoire
fonctionement de RC4: deux étapes (initialisation avec une clé de 256 octets / génération)
l'état interne du générateur est donnée par i, j entier et p[] contenant 256 octets (dans le désordre)
remarque: la taille de l'état est de 258 octets -> pow(256,258) états possibles
la période est borné par pow(256,258) ≃ 1 << 1700

initialisation

K: tableau de taille t<256 (seed)
P = {0, ..., 255}, j = 0
for i in 0..255 loop
j = j + P[i] + K[i%len]
swap(P[i], P[j])
end loop

génération

i = i+1
j = j + P[i]
swap(P[i], P[j])
return P[P[i] + P[j]];
 

9°) implémentation C89

#include <stdio.h>

typedef struct rc4_key
{
    unsigned char state[256];
    unsigned char x, y;
} rc4_key;

static void swap_byte(unsigned char *a, unsigned char *b)
{
    unsigned char swapByte = *a;
    *a = *b;
    *b = swapByte;
}

void prepare_key(unsigned char *key, int size, rc4_key *k)
{
    unsigned char x, y;
    unsigned char *state;
    short i;

    state = &k->state[0];
    k->x = k->y = x = y = 0;

    for(i = 0; i < 256; i++)
        state[i] = i;

    for(i = 0; i < 256; i++)
    {
        y = key[x] + state[i] + y;
        swap_byte(&state[i], &state[y]);
        x = (x + 1) % size;
    }
}

void rc4(unsigned char *data, int count, rc4_key *k, int offset)
{
    unsigned char x, y, idx;
    unsigned char* state;
    short i;

    x = k->x;
    y = k->y;

    state = &k->state[0];

    for(i = 0; i < offset; ++i)
    {
        x++;
        y = state[x] + y;
        swap_byte(&state[x], &state[y]);
    }

    for(i = 0; i<count; ++i)
    {
        x++;
        y = state[x] + y;
        swap_byte(&state[x], &state[y]);
        idx = state[x] + state[y];
        data[i] ^= state[idx];
    }

    k->x = x;
    k->y = y;
}

int main(int argc, const char **argv)
{
    short i;
    rc4_key info;

    unsigned char key[] = "WEP";
    unsigned char message[] = "info528";

    prepare_key(key, 3, &info);
    rc4(message, 7, &info, 1234);

    for(i = 0; i<7; ++i)
        printf("%02X", message[i]);
    printf("\n");
}