Diffie-Hellman, RSA, ElGranal, signature, RC4

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");
}