Source code: cryptix/jce/provider/cipher/DES.java
1 /* $Id: DES.java,v 1.11 2001/08/06 21:22:55 edwin Exp $
2 *
3 * Copyright (C) 1995-2000 The Cryptix Foundation Limited.
4 * All rights reserved.
5 *
6 * Use, modification, copying and distribution of this software is subject
7 * the terms and conditions of the Cryptix General Licence. You should have
8 * received a copy of the Cryptix General Licence along with this library;
9 * if not, you can download a copy from http://www.cryptix.org/ .
10 */
11 package cryptix.jce.provider.cipher;
12
13
14 import cryptix.jce.provider.key.*;
15 import java.security.InvalidKeyException;
16 import java.security.Key;
17
18
19 /**
20 * DES is a block cipher with an 8 byte block size. The key length
21 * is 8 bytes, but only 56 bits are used as the parity bit in each
22 * byte is ignored.
23 * <p>
24 * This algorithm has been seriously analysed over the last 30 years,
25 * and no significant weaknesses have been reported. Its only known
26 * flaw is that the key length of 56 bits makes it relatively easy to
27 * brute-force it.
28 * <p>
29 * To overcome this near-fatal flaw, it is recommended that DES be
30 * used in Triple DES mode. The JCA algorithm name for the recommended
31 * form of Triple DES is "DES-EDE3".
32 * <p>
33 * DES was invented by IBM and first released in 1976. The algorithm is
34 * freely usable for both single and triple encryption.
35 * <p>
36 * References:<br>
37 * <ul>
38 * <li>"Chapter 12 Data Encryption Standard,"
39 * Applied Cryptography, 2nd edition,
40 * Bruce Schneier, John Wiley & Sons, 1996.</li>
41 *
42 * <li>NIST FIPS PUB 46-2 (supercedes FIPS PUB 46-1),
43 * "Data Encryption Standard",
44 * U.S. Department of Commerce, December 1993.<br>
45 * <a href="http://www.itl.nist.gov/fipspubs/fip46-2.htm">
46 * http://www.itl.nist.gov/fipspubs/fip46-2.htm</a></li>
47 * </ul>
48 *
49 * @version $Revision: 1.11 $
50 * @author Systemics Ltd
51 * @author David Hopwood
52 * @author Eric Young
53 * @author Geoffrey Keating
54 * @author Jeroen C. van Gelderen (gelderen@cryptix.org)
55 * @author John F. Dumas (jdumas@zgs.com)
56 * @author Raif S. Naffah (raif@cryptix.org)
57 */
58 public final class DES
59 extends BlockCipher
60 {
61
62 // Static variables and constants
63 // ...................................................................
64
65 private static final int
66 ROUNDS = 16, // number of encryption/decryption rounds
67 BLOCK_SIZE = 8, // DES block size in bytes
68 KEY_LENGTH = 8, // DES key length in bytes
69 ALT_KEY_LENGTH = 7, // Alternate DES key length in bytes
70 INTERNAL_KEY_LENGTH = 2 * ROUNDS; // number of elements in key schedule
71
72
73 /** Table for PC2 permutations in key schedule computation. */
74 private static final int[] SKB = new int[8 * 64];
75
76
77 /** Table for S-boxes and permutations, used in encrypt_base. */
78 private static final int SP_TRANS[] = new int[8 * 64];
79
80
81 /** Build the SKB and SP_TRANS tables */
82 static
83 {
84 // build the SKB table
85 // represent the bit number that each permutated bit is derived from
86 // according to FIPS-46
87 String cd =
88 "D]PKESYM`UBJ\\@RXA`I[T`HC`LZQ"+"\\PB]TL`[C`JQ@Y`HSXDUIZRAM`EK";
89 int j, s, bit;
90 int count = 0;
91 int offset = 0;
92 for (int i = 0; i < cd.length(); i++)
93 {
94 s = cd.charAt(i) - '@';
95 if (s != 32)
96 {
97 bit = 1 << count++;
98 for (j = 0; j < 64; j++)
99 if ((bit & j) != 0) SKB[offset + j] |= 1 << s;
100 if (count == 6)
101 {
102 offset += 64;
103 count = 0;
104 }
105 }
106 }
107
108
109 // build the SP_TRANS table
110 // I'd _really_ like to just say 'SP_TRANS = { ... }', but
111 // that would be terribly inefficient (code size + time).
112 // Instead we use a compressed representation --GK
113 String spt =
114 "g3H821:80:H03BA0@N1290BAA88::3112aIH8:8282@0@AH0:1W3A8P810@22;22"+
115 "A18^@9H9@129:<8@822`?:@0@8PH2H81A19:G1@03403A0B1;:0@1g192:@919AA"+
116 "0A109:W21492H@0051919811:215011139883942N8::3112A2:31981jM118::A"+
117 "101@I88:1aN0<@030128:X;811`920:;H0310D1033@W980:8A4@804A3803o1A2"+
118 "021B2:@1AH023GA:8:@81@@12092B:098042P@:0:A0HA9>1;289:@1804:40Ph="+
119 "1:H0I0HP0408024bC9P8@I808A;@0@0PnH0::8:19J@818:@iF0398:8A9H0<13@"+
120 "001@11<8;@82B01P0a2989B:0AY0912889bD0A1@B1A0A0AB033O91182440A9P8"+
121 "@I80n@1I03@1J828212A`A8:12B1@19A9@9@8^B:0@H00<82AB030bB840821Q:8"+
122 "310A302102::A1::20A1;8"; // OK, try to type _that_!
123 // [526 chars, 3156 bits]
124 // The theory is that each bit position in each int of SP_TRANS is
125 // set in exactly 32 entries. We keep track of set bits.
126 offset = 0;
127 int k, c, param;
128 for (int i = 0; i < 32; i++) // each bit position
129 {
130 k = -1; // pretend the -1th bit was set
131 bit = 1 << i;
132 for (j = 0; j < 32; j++) // each set bit
133 {
134 // Each character consists of two three-bit values:
135 c = spt.charAt(offset >> 1) - '0' >> (offset & 1) * 3 & 7;
136 offset++;
137 if (c < 5)
138 {
139 // values 0...4 indicate a set bit 1...5 positions
140 // from the previous set bit
141 k += c + 1;
142 SP_TRANS[k] |= bit;
143 continue;
144 }
145 // other values take at least an additional parameter:
146 // the next value in the sequence.
147 param = spt.charAt(offset >> 1) - '0' >> (offset & 1) * 3 & 7;
148 offset++;
149 if (c == 5)
150 {
151 // indicates a bit set param+6 positions from
152 // the previous set bit
153 k += param + 6;
154 SP_TRANS[k] |= bit;
155 }
156 else if (c == 6)
157 {
158 // indicates a bit set (param * 64) + 1 positions
159 // from the previous set bit
160 k += (param << 6) + 1;
161 SP_TRANS[k] |= bit;
162 }
163 else
164 {
165 // indicates that we should skip (param * 64) positions,
166 // then process the next value which will be in the range
167 // 0...4.
168 k += param << 6;
169 j--;
170 }
171 }
172 }
173 }
174
175
176
177 // Instance variables
178 // ...................................................................
179
180 /** The internal key schedule */
181 private int[] sKey = new int[INTERNAL_KEY_LENGTH];
182
183
184
185 // Constructor, ...
186 // ...................................................................
187
188 public DES()
189 {
190 super("DES",BLOCK_SIZE);
191 }
192
193
194
195 // BPI methods
196 // ...................................................................
197
198 protected void coreInit(Key key, boolean decrypt)
199 throws InvalidKeyException
200 {
201 byte[] userkey = key.getEncoded();
202 if (userkey == null)
203 throw new InvalidKeyException("Null user key");
204
205 if (userkey.length == ALT_KEY_LENGTH) {
206
207 byte[] temp = new byte[KEY_LENGTH];
208
209 temp[0] = (byte)( userkey[0] );
210 temp[1] = (byte)( userkey[0] << 7 | userkey[1] >>> 1 & 0x7f );
211 temp[2] = (byte)( userkey[1] << 6 | userkey[2] >>> 2 & 0x3f );
212 temp[3] = (byte)( userkey[2] << 5 | userkey[3] >>> 3 & 0x1f );
213 temp[4] = (byte)( userkey[3] << 4 | userkey[4] >>> 4 & 0x0f );
214 temp[5] = (byte)( userkey[4] << 3 | userkey[5] >>> 5 & 0x07 );
215 temp[6] = (byte)( userkey[5] << 2 | userkey[6] >>> 6 & 0x03 );
216 temp[7] = (byte)( userkey[6] << 1 );
217
218 userkey = temp;
219 }
220
221 if (userkey.length != KEY_LENGTH)
222 throw new InvalidKeyException("Invalid user key length");
223
224 int i = 0;
225 int c = (userkey[i++] & 0xFF) |
226 (userkey[i++] & 0xFF) << 8 |
227 (userkey[i++] & 0xFF) << 16 |
228 (userkey[i++] ) << 24;
229 int d = (userkey[i++] & 0xFF) |
230 (userkey[i++] & 0xFF) << 8 |
231 (userkey[i++] & 0xFF) << 16 |
232 (userkey[i ] ) << 24;
233
234 int t = ((d >>> 4) ^ c) & 0x0F0F0F0F;
235 c ^= t;
236 d ^= t << 4;
237 t = ((c << 18) ^ c) & 0xCCCC0000;
238 c ^= t ^ t >>> 18;
239 t = ((d << 18) ^ d) & 0xCCCC0000;
240 d ^= t ^ t >>> 18;
241 t = ((d >>> 1) ^ c) & 0x55555555;
242 c ^= t;
243 d ^= t << 1;
244 t = ((c >>> 8) ^ d) & 0x00FF00FF;
245 d ^= t;
246 c ^= t << 8;
247 t = ((d >>> 1) ^ c) & 0x55555555;
248 c ^= t;
249 d ^= t << 1;
250
251 d = (d & 0x000000FF) << 16 |
252 (d & 0x0000FF00) |
253 (d & 0x00FF0000) >>> 16 |
254 (c & 0xF0000000) >>> 4;
255 c &= 0x0FFFFFFF;
256
257 int s;
258 int j = 0;
259
260 for (i = 0; i < ROUNDS; i++)
261 {
262 if ((0x7EFC >> i & 1) == 1)
263 {
264 c = (c >>> 2 | c << 26) & 0x0FFFFFFF;
265 d = (d >>> 2 | d << 26) & 0x0FFFFFFF;
266 }
267 else
268 {
269 c = (c >>> 1 | c << 27) & 0x0FFFFFFF;
270 d = (d >>> 1 | d << 27) & 0x0FFFFFFF;
271 }
272 s = SKB[ c & 0x3F ] |
273 SKB[0x040 | (((c >>> 6) & 0x03) | ((c >>> 7) & 0x3C))] |
274 SKB[0x080 | (((c >>> 13) & 0x0F) | ((c >>> 14) & 0x30))] |
275 SKB[0x0C0 | (((c >>> 20) & 0x01) | ((c >>> 21) & 0x06)
276 | ((c >>> 22) & 0x38))];
277 t = SKB[0x100 | ( d & 0x3F )] |
278 SKB[0x140 | (((d >>> 7) & 0x03) | ((d >>> 8) & 0x3c))] |
279 SKB[0x180 | ((d >>> 15) & 0x3F )] |
280 SKB[0x1C0 | (((d >>> 21) & 0x0F) | ((d >>> 22) & 0x30))];
281
282 sKey[j++] = t << 16 | (s & 0x0000FFFF);
283 s = s >>> 16 | (t & 0xFFFF0000);
284 sKey[j++] = s << 4 | s >>> 28;
285 }
286
287
288 // Reverse the subkeys if we're decrypting
289 // Best illustrated by example: 1 2 3 4 5 6 7 8 -> 7 8 5 6 3 4 1 2
290 if(decrypt)
291 {
292 for(i=0; i<16; i++)
293 {
294 j = 30 - i + ( i%2 * 2 );
295 t = sKey[i]; sKey[i] = sKey[j]; sKey[j] = t;
296 }
297 }
298 }
299
300
301
302 /**
303 * Perform a DES encryption or decryption operation of a single block.
304 */
305 protected void coreCrypt(byte[] in, int inOffset, byte[] out, int outOffset)
306 {
307 int L = (in[inOffset++] & 0xFF) |
308 (in[inOffset++] & 0xFF) << 8 |
309 (in[inOffset++] & 0xFF) << 16 |
310 (in[inOffset++] ) << 24;
311 int R = (in[inOffset++] & 0xFF) |
312 (in[inOffset++] & 0xFF) << 8 |
313 (in[inOffset++] & 0xFF) << 16 |
314 (in[inOffset ] ) << 24;
315
316 // Initial permutation
317 int t = ((R >>> 4) ^ L) & 0x0F0F0F0F;
318 L ^= t;
319 R ^= t << 4;
320 t = ((L >>> 16) ^ R) & 0x0000FFFF;
321 R ^= t;
322 L ^= t << 16;
323 t = ((R >>> 2) ^ L) & 0x33333333;
324 L ^= t;
325 R ^= t << 2;
326 t = ((L >>> 8) ^ R) & 0x00FF00FF;
327 R ^= t;
328 L ^= t << 8;
329 t = ((R >>> 1) ^ L) & 0x55555555;
330 L ^= t;
331 R ^= t << 1;
332
333
334 // look! we fit all four variables (plus the class itself)
335 // into short byte-codes!
336 int u = R << 1 | R >>> 31;
337 R = L << 1 | L >>> 31;
338 L = u;
339
340 for (int i = 0; i < INTERNAL_KEY_LENGTH;)
341 {
342 u = R ^ sKey[i++];
343 t = R ^ sKey[i++];
344 t = t >>> 4 | t << 28;
345 L ^= (SP_TRANS[0x040 | ( t & 0x3F)] |
346 SP_TRANS[0x0C0 | ((t >>> 8) & 0x3F)] |
347 SP_TRANS[0x140 | ((t >>> 16) & 0x3F)] |
348 SP_TRANS[0x1C0 | ((t >>> 24) & 0x3F)] |
349 SP_TRANS[ u & 0x3F ] |
350 SP_TRANS[0x080 | ((u >>> 8) & 0x3F)] |
351 SP_TRANS[0x100 | ((u >>> 16) & 0x3F)] |
352 SP_TRANS[0x180 | ((u >>> 24) & 0x3F)]);
353
354 u = L ^ sKey[i++];
355 t = L ^ sKey[i++];
356 t = t >>> 4 | t << 28;
357 R ^= (SP_TRANS[0x040 | ( t & 0x3F)] |
358 SP_TRANS[0x0C0 | ((t >>> 8) & 0x3F)] |
359 SP_TRANS[0x140 | ((t >>> 16) & 0x3F)] |
360 SP_TRANS[0x1C0 | ((t >>> 24) & 0x3F)] |
361 SP_TRANS[ u & 0x3F ] |
362 SP_TRANS[0x080 | ((u >>> 8) & 0x3F)] |
363 SP_TRANS[0x100 | ((u >>> 16) & 0x3F)] |
364 SP_TRANS[0x180 | ((u >>> 24) & 0x3F)]);
365 }
366 R = R >>> 1 | R << 31;
367 L = L >>> 1 | L << 31;
368
369
370 // Final permutation
371 t = (R >>> 1 ^ L) & 0x55555555;
372 L ^= t;
373 R ^= t << 1;
374 t = (L >>> 8 ^ R) & 0x00FF00FF;
375 R ^= t;
376 L ^= t << 8;
377 t = (R >>> 2 ^ L) & 0x33333333;
378 L ^= t;
379 R ^= t << 2;
380 t = (L >>> 16 ^ R) & 0x0000FFFF;
381 R ^= t;
382 L ^= t << 16;
383 t = (R >>> 4 ^ L) & 0x0F0F0F0F;
384
385 L ^= t;
386 R ^= (t << 4);
387
388 out[outOffset++] = (byte)(L );
389 out[outOffset++] = (byte)(L >> 8);
390 out[outOffset++] = (byte)(L >> 16);
391 out[outOffset++] = (byte)(L >> 24);
392 out[outOffset++] = (byte)(R );
393 out[outOffset++] = (byte)(R >> 8);
394 out[outOffset++] = (byte)(R >> 16);
395 out[outOffset ] = (byte)(R >> 24);
396 }
397 }