Incubator escapee wiki

RC5

Article Discussion

Template:Short description Template:About Template:Infobox block cipher In cryptography, RC5 is a symmetric-key block cipher notable for its simplicity. Designed by Ronald Rivest in 1994,<ref name="fse1994">Template:Cite conference</ref> RC stands for "Rivest Cipher", or alternatively, "Ron's Code" (compare RC2 and RC4). The Advanced Encryption Standard (AES) candidate RC6 was based on RC5.

DescriptionEdit

Unlike many schemes, RC5 has a variable block size (32, 64 or 128 bits), key size (0 to 2040 bits), and number of rounds (0 to 255). The original suggested choice of parameters were a block size of 64 bits, a 128-bit key, and 12 rounds.

A key feature of RC5 is the use of data-dependent rotations; one of the goals of RC5 was to prompt the study and evaluation of such operations as a cryptographic primitive.Template:Citation needed RC5 also consists of a number of modular additions and eXclusive OR (XOR)s. The general structure of the algorithm is a Feistel-like network, similar to RC2. The encryption and decryption routines can be specified in a few lines of code. The key schedule, however, is more complex, expanding the key using an essentially one-way function with the binary expansions of both e and the golden ratio as sources of "nothing up my sleeve numbers". The tantalising simplicity of the algorithm together with the novelty of the data-dependent rotations has made RC5 an attractive object of study for cryptanalysts.Template:According to whom RC5 is basically denoted as RC5-w/r/b where w=word size in bits, r=number of rounds, b=number of bytes in the key.

AlgorithmEdit

RC5 encryption and decryption both expand the random key into 2(r+1) words that will be used sequentially (and only once each) during the encryption and decryption processes. All of the below comes from Rivest's revised paper on RC5.<ref>{{#invoke:citation/CS1|citation |CitationClass=web }}</ref>

Key expansionEdit

The key expansion algorithm is illustrated below, first in pseudocode, then example C code copied directly from the reference paper's appendix.

Following the naming scheme of the paper, the following variable names are used:

<syntaxhighlight lang="python">

  1. Break K into words
  2. u = w / 8

c = ceiling(max(b, 1) / u)

  1. 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]
  1. Initialize key-independent pseudorandom S array
  2. 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
  1. 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
  1. return S

</syntaxhighlight>

The example source code is provided from the appendix of Rivest's paper on RC5. The implementation is designed to work with w = 32, r = 12, and b = 16.

<syntaxhighlight lang="c"> 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));
  }

} </syntaxhighlight>

EncryptionEdit

Encryption involved several rounds of a simple function, with 12 or 20 rounds seemingly recommended, depending on security needs and time considerations. Beyond the variables used above, the following variables are used in this algorithm:

  • A, B - The two words composing the block of plaintext to be encrypted.

<syntaxhighlight lang="python"> 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]
  1. The ciphertext block consists of the two-word wide block composed of A and B, in that order.

return A, B </syntaxhighlight>

The example C code given by Rivest is this.

<syntaxhighlight lang="c"> 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;

} </syntaxhighlight>

DecryptionEdit

Decryption is a fairly straightforward reversal of the encryption process. The below pseudocode shows the process.

<syntaxhighlight lang="python"> 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 </syntaxhighlight>

The example C code given by Rivest is this.

<syntaxhighlight lang="c"> 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];

} </syntaxhighlight>

CryptanalysisEdit

Twelve-round RC5 (with 64-bit blocks) is susceptible to a differential attack using 244 chosen plaintexts.<ref name="Biryukov">Template:Cite conference</ref> 18–20 rounds are suggested as sufficient protection.

A number of these challenge problems have been tackled using distributed computing, organised by Distributed.net. Distributed.net has brute-forced RC5 messages encrypted with 56-bit and 64-bit keys and has been working on cracking a 72-bit key since November 3, 2002.<ref name="distributed.net: Project RC5">{{#invoke:citation/CS1|citation |CitationClass=web }}</ref> As of July 26, 2023, 10.409% of the keyspace has been searched and based on the rate recorded that day, it would take a little more than 59 years to complete 100% of the keyspace.<ref>{{#invoke:citation/CS1|citation |CitationClass=web }}</ref> The task has inspired many new and novel developments in the field of cluster computing.<ref>Template:Cite press release</ref>

RSA Security, which had a (now expired) patent on the algorithm,<ref>Rivest, R. L, "Block Encryption Algorithm With Data Dependent Rotation", {{#if:5724428 |[{{#ifeq:|uspto|http://patft.uspto.gov/netacgi/nph-Parser?patentnumber=%7Chttps://patents.google.com/patent/US}}{{#iferror:{{#expr:5724428 }}|5724428}} U.S. patent {{#ifeq:Template:Replace|Template:Digits|Template:Replace|5724428}}] |{{US patent|123456|link text}}}}, issued on 3 March 1998, expired 1 November 2015.</ref> offered a series of US$10,000 prizes for breaking ciphertexts encrypted with RC5, but these contests were discontinued as of May 2007.<ref name="distributed.net: Project RC5"/> As a result, distributed.net decided to fund the monetary prize. The individual who discovers the winning key will receive US$1,000, their team (if applicable) will receive US$1,000, and the Free Software Foundation will receive US$2,000.<ref>{{#invoke:citation/CS1|citation |CitationClass=web }}</ref>

See alsoEdit

ReferencesEdit

Template:Reflist

External linksEdit

Template:Cryptography navbox

Retrieved from "https://zalansite.site/mediawiki/index.php?title=RC5&oldid=68405"