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