rfc2040.txt

来自「RFC 的详细文档！」· 文本 代码 · 共 1,628 行 · 第 1/4 页

Network Working Group                                         R. Baldwin
Request for Comments: 2040                       RSA Data Security, Inc.
Category: Informational                                        R. Rivest
                                     MIT Laboratory for Computer Science
                                             and RSA Data Security, Inc.
                                                            October 1996


         The RC5, RC5-CBC, RC5-CBC-Pad, and RC5-CTS Algorithms

Status of this Memo

   This memo provides information for the Internet community.  This memo
   does not specify an Internet standard of any kind.  Distribution of
   this memo is unlimited.

Acknowledgments

   We would like to thank Steve Dusse, Victor Chang, Tim Mathews, Brett
   Howard, and Burt Kaliski for helpful suggestions.

Table of Contents

     1.        Executive Summary .......................  1
     2.        Overview ................................  2
     3.        Terminology and Notation ................  3
     4.        Description of RC5 Keys .................  4
     5.        Description of RC5 Key Expansion ........  6
     6.        Description of RC5 Block Cipher ......... 10
     7.        Description of RC5-CBC and RC5-CBC-Pad .. 12
     8.        Description of RC5-CTS .................. 18
     9.        Test Program and Vectors ................ 19
     10.       Security Considerations ................. 26
     11.       ASN.1 Identifiers ....................... 28
     References ........................................ 28
     Authors' Addresses ................................ 29

1.  Executive Summary

   This document defines four ciphers with enough detail to ensure
   interoperability between different implementations.  The first cipher
   is the raw RC5 block cipher.  The RC5 cipher takes a fixed size input
   block and produces a fixed sized output block using a transformation
   that depends on a key.  The second cipher, RC5-CBC, is the Cipher
   Block Chaining (CBC) mode for RC5.  It can process messages whose
   length is a multiple of the RC5 block size.  The third cipher, RC5-
   CBC-Pad, handles plaintext of any length, though the ciphertext will
   be longer than the plaintext by at most the size of a single RC5



Baldwin & Rivest             Informational                      [Page 1]

RFC 2040         RC5, RC5-CBC, RC5-CBC-Pad, and RC5-CTS     October 1996


   block.  The RC5-CTS cipher is the Cipher Text Stealing mode of RC5,
   which handles plaintext of any length and the ciphertext length
   matches the plaintext length.

   The RC5 cipher was invented by Professor Ronald L. Rivest of the
   Massachusetts Institute of Technology in 1994.  It is a very fast and
   simple algorithm that is parameterized by the block size, the number
   of rounds, and key length.  These parameters can be adjusted to meet
   different goals for security, performance, and exportability.

   RSA Data Security Incorporated has filed a patent application on the
   RC5 cipher and for trademark protection for RC5, RC5-CBC, RC5-CBC-
   Pad, RC5-CTS and assorted variations.

2.  Overview

   This memo is a restatement of existing published material.  The
   description of RC5 follows the notation and order of explanation
   found in the original RC5 paper by Professor Rivest [2].  The CBC
   mode appears in reference works such as the one by Bruce Schneier
   [6].  The CBC-Pad mode is the same as in the Public Key Cryptography
   Standard (PKCS) number five [5].  Sample C code [8] is included for
   clarity only and is equivalent to the English language descriptions.

   The ciphers will be explained in a bottom up object-oriented fashion.
   First, RC5 keys will be presented along with the key expansion
   algorithm.  Second, the RC5 block cipher is explained, and finally,
   the RC5-CBC and RC5-CBC-Pad ciphers are specified.  For brevity, only
   the encryption process is described.  Decryption is achieved by
   inverting the steps of encryption.

   The object-oriented description found here should make it easier to
   implement interoperable systems, though it is not as terse as the
   functional descriptions found in the references.  There are two
   classes of objects, keys and cipher algorithms.  Both classes share
   operations that create and destroy these objects in a manner that
   ensures that secret information is not returned to the memory
   manager.

   Keys also have a "set" operation that copies a secret key into the
   object.  The "set" operation for the cipher objects defines the
   number of rounds, and the initialization vector.

   There are four operations for the cipher objects described in this
   memo.  There is binding a key to a cipher object, setting a new
   initialization vector for a cipher object without changing the key,
   encrypting part of a message (this would be performed multiple times
   for long messages), and processing the last part of a message which



Baldwin & Rivest             Informational                      [Page 2]

