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