summaryrefslogtreecommitdiff
path: root/doc/rfc/rfc2268.txt
diff options
context:
space:
mode:
Diffstat (limited to 'doc/rfc/rfc2268.txt')
-rw-r--r--doc/rfc/rfc2268.txt619
1 files changed, 619 insertions, 0 deletions
diff --git a/doc/rfc/rfc2268.txt b/doc/rfc/rfc2268.txt
new file mode 100644
index 0000000..cbbdf3b
--- /dev/null
+++ b/doc/rfc/rfc2268.txt
@@ -0,0 +1,619 @@
+
+
+
+
+
+
+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
+ 40: 54 d6 65 93 ce 60 b2 1c 73 56 c0 14 a7 8c f1 dc
+ 50: 12 75 ca 1f 3b be e4 d1 42 3d d4 30 a3 3c b6 26
+ 60: 6f bf 0e da 46 69 07 57 27 f2 1d 9b bc 94 43 03
+ 70: f8 11 c7 f6 90 ef 3e e7 06 c3 d5 2f c8 66 1e d7
+ 80: 08 e8 ea de 80 52 ee f7 84 aa 72 ac 35 4d 6a 2a
+ 90: 96 1a d2 71 5a 15 49 74 4b 9f d0 5e 04 18 a4 ec
+ a0: c2 e0 41 6e 0f 51 cb cc 24 91 af 50 a1 f4 70 39
+ b0: 99 7c 3a 85 23 b8 b4 7a fc 02 36 5b 25 55 97 31
+ c0: 2d 5d fa 98 e3 8a 92 ae 05 df 29 10 67 6c ba c9
+ d0: d3 00 e6 cf e1 9e a8 2c 63 16 01 3f 58 e2 89 a9
+ e0: 0d 38 34 1b ab 33 ff b0 bb 48 0c 5f b9 b1 cd 2e
+ f0: c5 f3 db 47 e5 a5 9c 77 0a a6 20 68 fe 7f c1 ad
+
+ The key expansion operation consists of the following two loops and
+ intermediate step:
+
+ for i = T, T+1, ..., 127 do
+ L[i] = PITABLE[L[i-1] + L[i-T]];
+
+ L[128-T8] = PITABLE[L[128-T8] & TM];
+
+ for i = 127-T8, ..., 0 do
+ L[i] = PITABLE[L[i+1] XOR L[i+T8]];
+
+ (In the first loop, the addition of L[i-1] and L[i-T] is performed
+ modulo 256.)
+
+ The "effective key" consists of the values L[128-T8],..., L[127].
+ The intermediate step's bitwise "and" operation reduces the search
+ space for L[128-T8] so that the effective number of key bits is T1.
+ The expanded key depends only on the effective key bits, regardless
+
+
+
+
+
+
+Rivest Informational [Page 3]
+
+RFC 2268 RC2(r) Encryption Algorithm March 1998
+
+
+ of the supplied key K. Since the expanded key is not itself modified
+ during encryption or decryption, as a pragmatic matter one can expand
+ the key just once when encrypting or decrypting a large block of
+ data.
+
+3. Encryption algorithm
+
+ The encryption operation is defined in terms of primitive "mix" and
+ "mash" operations.
+
+ Here the expression "x rol k" denotes the 16-bit word x rotated left
+ by k bits, with the bits shifted out the top end entering the bottom
+ end.
+
+3.1 Mix up R[i]
+
+ The primitive "Mix up R[i]" operation is defined as follows, where
+ s[0] is 1, s[1] is 2, s[2] is 3, and s[3] is 5, and where the indices
+ of the array R are always to be considered "modulo 4," so that R[i-1]
+ refers to R[3] if i is 0 (these values are
+
+ "wrapped around" so that R always has a subscript in the range 0 to 3
+ inclusive):
+
+ R[i] = R[i] + K[j] + (R[i-1] & R[i-2]) + ((~R[i-1]) & R[i-3]);
+ j = j + 1;
+ R[i] = R[i] rol s[i];
+
+ In words: The next key word K[j] is added to R[i], and j is advanced.
+ Then R[i-1] is used to create a "composite" word which is added to
+ R[i]. The composite word is identical with R[i-2] in those positions
+ where R[i-1] is one, and identical to R[i-3] in those positions where
+ R[i-1] is zero. Then R[i] is rotated left by s[i] bits (bits rotated
+ out the left end of R[i] are brought back in at the right). Here j is
+ a "global" variable so that K[j] is always the first key word in the
+ expanded key which has not yet been used in a "mix" operation.
+
+3.2 Mixing round
+
+ A "mixing round" consists of the following operations:
+
+ Mix up R[0]
+ Mix up R[1]
+ Mix up R[2]
+ Mix up R[3]
+
+
+
+
+
+
+Rivest Informational [Page 4]
+
+RFC 2268 RC2(r) Encryption Algorithm March 1998
+
+
+3.3 Mash R[i]
+
+ The primitive "Mash R[i]" operation is defined as follows (using the
+ previous conventions regarding subscripts for R):
+
+ R[i] = R[i] + K[R[i-1] & 63];
+
+ In words: R[i] is "mashed" by adding to it one of the words of the
+ expanded key. The key word to be used is determined by looking at the
+ low-order six bits of R[i-1], and using that as an index into the key
+ array K.
+
+3.4 Mashing round
+
+ A "mashing round" consists of:
+
+ Mash R[0]
+ Mash R[1]
+ Mash R[2]
+ Mash R[3]
+
+3.5 Encryption operation
+
+ The entire encryption operation can now be described as follows. Here
+ j is a global integer variable which is affected by the mixing
+ operations.
+
+ 1. Initialize words R[0], ..., R[3] to contain the
+ 64-bit input value.
+
+ 2. Expand the key, so that words K[0], ..., K[63] become
+ defined.
+
+ 3. Initialize j to zero.
+
+ 4. Perform five mixing rounds.
+
+ 5. Perform one mashing round.
+
+ 6. Perform six mixing rounds.
+
+ 7. Perform one mashing round.
+
+ 8. Perform five mixing rounds.
+
+ Note that each mixing round uses four key words, and that there are
+ 16 mixing rounds altogether, so that each key word is used exactly
+
+
+
+
+Rivest Informational [Page 5]
+
+RFC 2268 RC2(r) Encryption Algorithm March 1998
+
+
+ once in a mixing round. The mashing rounds will refer to up to eight
+ of the key words in a data-dependent manner. (There may be
+ repetitions, and the actual set of words referred to will vary from
+ encryption to encryption.)
+
+4. Decryption algorithm
+
+ The decryption operation is defined in terms of primitive operations
+ that undo the "mix" and "mash" operations of the encryption
+ algorithm. They are named "r-mix" and "r-mash" (r- denotes the
+ reverse operation).
+
+ Here the expression "x ror k" denotes the 16-bit word x rotated right
+ by k bits, with the bits shifted out the bottom end entering the top
+ end.
+
+4.1 R-Mix up R[i]
+
+ The primitive "R-Mix up R[i]" operation is defined as follows, where
+ s[0] is 1, s[1] is 2, s[2] is 3, and s[3] is 5, and where the indices
+ of the array R are always to be considered "modulo 4," so that R[i-1]
+ refers to R[3] if i is 0 (these values are "wrapped around" so that R
+ always has a subscript in the range 0 to 3 inclusive):
+
+ R[i] = R[i] ror s[i];
+ R[i] = R[i] - K[j] - (R[i-1] & R[i-2]) - ((~R[i-1]) & R[i-3]);
+ j = j - 1;
+
+ In words: R[i] is rotated right by s[i] bits (bits rotated out the
+ right end of R[i] are brought back in at the left). Here j is a
+ "global" variable so that K[j] is always the key word with greatest
+ index in the expanded key which has not yet been used in a "r-mix"
+ operation. The key word K[j] is subtracted from R[i], and j is
+ decremented. R[i-1] is used to create a "composite" word which is
+ subtracted from R[i]. The composite word is identical with R[i-2] in
+ those positions where R[i-1] is one, and identical to R[i-3] in those
+ positions where R[i-1] is zero.
+
+4.2 R-Mixing round
+
+ An "r-mixing round" consists of the following operations:
+
+ R-Mix up R[3]
+ R-Mix up R[2]
+ R-Mix up R[1]
+ R-Mix up R[0]
+
+
+
+
+
+Rivest Informational [Page 6]
+
+RFC 2268 RC2(r) Encryption Algorithm March 1998
+
+
+4.3 R-Mash R[i]
+
+ The primitive "R-Mash R[i]" operation is defined as follows (using
+ the previous conventions regarding subscripts for R):
+
+ R[i] = R[i] - K[R[i-1] & 63];
+
+ In words: R[i] is "r-mashed" by subtracting from it one of the words
+ of the expanded key. The key word to be used is determined by looking
+ at the low-order six bits of R[i-1], and using that as an index into
+ the key array K.
+
+4.4 R-Mashing round
+
+ An "r-mashing round" consists of:
+
+ R-Mash R[3]
+ R-Mash R[2]
+ R-Mash R[1]
+ R-Mash R[0]
+
+4.5 Decryption operation
+
+ The entire decryption operation can now be described as follows.
+ Here j is a global integer variable which is affected by the mixing
+ operations.
+
+ 1. Initialize words R[0], ..., R[3] to contain the 64-bit
+ ciphertext value.
+
+ 2. Expand the key, so that words K[0], ..., K[63] become
+ defined.
+
+ 3. Initialize j to 63.
+
+ 4. Perform five r-mixing rounds.
+
+ 5. Perform one r-mashing round.
+
+ 6. Perform six r-mixing rounds.
+
+ 7. Perform one r-mashing round.
+
+ 8. Perform five r-mixing rounds.
+
+5. Test vectors
+
+ Test vectors for encryption with RC2 are provided below.
+
+
+
+Rivest Informational [Page 7]
+
+RFC 2268 RC2(r) Encryption Algorithm March 1998
+
+
+ All quantities are given in hexadecimal notation.
+
+ Key length (bytes) = 8
+ Effective key length (bits) = 63
+ Key = 00000000 00000000
+ Plaintext = 00000000 00000000
+ Ciphertext = ebb773f9 93278eff
+
+ Key length (bytes) = 8
+ Effective key length (bits) = 64
+ Key = ffffffff ffffffff
+ Plaintext = ffffffff ffffffff
+ Ciphertext = 278b27e4 2e2f0d49
+
+ Key length (bytes) = 8
+ Effective key length (bits) = 64
+ Key = 30000000 00000000
+ Plaintext = 10000000 00000001
+ Ciphertext = 30649edf 9be7d2c2
+
+ Key length (bytes) = 1
+ Effective key length (bits) = 64
+ Key = 88
+ Plaintext = 00000000 00000000
+ Ciphertext = 61a8a244 adacccf0
+
+ Key length (bytes) = 7
+ Effective key length (bits) = 64
+ Key = 88bca90e 90875a
+ Plaintext = 00000000 00000000
+ Ciphertext = 6ccf4308 974c267f
+
+ Key length (bytes) = 16
+ Effective key length (bits) = 64
+ Key = 88bca90e 90875a7f 0f79c384 627bafb2
+ Plaintext = 00000000 00000000
+ Ciphertext = 1a807d27 2bbe5db1
+
+ Key length (bytes) = 16
+ Effective key length (bits) = 128
+ Key = 88bca90e 90875a7f 0f79c384 627bafb2
+ Plaintext = 00000000 00000000
+ Ciphertext = 2269552a b0f85ca6
+
+ Key length (bytes) = 33
+ Effective key length (bits) = 129
+ Key = 88bca90e 90875a7f 0f79c384 627bafb2 16f80a6f 85920584
+ c42fceb0 be255daf 1e
+
+
+
+Rivest Informational [Page 8]
+
+RFC 2268 RC2(r) Encryption Algorithm March 1998
+
+
+ Plaintext = 00000000 00000000
+ Ciphertext = 5b78d3a4 3dfff1f1
+
+6. RC2 Algorithm Object Identifier
+
+ The Object Identifier for RC2 in cipher block chaining mode is
+
+ rc2CBC OBJECT IDENTIFIER
+ ::= {iso(1) member-body(2) US(840) rsadsi(113549)
+ encryptionAlgorithm(3) 2}
+
+ RC2-CBC takes parameters
+
+ RC2-CBCParameter ::= CHOICE {
+ iv IV,
+ params SEQUENCE {
+ version RC2Version,
+ iv IV
+ }
+ }
+
+ where
+
+ IV ::= OCTET STRING -- 8 octets
+ RC2Version ::= INTEGER -- 1-1024
+
+ RC2 in CBC mode has two parameters: an 8-byte initialization vector
+ (IV) and a version number in the range 1-1024 which specifies in a
+ roundabout manner the number of effective key bits to be used for the
+ RC2 encryption/decryption.
+
+ The correspondence between effective key bits and version number is
+ as follows:
+
+ 1. If the number EKB of effective key bits is in the range 1-255,
+ then the version number is given by Table[EKB], where the 256-byte
+ translation table Table[] is specified below. Table[] specifies a
+ permutation on the numbers 0-255; note that it is not the same
+ table that appears in the key expansion phase of RC2.
+
+ 2. If the number EKB of effective key bits is in the range
+ 256-1024, then the version number is simply EKB.
+
+ The default number of effective key bits for RC2 is 32. If RC2-CBC
+ is being performed with 32 effective key bits, the parameters
+ should be supplied as a simple IV, rather than as a SEQUENCE
+ containing a version and an IV.
+
+
+
+
+Rivest Informational [Page 9]
+
+RFC 2268 RC2(r) Encryption Algorithm March 1998
+
+
+ 0 1 2 3 4 5 6 7 8 9 a b c d e f
+
+ 00: bd 56 ea f2 a2 f1 ac 2a b0 93 d1 9c 1b 33 fd d0
+ 10: 30 04 b6 dc 7d df 32 4b f7 cb 45 9b 31 bb 21 5a
+ 20: 41 9f e1 d9 4a 4d 9e da a0 68 2c c3 27 5f 80 36
+ 30: 3e ee fb 95 1a fe ce a8 34 a9 13 f0 a6 3f d8 0c
+ 40: 78 24 af 23 52 c1 67 17 f5 66 90 e7 e8 07 b8 60
+ 50: 48 e6 1e 53 f3 92 a4 72 8c 08 15 6e 86 00 84 fa
+ 60: f4 7f 8a 42 19 f6 db cd 14 8d 50 12 ba 3c 06 4e
+ 70: ec b3 35 11 a1 88 8e 2b 94 99 b7 71 74 d3 e4 bf
+ 80: 3a de 96 0e bc 0a ed 77 fc 37 6b 03 79 89 62 c6
+ 90: d7 c0 d2 7c 6a 8b 22 a3 5b 05 5d 02 75 d5 61 e3
+ a0: 18 8f 55 51 ad 1f 0b 5e 85 e5 c2 57 63 ca 3d 6c
+ b0: b4 c5 cc 70 b2 91 59 0d 47 20 c8 4f 58 e0 01 e2
+ c0: 16 38 c4 6f 3b 0f 65 46 be 7e 2d 7b 82 f9 40 b5
+ d0: 1d 73 f8 eb 26 c7 87 97 25 54 b1 28 aa 98 9d a5
+ e0: 64 6d 7a d4 10 81 44 ef 49 d6 ae 2e dd 76 5c 2f
+ f0: a7 1c c9 09 69 9a 83 cf 29 39 b9 e9 4c ff 43 ab
+
+A. Intellectual Property Notice
+
+ RC2 is a registered trademark of RSA Data Security, Inc. RSA's
+ copyrighted RC2 software is available under license from RSA Data
+ Security, Inc.
+
+B. Author's Address
+
+ Ron Rivest
+ RSA Laboratories
+ 100 Marine Parkway, #500
+ Redwood City, CA 94065 USA
+
+ Phone: (650) 595-7703
+ EMail: rsa-labs@rsa.com
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+Rivest Informational [Page 10]
+
+RFC 2268 RC2(r) Encryption Algorithm March 1998
+
+
+C. Full Copyright Statement
+
+ Copyright (C) The Internet Society (1998). All Rights Reserved.
+
+ This document and translations of it may be copied and furnished to
+ others, and derivative works that comment on or otherwise explain it
+ or assist in its implementation may be prepared, copied, published
+ and distributed, in whole or in part, without restriction of any
+ kind, provided that the above copyright notice and this paragraph are
+ included on all such copies and derivative works. However, this
+ document itself may not be modified in any way, such as by removing
+ the copyright notice or references to the Internet Society or other
+ Internet organizations, except as needed for the purpose of
+ developing Internet standards in which case the procedures for
+ copyrights defined in the Internet Standards process must be
+ followed, or as required to translate it into languages other than
+ English.
+
+ The limited permissions granted above are perpetual and will not be
+ revoked by the Internet Society or its successors or assigns.
+
+ This document and the information contained herein is provided on an
+ "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING
+ TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING
+ BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION
+ HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF
+ MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+Rivest Informational [Page 11]
+