RFC 2040         RC5, RC5-CBC, RC5-CBC-Pad, and RC5-CTS     October 1996


   may add padding or check the length of the message.

   In summary, the cipher will be explained in terms of these
   operations:

   RC5_Key_Create           - Create a key object.

   RC5_Key_Destroy          - Destroy a key object.

   RC5_Key_Set              - Bind a user key to a key object.

   RC5_CBC_Create           - Create a cipher object.

   RC5_CBC_Destroy          - Destroy a cipher object.

   RC5_CBC_Encrypt_Init     - Bind a key object to a cipher object.

   RC5_CBC_SetIV            - Set a new IV without changing the key.

   RC5_CBC_Encrypt_Update   - Process part of a message.

   RC5_CBC_Encrypt_Final    - Process the end of a message.

3.  Terminology and Notation

   The term "word" refers to a string of bits of a particular length
   that can be operated on as either an unsigned integer or as a bit
   vector.  For example a "word" might be 32 or 64 bits long depending
   on the desired block size for the RC5 cipher.  A 32 bit word will
   produce a 64 bit block size.  For best performance the RC5 word size
   should match the register size of the CPU.  The term "byte" refers to
   eight bits.

   The following variables will be used throughout this memo with these
   meanings:

  W  This is the word size for RC5 measured in bits.  It is half the
      block size.  The word sizes covered by this memo are 32 and 64.

  WW This is the word size for RC5 measured in bytes.

  B  This is the block size for RC5 measured in bits.  It is twice
      the word size.  When RC5 is used as a 64 bit block cipher, B is
      64 and W is 32. 0 < B < 257.  In the sample code, B, is used as
      a variable instead of a cipher system parameter, but this usage
      should be obvious from context.

  BB This is the block size for RC5 measured in bytes.  BB = B / 8.



Baldwin & Rivest             Informational                      [Page 3]

RFC 2040         RC5, RC5-CBC, RC5-CBC-Pad, and RC5-CTS     October 1996


  b  This is the byte length of the secret key.  0 <= b < 256.

  K  This is the secret key which is treated as a sequence of b
      bytes indexed by: K[0], ..., K[b-1].

  R  This is the number of rounds of the inner RC5 transform.
      0 <= R < 256.

  T  This is the number of words in the expanded key table.  It is
      always 2*(R + 1).  1 < T < 513.

  S  This is the expanded key table which is treated as a sequence
      of words indexed by: S[0], ..., S[T-1].

  N  This is the byte length of the plaintext message.

  P  This is the plaintext message which is treated as a sequence of
      N bytes indexed by: P[0], ..., P[N-1].

  C  This is the ciphertext output which is treated as a sequence of
      bytes indexed by: C[0], C[1], ...

  I  This is the initialization vector for the CBC mode which is
      treated as a sequence of bytes indexed by: I[0], ..., I[BB-1].

4.  Description of RC5 Keys

   Like most block ciphers, RC5 expands a small user key into a table of
   internal keys.  The byte length of the user key is one of the
   parameters of the cipher, so the RC5 user key object must be able to
   hold variable length keys.  A possible structure for this in C is:

  /* Definition of RC5 user key object. */
  typedef struct rc5UserKey
  {
    int          keyLength; /* In Bytes. */
    unsigned char   *keyBytes;
  } rc5UserKey;

   The basic operations on a key are to create, destroy and set.  To
   avoid exposing key material to other parts of an application, the
   destroy operation zeros the memory allocated for the key before
   releasing it to the memory manager.  A general key object may support
   other operations such as generating a new random key and deriving a
   key from key-agreement information.






Baldwin & Rivest             Informational                      [Page 4]

RFC 2040         RC5, RC5-CBC, RC5-CBC-Pad, and RC5-CTS     October 1996


4.1 Creating an RC5 Key

   To create a key, the memory for the key object must be allocated and
   initialized.  The C code below assumes that a function called
   "malloc" will return a block of uninitialized memory from the heap,
   or zero indicating an error.

  /* Allocate and initialize an RC5 user key.
   * Return 0 if problems.
   */
  rc5UserKey *RC5_Key_Create ()
  {
    rc5UserKey *pKey;

    pKey = (rc5UserKey *) malloc (sizeof(*pKey));
    if (pKey != ((rc5UserKey *) 0))
    {
        pKey->keyLength = 0;
        pKey->keyBytes = (unsigned char *) 0;
    }
    return (pKey);
  }

