1>From cygnus.mincom.oz.au!minbne.mincom.oz.au!bunyip.cc.uq.oz.au!munnari.OZ.AU!comp.vuw.ac.nz!waikato!auckland.ac.nz!news Mon Feb 12 18:48:17 EST 1996
2Article 23601 of sci.crypt:
3Path: cygnus.mincom.oz.au!minbne.mincom.oz.au!bunyip.cc.uq.oz.au!munnari.OZ.AU!comp.vuw.ac.nz!waikato!auckland.ac.nz!news
4>From: pgut01@cs.auckland.ac.nz (Peter Gutmann)
5Newsgroups: sci.crypt
6Subject: Specification for Ron Rivests Cipher No.2
7Date: 11 Feb 1996 06:45:03 GMT
8Organization: University of Auckland
9Lines: 203
10Sender: pgut01@cs.auckland.ac.nz (Peter Gutmann)
11Message-ID: <4fk39f$f70@net.auckland.ac.nz>
12NNTP-Posting-Host: cs26.cs.auckland.ac.nz
13X-Newsreader: NN version 6.5.0 #3 (NOV)
14
15
16
17
18                           Ron Rivest's Cipher No.2
19                           ------------------------
20 
21Ron Rivest's Cipher No.2 (hereafter referred to as RRC.2, other people may
22refer to it by other names) is word oriented, operating on a block of 64 bits
23divided into four 16-bit words, with a key table of 64 words.  All data units
24are little-endian.  This functional description of the algorithm is based in
25the paper "The RC5 Encryption Algorithm" (RC5 is a trademark of RSADSI), using
26the same general layout, terminology, and pseudocode style.
27 
28 
29Notation and RRC.2 Primitive Operations
30 
31RRC.2 uses the following primitive operations:
32 
331. Two's-complement addition of words, denoted by "+".  The inverse operation,
34   subtraction, is denoted by "-".
352. Bitwise exclusive OR, denoted by "^".
363. Bitwise AND, denoted by "&".
374. Bitwise NOT, denoted by "~".
385. A left-rotation of words; the rotation of word x left by y is denoted
39   x <<< y.  The inverse operation, right-rotation, is denoted x >>> y.
40 
41These operations are directly and efficiently supported by most processors.
42 
43 
44The RRC.2 Algorithm
45 
46RRC.2 consists of three components, a *key expansion* algorithm, an
47*encryption* algorithm, and a *decryption* algorithm.
48 
49 
50Key Expansion
51 
52The purpose of the key-expansion routine is to expand the user's key K to fill
53the expanded key array S, so S resembles an array of random binary words
54determined by the user's secret key K.
55 
56Initialising the S-box
57 
58RRC.2 uses a single 256-byte S-box derived from the ciphertext contents of
59Beale Cipher No.1 XOR'd with a one-time pad.  The Beale Ciphers predate modern
60cryptography by enough time that there should be no concerns about trapdoors
61hidden in the data.  They have been published widely, and the S-box can be
62easily recreated from the one-time pad values and the Beale Cipher data taken
63from a standard source.  To initialise the S-box:
64 
65  for i = 0 to 255 do
66    sBox[ i ] = ( beale[ i ] mod 256 ) ^ pad[ i ]
67 
68The contents of Beale Cipher No.1 and the necessary one-time pad are given as
69an appendix at the end of this document.  For efficiency, implementors may wish
70to skip the Beale Cipher expansion and store the sBox table directly.
71 
72Expanding the Secret Key to 128 Bytes
73 
74The secret key is first expanded to fill 128 bytes (64 words).  The expansion
75consists of taking the sum of the first and last bytes in the user key, looking
76up the sum (modulo 256) in the S-box, and appending the result to the key.  The
77operation is repeated with the second byte and new last byte of the key until
78all 128 bytes have been generated.  Note that the following pseudocode treats
79the S array as an array of 128 bytes rather than 64 words.
80 
81  for j = 0 to length-1 do
82    S[ j ] = K[ j ]
83  for j = length to 127 do
84    s[ j ] = sBox[ ( S[ j-length ] + S[ j-1 ] ) mod 256 ];
85 
86At this point it is possible to perform a truncation of the effective key
87length to ease the creation of espionage-enabled software products.  However
88since the author cannot conceive why anyone would want to do this, it will not
89be considered further.
90 
91The final phase of the key expansion involves replacing the first byte of S
92with the entry selected from the S-box:
93 
94  S[ 0 ] = sBox[ S[ 0 ] ]
95 
96 
97Encryption
98 
99The cipher has 16 full rounds, each divided into 4 subrounds.  Two of the full
100rounds perform an additional transformation on the data.  Note that the
101following pseudocode treats the S array as an array of 64 words rather than 128
102bytes.
103 
104  for i = 0 to 15 do
105    j = i * 4;
106    word0 = ( word0 + ( word1 & ~word3 ) + ( word2 & word3 ) + S[ j+0 ] ) <<< 1
107    word1 = ( word1 + ( word2 & ~word0 ) + ( word3 & word0 ) + S[ j+1 ] ) <<< 2
108    word2 = ( word2 + ( word3 & ~word1 ) + ( word0 & word1 ) + S[ j+2 ] ) <<< 3
109    word3 = ( word3 + ( word0 & ~word2 ) + ( word1 & word2 ) + S[ j+3 ] ) <<< 5
110 
111In addition the fifth and eleventh rounds add the contents of the S-box indexed
112by one of the data words to another of the data words following the four
113subrounds as follows:
114 
115    word0 = word0 + S[ word3 & 63 ];
116    word1 = word1 + S[ word0 & 63 ];
117    word2 = word2 + S[ word1 & 63 ];
118    word3 = word3 + S[ word2 & 63 ];
119 
120 
121Decryption
122 
123The decryption operation is simply the inverse of the encryption operation.
124Note that the following pseudocode treats the S array as an array of 64 words
125rather than 128 bytes.
126 
127  for i = 15 downto 0 do
128    j = i * 4;
129    word3 = ( word3 >>> 5 ) - ( word0 & ~word2 ) - ( word1 & word2 ) - S[ j+3 ]
130    word2 = ( word2 >>> 3 ) - ( word3 & ~word1 ) - ( word0 & word1 ) - S[ j+2 ]
131    word1 = ( word1 >>> 2 ) - ( word2 & ~word0 ) - ( word3 & word0 ) - S[ j+1 ]
132    word0 = ( word0 >>> 1 ) - ( word1 & ~word3 ) - ( word2 & word3 ) - S[ j+0 ]
133 
134In addition the fifth and eleventh rounds subtract the contents of the S-box
135indexed by one of the data words from another one of the data words following
136the four subrounds as follows:
137 
138    word3 = word3 - S[ word2 & 63 ]
139    word2 = word2 - S[ word1 & 63 ]
140    word1 = word1 - S[ word0 & 63 ]
141    word0 = word0 - S[ word3 & 63 ]
142 
143 
144Test Vectors
145 
146The following test vectors may be used to test the correctness of an RRC.2
147implementation:
148 
149  Key:      0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
150            0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00
151  Plain:    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00
152  Cipher:   0x1C, 0x19, 0x8A, 0x83, 0x8D, 0xF0, 0x28, 0xB7
153 
154  Key:      0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
155            0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01
156  Plain:    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00
157  Cipher:   0x21, 0x82, 0x9C, 0x78, 0xA9, 0xF9, 0xC0, 0x74
158 
159  Key:      0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
160            0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00
161  Plain:    0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF
162  Cipher:   0x13, 0xDB, 0x35, 0x17, 0xD3, 0x21, 0x86, 0x9E
163 
164  Key:      0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07,
165            0x08, 0x09, 0x0A, 0x0B, 0x0C, 0x0D, 0x0E, 0x0F
166  Plain:    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00
167  Cipher:   0x50, 0xDC, 0x01, 0x62, 0xBD, 0x75, 0x7F, 0x31
168 
169 
170Appendix: Beale Cipher No.1, "The Locality of the Vault", and One-time Pad for
171          Creating the S-Box
172 
173Beale Cipher No.1.
174 
175  71, 194,  38,1701,  89,  76,  11,  83,1629,  48,  94,  63, 132,  16, 111,  95,
176  84, 341, 975,  14,  40,  64,  27,  81, 139, 213,  63,  90,1120,   8,  15,   3,
177 126,2018,  40,  74, 758, 485, 604, 230, 436, 664, 582, 150, 251, 284, 308, 231,
178 124, 211, 486, 225, 401, 370,  11, 101, 305, 139, 189,  17,  33,  88, 208, 193,
179 145,   1,  94,  73, 416, 918, 263,  28, 500, 538, 356, 117, 136, 219,  27, 176,
180 130,  10, 460,  25, 485,  18, 436,  65,  84, 200, 283, 118, 320, 138,  36, 416,
181 280,  15,  71, 224, 961,  44,  16, 401,  39,  88,  61, 304,  12,  21,  24, 283,
182 134,  92,  63, 246, 486, 682,   7, 219, 184, 360, 780,  18,  64, 463, 474, 131,
183 160,  79,  73, 440,  95,  18,  64, 581,  34,  69, 128, 367, 460,  17,  81,  12,
184 103, 820,  62, 110,  97, 103, 862,  70,  60,1317, 471, 540, 208, 121, 890, 346,
185  36, 150,  59, 568, 614,  13, 120,  63, 219, 812,2160,1780,  99,  35,  18,  21,
186 136, 872,  15,  28, 170,  88,   4,  30,  44, 112,  18, 147, 436, 195, 320,  37,
187 122, 113,   6, 140,   8, 120, 305,  42,  58, 461,  44, 106, 301,  13, 408, 680,
188  93,  86, 116, 530,  82, 568,   9, 102,  38, 416,  89,  71, 216, 728, 965, 818,
189   2,  38, 121, 195,  14, 326, 148, 234,  18,  55, 131, 234, 361, 824,   5,  81,
190 623,  48, 961,  19,  26,  33,  10,1101, 365,  92,  88, 181, 275, 346, 201, 206
191 
192One-time Pad.
193 
194 158, 186, 223,  97,  64, 145, 190, 190, 117, 217, 163,  70, 206, 176, 183, 194,
195 146,  43, 248, 141,   3,  54,  72, 223, 233, 153,  91, 210,  36, 131, 244, 161,
196 105, 120, 113, 191, 113,  86,  19, 245, 213, 221,  43,  27, 242, 157,  73, 213,
197 193,  92, 166,  10,  23, 197, 112, 110, 193,  30, 156,  51, 125,  51, 158,  67,
198 197, 215,  59, 218, 110, 246, 181,   0, 135,  76, 164,  97,  47,  87, 234, 108,
199 144, 127,   6,   6, 222, 172,  80, 144,  22, 245, 207,  70, 227, 182, 146, 134,
200 119, 176,  73,  58, 135,  69,  23, 198,   0, 170,  32, 171, 176, 129,  91,  24,
201 126,  77, 248,   0, 118,  69,  57,  60, 190, 171, 217,  61, 136, 169, 196,  84,
202 168, 167, 163, 102, 223,  64, 174, 178, 166, 239, 242, 195, 249,  92,  59,  38,
203 241,  46, 236,  31,  59, 114,  23,  50, 119, 186,   7,  66, 212,  97, 222, 182,
204 230, 118, 122,  86, 105,  92, 179, 243, 255, 189, 223, 164, 194, 215,  98,  44,
205  17,  20,  53, 153, 137, 224, 176, 100, 208, 114,  36, 200, 145, 150, 215,  20,
206  87,  44, 252,  20, 235, 242, 163, 132,  63,  18,   5, 122,  74,  97,  34,  97,
207 142,  86, 146, 221, 179, 166, 161,  74,  69, 182,  88, 120, 128,  58,  76, 155,
208  15,  30,  77, 216, 165, 117, 107,  90, 169, 127, 143, 181, 208, 137, 200, 127,
209 170, 195,  26,  84, 255, 132, 150,  58, 103, 250, 120, 221, 237,  37,   8,  99
210 
211 
212Implementation
213 
214A non-US based programmer who has never seen any encryption code before will
215shortly be implementing RRC.2 based solely on this specification and not on
216knowledge of any other encryption algorithms.  Stand by.
217
218
219
220