Source code: cryptix/jce/provider/cipher/Square.java
1 /* $Id: Square.java,v 1.4 2000/01/20 14:59:24 gelderen 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 java.security.InvalidKeyException;
15 import java.security.Key;
16
17
18 /**
19 * The Square algorithm.
20 * <p>
21 * Square is a cipher algorithm developed by Joan Daemen <Daemen.J@banksys.com>
22 * and Vincent Rijmen <vincent.rijmen@esat.kuleuven.ac.be>
23 * <p>
24 * <b>References:</b>
25 * <p>
26 * <blockquote>
27 * <ul>
28 * <li>The
29 * <a href="http://www.esat.kuleuven.ac.be/%7Erijmen/square/">
30 * Square home page</a>
31 * has up-to-date comments, implementations, and certification data.
32 * <li>J. Daemen, L.R. Knudsen, V. Rijmen,
33 * "<a href="http://www.esat.kuleuven.ac.be/%7Erijmen/downloadable/square/fse.ps.gz">
34 * The block cipher Square</a>,"
35 * <cite>Fast Software Encryption</cite>,
36 * LNCS 1267, E. Biham, Ed., Springer-Verlag, 1997, pp. 149-165.
37 * </ul>
38 * </blockquote>
39 *
40 * @version $Revision: 1.4 $
41 * @author Raif S. Naffah
42 * @author Paulo S.L.M. Barreto
43 * @author David Hopwood
44 * @author Jeroen C. van Gelderen
45 */
46 public final class Square
47 extends BlockCipher
48 {
49
50 // Static variables and constants
51 //............................................................................
52
53 private static final int
54 BLOCK_SIZE = 16,
55 KEY_LENGTH = 10,
56 R = 8; // nof rounds
57
58 /** Encryption and decryption Square S-Box values */
59 private static final byte[]
60 SE = new byte[256],
61 SD = new byte[256];
62
63 /** Transposition boxes for encryption and decryption */
64 private static final int[]
65 TE = new int[256],
66 TD = new int[256];
67
68 private static final int ROOT = 0x1F5; // for generating GF(2**8)
69
70 private static final int[] OFFSET = new int[R];
71
72
73 // Static code to build some tables
74 //............................................................................
75
76 static
77 {
78 int i, j;
79
80 //
81 // Generate exp and log tables used in multiplication over GF(2 ** m)
82 //
83 byte[] exp = new byte[256];
84 byte[] log = new byte[256];
85
86 exp[0] = 1;
87 for (i = 1; i < 256; i++) {
88 j = exp[i - 1] << 1;
89 if ((j & 0x100) != 0)
90 j ^= ROOT; // reduce j (mod ROOT)
91
92 exp[i] = (byte)j;
93 log[j & 0xFF] = (byte)i;
94 }
95
96 //
97 // Compute the substitution box SE[] and its inverse SD[]
98 // based on F(x) = x**{-1} plus affine transform of the output.
99 //
100 SE[0] = 0;
101 SE[1] = 1;
102 for (i = 2; i < 256; i++)
103 SE[i] = exp[(255 - log[i]) & 0xFF];
104
105 //
106 // Let SE[i] be represented as an 8-row vector V over GF(2);
107 // the affine transformation is A * V + T, where the rows of
108 // the 8 x 8 matrix A are contained in trans[0]...trans[7]
109 // and the 8-row vector T is contained in 0xB1.
110 //
111 int[] trans = {0x01, 0x03, 0x05, 0x0F, 0x1F, 0x3D, 0x7B, 0xD6};
112 int u, v;
113 for (i = 0; i < 256; i++) {
114 v = 0xB1; // the affine part of the transform
115 for (j = 0; j < 8; j++) {
116 u = SE[i] & trans[j] & 0xFF; // column-wise multiplication over GF(2)
117 u ^= u >>> 4; // sum of all bits of u over GF(2)
118 u ^= u >>> 2;
119 u ^= u >>> 1;
120 u &= 1;
121 v ^= u << j; // row alignment of the result
122 }
123 SE[i] = (byte) v;
124 SD[v] = (byte) i; // inverse substitution box
125 }
126
127 //
128 // Generate the OFFSET values.
129 //
130 OFFSET[0] = 1;
131 for (i = 1; i < R; i++) {
132 OFFSET[i] = mul(OFFSET[i - 1], 2);
133 OFFSET[i - 1] <<= 24;
134 }
135 OFFSET[R - 1] <<= 24;
136
137 //
138 // Generate the TE and TD transposition boxes.
139 // Notes:
140 // (1) The function mul below computes the product of two
141 // elements of GF(2 ** 8) with ROOT as reduction polynomial
142 // (see implementation below in Square's Own Methods section)
143 // (2) the values used in computing the TE and TD values are
144 // the GF(2 ** 8) coefficients of the diffusion polynomial c(x)
145 // and its inverse (modulo x ** 4 + 1) d(x), defined in sections
146 // 2.1 and 4 of the algorithm designers' paper (see References
147 // above).
148 //
149 int se, sd;
150 for (i = 0; i < 256; i++) {
151 se = SE[i] & 0xFF;
152 sd = SD[i] & 0xFF;
153 TE[i] = SE[i & 3] == 0 ? 0 :
154 mul(se, 2) << 24 | se << 16 | se << 8 | mul(se, 3);
155 TD[i] = SD[i & 3] == 0 ? 0 :
156 mul(sd, 14) << 24 | mul(sd, 9) << 16 | mul(sd, 13) << 8 | mul(sd, 11);
157 }
158 }
159
160
161 // Instance variables
162 //............................................................................
163
164 /** This instance's Square key schedule. */
165 private int[][] sKey = new int[R + 1][4];
166
167 /** Are we decrypting? */
168 private boolean decrypt;
169
170
171 // Constructor
172 //............................................................................
173
174 public Square() {
175 super(BLOCK_SIZE);
176 }
177
178
179 // Implementation of abstract methods
180 //............................................................................
181
182 protected void coreInit(Key key, boolean decrypt)
183 throws InvalidKeyException
184 {
185 makeKey(key, !decrypt);
186 this.decrypt = decrypt;
187 }
188
189
190 protected void coreCrypt(byte[] in, int inOffset, byte[] out, int outOffset)
191 {
192 if(decrypt)
193 square(in, inOffset, out, outOffset, TD, SD);
194 else
195 square(in, inOffset, out, outOffset, TE, SE);
196 }
197
198
199 //............................................................................
200
201 /**
202 * Expands a user-key to a working key schedule.
203 *
204 * @param key the user-key object to use.
205 * @param doEncrypt true for encryption, false for decryption.
206 * @exception InvalidKeyException if one of the following occurs: <ul>
207 * <li> key.getEncoded() == null;
208 * <li> The length of the user key array is not KEY_LENGTH.
209 * </ul>
210 */
211 private void makeKey(Key key, boolean doEncrypt)
212 throws InvalidKeyException {
213
214 byte[] userkey = key.getEncoded();
215 if (userkey == null)
216 throw new InvalidKeyException("Null user key");
217
218 if (userkey.length != BLOCK_SIZE)
219 throw new InvalidKeyException("Invalid user key length");
220
221 int i, j = 0;
222 if (doEncrypt) {
223 for (i = 0; i < 4; i++)
224 sKey[0][i] = (userkey[j++] & 0xFF) << 24 | (userkey[j++] & 0xFF) << 16 |
225 (userkey[j++] & 0xFF) << 8 | (userkey[j++] & 0xFF);
226
227 for (i = 1; i < R + 1; i++) {
228 j = i - 1;
229 sKey[i][0] = sKey[j][0] ^ rot32L(sKey[j][3], 8) ^ OFFSET[j];
230 sKey[i][1] = sKey[j][1] ^ sKey[i][0];
231 sKey[i][2] = sKey[j][2] ^ sKey[i][1];
232 sKey[i][3] = sKey[j][3] ^ sKey[i][2];
233
234 transform(sKey[j], sKey[j]);
235 }
236 } else {
237 int[][] tKey = new int[R + 1][4];
238
239 // apply the key evolution function
240 for (i = 0; i < 4; i++)
241 tKey[0][i] = (userkey[j++] & 0xFF) << 24 | (userkey[j++] & 0xFF) << 16 |
242 (userkey[j++] & 0xFF) << 8 | (userkey[j++] & 0xFF);
243
244 for (i = 1; i < R + 1; i++) {
245 j = i - 1;
246 tKey[i][0] = tKey[j][0] ^ rot32L(tKey[j][3], 8) ^ OFFSET[j];
247 tKey[i][1] = tKey[j][1] ^ tKey[i][0];
248 tKey[i][2] = tKey[j][2] ^ tKey[i][1];
249 tKey[i][3] = tKey[j][3] ^ tKey[i][2];
250 }
251 for (i = 0; i < R; i++)
252 System.arraycopy(tKey[R - i], 0, sKey[i], 0, 4);
253
254 transform(tKey[0], sKey[R]);
255 }
256 }
257
258
259 /**
260 * Applies the Theta function to an input <i>in</i> in order to
261 * produce in <i>out</i> an internal session sub-key.
262 * <p>
263 * Both <i>in</i> and <i>out</i> are arrays of four ints.
264 * <p>
265 * Pseudo-code is:
266 * <pre>
267 * for (i = 0; i < 4; i++) {
268 * out[i] = 0;
269 * for (j = 0, n = 24; j < 4; j++, n -= 8) {
270 * k = mul(in[i] >>> 24, G[0][j]) ^
271 * mul(in[i] >>> 16, G[1][j]) ^
272 * mul(in[i] >>> 8, G[2][j]) ^
273 * mul(in[i] , G[3][j]);
274 * out[i] ^= k << n;
275 * }
276 * }
277 * </pre>
278 */
279 private static void transform (int[] in, int[] out) {
280 int l3, l2, l1, l0, m;
281 for (int i = 0; i < 4; i++) {
282 l3 = in[i];
283 l2 = l3 >>> 8;
284 l1 = l3 >>> 16;
285 l0 = l3 >>> 24;
286 m = ((mul(l0, 2) ^ mul(l1, 3) ^ l2 ^ l3) & 0xFF) << 24;
287 m ^= ((l0 ^ mul(l1, 2) ^ mul(l2, 3) ^ l3) & 0xFF) << 16;
288 m ^= ((l0 ^ l1 ^ mul(l2, 2) ^ mul(l3, 3)) & 0xFF) << 8;
289 m ^= (mul(l0, 3) ^l1 ^ l2 ^ mul(l3, 2) ) & 0xFF;
290 out[i] = m;
291 }
292 }
293
294
295 /**
296 * Left rotate a 32-bit chunk.
297 *
298 * @param x the 32-bit data to rotate
299 * @param s number of places to left-rotate by
300 * @return the newly permutated value.
301 */
302 private static int rot32L (int x, int s) { return x << s | x >>> (32 - s); }
303
304
305 /**
306 * Right rotate a 32-bit chunk.
307 *
308 * @param x the 32-bit data to rotate
309 * @param s number of places to right-rotate by
310 * @return the newly permutated value.
311 */
312 private static int rot32R (int x, int s) { return x >>> s | x << (32 - s); }
313
314
315 /**
316 * Returns the product of two binary numbers a and b, using
317 * the generator ROOT as the modulus: p = (a * b) mod ROOT.
318 * ROOT Generates a suitable Galois Field in GF(2 ** 8).
319 * <p>
320 * For best performance call it with abs(b) < abs(a).
321 *
322 * @param a operand for multiply.
323 * @param b operand for multiply.
324 * @return the result of (a * b) % ROOT.
325 */
326 private static final int mul (int a, int b) {
327 if (a == 0)
328 return 0;
329
330 a &= 0xFF;
331 b &= 0xFF;
332 int p = 0;
333 while (b != 0) {
334 if ((b & 0x01) != 0)
335 p ^= a;
336 a <<= 1;
337 if (a > 0xFF)
338 a ^= ROOT;
339 b >>>= 1;
340 }
341 return p & 0xFF;
342 }
343
344
345 /**
346 * Applies the Square algorithm (for both encryption and decryption since
347 * it is the same) on a 128-bit plain/cipher text into a same length cipher/
348 * plain text using the Square formulae, relevant sub-keys, transposition
349 * and S-Box values.
350 *
351 * @param in contains the plain-text 128-bit block.
352 * @param off start index within input where data is considered.
353 * @param out will contain the cipher-text block.
354 * @param outOff index in out where cipher-text starts.
355 * @param T reference to either the encryption (TE) or decryption
356 * (TD) transposition vector.
357 * @param S reference to either the encryption (SE) or decryption
358 * (SD) S-Box values.
359 */
360 private void
361 square (byte[] in, int off, byte[] out, int outOff, int[] T, byte[] S) {
362
363 int a = (in[off++] & 0xFF) << 24 | (in[off++] & 0xFF) << 16 |
364 (in[off++] & 0xFF) << 8 | (in[off++] & 0xFF);
365 int b = (in[off++] & 0xFF) << 24 | (in[off++] & 0xFF) << 16 |
366 (in[off++] & 0xFF) << 8 | (in[off++] & 0xFF);
367 int c = (in[off++] & 0xFF) << 24 | (in[off++] & 0xFF) << 16 |
368 (in[off++] & 0xFF) << 8 | (in[off++] & 0xFF);
369 int d = (in[off++] & 0xFF) << 24 | (in[off++] & 0xFF) << 16 |
370 (in[off++] & 0xFF) << 8 | (in[off++] & 0xFF);
371
372 int aa, bb, cc, dd;
373 int i, j, k;
374
375 a ^= sKey[0][0];
376 b ^= sKey[0][1];
377 c ^= sKey[0][2];
378 d ^= sKey[0][3];
379
380 // R - 1 full rounds
381 for (i = 1; i < R; i++) {
382 aa = T[(a >>> 24) & 0xFF] ^
383 rot32R(T[(b >>> 24) & 0xFF], 8) ^
384 rot32R(T[(c >>> 24) & 0xFF], 16) ^
385 rot32R(T[(d >>> 24) & 0xFF], 24) ^ sKey[i][0];
386
387 bb = T[(a >>> 16) & 0xFF] ^
388 rot32R(T[(b >>> 16) & 0xFF], 8) ^
389 rot32R(T[(c >>> 16) & 0xFF], 16) ^
390 rot32R(T[(d >>> 16) & 0xFF], 24) ^ sKey[i][1];
391
392 cc = T[(a >>> 8) & 0xFF] ^
393 rot32R(T[(b >>> 8) & 0xFF], 8) ^
394 rot32R(T[(c >>> 8) & 0xFF], 16) ^
395 rot32R(T[(d >>> 8) & 0xFF], 24) ^ sKey[i][2];
396
397 dd = T[ a & 0xFF] ^
398 rot32R(T[ b & 0xFF], 8) ^
399 rot32R(T[ c & 0xFF], 16) ^
400 rot32R(T[ d & 0xFF], 24) ^ sKey[i][3];
401
402 a = aa;
403 b = bb;
404 c = cc;
405 d = dd;
406 }
407 // last round (diffusion becomes only transposition)
408 for (i = 0, j = 24; i < 4; i++, j -= 8) {
409 k = (S[(a >>> j) & 0xFF] & 0xFF) << 24 |
410 (S[(b >>> j) & 0xFF] & 0xFF) << 16 |
411 (S[(c >>> j) & 0xFF] & 0xFF) << 8 |
412 (S[(d >>> j) & 0xFF] & 0xFF);
413 k ^= sKey[R][i];
414
415 out[outOff++] = (byte)((k >>> 24) & 0xFF);
416 out[outOff++] = (byte)((k >>> 16) & 0xFF);
417 out[outOff++] = (byte)((k >>> 8) & 0xFF);
418 out[outOff++] = (byte) (k & 0xFF);
419 }
420 }
421 }