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