crypto/rc2/rrc2.doc

   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@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