RC5 - RC5

RC5
RC5 InfoBox Diagram.svg
Uma rodada (duas meias rodadas) da cifra de bloco RC5
Em geral
Designers Ron Rivest
Publicado pela primeira vez 1994
Sucessores RC6 , Akelarre
Detalhe de cifra
Tamanhos de chave 0 a 2040 bits (128 sugeridos)
Tamanhos de bloco 32, 64 ou 128 bits (64 sugeridos)
Estrutura Rede Feistel
Rodadas 1-255 (12 sugeridos originalmente)
Melhor criptoanálise pública
12-round RC5 (com blocos de 64 bits) é suscetível a um ataque diferencial usando 2 44 textos simples escolhidos.

Em criptografia , RC5 é uma cifra de bloco de chave simétrica notável por sua simplicidade. Desenhado por Ronald Rivest em 1994, RC significa "Rivest Cipher" ou, alternativamente, "Ron's Code" (compare RC2 e RC4 ). O candidato RC6 do Advanced Encryption Standard (AES) foi baseado no RC5.

Descrição

Ao contrário de muitos esquemas, RC5 tem um tamanho de bloco variável (32, 64 ou 128 bits ), tamanho de chave (0 a 2040 bits) e número de rodadas (0 a 255). A escolha original de parâmetros sugerida era um tamanho de bloco de 64 bits, uma chave de 128 bits e 12 rodadas.

Uma característica chave do RC5 é o uso de rotações dependentes de dados; um dos objetivos do RC5 era estimular o estudo e a avaliação de tais operações como uma primitiva criptográfica . RC5 também consiste em uma série de adições modulares e eXclusive OR (XOR) s . A estrutura geral do algoritmo é uma rede do tipo Feistel . As rotinas de criptografia e descriptografia podem ser especificadas em algumas linhas de código. A programação da chave, no entanto, é mais complexa, expandindo a chave usando uma função essencialmente unilateral com as expansões binárias de e e a proporção áurea como fontes de " nada na manga ". A tentadora simplicidade do algoritmo, juntamente com a novidade das rotações dependentes de dados, tornou o RC5 um atraente objeto de estudo para criptanalistas. O RC5 é basicamente denotado como RC5-w / r / b onde w = tamanho da palavra em bits, r = número de rodadas, b = número de bytes de 8 bits na chave.

Algoritmo

A criptografia e a descriptografia RC5 expandem a chave aleatória em 2 (r + 1) palavras que serão usadas sequencialmente (e apenas uma vez cada) durante os processos de criptografia e descriptografia. Todos os itens abaixo vêm do artigo revisado de Rivest sobre RC5.

Expansão de chave

O algoritmo de expansão de chave é ilustrado abaixo, primeiro em pseudocódigo, depois em código C de exemplo copiado diretamente do apêndice do documento de referência.

Seguindo o esquema de nomenclatura do papel, os seguintes nomes de variáveis ​​são usados:

  • w - O comprimento de uma palavra em bits, normalmente 16, 32 ou 64. A criptografia é feita em blocos de 2 palavras.
  • u = w / 8 - O comprimento de uma palavra em bytes.
  • b - O comprimento da chave em bytes.
  • K [] - A chave, considerada como uma matriz de bytes (usando indexação baseada em 0).
  • c - O comprimento da chave em palavras (ou 1, se b = 0).
  • L [] - Uma matriz de trabalho temporária usada durante o agendamento de chave. inicializado com a chave em palavras.
  • r - O número de rodadas a serem usadas ao criptografar dados.
  • t = 2 (r + 1) - o número de subchaves redondas necessárias.
  • S [] - As palavras-chave redondas.
  • P W - A primeira constante mágica, como definido , onde impar é o número inteiro ímpar mais próxima para a entrada de dados, e é a base do logaritmo natural , e W é definido acima. Para valores comuns de w , os valores associados de P w são dados aqui em hexadecimal:
    • Para w = 16: 0xB7E1
    • Para w = 32: 0xB7E15163
    • Para w = 64: 0xB7E151628AED2A6B
  • Q w - A segunda constante mágica, como definido , onde impar é o número inteiro ímpar mais próxima para a entrada de dados, em que é a razão de ouro , e W é definido acima. Para valores comuns de w , os valores associados de Q w são dados aqui em hexadecimal:
    • Para w = 16: 0x9E37
    • Para w = 32: 0x9E3779B9
    • Para w = 64: 0x9E3779B97F4A7C15
# Break K into words
# u = w / 8
c = ceiling(max(b, 1) / u)
# L is initially a c-length list of 0-valued w-length words
for i = b-1 down to 0 do:
    L[i / u] = (L[i / u] <<< 8) + K[i]
     
