OLD | NEW |
| (Empty) |
1 >From cygnus.mincom.oz.au!minbne.mincom.oz.au!bunyip.cc.uq.oz.au!munnari.OZ.AU!c
omp.vuw.ac.nz!waikato!auckland.ac.nz!news Mon Feb 12 18:48:17 EST 1996 | |
2 Article 23601 of sci.crypt: | |
3 Path: cygnus.mincom.oz.au!minbne.mincom.oz.au!bunyip.cc.uq.oz.au!munnari.OZ.AU!c
omp.vuw.ac.nz!waikato!auckland.ac.nz!news | |
4 >From: pgut01@cs.auckland.ac.nz (Peter Gutmann) | |
5 Newsgroups: sci.crypt | |
6 Subject: Specification for Ron Rivests Cipher No.2 | |
7 Date: 11 Feb 1996 06:45:03 GMT | |
8 Organization: University of Auckland | |
9 Lines: 203 | |
10 Sender: pgut01@cs.auckland.ac.nz (Peter Gutmann) | |
11 Message-ID: <4fk39f$f70@net.auckland.ac.nz> | |
12 NNTP-Posting-Host: cs26.cs.auckland.ac.nz | |
13 X-Newsreader: NN version 6.5.0 #3 (NOV) | |
14 | |
15 | |
16 | |
17 | |
18 Ron Rivest's Cipher No.2 | |
19 ------------------------ | |
20 | |
21 Ron Rivest's Cipher No.2 (hereafter referred to as RRC.2, other people may | |
22 refer to it by other names) is word oriented, operating on a block of 64 bits | |
23 divided into four 16-bit words, with a key table of 64 words. All data units | |
24 are little-endian. This functional description of the algorithm is based in | |
25 the paper "The RC5 Encryption Algorithm" (RC5 is a trademark of RSADSI), using | |
26 the same general layout, terminology, and pseudocode style. | |
27 | |
28 | |
29 Notation and RRC.2 Primitive Operations | |
30 | |
31 RRC.2 uses the following primitive operations: | |
32 | |
33 1. Two's-complement addition of words, denoted by "+". The inverse operation, | |
34 subtraction, is denoted by "-". | |
35 2. Bitwise exclusive OR, denoted by "^". | |
36 3. Bitwise AND, denoted by "&". | |
37 4. Bitwise NOT, denoted by "~". | |
38 5. 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 | |
41 These operations are directly and efficiently supported by most processors. | |
42 | |
43 | |
44 The RRC.2 Algorithm | |
45 | |
46 RRC.2 consists of three components, a *key expansion* algorithm, an | |
47 *encryption* algorithm, and a *decryption* algorithm. | |
48 | |
49 | |
50 Key Expansion | |
51 | |
52 The purpose of the key-expansion routine is to expand the user's key K to fill | |
53 the expanded key array S, so S resembles an array of random binary words | |
54 determined by the user's secret key K. | |
55 | |
56 Initialising the S-box | |
57 | |
58 RRC.2 uses a single 256-byte S-box derived from the ciphertext contents of | |
59 Beale Cipher No.1 XOR'd with a one-time pad. The Beale Ciphers predate modern | |
60 cryptography by enough time that there should be no concerns about trapdoors | |
61 hidden in the data. They have been published widely, and the S-box can be | |
62 easily recreated from the one-time pad values and the Beale Cipher data taken | |
63 from 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 | |
68 The contents of Beale Cipher No.1 and the necessary one-time pad are given as | |
69 an appendix at the end of this document. For efficiency, implementors may wish | |
70 to skip the Beale Cipher expansion and store the sBox table directly. | |
71 | |
72 Expanding the Secret Key to 128 Bytes | |
73 | |
74 The secret key is first expanded to fill 128 bytes (64 words). The expansion | |
75 consists of taking the sum of the first and last bytes in the user key, looking | |
76 up the sum (modulo 256) in the S-box, and appending the result to the key. The | |
77 operation is repeated with the second byte and new last byte of the key until | |
78 all 128 bytes have been generated. Note that the following pseudocode treats | |
79 the 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 | |
86 At this point it is possible to perform a truncation of the effective key | |
87 length to ease the creation of espionage-enabled software products. However | |
88 since the author cannot conceive why anyone would want to do this, it will not | |
89 be considered further. | |
90 | |
91 The final phase of the key expansion involves replacing the first byte of S | |
92 with the entry selected from the S-box: | |
93 | |
94 S[ 0 ] = sBox[ S[ 0 ] ] | |
95 | |
96 | |
97 Encryption | |
98 | |
99 The cipher has 16 full rounds, each divided into 4 subrounds. Two of the full | |
100 rounds perform an additional transformation on the data. Note that the | |
101 following pseudocode treats the S array as an array of 64 words rather than 128 | |
102 bytes. | |
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 | |
111 In addition the fifth and eleventh rounds add the contents of the S-box indexed | |
112 by one of the data words to another of the data words following the four | |
113 subrounds 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 | |
121 Decryption | |
122 | |
123 The decryption operation is simply the inverse of the encryption operation. | |
124 Note that the following pseudocode treats the S array as an array of 64 words | |
125 rather 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 | |
134 In addition the fifth and eleventh rounds subtract the contents of the S-box | |
135 indexed by one of the data words from another one of the data words following | |
136 the 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 | |
144 Test Vectors | |
145 | |
146 The following test vectors may be used to test the correctness of an RRC.2 | |
147 implementation: | |
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 | |
170 Appendix: Beale Cipher No.1, "The Locality of the Vault", and One-time Pad for | |
171 Creating the S-Box | |
172 | |
173 Beale 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 | |
192 One-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 | |
212 Implementation | |
213 | |
214 A non-US based programmer who has never seen any encryption code before will | |
215 shortly be implementing RRC.2 based solely on this specification and not on | |
216 knowledge of any other encryption algorithms. Stand by. | |
217 | |
218 | |
219 | |
OLD | NEW |