1 /*
2 * Copyright (c) 2007, 2012, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation.
8 *
9 * This code is distributed in the hope that it will be useful, but WITHOUT
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
12 * version 2 for more details (a copy is included in the LICENSE file that
13 * accompanied this code).
14 *
15 * You should have received a copy of the GNU General Public License version
16 * 2 along with this work; if not, write to the Free Software Foundation,
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18 *
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 */
23 // Checkstyle: stop
24
25 package org.graalvm.compiler.jtt.hotpath;
26
27 import java.util.Random;
28
29 import org.junit.Test;
30
31 import org.graalvm.compiler.jtt.JTTTest;
32
33 public class HP_idea extends JTTTest {
34
35 public boolean test() {
36 buildTestData();
37 Do();
38 return verify();
39 }
40
41 // Declare class data. Byte buffer plain1 holds the original
42 // data for encryption, crypt1 holds the encrypted data, and
43 // plain2 holds the decrypted data, which should match plain1
44 // byte for byte.
45
46 int array_rows;
47
48 byte[] plain1; // Buffer for plaintext data.
49 byte[] crypt1; // Buffer for encrypted data.
50 byte[] plain2; // Buffer for decrypted data.
51
52 short[] userkey; // Key for encryption/decryption.
53 int[] Z; // Encryption subkey (userkey derived).
54 int[] DK; // Decryption subkey (userkey derived).
55
56 void Do() {
57 cipher_idea(plain1, crypt1, Z); // Encrypt plain1.
58 cipher_idea(crypt1, plain2, DK); // Decrypt.
59 }
60
61 /*
62 * buildTestData
63 *
64 * Builds the data used for the test -- each time the test is run.
65 */
66
67 void buildTestData() {
68 // Create three byte arrays that will be used (and reused) for
69 // encryption/decryption operations.
70
71 plain1 = new byte[array_rows];
72 crypt1 = new byte[array_rows];
73 plain2 = new byte[array_rows];
74
75 Random rndnum = new Random(136506717L); // Create random number generator.
76
77 // Allocate three arrays to hold keys: userkey is the 128-bit key.
78 // Z is the set of 16-bit encryption subkeys derived from userkey,
79 // while DK is the set of 16-bit decryption subkeys also derived
80 // from userkey. NOTE: The 16-bit values are stored here in
81 // 32-bit int arrays so that the values may be used in calculations
82 // as if they are unsigned. Each 64-bit block of plaintext goes
83 // through eight processing rounds involving six of the subkeys
84 // then a final output transform with four of the keys; (8 * 6)
85 // + 4 = 52 subkeys.
86
87 userkey = new short[8]; // User key has 8 16-bit shorts.
88 Z = new int[52]; // Encryption subkey (user key derived).
89 DK = new int[52]; // Decryption subkey (user key derived).
90
91 // Generate user key randomly; eight 16-bit values in an array.
92
93 for (int i = 0; i < 8; i++) {
94 // Again, the random number function returns int. Converting
95 // to a short type preserves the bit pattern in the lower 16
96 // bits of the int and discards the rest.
97
98 userkey[i] = (short) rndnum.nextInt();
99 }
100
101 // Compute encryption and decryption subkeys.
102
103 calcEncryptKey();
104 calcDecryptKey();
105
106 // Fill plain1 with "text."
107 for (int i = 0; i < array_rows; i++) {
108 plain1[i] = (byte) i;
109
110 // Converting to a byte
111 // type preserves the bit pattern in the lower 8 bits of the
112 // int and discards the rest.
113 }
114 }
115
116 /*
117 * calcEncryptKey
118 *
119 * Builds the 52 16-bit encryption subkeys Z[] from the user key and stores in 32-bit int array.
120 * The routing corrects an error in the source code in the Schnier book. Basically, the sense of
121 * the 7- and 9-bit shifts are reversed. It still works reversed, but would encrypted code would
122 * not decrypt with someone else's IDEA code.
123 */
124
125 private void calcEncryptKey() {
126 int j; // Utility variable.
127
128 for (int i = 0; i < 52; i++) {
129 // Zero out the 52-int Z array.
130 Z[i] = 0;
131 }
132
133 for (int i = 0; i < 8; i++) // First 8 subkeys are userkey itself.
134 {
135 Z[i] = userkey[i] & 0xffff; // Convert "unsigned"
136 // short to int.
137 }
138
139 // Each set of 8 subkeys thereafter is derived from left rotating
140 // the whole 128-bit key 25 bits to left (once between each set of
141 // eight keys and then before the last four). Instead of actually
142 // rotating the whole key, this routine just grabs the 16 bits
143 // that are 25 bits to the right of the corresponding subkey
144 // eight positions below the current subkey. That 16-bit extent
145 // straddles two array members, so bits are shifted left in one
146 // member and right (with zero fill) in the other. For the last
147 // two subkeys in any group of eight, those 16 bits start to
148 // wrap around to the first two members of the previous eight.
149
150 for (int i = 8; i < 52; i++) {
151 j = i % 8;
152 if (j < 6) {
153 Z[i] = ((Z[i - 7] >>> 9) | (Z[i - 6] << 7)) // Shift and combine.
154 & 0xFFFF; // Just 16 bits.
155 continue; // Next iteration.
156 }
157
158 if (j == 6) // Wrap to beginning for second chunk.
159 {
160 Z[i] = ((Z[i - 7] >>> 9) | (Z[i - 14] << 7)) & 0xFFFF;
161 continue;
162 }
163
164 // j == 7 so wrap to beginning for both chunks.
165
166 Z[i] = ((Z[i - 15] >>> 9) | (Z[i - 14] << 7)) & 0xFFFF;
167 }
168 }
169
170 /*
171 * calcDecryptKey
172 *
173 * Builds the 52 16-bit encryption subkeys DK[] from the encryption- subkeys Z[]. DK[] is a
174 * 32-bit int array holding 16-bit values as unsigned.
175 */
176
177 private void calcDecryptKey() {
178 int j, k; // Index counters.
179 int t1, t2, t3; // Temps to hold decrypt subkeys.
180
181 t1 = inv(Z[0]); // Multiplicative inverse (mod x10001).
182 t2 = -Z[1] & 0xffff; // Additive inverse, 2nd encrypt subkey.
183 t3 = -Z[2] & 0xffff; // Additive inverse, 3rd encrypt subkey.
184
185 DK[51] = inv(Z[3]); // Multiplicative inverse (mod x10001).
186 DK[50] = t3;
187 DK[49] = t2;
188 DK[48] = t1;
189
190 j = 47; // Indices into temp and encrypt arrays.
191 k = 4;
192 for (int i = 0; i < 7; i++) {
193 t1 = Z[k++];
194 DK[j--] = Z[k++];
195 DK[j--] = t1;
196 t1 = inv(Z[k++]);
197 t2 = -Z[k++] & 0xffff;
198 t3 = -Z[k++] & 0xffff;
199 DK[j--] = inv(Z[k++]);
200 DK[j--] = t2;
201 DK[j--] = t3;
202 DK[j--] = t1;
203 }
204
205 t1 = Z[k++];
206 DK[j--] = Z[k++];
207 DK[j--] = t1;
208 t1 = inv(Z[k++]);
209 t2 = -Z[k++] & 0xffff;
210 t3 = -Z[k++] & 0xffff;
211 DK[j--] = inv(Z[k++]);
212 DK[j--] = t3;
213 DK[j--] = t2;
214 DK[j--] = t1;
215 }
216
217 /*
218 * cipher_idea
219 *
220 * IDEA encryption/decryption algorithm. It processes plaintext in 64-bit blocks, one at a time,
221 * breaking the block into four 16-bit unsigned subblocks. It goes through eight rounds of
222 * processing using 6 new subkeys each time, plus four for last step. The source text is in
223 * array text1, the destination text goes into array text2 The routine represents 16-bit
224 * subblocks and subkeys as type int so that they can be treated more easily as unsigned.
225 * Multiplication modulo 0x10001 interprets a zero sub-block as 0x10000; it must to fit in 16
226 * bits.
227 */
228
229 @SuppressWarnings("static-method")
230 private void cipher_idea(byte[] text1, byte[] text2, int[] key) {
231
232 int i1 = 0; // Index into first text array.
233 int i2 = 0; // Index into second text array.
234 int ik; // Index into key array.
235 int x1, x2, x3, x4, t1, t2; // Four "16-bit" blocks, two temps.
236 int r; // Eight rounds of processing.
237
238 for (int i = 0; i < text1.length; i += 8) {
239
240 ik = 0; // Restart key index.
241 r = 8; // Eight rounds of processing.
242
243 // Load eight plain1 bytes as four 16-bit "unsigned" integers.
244 // Masking with 0xff prevents sign extension with cast to int.
245
246 x1 = text1[i1++] & 0xff; // Build 16-bit x1 from 2 bytes,
247 x1 |= (text1[i1++] & 0xff) << 8; // assuming low-order byte first.
248 x2 = text1[i1++] & 0xff;
249 x2 |= (text1[i1++] & 0xff) << 8;
250 x3 = text1[i1++] & 0xff;
251 x3 |= (text1[i1++] & 0xff) << 8;
252 x4 = text1[i1++] & 0xff;
253 x4 |= (text1[i1++] & 0xff) << 8;
254
255 do {
256 // 1) Multiply (modulo 0x10001), 1st text sub-block
257 // with 1st key sub-block.
258
259 x1 = (int) ((long) x1 * key[ik++] % 0x10001L & 0xffff);
260
261 // 2) Add (modulo 0x10000), 2nd text sub-block
262 // with 2nd key sub-block.
263
264 x2 = x2 + key[ik++] & 0xffff;
265
266 // 3) Add (modulo 0x10000), 3rd text sub-block
267 // with 3rd key sub-block.
268
269 x3 = x3 + key[ik++] & 0xffff;
270
271 // 4) Multiply (modulo 0x10001), 4th text sub-block
272 // with 4th key sub-block.
273
274 x4 = (int) ((long) x4 * key[ik++] % 0x10001L & 0xffff);
275
276 // 5) XOR results from steps 1 and 3.
277
278 t2 = x1 ^ x3;
279
280 // 6) XOR results from steps 2 and 4.
281 // Included in step 8.
282
283 // 7) Multiply (modulo 0x10001), result of step 5
284 // with 5th key sub-block.
285
286 t2 = (int) ((long) t2 * key[ik++] % 0x10001L & 0xffff);
287
288 // 8) Add (modulo 0x10000), results of steps 6 and 7.
289
290 t1 = t2 + (x2 ^ x4) & 0xffff;
291
292 // 9) Multiply (modulo 0x10001), result of step 8
293 // with 6th key sub-block.
294
295 t1 = (int) ((long) t1 * key[ik++] % 0x10001L & 0xffff);
296
297 // 10) Add (modulo 0x10000), results of steps 7 and 9.
298
299 t2 = t1 + t2 & 0xffff;
300
301 // 11) XOR results from steps 1 and 9.
302
303 x1 ^= t1;
304
305 // 14) XOR results from steps 4 and 10. (Out of order).
306
307 x4 ^= t2;
308
309 // 13) XOR results from steps 2 and 10. (Out of order).
310
311 t2 ^= x2;
312
313 // 12) XOR results from steps 3 and 9. (Out of order).
314
315 x2 = x3 ^ t1;
316
317 x3 = t2; // Results of x2 and x3 now swapped.
318
319 } while (--r != 0); // Repeats seven more rounds.
320
321 // Final output transform (4 steps).
322
323 // 1) Multiply (modulo 0x10001), 1st text-block
324 // with 1st key sub-block.
325
326 x1 = (int) ((long) x1 * key[ik++] % 0x10001L & 0xffff);
327
328 // 2) Add (modulo 0x10000), 2nd text sub-block
329 // with 2nd key sub-block. It says x3, but that is to undo swap
330 // of subblocks 2 and 3 in 8th processing round.
331
332 x3 = x3 + key[ik++] & 0xffff;
333
334 // 3) Add (modulo 0x10000), 3rd text sub-block
335 // with 3rd key sub-block. It says x2, but that is to undo swap
336 // of subblocks 2 and 3 in 8th processing round.
337
338 x2 = x2 + key[ik++] & 0xffff;
339
340 // 4) Multiply (modulo 0x10001), 4th text-block
341 // with 4th key sub-block.
342
343 x4 = (int) ((long) x4 * key[ik++] % 0x10001L & 0xffff);
344
345 // Repackage from 16-bit sub-blocks to 8-bit byte array text2.
346
347 text2[i2++] = (byte) x1;
348 text2[i2++] = (byte) (x1 >>> 8);
349 text2[i2++] = (byte) x3; // x3 and x2 are switched
350 text2[i2++] = (byte) (x3 >>> 8); // only in name.
351 text2[i2++] = (byte) x2;
352 text2[i2++] = (byte) (x2 >>> 8);
353 text2[i2++] = (byte) x4;
354 text2[i2++] = (byte) (x4 >>> 8);
355
356 } // End for loop.
357
358 } // End routine.
359
360 /*
361 * mul
362 *
363 * Performs multiplication, modulo (2**16)+1. This code is structured on the assumption that
364 * untaken branches are cheaper than taken branches, and that the compiler doesn't schedule
365 * branches. Java: Must work with 32-bit int and one 64-bit long to keep 16-bit values and their
366 * products "unsigned." The routine assumes that both a and b could fit in 16 bits even though
367 * they come in as 32-bit ints. Lots of "& 0xFFFF" masks here to keep things 16-bit. Also,
368 * because the routine stores mod (2**16)+1 results in a 2**16 space, the result is truncated to
369 * zero whenever the result would zero, be 2**16. And if one of the multiplicands is 0, the
370 * result is not zero, but (2**16) + 1 minus the other multiplicand (sort of an additive inverse
371 * mod 0x10001).
372 *
373 * NOTE: The java conversion of this routine works correctly, but is half the speed of using
374 * Java's modulus division function (%) on the multiplication with a 16-bit masking of the
375 * result--running in the Symantec Caje IDE. So it's not called for now; the test uses Java %
376 * instead.
377 */
378
379 /*
380 * private int mul(int a, int b) throws ArithmeticException { long p; // Large enough to catch
381 * 16-bit multiply // without hitting sign bit. if (a != 0) { if (b != 0) { p = (long) a * b; b
382 * = (int) p & 0xFFFF; // Lower 16 bits. a = (int) p >>> 16; // Upper 16 bits.
383 *
384 * return (b - a + (b < a ? 1 : 0) & 0xFFFF); } else return ((1 - a) & 0xFFFF); // If b = 0,
385 * then same as // 0x10001 - a. } else // If a = 0, then return return((1 - b) & 0xFFFF); //
386 * same as 0x10001 - b. }
387 */
388
389 /*
390 * inv
391 *
392 * Compute multiplicative inverse of x, modulo (2**16)+1 using extended Euclid's GCD (greatest
393 * common divisor) algorithm. It is unrolled twice to avoid swapping the meaning of the
394 * registers. And some subtracts are changed to adds. Java: Though it uses signed 32-bit ints,
395 * the interpretation of the bits within is strictly unsigned 16-bit.
396 */
397
398 public int inv(int x) {
399 int x2 = x;
400 int t0, t1;
401 int q, y;
402
403 if (x2 <= 1) {
404 return (x2); // 0 and 1 are self-inverse.
405 }
406
407 t1 = 0x10001 / x2; // (2**16+1)/x; x is >= 2, so fits 16 bits.
408 y = 0x10001 % x2;
409 if (y == 1) {
410 return ((1 - t1) & 0xFFFF);
411 }
412
413 t0 = 1;
414 do {
415 q = x2 / y;
416 x2 = x2 % y;
417 t0 += q * t1;
418 if (x2 == 1) {
419 return (t0);
420 }
421 q = y / x2;
422 y = y % x2;
423 t1 += q * t0;
424 } while (y != 1);
425
426 return ((1 - t1) & 0xFFFF);
427 }
428
429 boolean verify() {
430 boolean error;
431 for (int i = 0; i < array_rows; i++) {
432 error = (plain1[i] != plain2[i]);
433 if (error) {
434 return false;
435 }
436 }
437 return true;
438 }
439
440 /*
441 * freeTestData
442 *
443 * Nulls arrays and forces garbage collection to free up memory.
444 */
445
446 void freeTestData() {
447 plain1 = null;
448 crypt1 = null;
449 plain2 = null;
450 userkey = null;
451 Z = null;
452 DK = null;
453 }
454
455 public HP_idea() {
456 array_rows = 3000;
457 }
458
459 @Test
460 public void run0() throws Throwable {
461 runTest("test");
462 }
463
464 @Test
465 public void runInv() {
466 runTest("inv", 724);
467 }
468 }