Saltar para o conteúdo

RC4: diferenças entre revisões

Origem: Wikipédia, a enciclopédia livre.
Conteúdo apagado Conteúdo adicionado
Linha 156: Linha 156:


==== Implementação em C ====
==== Implementação em C ====
<syntaxhighlight lang="C">
<pre>
#include <stdio.h>
#include <stdio.h>
#include <stdlib.h>
#include <stdlib.h>
Linha 251: Linha 251:
return 0;
return 0;
}
}
</syntaxhighlight>
</pre>


{{Wikisource|RC4 Algorithm}}
{{Wikisource|RC4 Algorithm}}

Revisão das 16h25min de 7 de junho de 2013

Esquema de um ciclo do algoritmo RC4.

Em criptografia, RC4 (ou ARC4) é o algoritmo simétrico de criptografia de fluxo mais usado no software e utilizado nos protocolos mais conhecidos, como Secure Socket Layers (SSL) (para proteger o tráfego Internet) e WEP (para a segurança de redes sem fios). RC4 não é considerado um dos melhores sistemas criptográficos pelos adeptos da criptografia, e em algumas aplicações podem converter-se em sistemas muito inseguros. No entanto, alguns sistemas baseados em RC4 são seguros o bastante num contexto prático.

História

Em 1987 Ronald Rivest desenvolveu o algoritmo RC4 para a empresa RSA Data Security, Inc., líder mundial em algoritmos de criptografia. Foi, durante tempos, um segredo comercial muito bem guardado, muito popular, e utilizado largamente em software, como Lotus Notes, Apple Computer’s AOCE, Oracle Secure SQL, Internet Explorer, Netscape e Adobe Acrobat.

Sete anos depois, surge numa mailing list dedicada à criptografia (Cypherpunks) código alegadamente equivalente ao RC4. Utilizadores com cópias legais puderam confirmar a compatibilidade. É de realçar, no entanto, que esta não é a implementação comercial, e, como tal, é habitualmente referida como ARC4 (Alleged RC4).

As transformações neste algoritmo são lineares, não são necessários cálculos complexos, já que o sistema funciona basicamente por permutações e somas de valores inteiros, o que torna este algoritmo muito simples e rápido.

De uma forma geral, o algoritmo consiste em utilizar um array que a cada utilização tem os seus valores permutados, e misturados com a chave, o que provoca que seja muito dependente desta. Esta chave, utilizada na inicialização do array, pode ter até 256 bytes (2048 bits), embora o algoritmo seja mais eficiente quando é menor, pois a perturbação aleatória induzida no array é superior.

Algoritmo

KSA

O algoritmo key-scheduling é usado para inicializar a permutação no array S. K.Length é definido como o número de bytes na chave e pode variar entre 1 e 256, tipicamente entre 5 e 16 correspondendo ao tamanho de chave de 40-128 bits.
Primeiro, o array S é inicializado de tamanho 256.
Na primeira repetição:

  1. O array S é preenchido com os valores de 0 à 255.

Na segunda repetição:

  1. É somado o valor de j, o valor de S apontado por i e o valor de K (chave) apontado por i e armazenado na variável j.
  2. Troca os valores entre S[i] e S[j].

C#

byte[] S = new byte[256];

for (int i = 0; i < 256; i++)
{
 S[i] = (byte)i;
}

int j = 0;

for (int i = 0; i < 256; i++)
{
 j = (j + S[i] + K[i % K.Length]) % 256;
 Troca(ref S[i], ref S[j]);
}

PRGA

Para todas repetições necessárias, o PRGA modifica o estado e a saída do byte resultante. Em cada repetição:

  1. O PRGA incrementa em 1 a variável i.
  2. Adiciona o valor de S apontado por i com j e armazena o resultado em j.
  3. Troca os valores entre S[i] e S[j].
  4. A saída é então calculada fazendo-se a operação XOR (ver em Lógica binária) entre o valor de S apontado por S[i] + S[j] e a mensagem original apontado por k.

C#

int i = 0, j = 0;
// a mensagem original está armazenada na variável "input".
byte[] result = new byte[input.Length];

for (int k = 0; k < input.Length; k++)
{
 i = (i + 1) % 256;
 j = (j + S[i]) % 256;
 Swap(ref S[i], ref S[j]);
 result[k] = (byte)(S[(S[i] + S[j]) % 256] ^ input[k]);
}
return result;

//O algoritmo usado para trocar os valores das variáveis (ver [[Algoritmo Xor Swap]]).

static void Swap(ref byte val1, ref byte val2)
{
 val1 = (byte)(val1 ^ val2); // val1 XOR val2
 val2 = (byte)(val1 ^ val2);
 val1 = (byte)(val1 ^ val2);
}

Exemplo

Considere a mensagem input = "Texto", convertido em bytes (ver Ascii), input = { 84, 101, 120, 116, 111 }.

Adoptemos a chave K = "chave", que convertido em bytes, K = { 99, 104, 97, 118, 101 }.

