2
0

rrc2.doc 9.6 KB

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