# Initialize key-independent pseudorandom S array
# S is initially a t=2(r+1) length list of undefined w-length words
S[0] = P_w
for i = 1 to t-1 do:
    S[i] = S[i - 1] + Q_w
    
# The main key scheduling loop
i = j = 0
A = B = 0
do 3 * max(t, c) times:
    A = S[i] = (S[i] + A + B) <<< 3
    B = L[j] = (L[j] + A + B) <<< (A + B)
    i = (i + 1) % t
    j = (j + 1) % c

# return S

O código-fonte de exemplo é fornecido no apêndice do artigo de Rivest sobre RC5. A implementação foi projetada para funcionar com w = 32, r = 12 e b = 16.

void RC5_SETUP(unsigned char *K)
{
   // w = 32, r = 12, b = 16
   // c = max(1, ceil(8 * b/w))
   // t = 2 * (r+1)
   WORD i, j, k, u = w/8, A, B, L[c];
   
   for (i = b-1, L[c-1] = 0; i != -1; i--)
      L[i/u] = (L[i/u] << 8) + K[i];
   
   for (S[0] = P, i = 1; i < t; i++)
      S[i] = S[i-1] + Q;
   
   for (A = B = i = j = k = 0; k < 3 * t; k++, i = (i+1) % t, j = (j+1) % c)
   {
      A = S[i] = ROTL(S[i] + (A + B), 3);
      B = L[j] = ROTL(L[j] + (A + B), (A + B));
   }
}

Encriptação

A criptografia envolveu várias rodadas de uma função simples. 12 ou 20 rodadas parecem ser recomendadas, dependendo das necessidades de segurança e das considerações de tempo. Além das variáveis ​​usadas acima, as seguintes variáveis ​​são usadas neste algoritmo:

  • A, B - As duas palavras que compõem o bloco de texto simples a ser criptografado.
A = A + S[0]
B = B + S[1]
for i = 1 to r do:
    A = ((A ^ B) <<< B) + S[2 * i]
    B = ((B ^ A) <<< A) + S[2 * i + 1]

# The ciphertext block consists of the two-word wide block composed of A and B, in that order.
return A, B

O exemplo de código C fornecido por Rivest é este.

void RC5_ENCRYPT(WORD *pt, WORD *ct)
{
   WORD i, A = pt[0] + S[0], B = pt[1] + S[1];
   
   for (i = 1; i <= r; i++)
   {
      A = ROTL(A ^ B, B) + S[2*i];
      B = ROTL(B ^ A, A) + S[2*i + 1];
   }
   ct[0] = A; ct[1] = B;
}

Decifrar

A descriptografia é uma reversão bastante direta do processo de criptografia. O pseudocódigo abaixo mostra o processo.

for i = r down to 1 do:
    B = ((B - S[2 * i + 1]) >>> A) ^ A
    A = ((A - S[2 * i]) >>> B) ^ B
B = B - S[1]
A = A - S[0]

return A, B

O exemplo de código C fornecido por Rivest é este.

void RC5_DECRYPT(WORD *ct, WORD *pt)
{
   WORD i, B=ct[1], A=ct[0];
   
   for (i = r; i > 0; i--)
   {
      B = ROTR(B - S[2*i + 1], A) ^ A;
      A = ROTR(A - S[2*i], B) ^ B;
   }
   
   pt[1] = B - S[1]; pt[0] = A - S[0];
}

Criptanálise

12-round RC5 (com blocos de 64 bits) é suscetível a um ataque diferencial usando 2 44 textos simples escolhidos. 18–20 rodadas são sugeridas como proteção suficiente.

Vários desses problemas de desafio foram enfrentados usando computação distribuída , organizada por Distributed.net . Distributed.net tem mensagens RC5 de força bruta criptografadas com chaves de 56 e 64 bits e tem trabalhado na quebra de uma chave de 72 bits desde 3 de novembro de 2002. Desde 6 de agosto de 2021, 7,900% do keyspace foi pesquisado e com base na taxa registrada naquele dia, levaria 127 anos para completar 100% do keyspace. A tarefa inspirou muitos desenvolvimentos novos e inovadores no campo da computação em cluster.

A RSA Security , que tinha uma patente sobre o algoritmo, ofereceu uma série de prêmios de US $ 10.000 para quebrar textos criptografados com RC5, mas esses concursos foram descontinuados em maio de 2007. Como resultado, o Distribution.net decidiu financiar o prêmio em dinheiro. O indivíduo que descobrir a chave vencedora receberá US $ 1.000, sua equipe (se aplicável) receberá US $ 1.000 e a Free Software Foundation receberá US $ 2.000.

Veja também

Referências

links externos