4.2 Destroying an RC5 Key

   To destroy a key, the memory must be zeroed and released to the
   memory manager.  The C code below assumes that a function called
   "free" will return a block of memory to the heap.

  /* Zero and free an RC5 user key.
   */
  void RC5_Key_Destroy (pKey)
    rc5UserKey      *pKey;
  {
    unsigned char   *to;
    int          count;

    if (pKey == ((rc5UserKey *) 0))
        return;
    if (pKey->keyBytes == ((unsigned char *) 0))
        return;
    to = pKey->keyBytes;
    for (count = 0 ; count < pKey->keyLength ; count++)
        *to++ = (unsigned char) 0;
    free (pKey->keyBytes);
    pKey->keyBytes = (unsigned char *) 0;
    pKey->keyLength = 0;
    free (pKey);



Baldwin & Rivest             Informational                      [Page 5]

RFC 2040         RC5, RC5-CBC, RC5-CBC-Pad, and RC5-CTS     October 1996


  }

4.3 Setting an RC5 Key

   Setting the key object makes a copy of the secret key into a block of
   memory allocated from the heap.

  /* Set the value of an RC5 user key.
   * Copy the key bytes so the caller can zero and
   * free the original.
   * Return zero if problems
   */
  int RC5_Key_Set (pKey, keyLength, keyBytes)
    rc5UserKey  *pKey;
    int          keyLength;
    unsigned char   *keyBytes;
  {
    unsigned char   *keyBytesCopy;
    unsigned char   *from, *to;
    int          count;

    keyBytesCopy = (unsigned char *) malloc (keyLength);
    if (keyBytesCopy == ((unsigned char *) 0))
        return (0);
    from = keyBytes;
    to = keyBytesCopy;
    for (count = 0 ; count < keyLength ; count++)
        *to++ = *from++;
    pKey->keyLength = count;
    pKey->keyBytes = keyBytesCopy;
    return (1);
  }

5.  Description of RC5 Key Expansion

   This section describes the key expansion algorithm.  To be specific,
   the sample code assumes that the block size is 64 bits.  Several
   programming parameters depend on the block size.

  /* Definitions for RC5 as a 64 bit block cipher. */
  /* The "unsigned int" will be 32 bits on all but */
  /* the oldest compilers, which will make it 16 bits. */
  /* On a DEC Alpha "unsigned long" is 64 bits, not 32. */
  #define RC5_WORD     unsigned int
  #define W            (32)
  #define WW           (W / 8)
  #define ROT_MASK     (W - 1)
  #define BB           ((2 * W) / 8) /* Bytes per block */



Baldwin & Rivest             Informational                      [Page 6]

RFC 2040         RC5, RC5-CBC, RC5-CBC-Pad, and RC5-CTS     October 1996


  /* Define macros used in multiple procedures. */
  /* These macros assumes ">>" is an unsigned operation, */
  /* and that x and s are of type RC5_WORD. */
  #define SHL(x,s)    ((RC5_WORD)((x)<<((s)&ROT_MASK)))
  #define SHR(x,s,w)  ((RC5_WORD)((x)>>((w)-((s)&ROT_MASK))))
  #define ROTL(x,s,w) ((RC5_WORD)(SHL((x),(s))|SHR((x),(s),(w))))

5.1 Definition of initialization constants

   Two constants, Pw and Qw, are defined for any word size W by the
   expressions:

        Pw = Odd((e-2)*2**W)

        Qw = Odd((phi-1)*2**W)

   where e is the base of the natural logarithm (2.71828 ...), and phi
   is the golden ratio (1.61803 ...), and 2**W is 2 raised to the power
   of W, and Odd(x) is equal to x if x is odd, or equal to x plus one if
   x is even.  For W equal to 16, 32, and 64, the Pw and Qw constants
   are the following hexadecimal values:

  #define P16  0xb7e1
  #define Q16  0x9e37
  #define P32  0xb7e15163
  #define Q32  0x9e3779b9
  #define P64  0xb7e151628aed2a6b
  #define Q64  0x9e3779b97f4a7c15
  #if W == 16
  #define Pw   P16 /* Select 16 bit word size */
  #define Qw   Q16
  #endif
  #if W == 32
  #define Pw   P32 /* Select 32 bit word size */
  #define Qw   Q32
  #endif
  #if W == 64
  #define Pw   P64 /* Select 64 bit word size */
  #define Qw   Q64
  #endif











Baldwin & Rivest             Informational                      [Page 7]

RFC 2040         RC5, RC5-CBC, RC5-CBC-Pad, and RC5-CTS     October 1996


5.2 Interface definition

   The key expansion routine converts the b-byte secret key, K, into an
   expanded key, S, which is a sequence of T = 2*(R+1) words.  The
   expansion algorithm uses two constants that are derived from the
   constants, e, and phi.  These are used to initialize S, which is then
   modified using K.  A C code procedure header for this routine could
   be: