idnits 2.17.1 draft-rivest-rc2desc-00.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** Cannot find the required boilerplate sections (Copyright, IPR, etc.) in this document. Expected boilerplate is as follows today (2024-04-19) according to https://trustee.ietf.org/license-info : IETF Trust Legal Provisions of 28-dec-2009, Section 6.a: This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79. IETF Trust Legal Provisions of 28-dec-2009, Section 6.b(i), paragraph 2: Copyright (c) 2024 IETF Trust and the persons identified as the document authors. All rights reserved. IETF Trust Legal Provisions of 28-dec-2009, Section 6.b(i), paragraph 3: This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (https://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Code Components extracted from this document must include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Simplified BSD License. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- ** Missing expiration date. The document expiration date should appear on the first and last page. ** The document seems to lack a 1id_guidelines paragraph about Internet-Drafts being working documents. ** The document seems to lack a 1id_guidelines paragraph about the list of current Internet-Drafts. ** The document seems to lack a 1id_guidelines paragraph about the list of Shadow Directories. == No 'Intended status' indicated for this document; assuming Proposed Standard == The page length should not exceed 58 lines per page, but there was 1 longer page, the longest (page 1) being 268 lines Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack an Abstract section. ** The document seems to lack a Security Considerations section. ** The document seems to lack an IANA Considerations section. (See Section 2.2 of https://www.ietf.org/id-info/checklist for how to handle the case when there are no actions for IANA.) Miscellaneous warnings: ---------------------------------------------------------------------------- -- The document seems to lack a disclaimer for pre-RFC5378 work, but may have content which was first submitted before 10 November 2008. If you have contacted all the original authors and they are all willing to grant the BCP78 rights to the IETF Trust, then this is fine, and you can ignore this comment. If not, you may need to add the pre-RFC5378 disclaimer. (See the Legal Provisions document at https://trustee.ietf.org/license-info for more information.) -- The document date (December 22, 1997) is 9615 days in the past. Is this intentional? Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) -- Missing reference section? '0' on line 226 looks like a reference -- Missing reference section? '63' on line 226 looks like a reference -- Missing reference section? '3' on line 223 looks like a reference -- Missing reference section? '127' on line 146 looks like a reference -- Missing reference section? 'T-1' on line 94 looks like a reference -- Missing reference section? '255' on line 109 looks like a reference -- Missing reference section? '128-T8' on line 148 looks like a reference -- Missing reference section? '1' on line 213 looks like a reference -- Missing reference section? '2' on line 214 looks like a reference Summary: 8 errors (**), 0 flaws (~~), 2 warnings (==), 11 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 1 Internet Draft Ron Rivest 2 draft-rivest-rc2desc-00.txt RSA Data Security, Inc. 3 Created 1987 4 Revised March 12, 1992 5 Revised June 23, 1997 Expires December 22, 1997 7 A Description of the RC2(r) Encryption Algorithm 9 Status of this memo 11 This document is an Internet-Draft. Internet-Drafts are working 12 documents of the Internet Engineering Task Force (IETF), its areas, 13 and its working groups. Note that other groups may also distribute 14 working documents as Internet-Drafts. 16 Internet-Drafts are draft documents valid for a maximum of six months 17 and may be updated, replaced, or obsoleted by other documents at any 18 time. It is inappropriate to use Internet-Drafts as reference material 19 or to cite them other than as "work in progress." 21 To learn the current status of any Internet-Draft, please check the 22 "1id-abstracts.txt" listing contained in the Internet-Drafts Shadow 23 Directories on ftp.is.co.za (Africa), nic.nordu.net (Europe), 24 munnari.oz.au (Pacific Rim), ds.internic.net (US East Coast), or 25 ftp.isi.edu (US West Coast). 27 1. Introduction 29 This draft is an RSA Laboratories Technical Note. It is meant for 30 informational use by the Internet community. 32 This memo describes a conventional (secret-key) block encryption 33 algorithm, called RC2, which may be considered as a proposal for a DES 34 replacement. The input and output block sizes are 64 bits each. The 35 key size is variable, from one byte up to 128 bytes, although the 36 current implementation uses eight bytes. 38 The algorithm is designed to be easy to implement on 16-bit 39 microprocessors. On an IBM AT, the encryption runs about twice as fast 40 as DES (assuming that key expansion has been done). 42 1.1 Algorithm description 44 We use the term "word" to denote a 16-bit quantity. The symbol + will 45 denote twos-complement addition. The symbol & will denote the bitwise 46 "and" operation. The term XOR will denote the bitwise "exclusive-or" 47 operation. The symbol ~ will denote bitwise complement. The symbol ^ 48 will denote the exponentiation operation. The term MOD will denote 49 the modulo operation. 51 There are three separate algorithms involved: 53 Key expansion. This takes a (variable-length) input key and 54 produces an expanded key consisting of 64 words K[0], ..., K[63]. 56 Encryption. This takes a 64-bit input quantity stored in words 57 R[0], ..., R[3] and encrypts it "in place" (the result is left in 58 R[0], ..., R[3]). 60 Decryption. The inverse operation to encryption. (This will not be 61 described, since it is merely the inverse operation.) 63 2. Key expansion 65 Since we will be dealing with eight-bit byte operations as well 66 as 16-bit word operations, we will use two alternative notations 67 for referring to the key buffer: 69 For word operations, we will refer to the positions of the 70 buffer as K[0], ..., K[63]; each K[i] is a 16-bit word. 72 For byte operations, we will refer to the key buffer as 73 L[0], ..., L[127]; each L[i] is an eight-bit byte. 75 These are alternative views of the same data buffer. At all times 76 it will be true that 78 K[i] = L[2*i] + 256*L[2*i+1]. 80 (Note that the low-order byte of each K word is given before the 81 high-order byte.) 83 We will assume that exactly T bytes of key are supplied, for some 84 T in the range 1 <= T <= 128. (Our current implementation uses T 85 = 8.) However, regardless of T, the algorithm has a maximum 86 effective key length in bits, denoted T1. That is, the search 87 space is 2^(8*T), or 2^T1, whichever is smaller. 89 The purpose of the key-expansion algorithm is to modify the key 90 buffer so that each bit of the expanded key depends in a 91 complicated way on every bit of the supplied input key. 93 The key expansion algorithm begins by placing the supplied T-byte 94 key into bytes L[0], ..., L[T-1] of the key buffer. 96 The key expansion algorithm then computes the effective key 97 length in bytes T8 and a mask TM based on the effective key 98 length in bits T1. It uses the following operations: 100 T8 = (T1+7)/8; 101 TM = 255 MOD 2^(8 + T1 - 8*T8); 103 Thus TM has its 8 - (8*T8 - T1) least significant bits set. 105 For example, with an effective key length of 64 bits, T1 = 64, 106 T8 = 8 and TM = 0xff. With an effective key length of 63 bits, 107 T1 = 63, T8 = 8 and TM = 0x7f. 109 Here PITABLE[0], ..., PITABLE[255] is an array of "random" bytes 110 based on the digits of PI = 3.14159... . More precisely, the array 111 PITABLE is a random permutation of the values 0, ..., 255. Here is 112 the PITABLE in hexadecimal notation: 114 0 1 2 3 4 5 6 7 8 9 a b c d e f 115 00: d9 78 f9 c4 19 dd b5 ed 28 e9 fd 79 4a a0 d8 9d 116 10: c6 7e 37 83 2b 76 53 8e 62 4c 64 88 44 8b fb a2 117 20: 17 9a 59 f5 87 b3 4f 13 61 45 6d 8d 09 81 7d 32 118 30: bd 8f 40 eb 86 b7 7b 0b f0 95 21 22 5c 6b 4e 82 119 40: 54 d6 65 93 ce 60 b2 1c 73 56 c0 14 a7 8c f1 dc 120 50: 12 75 ca 1f 3b be e4 d1 42 3d d4 30 a3 3c b6 26 121 60: 6f bf 0e da 46 69 07 57 27 f2 1d 9b bc 94 43 03 122 70: f8 11 c7 f6 90 ef 3e e7 06 c3 d5 2f c8 66 1e d7 123 80: 08 e8 ea de 80 52 ee f7 84 aa 72 ac 35 4d 6a 2a 124 90: 96 1a d2 71 5a 15 49 74 4b 9f d0 5e 04 18 a4 ec 125 a0: c2 e0 41 6e 0f 51 cb cc 24 91 af 50 a1 f4 70 39 126 b0: 99 7c 3a 85 23 b8 b4 7a fc 02 36 5b 25 55 97 31 127 c0: 2d 5d fa 98 e3 8a 92 ae 05 df 29 10 67 6c ba c9 128 d0: d3 00 e6 cf e1 9e a8 2c 63 16 01 3f 58 e2 89 a9 129 e0: 0d 38 34 1b ab 33 ff b0 bb 48 0c 5f b9 b1 cd 2e 130 f0: c5 f3 db 47 e5 a5 9c 77 0a a6 20 68 fe 7f c1 ad 132 The key expansion operation consists of the following two loops 133 and intermediate step: 135 for i = T, T+1, ..., 127 do 136 L[i] = PITABLE[L[i-1] + L[i-T]]; 138 L[128-T8] = PITABLE[L[128-T8] & TM]; 140 for i = 127-T8, ..., 0 do 141 L[i] = PITABLE[L[i+1] XOR L[i+T8]]; 143 (In the first loop, the addition of L[i-1] and L[i-T] is 144 performed modulo 256.) 146 The "effective key" consists of the values L[128-T8], ..., L[127]. 147 The intermediate step's bitwise "and" operation reduces the 148 search space for L[128-T8] so that the effective number of key 149 bits is T1. The expanded key depends only on the effective key 150 bits, regardless of the supplied key K. Since the expanded key is 151 not itself modified during encryption or decryption, as a 152 pragmatic matter one can expand the key just once when encrypting 153 or decrypting a large block of data. 155 3. Encryption algorithm 157 The encryption operation is defined in terms of primitive "mix" 158 and "mash" operations. 160 Here the expression "x rol k" denotes the 16-bit word x rotated 161 left by k bits, with the bits shifted out the top end entering 162 the bottom end. 164 3.1 Mix up R[i] 166 The primitive "Mix up R[i]" operation is defined as follows, 167 where s[0] is 1, s[1] is 2, s[2] is 3, and s[3] is 5, and where 168 the indices of the array R are always to be considered "modulo 169 4," so that R[i-1] refers to R[3] if i is 0 (these values a 170 "wrapped around" so that R always has a subscript in the range 0 171 to 3 inclusive): 173 R[i] = R[i] + K[j] + (R[i-1] & R[i-2]) + ((~R[i-1]) & R[i-3]); 174 j = j + 1; 175 R[i] = R[i] rol s[i]; 177 In words: The next key word K[j] is added to R[i], and j is 178 advanced. Then R[i-1] is used to create a "composite" word which 179 is added to R[i]. The composite word is identical with R[i-2] in 180 those positions where R[i-1] is one, and identical to R[i-3] in 181 those positions where R[i-1] is zero. Then R[i] is rotated left 182 by s[i] bits (bits rotated out the left end of R[i] are brought 183 back in at the right). Here j is a "global" variable so that K[j] 184 is always the first key word in the expanded key which has not 185 yet been used in a "mix" operation. 187 3.2 Mixing round 189 A "mixing round" consists of the following operations: 191 Mix up R[0] 192 Mix up R[1] 193 Mix up R[2] 194 Mix up R[3] 196 3.3 Mash R[i] 198 The primitive "Mash R[i]" operation is defined as follows (using 199 the previous conventions regarding subscripts for R): 201 R[i] = R[i] + K[R[i-1] & 63]; 203 In words: R[i] is "mashed" by adding to it one of the words of 204 the expanded key. The key word to be used is determined by 205 looking at the low-order six bits of R[i-1], and using that as an 206 index into the key array K. 208 3.4 Mashing round 210 A "mashing round" consists of: 212 Mash R[0] 213 Mash R[1] 214 Mash R[2] 215 Mash R[3] 217 3.5 Encryption operation 219 The entire encryption operation can now be described as follows. 220 Here j is a global integer variable which is affected by the 221 mixing operations. 223 1. Initialize words R[0], ..., R[3] to contain the 64-bit input 224 value. 226 2. Expand the key, so that words K[0], ..., K[63] become 227 defined. 229 3. Initialize j to zero. 231 4. Perform five mixing rounds. 233 5. Perform one mashing round. 235 6. Perform six mixing rounds. 237 7. Perform one mashing round. 239 8. Perform five mixing rounds. 241 Note that each mixing round uses four key words, and that there 242 are 16 mixing rounds altogether, so that each key word is used 243 exactly once in a mixing round. The mashing rounds will refer to 244 up to eight of the key words in a data-dependent manner. (There 245 may be repetitions, and the actual set of words referred to will 246 vary from encryption to encryption.) 248 A. Intellectual Property Notice 250 RC2 is a registered trademark of RSA Data Security, Inc. RSA's 251 copyrighted RC2 software is available under license from RSA 252 Data Security, Inc. 254 B. Author's Address 256 Ron Rivest 257 RSA Laboratories 258 100 Marine Parkway, #500 259 Redwood City, CA 94065 USA 260 (415) 595-8782 261 rsa-labs@rsa.com