Em cada repetição:

k = 0

i = (i + 1) % 256;
i = 1
j = (j + S[i]) % 256;
j = (0 + S[1]) % 256
j = 229
Swap(ref S[i], ref S[j]);
S[229] = 204
S[1] = 229
result[k] = (byte)(S[(S[i] + S[j]) % 256] ^ input[k]);
result[0] = S[(229 + 204) % 256] ^ 84
result[0] = S[177] ^ 84
result[0] = 104 ^ 84
result[0] = 60

k = 1

i = (i + 1) % 256;
i = 2
j = (j + S[i]) % 256;
j = (229 + S[2]) % 256
j = 20
Swap(ref S[i], ref S[j]);
S[20] = 68
S[2] = 47
result[k] = (byte)(S[(S[i] + S[j]) % 256] ^ input[k]);
result[1] = S[(47 + 68) % 256] ^ 101
result[1] = S[115] ^ 101
result[1] = 125 ^ 101
result[1] = 24

k = 2

i = (i + 1) % 256;
i = 3
j = (j + S[i]) % 256;
j = (20 + S[3]) % 256
j = 188
Swap(ref S[i], ref S[j]);
S[188] = 92
S[3] = 168
result[k] = (byte)(S[(S[i] + S[j]) % 256] ^ input[k]);
result[2] = S[(168 + 92) % 256] ^ 120
result[2] = S[4] ^ 120
result[2] = 17 ^ 120
result[2] = 105

k = 3

i = (i + 1) % 256;
i = 4
j = (j + S[i]) % 256;
j = (188 + S[4]) % 256
j = 205
Swap(ref S[i], ref S[j]);
S[205] = 42
S[4] = 17
result[k] = (byte)(S[(S[i] + S[j]) % 256] ^ input[k]);
result[3] = S[(17 + 42) % 256] ^ 116
result[3] = S[59] ^ 116
result[3] = 160 ^ 116
result[3] = 212

k = 4

i = (i + 1) % 256;
i = 5
j = (j + S[i]) % 256;
j = (205 + S[5]) % 256
j = 70
Swap(ref S[i], ref S[j]);
S[70] = 153
S[5] = 121
result[k] = (byte)(S[(S[i] + S[j]) % 256] ^ input[k]);
result[4] = S[(121 + 153) % 256] ^ 111
result[4] = S[18] ^ 111
result[4] = 85 ^ 111
result[4] = 58

Ou seja, o texto cifrado result = { 60, 24, 105, 212, 58 }. Aplicando o mesmo algoritmo em result, com a mesma chave consegue-se recuperar a mensagem original input.

Implementação em C

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

//==================================================
unsigned char chave[256];
unsigned char entrada[256];
unsigned char *resultado;
unsigned char s[256];
unsigned int i, j, tamanho_chave, tamanho_entrada;
//==================================================
void troca()
{
unsigned char aux;
aux=s[i];
s[i]=s[j];
s[j]=aux;
}

//====================================================

void ksa ()
{
 for (i = 0; i < 256; i++)
{
     s[i]=i;
} 
  j=0;
 for (i = 0; i < 256; i++)
   {
   j = (j + s[i] + chave[i % tamanho_chave]) % 256;
   troca(s, i, j);
   }
 i=0;
 j=0;
}

//====================================================

void prga ()
{ 
unsigned int aux;
unsigned char result[tamanho_entrada-1];
for (aux=0; aux < tamanho_entrada; aux++)
  {
   i = (i + 1) % 256;
   j = (j + s[i]) % 256;
   troca(s,i,j);
 result[aux]=(s[(s[i] + s[j]) % 256])^entrada[aux];
  }
resultado=(unsigned char*)malloc((tamanho_entrada-1)*(sizeof(unsigned char)));
strcpy(resultado, result);
}

//====================================================

int main ()
{
unsigned char confirma[256];
int confirm;
printf ("Escreva a Frase a ser Criptografada:");
scanf ("%[^\n]", entrada);
tamanho_entrada=strlen(entrada);
fflush(stdin);
printf ("\nChave:");
scanf ("%[^\n]", chave);
tamanho_chave=strlen(chave);
system("pause");
ksa ();
prga ();
printf ("\nResultado Gerado: %s\n", resultado);
system("pause");
fflush(stdin);
printf ("\n\nPara Desfazer, confirme a chave: ");
TENTA: scanf ("%[^\n]", confirma);
confirm=strcmp(confirma, chave); 
if (confirm==0)
 { 
 printf ("\nDesfazendo....\n");
 strcpy(entrada, resultado);
 ksa();
 prga ();
 printf ("\nFrase Original: %s\n", resultado);
 fflush(stdin);
 system("pause");
 }
else
  {
  fflush(stdin);
  printf ("Chave nao confere, por favor insira a chave correta:\n");
  goto TENTA;
  }
return 0;
}
Wikisource
Wikisource
A Wikisource contém fontes primárias relacionadas com RC4

Ligações externas

RC4

RC4 em WEP

Implementações