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 2 Article 23601 of sci.crypt: 3 Path: 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 (a] 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 (a] cs.auckland.ac.nz (Peter Gutmann) 11 Message-ID: <4fk39f$f70 (a] 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 220
