A Description of the RC2(r) Encryption Algorithm
RFC 2268

Document Type RFC - Informational (March 1998; Errata)
Was draft-rivest-rc2desc (individual)
Last updated 2013-03-02
Stream Legacy
Formats plain text pdf html
Stream Legacy state (None)
Document shepherd No shepherd assigned
IESG IESG state RFC 2268 (Informational)
Telechat date
Responsible AD (None)
Send notices to (None)
Network Working Group                                          R. Rivest
Request for Comments: 2268           MIT Laboratory for Computer Science
Category: Informational                      and RSA Data Security, Inc.
                                                              March 1998

            A Description of the RC2(r) Encryption Algorithm

Status of this Memo

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

Copyright Notice

   Copyright (C) The Internet Society (1998).  All Rights Reserved.

1. Introduction

   This memo is an RSA Laboratories Technical Note.  It is meant for
   informational use by the Internet community.

   This memo describes a conventional (secret-key) block encryption
   algorithm, called RC2, which may be considered as a proposal for a
   DES replacement. The input and output block sizes are 64 bits each.
   The key size is variable, from one byte up to 128 bytes, although the
   current implementation uses eight bytes.

   The algorithm is designed to be easy to implement on 16-bit
   microprocessors. On an IBM AT, the encryption runs about twice as
   fast as DES (assuming that key expansion has been done).

1.1 Algorithm description

   We use the term "word" to denote a 16-bit quantity. The symbol + will
   denote twos-complement addition. The symbol & will denote the bitwise
   "and" operation. The term XOR will denote the bitwise "exclusive-or"
   operation. The symbol ~ will denote bitwise complement.  The symbol ^
   will denote the exponentiation operation.  The term MOD will denote
   the modulo operation.

   There are three separate algorithms involved:

     Key expansion. This takes a (variable-length) input key and
     produces an expanded key consisting of 64 words K[0],...,K[63].

Rivest                       Informational                      [Page 1]
RFC 2268              RC2(r) Encryption Algorithm             March 1998

     Encryption. This takes a 64-bit input quantity stored in words
     R[0], ..., R[3] and encrypts it "in place" (the result is left in
     R[0], ..., R[3]).

     Decryption. The inverse operation to encryption.

2. Key expansion

   Since we will be dealing with eight-bit byte operations as well as
   16-bit word operations, we will use two alternative notations

   for referring to the key buffer:

        For word operations, we will refer to the positions of the
             buffer as K[0], ..., K[63]; each K[i] is a 16-bit word.

        For byte operations,  we will refer to the key buffer as
             L[0], ..., L[127]; each L[i] is an eight-bit byte.

   These are alternative views of the same data buffer. At all times it
   will be true that

                       K[i] = L[2*i] + 256*L[2*i+1].

   (Note that the low-order byte of each K word is given before the
   high-order byte.)

   We will assume that exactly T bytes of key are supplied, for some T
   in the range 1 <= T <= 128. (Our current implementation uses T = 8.)
   However, regardless of T, the algorithm has a maximum effective key
   length in bits, denoted T1. That is, the search space is 2^(8*T), or
   2^T1, whichever is smaller.

   The purpose of the key-expansion algorithm is to modify the key
   buffer so that each bit of the expanded key depends in a complicated
   way on every bit of the supplied input key.

   The key expansion algorithm begins by placing the supplied T-byte key
   into bytes L[0], ..., L[T-1] of the key buffer.

   The key expansion algorithm then computes the effective key length in
   bytes T8 and a mask TM based on the effective key length in bits T1.
   It uses the following operations:

   T8 = (T1+7)/8;
   TM = 255 MOD 2^(8 + T1 - 8*T8);

   Thus TM has its 8 - (8*T8 - T1) least significant bits set.

Rivest                       Informational                      [Page 2]
RFC 2268              RC2(r) Encryption Algorithm             March 1998

   For example, with an effective key length of 64 bits, T1 = 64, T8 = 8
   and TM = 0xff.  With an effective key length of 63 bits, T1 = 63, T8
   = 8 and TM = 0x7f.

   Here PITABLE[0], ..., PITABLE[255] is an array of "random" bytes
   based on the digits of PI = 3.14159... . More precisely, the array
   PITABLE is a random permutation of the values 0, ..., 255. Here is
   the PITABLE in hexadecimal notation:

        0  1  2  3  4  5  6  7  8  9  a  b  c  d  e  f
   00: d9 78 f9 c4 19 dd b5 ed 28 e9 fd 79 4a a0 d8 9d
   10: c6 7e 37 83 2b 76 53 8e 62 4c 64 88 44 8b fb a2
   20: 17 9a 59 f5 87 b3 4f 13 61 45 6d 8d 09 81 7d 32
   30: bd 8f 40 eb 86 b7 7b 0b f0 95 21 22 5c 6b 4e 82
Show full document text