Usuari:Mcapdevila/RC4

Diagrama de l'algorisme RC4.

Entre la criptografia RC4 o ARC4 és el sistema de xifratge de flux Stream cipher més utilitzat i es fa servir en alguns dels protocols més populars com Transport Layer Security (TLS/SSL) (per protegir el tràfic d'Internet) i Wired Equivalent Privacy (WEP) (per afegir seguretat a les xarxes sense fils). RC4 va ser exclòs de seguida dels estàndards d'alta seguretat pels criptògrafs i algunes maneres d'utilitzar l'algorisme de criptografia RC4 l'han portat a ser un sistema de criptografia molt insegur, incloent el seu ús WEP. No està recomanat el seu ús en els nous sistemes, però, alguns sistemes basats en RC4 són prou segurs per a un ús comú.

Història

L'algorisme de criptografia RC4 va ser dissenyat per Ron Rivest de la RSA Security l'any 1987; el seu nom complet és Rivest Cipher 4, tenint l'acrònim RC un significat alternatiu al de Ron s Code utilitzat per als algoritmes de xifrat RC2, RC5 i RC6.

Inicialment l'algorisme era un secret registrat, però al setembre de 1994 una descripció de l'algorisme va ser postejada anònimament en una llista de correu de cypherpunks. De seguida va passar al grup de correu sci.crypt i d'aquí va ser publicat en nombrosos llocs d'Internet. A causa del coneixement de l'algorisme, aquest va deixar de ser un secret registrat. No obstant això RC4 encara és una marca registrada. Actualment la implementació no oficial de RC4 és legal, però no pot ser utilitzada amb el nom de RC4. Per aquest motiu, i a fi d'evitar problemes legals arran de la marca registrada, sovint podem veure-ho nomenat com ARCFOUR, ARC4 o Alleged-RC4. RSA Security mai ha alliberat l'algoritme de la seva RC4.

RC4 és part dels protocols de xifrat més comuns com WEP, WPA per a targetes wireless i TLS. Entre els factors principals que han ajudat que RC4 estigui en un rang tan ampli d'aplicacions són la seva increïble velocitat i simplicitat. La implementació tant en programari com en maquinari és molt senzilla de desenvolupar i són molt pocs els recursos necessaris per obtenir un rendiment eficient d'ARC4.

Descripció

RC4 és un algorisme sorprenentment simple. Aquest consisteix en 2 algorismes: 1-Key Scheduling Algorithm (KSA) i 2 - Pseudo-Random Generation Algorithm (PRGA). Tots dos d'aquests algorismes usen 8-by-8 S-box, el qual és només un array de 256 nombres en el qual ambdós són únics quant a rang i el seu valor va des de 0 fins a 255. Tots els nombres de 0 a 255 existeixen en cas de fallida, però estan només barrejats de diferents maneres, el KSA s'encarrega de realitzar la primera barreja en el S-Box, basat en el valor de la llavor donada dins d'ell, i aquesta "llavor" pot ser de 256 bits de llarg.

Primer, el S-box array és omplert amb valors seqüencials des 0-255. Aquest array serà cridat simplement S. Llavors, l'altre array de 256-bits és omplert amb el valor de la "llavor", repetint com sigui necessari fins que tot l'array és omplert. Aquest array serà cridat K, llavors la matriu S és barrejat usant el següent pseudocodi.

 j = 0;
 for i = 0 to 255
{
    j = (j+S [i]+K [i]) mod 256;
    intercanvia S [i] and S [j];
}

Quan això és fet, la S-box és intercanviada basant-se en el valor de la "llavor". Aquesta és la "Key" programada per a l'algorisme, alguna cosa senzilla.

Ara quan el keystream data és necessitat, el Pseudo-Random Generation Algorithm (PRGA) és usat. Aquest algorisme té 2 comptadors, l'i i la j, en el qual ambdós són inicialitzats a 0 per començar. Després d'això, cada bit de keystream data és usat en el següent Pseudo-Code:

i = (i+1) mod 256;
j = (j+S [i]) mod 256;
intercanvia S [i] and S [j];
t = (S [i]+S [j] mod 256;
Exposar valor de S [t];

El valor exposat del byte de S [t] és el primer byte del keystream. Aquest algorisme és repetit per aconseguir bytes addicionals de keystream. RC4 és simplement suficient, que pot ser fàcilment memoritzat i implementat en l'aire, i pot arribar a ser una mica "més" segur si és usat apropiadament, en fi, hi ha alguns problemes amb la forma que RC4 és usat amb el xifrat WEP en Wi-Fi.

Una possible implementació en C:

unsigned char S [256];
unsigned int i, j;

void swap (unsigned char * s, unsigned int i, unsigned int j){
    unsigned char temp = s [i];
    s [i] = s [j];
    s [j] = temp;
}

/* KSA */
void rc4_init (unsigned char * key, unsigned int key_length){
    for (i = 0; i <256; i++)
        S [i] = i;
 
    for (i = j = 0; i <256; i++){
        j = (j+key [i% key_length]+S [i]) & 255;
        swap (S, i, j);
   }
 
    i = j = 0;
}
 
/* PRGA */
unsigned char rc4_output (){
    i = (i+1) & 255;
    j = (j+S [i]) & 255;

    swap (S, i, j);

    return S [(S [i]+S [j]) & 255];
}
 
#Include <stdio.h>
#Include <string.h>
#Include <stdlib.h>

#Define ARRAY_SIZE (a) (sizeof (a)/sizeof (a [0]))

int main (){
    unsigned char * test_vectors [] [2] =
   {
       {"Key", "Plaintext"},
       {"Wiki", "pedia"},
       {"Secret", "Attack at dawn"}
   };
 
    int x;
    for (x = 0; x <ARRAY_SIZE (test_vectors); x++){
        int i;
        rc4_init (test_vectors [x] [0], strlen ((char *) test_vectors [x] [0]));

        for (i = 0; i <strlen ((char *) test_vectors [x] [1]), i++)
            printf ("% 02X", test_vectors [x] [1] [i]^rc4_output ());
        printf ("\n");
   }
    getch ();
    return 0;
}

Test vectors

Aquesta prova no és oficial, però resulta adequada per a algú provant el seu propi programa RC4. Les claus i el text en clar estan en ASCII, el text xifrat està en hexadecimal

Clau	Keystream	Missatge	Text xifrat
Key	eb9f7781b734ca72a719 ...	Plaintext	BBF316E8D940AF0AD3
Wiki	6044db6d41b7 ...	pedia	1021BF0420
Secret	04d46b053ca87b59 ...	Attack at dawn	45A01F645FC35B383552544B9BF5