// // Decompiled by Procyon v0.6.0 // package org.bouncycastle.pqc.crypto.falcon; import org.bouncycastle.util.Pack; import org.bouncycastle.crypto.digests.SHAKEDigest; class FalconKeyGen { private static final short[] REV10; private static final long[] gauss_1024_12289; private static final int[] MAX_BL_SMALL; private static final int[] MAX_BL_LARGE; private static final int[] bitlength_avg; private static final int[] bitlength_std; private static final int DEPTH_INT_FG = 4; private static int mkn(final int n) { return 1 << n; } private static int modp_set(final int n, final int n2) { return n + (n2 & -(n >>> 31)); } private static int modp_norm(final int n, final int n2) { return n - (n2 & (n - (n2 + 1 >>> 1) >>> 31) - 1); } private static int modp_ninv31(final int n) { final int n2 = 2 - n; final int n3 = n2 * (2 - n * n2); final int n4 = n3 * (2 - n * n3); final int n5 = n4 * (2 - n * n4); return Integer.MAX_VALUE & -(n5 * (2 - n * n5)); } private static int modp_R(final int n) { return Integer.MIN_VALUE - n; } private static int modp_add(final int n, final int n2, final int n3) { final int n4 = n + n2 - n3; return n4 + (n3 & -(n4 >>> 31)); } private static int modp_sub(final int n, final int n2, final int n3) { final int n4 = n - n2; return n4 + (n3 & -(n4 >>> 31)); } private static int modp_montymul(final int n, final int n2, final int n3, final int n4) { final long n5 = toUnsignedLong(n) * toUnsignedLong(n2); final int n6 = (int)(n5 + (n5 * n4 & 0x7FFFFFFFL) * n3 >>> 31) - n3; return n6 + (n3 & -(n6 >>> 31)); } private static int modp_R2(final int n, final int n2) { final int modp_R = modp_R(n); final int modp_add = modp_add(modp_R, modp_R, n); final int modp_montymul = modp_montymul(modp_add, modp_add, n, n2); final int modp_montymul2 = modp_montymul(modp_montymul, modp_montymul, n, n2); final int modp_montymul3 = modp_montymul(modp_montymul2, modp_montymul2, n, n2); final int modp_montymul4 = modp_montymul(modp_montymul3, modp_montymul3, n, n2); final int modp_montymul5 = modp_montymul(modp_montymul4, modp_montymul4, n, n2); return modp_montymul5 + (n & -(modp_montymul5 & 0x1)) >>> 1; } private static int modp_Rx(int n, final int n2, final int n3, final int n4) { --n; int modp_montymul = n4; int n5 = modp_R(n2); for (int n6 = 0; 1 << n6 <= n; ++n6) { if ((n & 1 << n6) != 0x0) { n5 = modp_montymul(n5, modp_montymul, n2, n3); } modp_montymul = modp_montymul(modp_montymul, modp_montymul, n2, n3); } return n5; } private static int modp_div(final int n, final int n2, final int n3, final int n4, final int n5) { final int n6 = n3 - 2; int n7 = n5; for (int i = 30; i >= 0; --i) { final int modp_montymul = modp_montymul(n7, n7, n3, n4); n7 = (modp_montymul ^ ((modp_montymul ^ modp_montymul(modp_montymul, n2, n3, n4)) & -(n6 >>> i & 0x1))); } return modp_montymul(n, modp_montymul(n7, 1, n3, n4), n3, n4); } private static void modp_mkgm2(final int[] array, final int n, final int[] array2, final int n2, final int n3, int n4, final int n5, final int n6) { final int mkn = mkn(n3); final int modp_R2 = modp_R2(n5, n6); n4 = modp_montymul(n4, modp_R2, n5, n6); for (int i = n3; i < 10; ++i) { n4 = modp_montymul(n4, n4, n5, n6); } final int modp_div = modp_div(modp_R2, n4, n5, n6, modp_R(n5)); final int n7 = 10 - n3; int n8; int modp_montymul = n8 = modp_R(n5); for (int j = 0; j < mkn; ++j) { final short n9 = FalconKeyGen.REV10[j << n7]; array[n + n9] = n8; array2[n2 + n9] = modp_montymul; n8 = modp_montymul(n8, n4, n5, n6); modp_montymul = modp_montymul(modp_montymul, modp_div, n5, n6); } } private static void modp_NTT2_ext(final int[] array, final int n, final int n2, final int[] array2, final int n3, final int n4, final int n5, final int n6) { if (n4 == 0) { return; } int mkn; for (int n7 = mkn = mkn(n4), i = 1; i < n7; i <<= 1) { final int n8 = mkn >> 1; for (int j = 0, n9 = 0; j < i; ++j, n9 += mkn) { final int n10 = array2[n3 + i + j]; for (int n11 = n + n9 * n2, n12 = n11 + n8 * n2, k = 0; k < n8; ++k, n11 += n2, n12 += n2) { final int n13 = array[n11]; final int modp_montymul = modp_montymul(array[n12], n10, n5, n6); array[n11] = modp_add(n13, modp_montymul, n5); array[n12] = modp_sub(n13, modp_montymul, n5); } } mkn = n8; } } private static void modp_iNTT2_ext(final int[] array, final int n, final int n2, final int[] array2, final int n3, final int n4, final int n5, final int n6) { if (n4 == 0) { return; } final int mkn = mkn(n4); int n7 = 1; for (int i = mkn; i > 1; i >>= 1) { final int n8 = i >> 1; final int n9 = n7 << 1; for (int j = 0, n10 = 0; j < n8; ++j, n10 += n9) { final int n11 = array2[n3 + n8 + j]; for (int n12 = n + n10 * n2, n13 = n12 + n7 * n2, k = 0; k < n7; ++k, n12 += n2, n13 += n2) { final int n14 = array[n12]; final int n15 = array[n13]; array[n12] = modp_add(n14, n15, n5); array[n13] = modp_montymul(modp_sub(n14, n15, n5), n11, n5, n6); } } n7 = n9; } final int n16 = 1 << 31 - n4; for (int l = 0, n17 = n; l < mkn; ++l, n17 += n2) { array[n17] = modp_montymul(array[n17], n16, n5, n6); } } private static void modp_NTT2(final int[] array, final int n, final int[] array2, final int n2, final int n3, final int n4, final int n5) { modp_NTT2_ext(array, n, 1, array2, n2, n3, n4, n5); } private static void modp_iNTT2(final int[] array, final int n, final int[] array2, final int n2, final int n3, final int n4, final int n5) { modp_iNTT2_ext(array, n, 1, array2, n2, n3, n4, n5); } private static void modp_poly_rec_res(final int[] array, final int n, final int n2, final int n3, final int n4, final int n5) { for (int n6 = 1 << n2 - 1, i = 0; i < n6; ++i) { array[n + i] = modp_montymul(modp_montymul(array[n + (i << 1)], array[n + (i << 1) + 1], n3, n4), n5, n3, n4); } } private static void zint_sub(final int[] array, final int n, final int[] array2, final int n2, final int n3, final int n4) { int n5 = 0; final int n6 = -n4; for (int i = 0; i < n3; ++i) { final int n7 = n + i; final int n8 = array[n7]; final int n9 = n8 - array2[n2 + i] - n5; n5 = n9 >>> 31; array[n7] = (n8 ^ (((n9 & Integer.MAX_VALUE) ^ n8) & n6)); } } private static int zint_mul_small(final int[] array, final int n, final int n2, final int n3) { int n4 = 0; for (int i = 0; i < n2; ++i) { final long n5 = toUnsignedLong(array[n + i]) * toUnsignedLong(n3) + n4; array[n + i] = ((int)n5 & Integer.MAX_VALUE); n4 = (int)(n5 >> 31); } return n4; } private static int zint_mod_small_unsigned(final int[] array, final int n, final int n2, final int n3, final int n4, final int n5) { int modp_add = 0; int n6 = n2; while (n6-- > 0) { final int modp_montymul = modp_montymul(modp_add, n5, n3, n4); final int n7 = array[n + n6] - n3; modp_add = modp_add(modp_montymul, n7 + (n3 & -(n7 >>> 31)), n3); } return modp_add; } private static int zint_mod_small_signed(final int[] array, final int n, final int n2, final int n3, final int n4, final int n5, final int n6) { if (n2 == 0) { return 0; } return modp_sub(zint_mod_small_unsigned(array, n, n2, n3, n4, n5), n6 & -(array[n + n2 - 1] >>> 30), n3); } private static void zint_add_mul_small(final int[] array, final int n, final int[] array2, final int n2, final int n3, final int n4) { int n5 = 0; for (int i = 0; i < n3; ++i) { final long n6 = toUnsignedLong(array2[n2 + i]) * toUnsignedLong(n4) + toUnsignedLong(array[n + i]) + toUnsignedLong(n5); array[n + i] = ((int)n6 & Integer.MAX_VALUE); n5 = (int)(n6 >>> 31); } array[n + n3] = n5; } private static void zint_norm_zero(final int[] array, final int n, final int[] array2, final int n2, final int n3) { int n4 = 0; int n5 = 0; int n6 = n3; while (n6-- > 0) { final int n7 = array[n + n6]; final int n8 = array2[n2 + n6] >>> 1 | n5 << 30; n5 = (array2[n2 + n6] & 0x1); final int n9 = n8 - n7; n4 |= ((-n9 >>> 31 | -(n9 >>> 31)) & (n4 & 0x1) - 1); } zint_sub(array, n, array2, n2, n3, n4 >>> 31); } private static void zint_rebuild_CRT(final int[] array, final int n, final int n2, final int n3, final int n4, final int n5, final int[] array2, final int n6) { array2[n6] = FalconSmallPrimeList.PRIMES[0].p; for (int i = 1; i < n2; ++i) { final int p8 = FalconSmallPrimeList.PRIMES[i].p; final int s = FalconSmallPrimeList.PRIMES[i].s; final int modp_ninv31 = modp_ninv31(p8); final int modp_R2 = modp_R2(p8, modp_ninv31); for (int j = 0, n7 = n; j < n4; ++j, n7 += n3) { zint_add_mul_small(array, n7, array2, n6, i, modp_montymul(s, modp_sub(array[n7 + i], zint_mod_small_unsigned(array, n7, i, p8, modp_ninv31, modp_R2), p8), p8, modp_ninv31)); } array2[n6 + i] = zint_mul_small(array2, n6, i, p8); } if (n5 != 0) { for (int k = 0, n8 = n; k < n4; ++k, n8 += n3) { zint_norm_zero(array, n8, array2, n6, n2); } } } private static void zint_negate(final int[] array, final int n, final int n2, final int n3) { int n4 = n3; final int n5 = -n3 >>> 1; for (int i = 0; i < n2; ++i) { final int n6 = (array[n + i] ^ n5) + n4; array[n + i] = (n6 & Integer.MAX_VALUE); n4 = n6 >>> 31; } } private static int zint_co_reduce(final int[] array, final int n, final int[] array2, final int n2, final int n3, final long n4, final long n5, final long n6, final long n7) { long n8 = 0L; long n9 = 0L; for (int i = 0; i < n3; ++i) { final int n10 = array[n + i]; final int n11 = array2[n2 + i]; final long n12 = n10 * n4 + n11 * n5 + n8; final long n13 = n10 * n6 + n11 * n7 + n9; if (i > 0) { array[n + i - 1] = ((int)n12 & Integer.MAX_VALUE); array2[n2 + i - 1] = ((int)n13 & Integer.MAX_VALUE); } n8 = n12 >> 31; n9 = n13 >> 31; } array[n + n3 - 1] = (int)n8; array2[n2 + n3 - 1] = (int)n9; final int n14 = (int)(n8 >>> 63); final int n15 = (int)(n9 >>> 63); zint_negate(array, n, n3, n14); zint_negate(array2, n2, n3, n15); return n14 | n15 << 1; } private static void zint_finish_mod(final int[] array, final int n, final int n2, final int[] array2, final int n3, final int n4) { int n5 = 0; for (int i = 0; i < n2; ++i) { n5 = array[n + i] - array2[n3 + i] - n5 >>> 31; } final int n6 = -n4 >>> 1; final int n7 = -(n4 | 1 - n5); int n8 = n4; for (int j = 0; j < n2; ++j) { final int n9 = array[n + j] - ((array2[n3 + j] ^ n6) & n7) - n8; array[n + j] = (n9 & Integer.MAX_VALUE); n8 = n9 >>> 31; } } private static void zint_co_reduce_mod(final int[] array, final int n, final int[] array2, final int n2, final int[] array3, final int n3, final int n4, final int n5, final long n6, final long n7, final long n8, final long n9) { long n10 = 0L; long n11 = 0L; final int n12 = (array[n] * (int)n6 + array2[n2] * (int)n7) * n5 & Integer.MAX_VALUE; final int n13 = (array[n] * (int)n8 + array2[n2] * (int)n9) * n5 & Integer.MAX_VALUE; for (int i = 0; i < n4; ++i) { final int n14 = array[n + i]; final int n15 = array2[n2 + i]; final long n16 = n14 * n6 + n15 * n7 + array3[n3 + i] * toUnsignedLong(n12) + n10; final long n17 = n14 * n8 + n15 * n9 + array3[n3 + i] * toUnsignedLong(n13) + n11; if (i > 0) { array[n + i - 1] = ((int)n16 & Integer.MAX_VALUE); array2[n2 + i - 1] = ((int)n17 & Integer.MAX_VALUE); } n10 = n16 >> 31; n11 = n17 >> 31; } array[n + n4 - 1] = (int)n10; array2[n2 + n4 - 1] = (int)n11; zint_finish_mod(array, n, n4, array3, n3, (int)(n10 >>> 63)); zint_finish_mod(array2, n2, n4, array3, n3, (int)(n11 >>> 63)); } private static int zint_bezout(final int[] array, final int n, final int[] array2, final int n2, final int[] array3, final int n3, final int[] array4, final int n4, final int n5, final int[] array5, final int n6) { if (n5 == 0) { return 0; } final int n7 = n6 + n5; final int n8 = n7 + n5; final int n9 = n8 + n5; final int modp_ninv31 = modp_ninv31(array3[n3]); final int modp_ninv32 = modp_ninv31(array4[n4]); System.arraycopy(array3, n3, array5, n8, n5); System.arraycopy(array4, n4, array5, n9, n5); array[n] = 1; array2[n2] = 0; for (int i = 1; i < n5; ++i) { array2[n2 + i] = (array[n + i] = 0); } System.arraycopy(array4, n4, array5, n6, n5); System.arraycopy(array3, n3, array5, n7, n5); final int n10 = n7; --array5[n10]; for (int j = 62 * n5 + 30; j >= 30; j -= 30) { int n11 = -1; int n12 = -1; int n13 = 0; int n14 = 0; int n15 = 0; int n16 = 0; int n17 = n5; while (n17-- > 0) { final int n18 = array5[n8 + n17]; final int n19 = array5[n9 + n17]; n13 ^= ((n13 ^ n18) & n11); n14 ^= ((n14 ^ n18) & n12); n15 ^= ((n15 ^ n19) & n11); n16 ^= ((n16 ^ n19) & n12); n12 = n11; n11 &= ((n18 | n19) + Integer.MAX_VALUE >>> 31) - 1; } final int n20 = n14 | (n13 & n12); final int n21 = n13 & ~n12; final int n22 = n16 | (n15 & n12); final int n23 = n15 & ~n12; long n24 = (toUnsignedLong(n21) << 31) + toUnsignedLong(n20); long n25 = (toUnsignedLong(n23) << 31) + toUnsignedLong(n22); int n26 = array5[n8]; int n27 = array5[n9]; long n28 = 1L; long n29 = 0L; long n30 = 0L; long n31 = 1L; for (int k = 0; k < 31; ++k) { final long n32 = n25 - n24; final int n33 = (int)((n32 ^ ((n24 ^ n25) & (n24 ^ n32))) >>> 63); final int n34 = n26 >> k & 0x1; final int n35 = n27 >> k & 0x1; final int n36 = n34 & n35 & n33; final int n37 = n34 & n35 & ~n33; final int n38 = n36 | (n34 ^ 0x1); final int n39 = n26 - (n27 & -n36); final long n40 = n24 - (n25 & -toUnsignedLong(n36)); final long n41 = n28 - (n30 & -n36); final long n42 = n29 - (n31 & -n36); final int n43 = n27 - (n39 & -n37); final long n44 = n25 - (n40 & -toUnsignedLong(n37)); final long n45 = n30 - (n41 & -n37); final long n46 = n31 - (n42 & -n37); n26 = n39 + (n39 & n38 - 1); n28 = n41 + (n41 & n38 - 1L); n29 = n42 + (n42 & n38 - 1L); n24 = (n40 ^ ((n40 ^ n40 >> 1) & -toUnsignedLong(n38))); n27 = n43 + (n43 & -n38); n30 = n45 + (n45 & -n38); n31 = n46 + (n46 & -n38); n25 = (n44 ^ ((n44 ^ n44 >> 1) & toUnsignedLong(n38) - 1L)); } final int zint_co_reduce = zint_co_reduce(array5, n8, array5, n9, n5, n28, n29, n30, n31); final long n47 = n28 - (n28 + n28 & -(zint_co_reduce & 0x1)); final long n48 = n29 - (n29 + n29 & -(zint_co_reduce & 0x1)); final long n49 = n30 - (n30 + n30 & -(zint_co_reduce >>> 1)); final long n50 = n31 - (n31 + n31 & -(zint_co_reduce >>> 1)); zint_co_reduce_mod(array, n, array5, n6, array4, n4, n5, modp_ninv32, n47, n48, n49, n50); zint_co_reduce_mod(array2, n2, array5, n7, array3, n3, n5, modp_ninv31, n47, n48, n49, n50); } int n51 = array5[n8] ^ 0x1; for (int l = 1; l < n5; ++l) { n51 |= array5[n8 + l]; } return 1 - ((n51 | -n51) >>> 31) & array3[n3] & array4[n4]; } private static void zint_add_scaled_mul_small(final int[] array, final int n, final int n2, final int[] array2, final int n3, final int n4, final int n5, final int n6, final int n7) { if (n4 == 0) { return; } final int n8 = -(array2[n3 + n4 - 1] >>> 30) >>> 1; int n9 = 0; int n10 = 0; for (int i = n6; i < n2; ++i) { final int n11 = i - n6; final int n12 = (n11 < n4) ? array2[n3 + n11] : n8; final int n13 = (n12 << n7 & Integer.MAX_VALUE) | n9; n9 = n12 >>> 31 - n7; final long n14 = toUnsignedLong(n13) * n5 + toUnsignedLong(array[n + i]) + n10; array[n + i] = ((int)n14 & Integer.MAX_VALUE); n10 = (int)(n14 >>> 31); } } private static void zint_sub_scaled(final int[] array, final int n, final int n2, final int[] array2, final int n3, final int n4, final int n5, final int n6) { if (n4 == 0) { return; } final int n7 = -(array2[n3 + n4 - 1] >>> 30) >>> 1; int n8 = 0; int n9 = 0; for (int i = n5; i < n2; ++i) { final int n10 = i - n5; final int n11 = (n10 < n4) ? array2[n3 + n10] : n7; final int n12 = (n11 << n6 & Integer.MAX_VALUE) | n8; n8 = n11 >>> 31 - n6; final int n13 = array[n + i] - n12 - n9; array[n + i] = (n13 & Integer.MAX_VALUE); n9 = n13 >>> 31; } } private static int zint_one_to_plain(final int[] array, final int n) { final int n2 = array[n]; return n2 | (n2 & 0x40000000) << 1; } private static void poly_big_to_fp(final double[] array, final int[] array2, int n, final int n2, final int n3, final int n4) { final int mkn = mkn(n4); if (n2 == 0) { for (int i = 0; i < mkn; ++i) { array[i] = 0.0; } return; } for (int j = 0; j < mkn; ++j, n += n3) { final int n5 = -(array2[n + n2 - 1] >>> 30); final int n6 = n5 >>> 1; int n7 = n5 & 0x1; double n8 = 0.0; double n9 = 1.0; for (int k = 0; k < n2; ++k, n9 *= 2.147483648E9) { final int n10 = (array2[n + k] ^ n6) + n7; n7 = n10 >>> 31; final int n11 = n10 & Integer.MAX_VALUE; n8 += (n11 - (n11 << 1 & n5)) * n9; } array[j] = n8; } } private static int poly_big_to_small(final byte[] array, final int n, final int[] array2, final int n2, final int n3, final int n4) { for (int mkn = mkn(n4), i = 0; i < mkn; ++i) { final int zint_one_to_plain = zint_one_to_plain(array2, n2 + i); if (zint_one_to_plain < -n3 || zint_one_to_plain > n3) { return 0; } array[n + i] = (byte)zint_one_to_plain; } return 1; } private static void poly_sub_scaled(final int[] array, final int n, final int n2, final int n3, final int[] array2, final int n4, final int n5, final int n6, final int[] array3, final int n7, final int n8, final int n9) { for (int mkn = mkn(n9), i = 0; i < mkn; ++i) { int n10 = -array3[i]; int n11 = n + i * n3; int n12 = n4; for (int j = 0; j < mkn; ++j) { zint_add_scaled_mul_small(array, n11, n2, array2, n12, n5, n10, n7, n8); if (i + j == mkn - 1) { n11 = n; n10 = -n10; } else { n11 += n3; } n12 += n6; } } } private static void poly_sub_scaled_ntt(final int[] array, final int n, final int n2, final int n3, final int[] array2, final int n4, final int n5, final int n6, final int[] array3, final int n7, final int n8, final int n9, final int[] array4, final int n10) { final int mkn = mkn(n9); final int n11 = n5 + 1; final int n12 = n10 + mkn(n9); final int n13 = n12 + mkn(n9); final int n14 = n13 + mkn * n11; for (int i = 0; i < n11; ++i) { final int p14 = FalconSmallPrimeList.PRIMES[i].p; final int modp_ninv31 = modp_ninv31(p14); final int modp_R2 = modp_R2(p14, modp_ninv31); final int modp_Rx = modp_Rx(n5, p14, modp_ninv31, modp_R2); modp_mkgm2(array4, n10, array4, n12, n9, FalconSmallPrimeList.PRIMES[i].g, p14, modp_ninv31); for (int j = 0; j < mkn; ++j) { array4[n14 + j] = modp_set(array3[j], p14); } modp_NTT2(array4, n14, array4, n10, n9, p14, modp_ninv31); for (int k = 0, n15 = n4, n16 = n13 + i; k < mkn; ++k, n15 += n6, n16 += n11) { array4[n16] = zint_mod_small_signed(array2, n15, n5, p14, modp_ninv31, modp_R2, modp_Rx); } modp_NTT2_ext(array4, n13 + i, n11, array4, n10, n9, p14, modp_ninv31); for (int l = 0, n17 = n13 + i; l < mkn; ++l, n17 += n11) { array4[n17] = modp_montymul(modp_montymul(array4[n14 + l], array4[n17], p14, modp_ninv31), modp_R2, p14, modp_ninv31); } modp_iNTT2_ext(array4, n13 + i, n11, array4, n12, n9, p14, modp_ninv31); } zint_rebuild_CRT(array4, n13, n11, n11, mkn, 1, array4, n14); for (int n18 = 0, n19 = n, n20 = n13; n18 < mkn; ++n18, n19 += n3, n20 += n11) { zint_sub_scaled(array, n19, n2, array4, n20, n11, n7, n8); } } private static long get_rng_u64(final SHAKEDigest shakeDigest) { final byte[] array = new byte[8]; shakeDigest.doOutput(array, 0, array.length); return Pack.littleEndianToLong(array, 0); } private static int mkgauss(final SHAKEDigest shakeDigest, final int n) { final int n2 = 1 << 10 - n; int n3 = 0; for (int i = 0; i < n2; ++i) { final long get_rng_u64 = get_rng_u64(shakeDigest); final int n4 = (int)(get_rng_u64 >>> 63); int n5 = (int)((get_rng_u64 & Long.MAX_VALUE) - FalconKeyGen.gauss_1024_12289[0] >>> 63); int n6 = 0; final long n7 = get_rng_u64(shakeDigest) & Long.MAX_VALUE; for (int j = 1; j < FalconKeyGen.gauss_1024_12289.length; ++j) { final int n8 = (int)(n7 - FalconKeyGen.gauss_1024_12289[j] >>> 63) ^ 0x1; n6 |= (j & -(n8 & (n5 ^ 0x1))); n5 |= n8; } n3 += (n6 ^ -n4) + n4; } return n3; } private static int poly_small_sqnorm(final byte[] array, final int n) { final int mkn = mkn(n); int n2 = 0; int n3 = 0; for (final byte b : array) { n2 += b * b; n3 |= n2; } return n2 | -(n3 >>> 31); } private static void poly_small_to_fp(final double[] array, final int n, final byte[] array2, final int n2) { for (int mkn = mkn(n2), i = 0; i < mkn; ++i) { array[n + i] = array2[i]; } } private static void make_fg_step(final int[] array, final int n, final int n2, final int n3, final int n4, final int n5) { final int n6 = 1 << n2; final int n7 = n6 >> 1; final int n8 = FalconKeyGen.MAX_BL_SMALL[n3]; final int n9 = FalconKeyGen.MAX_BL_SMALL[n3 + 1]; final int n10 = n + n7 * n9; final int n11 = n10 + n7 * n9; final int n12 = n11 + n6 * n8; final int n13 = n12 + n6 * n8; final int n14 = n13 + n6; final int n15 = n14 + n6; System.arraycopy(array, n, array, n11, 2 * n6 * n8); for (int i = 0; i < n8; ++i) { final int p6 = FalconSmallPrimeList.PRIMES[i].p; final int modp_ninv31 = modp_ninv31(p6); final int modp_R2 = modp_R2(p6, modp_ninv31); modp_mkgm2(array, n13, array, n14, n2, FalconSmallPrimeList.PRIMES[i].g, p6, modp_ninv31); for (int j = 0, n16 = n11 + i; j < n6; ++j, n16 += n8) { array[n15 + j] = array[n16]; } if (n4 == 0) { modp_NTT2(array, n15, array, n13, n2, p6, modp_ninv31); } for (int k = 0, n17 = n + i; k < n7; ++k, n17 += n9) { array[n17] = modp_montymul(modp_montymul(array[n15 + (k << 1)], array[n15 + (k << 1) + 1], p6, modp_ninv31), modp_R2, p6, modp_ninv31); } if (n4 != 0) { modp_iNTT2_ext(array, n11 + i, n8, array, n14, n2, p6, modp_ninv31); } for (int l = 0, n18 = n12 + i; l < n6; ++l, n18 += n8) { array[n15 + l] = array[n18]; } if (n4 == 0) { modp_NTT2(array, n15, array, n13, n2, p6, modp_ninv31); } for (int n19 = 0, n20 = n10 + i; n19 < n7; ++n19, n20 += n9) { array[n20] = modp_montymul(modp_montymul(array[n15 + (n19 << 1)], array[n15 + (n19 << 1) + 1], p6, modp_ninv31), modp_R2, p6, modp_ninv31); } if (n4 != 0) { modp_iNTT2_ext(array, n12 + i, n8, array, n14, n2, p6, modp_ninv31); } if (n5 == 0) { modp_iNTT2_ext(array, n + i, n9, array, n14, n2 - 1, p6, modp_ninv31); modp_iNTT2_ext(array, n10 + i, n9, array, n14, n2 - 1, p6, modp_ninv31); } } zint_rebuild_CRT(array, n11, n8, n8, n6, 1, array, n13); zint_rebuild_CRT(array, n12, n8, n8, n6, 1, array, n13); for (int n21 = n8; n21 < n9; ++n21) { final int p7 = FalconSmallPrimeList.PRIMES[n21].p; final int modp_ninv32 = modp_ninv31(p7); final int modp_R3 = modp_R2(p7, modp_ninv32); final int modp_Rx = modp_Rx(n8, p7, modp_ninv32, modp_R3); modp_mkgm2(array, n13, array, n14, n2, FalconSmallPrimeList.PRIMES[n21].g, p7, modp_ninv32); for (int n22 = 0, n23 = n11; n22 < n6; ++n22, n23 += n8) { array[n15 + n22] = zint_mod_small_signed(array, n23, n8, p7, modp_ninv32, modp_R3, modp_Rx); } modp_NTT2(array, n15, array, n13, n2, p7, modp_ninv32); for (int n24 = 0, n25 = n + n21; n24 < n7; ++n24, n25 += n9) { array[n25] = modp_montymul(modp_montymul(array[n15 + (n24 << 1)], array[n15 + (n24 << 1) + 1], p7, modp_ninv32), modp_R3, p7, modp_ninv32); } for (int n26 = 0, n27 = n12; n26 < n6; ++n26, n27 += n8) { array[n15 + n26] = zint_mod_small_signed(array, n27, n8, p7, modp_ninv32, modp_R3, modp_Rx); } modp_NTT2(array, n15, array, n13, n2, p7, modp_ninv32); for (int n28 = 0, n29 = n10 + n21; n28 < n7; ++n28, n29 += n9) { array[n29] = modp_montymul(modp_montymul(array[n15 + (n28 << 1)], array[n15 + (n28 << 1) + 1], p7, modp_ninv32), modp_R3, p7, modp_ninv32); } if (n5 == 0) { modp_iNTT2_ext(array, n + n21, n9, array, n14, n2 - 1, p7, modp_ninv32); modp_iNTT2_ext(array, n10 + n21, n9, array, n14, n2 - 1, p7, modp_ninv32); } } } private static void make_fg(final int[] array, final int n, final byte[] array2, final byte[] array3, final int n2, final int n3, final int n4) { final int mkn = mkn(n2); final int n5 = n + mkn; final int p7 = FalconSmallPrimeList.PRIMES[0].p; for (int i = 0; i < mkn; ++i) { array[n + i] = modp_set(array2[i], p7); array[n5 + i] = modp_set(array3[i], p7); } if (n3 == 0 && n4 != 0) { final int p8 = FalconSmallPrimeList.PRIMES[0].p; final int modp_ninv31 = modp_ninv31(p8); final int n6 = n5 + mkn; modp_mkgm2(array, n6, array, n6 + mkn, n2, FalconSmallPrimeList.PRIMES[0].g, p8, modp_ninv31); modp_NTT2(array, n, array, n6, n2, p8, modp_ninv31); modp_NTT2(array, n5, array, n6, n2, p8, modp_ninv31); return; } for (int j = 0; j < n3; ++j) { make_fg_step(array, n, n2 - j, j, (j != 0) ? 1 : 0, (j + 1 < n3 || n4 != 0) ? 1 : 0); } } private static int solve_NTRU_deepest(final int n, final byte[] array, final byte[] array2, final int[] array3) { final int n2 = FalconKeyGen.MAX_BL_SMALL[n]; final int n3 = 0; final int n4 = n3 + n2; final int n5 = n4 + n2; final int n6 = n5 + n2; final int n7 = n6 + n2; make_fg(array3, n5, array, array2, n, n, 0); zint_rebuild_CRT(array3, n5, n2, n2, 2, 0, array3, n7); if (zint_bezout(array3, n4, array3, n3, array3, n5, array3, n6, n2, array3, n7) == 0) { return 0; } final int n8 = 12289; if (zint_mul_small(array3, n3, n2, n8) != 0 || zint_mul_small(array3, n4, n2, n8) != 0) { return 0; } return 1; } private static int solve_NTRU_intermediate(final int n, final byte[] array, final byte[] array2, final int n2, final int[] array3) { final int n3 = n - n2; final int n4 = 1 << n3; final int n5 = n4 >> 1; final int a = FalconKeyGen.MAX_BL_SMALL[n2]; final int n6 = FalconKeyGen.MAX_BL_SMALL[n2 + 1]; final int n7 = FalconKeyGen.MAX_BL_LARGE[n2]; final int n8 = 0; final int n9 = n8 + n6 * n5 + n6 * n5; make_fg(array3, n9, array, array2, n, n2, 1); int n10 = 0; int n11 = n10 + n4 * n7; final int n12 = n11 + n4 * n7; final int n13 = n4 * a; System.arraycopy(array3, n9, array3, n12, n13 + n13); final int n14 = n12; final int n15 = n14 + n13; final int n16 = n15 + n13; final int n17 = n5 * n6; System.arraycopy(array3, n8, array3, n16, n17 + n17); final int n18 = n16; final int n19 = n18 + n17; for (int i = 0; i < n7; ++i) { final int p5 = FalconSmallPrimeList.PRIMES[i].p; final int modp_ninv31 = modp_ninv31(p5); final int modp_R2 = modp_R2(p5, modp_ninv31); final int modp_Rx = modp_Rx(n6, p5, modp_ninv31, modp_R2); for (int j = 0, n20 = n18, n21 = n19, n22 = n10 + i, n23 = n11 + i; j < n5; ++j, n20 += n6, n21 += n6, n22 += n7, n23 += n7) { array3[n22] = zint_mod_small_signed(array3, n20, n6, p5, modp_ninv31, modp_R2, modp_Rx); array3[n23] = zint_mod_small_signed(array3, n21, n6, p5, modp_ninv31, modp_R2, modp_Rx); } } for (int k = 0; k < n7; ++k) { final int p6 = FalconSmallPrimeList.PRIMES[k].p; final int modp_ninv32 = modp_ninv31(p6); final int modp_R3 = modp_R2(p6, modp_ninv32); if (k == a) { zint_rebuild_CRT(array3, n14, a, a, n4, 1, array3, n16); zint_rebuild_CRT(array3, n15, a, a, n4, 1, array3, n16); } final int n24 = n16; final int n25 = n24 + n4; final int n26 = n25 + n4; final int n27 = n26 + n4; modp_mkgm2(array3, n24, array3, n25, n3, FalconSmallPrimeList.PRIMES[k].g, p6, modp_ninv32); if (k < a) { for (int l = 0, n28 = n14 + k, n29 = n15 + k; l < n4; ++l, n28 += a, n29 += a) { array3[n26 + l] = array3[n28]; array3[n27 + l] = array3[n29]; } modp_iNTT2_ext(array3, n14 + k, a, array3, n25, n3, p6, modp_ninv32); modp_iNTT2_ext(array3, n15 + k, a, array3, n25, n3, p6, modp_ninv32); } else { final int modp_Rx2 = modp_Rx(a, p6, modp_ninv32, modp_R3); for (int n30 = 0, n31 = n14, n32 = n15; n30 < n4; ++n30, n31 += a, n32 += a) { array3[n26 + n30] = zint_mod_small_signed(array3, n31, a, p6, modp_ninv32, modp_R3, modp_Rx2); array3[n27 + n30] = zint_mod_small_signed(array3, n32, a, p6, modp_ninv32, modp_R3, modp_Rx2); } modp_NTT2(array3, n26, array3, n24, n3, p6, modp_ninv32); modp_NTT2(array3, n27, array3, n24, n3, p6, modp_ninv32); } final int n33 = n27 + n4; final int n34 = n33 + n5; for (int n35 = 0, n36 = n10 + k, n37 = n11 + k; n35 < n5; ++n35, n36 += n7, n37 += n7) { array3[n33 + n35] = array3[n36]; array3[n34 + n35] = array3[n37]; } modp_NTT2(array3, n33, array3, n24, n3 - 1, p6, modp_ninv32); modp_NTT2(array3, n34, array3, n24, n3 - 1, p6, modp_ninv32); for (int n38 = 0, n39 = n10 + k, n40 = n11 + k; n38 < n5; ++n38, n39 += n7 << 1, n40 += n7 << 1) { final int n41 = array3[n26 + (n38 << 1)]; final int n42 = array3[n26 + (n38 << 1) + 1]; final int n43 = array3[n27 + (n38 << 1)]; final int n44 = array3[n27 + (n38 << 1) + 1]; final int modp_montymul = modp_montymul(array3[n33 + n38], modp_R3, p6, modp_ninv32); final int modp_montymul2 = modp_montymul(array3[n34 + n38], modp_R3, p6, modp_ninv32); array3[n39] = modp_montymul(n44, modp_montymul, p6, modp_ninv32); array3[n39 + n7] = modp_montymul(n43, modp_montymul, p6, modp_ninv32); array3[n40] = modp_montymul(n42, modp_montymul2, p6, modp_ninv32); array3[n40 + n7] = modp_montymul(n41, modp_montymul2, p6, modp_ninv32); } modp_iNTT2_ext(array3, n10 + k, n7, array3, n25, n3, p6, modp_ninv32); modp_iNTT2_ext(array3, n11 + k, n7, array3, n25, n3, p6, modp_ninv32); } zint_rebuild_CRT(array3, n10, n7, n7, n4, 1, array3, n16); zint_rebuild_CRT(array3, n11, n7, n7, n4, 1, array3, n16); final double[] array4 = new double[n4]; final double[] array5 = new double[n4]; final double[] array6 = new double[n4]; final double[] array7 = new double[n4]; final double[] array8 = new double[n4 >> 1]; final int[] array9 = new int[n4]; final int min = Math.min(a, 10); poly_big_to_fp(array6, array3, n14 + a - min, min, a, n3); poly_big_to_fp(array7, array3, n15 + a - min, min, a, n3); final int n45 = 31 * (a - min); final int n46 = FalconKeyGen.bitlength_avg[n2] - 6 * FalconKeyGen.bitlength_std[n2]; final int n47 = FalconKeyGen.bitlength_avg[n2] + 6 * FalconKeyGen.bitlength_std[n2]; FalconFFT.FFT(array6, 0, n3); FalconFFT.FFT(array7, 0, n3); FalconFFT.poly_invnorm2_fft(array8, 0, array6, 0, array7, 0, n3); FalconFFT.poly_adj_fft(array6, 0, n3); FalconFFT.poly_adj_fft(array7, 0, n3); int a2 = n7; int n48 = 31 * n7; int n49 = n48 - n46; while (true) { final int min2 = Math.min(a2, 10); final int n50 = 31 * (a2 - min2); poly_big_to_fp(array4, array3, n10 + a2 - min2, min2, n7, n3); poly_big_to_fp(array5, array3, n11 + a2 - min2, min2, n7, n3); FalconFFT.FFT(array4, 0, n3); FalconFFT.FFT(array5, 0, n3); FalconFFT.poly_mul_fft(array4, 0, array6, 0, n3); FalconFFT.poly_mul_fft(array5, 0, array7, 0, n3); FalconFFT.poly_add(array5, 0, array4, 0, n3); FalconFFT.poly_mul_autoadj_fft(array5, 0, array8, 0, n3); FalconFFT.iFFT(array5, 0, n3); int n51 = n49 - n50 + n45; double n52; if (n51 < 0) { n51 = -n51; n52 = 2.0; } else { n52 = 0.5; } double n53 = 1.0; while (n51 != 0) { if ((n51 & 0x1) != 0x0) { n53 *= n52; } n51 >>= 1; n52 *= n52; } for (int n54 = 0; n54 < n4; ++n54) { final double n55 = array5[n54] * n53; if (-2.147483647E9 >= n55 || n55 >= 2.147483647E9) { return 0; } array9[n54] = (int)FPREngine.fpr_rint(n55); } final int n56 = n49 / 31; final int n57 = n49 % 31; if (n2 <= 4) { poly_sub_scaled_ntt(array3, n10, a2, n7, array3, n14, a, a, array9, n56, n57, n3, array3, n16); poly_sub_scaled_ntt(array3, n11, a2, n7, array3, n15, a, a, array9, n56, n57, n3, array3, n16); } else { poly_sub_scaled(array3, n10, a2, n7, array3, n14, a, a, array9, n56, n57, n3); poly_sub_scaled(array3, n11, a2, n7, array3, n15, a, a, array9, n56, n57, n3); } final int n58 = n49 + n47 + 10; if (n58 < n48) { n48 = n58; if (a2 * 31 >= n48 + 31) { --a2; } } if (n49 <= 0) { if (a2 < a) { for (int n59 = 0; n59 < n4; ++n59, n10 += n7, n11 += n7) { final int n60 = -(array3[n10 + a2 - 1] >>> 30) >>> 1; for (int n61 = a2; n61 < a; ++n61) { array3[n10 + n61] = n60; } final int n62 = -(array3[n11 + a2 - 1] >>> 30) >>> 1; for (int n63 = a2; n63 < a; ++n63) { array3[n11 + n63] = n62; } } } for (int n64 = 0, n65 = 0, n66 = 0; n64 < n4 << 1; ++n64, n65 += a, n66 += n7) { System.arraycopy(array3, n66, array3, n65, a); } return 1; } n49 -= 25; if (n49 >= 0) { continue; } n49 = 0; } } private static int solve_NTRU_binary_depth1(final int n, final byte[] array, final byte[] array2, final int[] array3) { final int n2 = 1; final int n3 = 1 << n; final int n4 = n - n2; final int n5 = 1 << n4; final int n6 = n5 >> 1; final int n7 = FalconKeyGen.MAX_BL_SMALL[n2]; final int n8 = FalconKeyGen.MAX_BL_SMALL[n2 + 1]; final int n9 = FalconKeyGen.MAX_BL_LARGE[n2]; final int n10 = 0; final int n11 = n10 + n8 * n6; final int n12 = n11 + n8 * n6; final int n13 = n12 + n9 * n5; for (int i = 0; i < n9; ++i) { final int p4 = FalconSmallPrimeList.PRIMES[i].p; final int modp_ninv31 = modp_ninv31(p4); final int modp_R2 = modp_R2(p4, modp_ninv31); final int modp_Rx = modp_Rx(n8, p4, modp_ninv31, modp_R2); for (int j = 0, n14 = n10, n15 = n11, n16 = n12 + i, n17 = n13 + i; j < n6; ++j, n14 += n8, n15 += n8, n16 += n9, n17 += n9) { array3[n16] = zint_mod_small_signed(array3, n14, n8, p4, modp_ninv31, modp_R2, modp_Rx); array3[n17] = zint_mod_small_signed(array3, n15, n8, p4, modp_ninv31, modp_R2, modp_Rx); } } System.arraycopy(array3, n12, array3, 0, n9 * n5); final int n18 = 0; System.arraycopy(array3, n13, array3, n18 + n9 * n5, n9 * n5); final int n19 = n18 + n9 * n5; final int n20 = n19 + n9 * n5; final int n21 = n20 + n7 * n5; final int n22 = n21 + n7 * n5; for (int k = 0; k < n9; ++k) { final int p5 = FalconSmallPrimeList.PRIMES[k].p; final int modp_ninv32 = modp_ninv31(p5); final int modp_R3 = modp_R2(p5, modp_ninv32); final int n23 = n22; final int n24 = n23 + n3; final int n25 = n24 + n5; final int n26 = n25 + n3; modp_mkgm2(array3, n23, array3, n24, n, FalconSmallPrimeList.PRIMES[k].g, p5, modp_ninv32); for (int l = 0; l < n3; ++l) { array3[n25 + l] = modp_set(array[l], p5); array3[n26 + l] = modp_set(array2[l], p5); } modp_NTT2(array3, n25, array3, n23, n, p5, modp_ninv32); modp_NTT2(array3, n26, array3, n23, n, p5, modp_ninv32); for (int n27 = n; n27 > n4; --n27) { modp_poly_rec_res(array3, n25, n27, p5, modp_ninv32, modp_R3); modp_poly_rec_res(array3, n26, n27, p5, modp_ninv32, modp_R3); } System.arraycopy(array3, n24, array3, n23 + n5, n5); final int n28 = n23 + n5; System.arraycopy(array3, n25, array3, n28 + n5, n5); final int n29 = n28 + n5; System.arraycopy(array3, n26, array3, n29 + n5, n5); final int n30 = n29 + n5; final int n31 = n30 + n5; final int n32 = n31 + n6; for (int n33 = 0, n34 = n18 + k, n35 = n19 + k; n33 < n6; ++n33, n34 += n9, n35 += n9) { array3[n31 + n33] = array3[n34]; array3[n32 + n33] = array3[n35]; } modp_NTT2(array3, n31, array3, n23, n4 - 1, p5, modp_ninv32); modp_NTT2(array3, n32, array3, n23, n4 - 1, p5, modp_ninv32); for (int n36 = 0, n37 = n18 + k, n38 = n19 + k; n36 < n6; ++n36, n37 += n9 << 1, n38 += n9 << 1) { final int n39 = array3[n29 + (n36 << 1)]; final int n40 = array3[n29 + (n36 << 1) + 1]; final int n41 = array3[n30 + (n36 << 1)]; final int n42 = array3[n30 + (n36 << 1) + 1]; final int modp_montymul = modp_montymul(array3[n31 + n36], modp_R3, p5, modp_ninv32); final int modp_montymul2 = modp_montymul(array3[n32 + n36], modp_R3, p5, modp_ninv32); array3[n37] = modp_montymul(n42, modp_montymul, p5, modp_ninv32); array3[n37 + n9] = modp_montymul(n41, modp_montymul, p5, modp_ninv32); array3[n38] = modp_montymul(n40, modp_montymul2, p5, modp_ninv32); array3[n38 + n9] = modp_montymul(n39, modp_montymul2, p5, modp_ninv32); } modp_iNTT2_ext(array3, n18 + k, n9, array3, n28, n4, p5, modp_ninv32); modp_iNTT2_ext(array3, n19 + k, n9, array3, n28, n4, p5, modp_ninv32); if (k < n7) { modp_iNTT2(array3, n29, array3, n28, n4, p5, modp_ninv32); modp_iNTT2(array3, n30, array3, n28, n4, p5, modp_ninv32); for (int n43 = 0, n44 = n20 + k, n45 = n21 + k; n43 < n5; ++n43, n44 += n7, n45 += n7) { array3[n44] = array3[n29 + n43]; array3[n45] = array3[n30 + n43]; } } } zint_rebuild_CRT(array3, n18, n9, n9, n5 << 1, 1, array3, n22); zint_rebuild_CRT(array3, n20, n7, n7, n5 << 1, 1, array3, n22); final double[] array4 = new double[n5]; final double[] array5 = new double[n5]; poly_big_to_fp(array4, array3, n18, n9, n9, n4); poly_big_to_fp(array5, array3, n19, n9, n9, n4); System.arraycopy(array3, n20, array3, 0, 2 * n7 * n5); final int n46 = 0; final int n47 = n46 + n7 * n5; final double[] array6 = new double[n5]; final double[] array7 = new double[n5]; poly_big_to_fp(array6, array3, n46, n7, n7, n4); poly_big_to_fp(array7, array3, n47, n7, n7, n4); FalconFFT.FFT(array4, 0, n4); FalconFFT.FFT(array5, 0, n4); FalconFFT.FFT(array6, 0, n4); FalconFFT.FFT(array7, 0, n4); final double[] array8 = new double[n5]; final double[] array9 = new double[n5 >> 1]; FalconFFT.poly_add_muladj_fft(array8, array4, array5, array6, array7, n4); FalconFFT.poly_invnorm2_fft(array9, 0, array6, 0, array7, 0, n4); FalconFFT.poly_mul_autoadj_fft(array8, 0, array9, 0, n4); FalconFFT.iFFT(array8, 0, n4); for (int n48 = 0; n48 < n5; ++n48) { final double n49 = array8[n48]; if (n49 >= 9.223372036854776E18 || -9.223372036854776E18 >= n49) { return 0; } array8[n48] = (double)FPREngine.fpr_rint(n49); } FalconFFT.FFT(array8, 0, n4); FalconFFT.poly_mul_fft(array6, 0, array8, 0, n4); FalconFFT.poly_mul_fft(array7, 0, array8, 0, n4); FalconFFT.poly_sub(array4, 0, array6, 0, n4); FalconFFT.poly_sub(array5, 0, array7, 0, n4); FalconFFT.iFFT(array4, 0, n4); FalconFFT.iFFT(array5, 0, n4); final int n50 = n18 + n5; for (int n51 = 0; n51 < n5; ++n51) { array3[n18 + n51] = (int)FPREngine.fpr_rint(array4[n51]); array3[n50 + n51] = (int)FPREngine.fpr_rint(array5[n51]); } return 1; } private static int solve_NTRU_binary_depth0(final int n, final byte[] array, final byte[] array2, final int[] array3) { final int n2 = 1 << n; final int n3 = n2 >> 1; final int p4 = FalconSmallPrimeList.PRIMES[0].p; final int modp_ninv31 = modp_ninv31(p4); final int modp_R2 = modp_R2(p4, modp_ninv31); final int n4 = 0; final int n5 = n4 + n3; final int n6 = n5 + n3; final int n7 = n6 + n2; final int n8 = n7 + n2; final int n9 = n8 + n2; modp_mkgm2(array3, n8, array3, n9, n, FalconSmallPrimeList.PRIMES[0].g, p4, modp_ninv31); for (int i = 0; i < n3; ++i) { array3[n4 + i] = modp_set(zint_one_to_plain(array3, n4 + i), p4); array3[n5 + i] = modp_set(zint_one_to_plain(array3, n5 + i), p4); } modp_NTT2(array3, n4, array3, n8, n - 1, p4, modp_ninv31); modp_NTT2(array3, n5, array3, n8, n - 1, p4, modp_ninv31); for (int j = 0; j < n2; ++j) { array3[n6 + j] = modp_set(array[j], p4); array3[n7 + j] = modp_set(array2[j], p4); } modp_NTT2(array3, n6, array3, n8, n, p4, modp_ninv31); modp_NTT2(array3, n7, array3, n8, n, p4, modp_ninv31); for (int k = 0; k < n2; k += 2) { final int n10 = array3[n6 + k]; final int n11 = array3[n6 + k + 1]; final int n12 = array3[n7 + k]; final int n13 = array3[n7 + k + 1]; final int modp_montymul = modp_montymul(array3[n4 + (k >> 1)], modp_R2, p4, modp_ninv31); final int modp_montymul2 = modp_montymul(array3[n5 + (k >> 1)], modp_R2, p4, modp_ninv31); array3[n6 + k] = modp_montymul(n13, modp_montymul, p4, modp_ninv31); array3[n6 + k + 1] = modp_montymul(n12, modp_montymul, p4, modp_ninv31); array3[n7 + k] = modp_montymul(n11, modp_montymul2, p4, modp_ninv31); array3[n7 + k + 1] = modp_montymul(n10, modp_montymul2, p4, modp_ninv31); } modp_iNTT2(array3, n6, array3, n9, n, p4, modp_ninv31); modp_iNTT2(array3, n7, array3, n9, n, p4, modp_ninv31); final int n14 = n4 + n2; final int n15 = n14 + n2; System.arraycopy(array3, n6, array3, n4, 2 * n2); final int n16 = n15 + n2; final int n17 = n16 + n2; final int n18 = n17 + n2; final int n19 = n18 + n2; modp_mkgm2(array3, n15, array3, n16, n, FalconSmallPrimeList.PRIMES[0].g, p4, modp_ninv31); modp_NTT2(array3, n4, array3, n15, n, p4, modp_ninv31); modp_NTT2(array3, n14, array3, n15, n, p4, modp_ninv31); array3[n18] = (array3[n19] = modp_set(array[0], p4)); for (int l = 1; l < n2; ++l) { array3[n18 + l] = modp_set(array[l], p4); array3[n19 + n2 - l] = modp_set(-array[l], p4); } modp_NTT2(array3, n18, array3, n15, n, p4, modp_ninv31); modp_NTT2(array3, n19, array3, n15, n, p4, modp_ninv31); for (int n20 = 0; n20 < n2; ++n20) { final int modp_montymul3 = modp_montymul(array3[n19 + n20], modp_R2, p4, modp_ninv31); array3[n16 + n20] = modp_montymul(modp_montymul3, array3[n4 + n20], p4, modp_ninv31); array3[n17 + n20] = modp_montymul(modp_montymul3, array3[n18 + n20], p4, modp_ninv31); } array3[n18] = (array3[n19] = modp_set(array2[0], p4)); for (int n21 = 1; n21 < n2; ++n21) { array3[n18 + n21] = modp_set(array2[n21], p4); array3[n19 + n2 - n21] = modp_set(-array2[n21], p4); } modp_NTT2(array3, n18, array3, n15, n, p4, modp_ninv31); modp_NTT2(array3, n19, array3, n15, n, p4, modp_ninv31); for (int n22 = 0; n22 < n2; ++n22) { final int modp_montymul4 = modp_montymul(array3[n19 + n22], modp_R2, p4, modp_ninv31); array3[n16 + n22] = modp_add(array3[n16 + n22], modp_montymul(modp_montymul4, array3[n14 + n22], p4, modp_ninv31), p4); array3[n17 + n22] = modp_add(array3[n17 + n22], modp_montymul(modp_montymul4, array3[n18 + n22], p4, modp_ninv31), p4); } modp_mkgm2(array3, n15, array3, n18, n, FalconSmallPrimeList.PRIMES[0].g, p4, modp_ninv31); modp_iNTT2(array3, n16, array3, n18, n, p4, modp_ninv31); modp_iNTT2(array3, n17, array3, n18, n, p4, modp_ninv31); for (int n23 = 0; n23 < n2; ++n23) { array3[n15 + n23] = modp_norm(array3[n16 + n23], p4); array3[n16 + n23] = modp_norm(array3[n17 + n23], p4); } final double[] array4 = new double[3 * n2]; final int n24 = 0 + n2; final int n25 = n24 + n2; for (int n26 = 0; n26 < n2; ++n26) { array4[n25 + n26] = array3[n16 + n26]; } FalconFFT.FFT(array4, n25, n); System.arraycopy(array4, n25, array4, n24, n3); final int n27 = n24 + n3; for (int n28 = 0; n28 < n2; ++n28) { array4[n27 + n28] = array3[n15 + n28]; } FalconFFT.FFT(array4, n27, n); FalconFFT.poly_div_autoadj_fft(array4, n27, array4, n24, n); FalconFFT.iFFT(array4, n27, n); for (int n29 = 0; n29 < n2; ++n29) { array3[n15 + n29] = modp_set((int)FPREngine.fpr_rint(array4[n27 + n29]), p4); } final int n30 = n15 + n2; final int n31 = n30 + n2; final int n32 = n31 + n2; final int n33 = n32 + n2; modp_mkgm2(array3, n30, array3, n31, n, FalconSmallPrimeList.PRIMES[0].g, p4, modp_ninv31); for (int n34 = 0; n34 < n2; ++n34) { array3[n32 + n34] = modp_set(array[n34], p4); array3[n33 + n34] = modp_set(array2[n34], p4); } modp_NTT2(array3, n15, array3, n30, n, p4, modp_ninv31); modp_NTT2(array3, n32, array3, n30, n, p4, modp_ninv31); modp_NTT2(array3, n33, array3, n30, n, p4, modp_ninv31); for (int n35 = 0; n35 < n2; ++n35) { final int modp_montymul5 = modp_montymul(array3[n15 + n35], modp_R2, p4, modp_ninv31); array3[n4 + n35] = modp_sub(array3[n4 + n35], modp_montymul(modp_montymul5, array3[n32 + n35], p4, modp_ninv31), p4); array3[n14 + n35] = modp_sub(array3[n14 + n35], modp_montymul(modp_montymul5, array3[n33 + n35], p4, modp_ninv31), p4); } modp_iNTT2(array3, n4, array3, n31, n, p4, modp_ninv31); modp_iNTT2(array3, n14, array3, n31, n, p4, modp_ninv31); for (int n36 = 0; n36 < n2; ++n36) { array3[n4 + n36] = modp_norm(array3[n4 + n36], p4); array3[n14 + n36] = modp_norm(array3[n14 + n36], p4); } return 1; } private static int solve_NTRU(final int n, final byte[] array, final byte[] array2, final byte[] array3, final int n2, final int[] array4) { final int n3 = 0; final int mkn = mkn(n); if (solve_NTRU_deepest(n, array2, array3, array4) == 0) { return 0; } if (n <= 2) { int n4 = n; while (n4-- > 0) { if (solve_NTRU_intermediate(n, array2, array3, n4, array4) == 0) { return 0; } } } else { int n5 = n; while (n5-- > 2) { if (solve_NTRU_intermediate(n, array2, array3, n5, array4) == 0) { return 0; } } if (solve_NTRU_binary_depth1(n, array2, array3, array4) == 0) { return 0; } if (solve_NTRU_binary_depth0(n, array2, array3, array4) == 0) { return 0; } } final byte[] array5 = new byte[mkn]; if (poly_big_to_small(array, 0, array4, 0, n2, n) == 0 || poly_big_to_small(array5, n3, array4, mkn, n2, n) == 0) { return 0; } final int n6 = 0; final int n7 = n6 + mkn; final int n8 = n7 + mkn; final int n9 = n8 + mkn; final int n10 = n9 + mkn; final int p6 = FalconSmallPrimeList.PRIMES[0].p; final int modp_ninv31 = modp_ninv31(p6); modp_mkgm2(array4, n10, array4, 0, n, FalconSmallPrimeList.PRIMES[0].g, p6, modp_ninv31); for (int i = 0; i < mkn; ++i) { array4[n6 + i] = modp_set(array5[n3 + i], p6); } for (int j = 0; j < mkn; ++j) { array4[n7 + j] = modp_set(array2[j], p6); array4[n8 + j] = modp_set(array3[j], p6); array4[n9 + j] = modp_set(array[j], p6); } modp_NTT2(array4, n7, array4, n10, n, p6, modp_ninv31); modp_NTT2(array4, n8, array4, n10, n, p6, modp_ninv31); modp_NTT2(array4, n9, array4, n10, n, p6, modp_ninv31); modp_NTT2(array4, n6, array4, n10, n, p6, modp_ninv31); final int modp_montymul = modp_montymul(12289, 1, p6, modp_ninv31); for (int k = 0; k < mkn; ++k) { if (modp_sub(modp_montymul(array4[n7 + k], array4[n6 + k], p6, modp_ninv31), modp_montymul(array4[n8 + k], array4[n9 + k], p6, modp_ninv31), p6) != modp_montymul) { return 0; } } return 1; } private static void poly_small_mkgauss(final SHAKEDigest shakeDigest, final byte[] array, final int n) { final int mkn = mkn(n); int n2 = 0; for (int i = 0; i < mkn; ++i) { int mkgauss; while (true) { mkgauss = mkgauss(shakeDigest, n); if (mkgauss >= -127) { if (mkgauss > 127) { continue; } if (i != mkn - 1) { n2 ^= (mkgauss & 0x1); break; } if ((n2 ^ (mkgauss & 0x1)) == 0x0) { continue; } break; } } array[i] = (byte)mkgauss; } } static void keygen(final SHAKEDigest shakeDigest, final byte[] array, final byte[] array2, final byte[] array3, short[] array4, final int n) { final int mkn = mkn(n); while (true) { final double[] array5 = new double[3 * mkn]; poly_small_mkgauss(shakeDigest, array, n); poly_small_mkgauss(shakeDigest, array2, n); int n2 = 1 << FalconCodec.max_fg_bits[n] - 1; for (int i = 0; i < mkn; ++i) { if (array[i] >= n2 || array[i] <= -n2 || array2[i] >= n2 || array2[i] <= -n2) { n2 = -1; break; } } if (n2 < 0) { continue; } final int poly_small_sqnorm = poly_small_sqnorm(array, n); final int poly_small_sqnorm2 = poly_small_sqnorm(array2, n); if (((long)(poly_small_sqnorm + poly_small_sqnorm2 | -((poly_small_sqnorm | poly_small_sqnorm2) >>> 31)) & 0xFFFFFFFFL) >= 16823L) { continue; } final int n3 = 0; final int n4 = n3 + mkn; final int n5 = n4 + mkn; poly_small_to_fp(array5, n3, array, n); poly_small_to_fp(array5, n4, array2, n); FalconFFT.FFT(array5, n3, n); FalconFFT.FFT(array5, n4, n); FalconFFT.poly_invnorm2_fft(array5, n5, array5, n3, array5, n4, n); FalconFFT.poly_adj_fft(array5, n3, n); FalconFFT.poly_adj_fft(array5, n4, n); FalconFFT.poly_mulconst(array5, n3, 12289.0, n); FalconFFT.poly_mulconst(array5, n4, 12289.0, n); FalconFFT.poly_mul_autoadj_fft(array5, n3, array5, n5, n); FalconFFT.poly_mul_autoadj_fft(array5, n4, array5, n5, n); FalconFFT.iFFT(array5, n3, n); FalconFFT.iFFT(array5, n4, n); double n6 = 0.0; for (int j = 0; j < mkn; ++j) { n6 += array5[n3 + j] * array5[n3 + j] + array5[n4 + j] * array5[n4 + j]; } if (n6 >= 16822.4121) { continue; } final short[] array6 = new short[2 * mkn]; int n7; int n8; if (array4 == null) { n7 = 0; array4 = array6; n8 = n7 + mkn; } else { n7 = 0; n8 = 0; } if (FalconVrfy.compute_public(array4, n7, array, array2, n, array6, n8) == 0) { continue; } if (solve_NTRU(n, array3, array, array2, (1 << FalconCodec.max_FG_bits[n] - 1) - 1, (n > 2) ? new int[28 * mkn] : new int[28 * mkn * 3]) == 0) { continue; } break; } } private static long toUnsignedLong(final int n) { return (long)n & 0xFFFFFFFFL; } static { REV10 = new short[] { 0, 512, 256, 768, 128, 640, 384, 896, 64, 576, 320, 832, 192, 704, 448, 960, 32, 544, 288, 800, 160, 672, 416, 928, 96, 608, 352, 864, 224, 736, 480, 992, 16, 528, 272, 784, 144, 656, 400, 912, 80, 592, 336, 848, 208, 720, 464, 976, 48, 560, 304, 816, 176, 688, 432, 944, 112, 624, 368, 880, 240, 752, 496, 1008, 8, 520, 264, 776, 136, 648, 392, 904, 72, 584, 328, 840, 200, 712, 456, 968, 40, 552, 296, 808, 168, 680, 424, 936, 104, 616, 360, 872, 232, 744, 488, 1000, 24, 536, 280, 792, 152, 664, 408, 920, 88, 600, 344, 856, 216, 728, 472, 984, 56, 568, 312, 824, 184, 696, 440, 952, 120, 632, 376, 888, 248, 760, 504, 1016, 4, 516, 260, 772, 132, 644, 388, 900, 68, 580, 324, 836, 196, 708, 452, 964, 36, 548, 292, 804, 164, 676, 420, 932, 100, 612, 356, 868, 228, 740, 484, 996, 20, 532, 276, 788, 148, 660, 404, 916, 84, 596, 340, 852, 212, 724, 468, 980, 52, 564, 308, 820, 180, 692, 436, 948, 116, 628, 372, 884, 244, 756, 500, 1012, 12, 524, 268, 780, 140, 652, 396, 908, 76, 588, 332, 844, 204, 716, 460, 972, 44, 556, 300, 812, 172, 684, 428, 940, 108, 620, 364, 876, 236, 748, 492, 1004, 28, 540, 284, 796, 156, 668, 412, 924, 92, 604, 348, 860, 220, 732, 476, 988, 60, 572, 316, 828, 188, 700, 444, 956, 124, 636, 380, 892, 252, 764, 508, 1020, 2, 514, 258, 770, 130, 642, 386, 898, 66, 578, 322, 834, 194, 706, 450, 962, 34, 546, 290, 802, 162, 674, 418, 930, 98, 610, 354, 866, 226, 738, 482, 994, 18, 530, 274, 786, 146, 658, 402, 914, 82, 594, 338, 850, 210, 722, 466, 978, 50, 562, 306, 818, 178, 690, 434, 946, 114, 626, 370, 882, 242, 754, 498, 1010, 10, 522, 266, 778, 138, 650, 394, 906, 74, 586, 330, 842, 202, 714, 458, 970, 42, 554, 298, 810, 170, 682, 426, 938, 106, 618, 362, 874, 234, 746, 490, 1002, 26, 538, 282, 794, 154, 666, 410, 922, 90, 602, 346, 858, 218, 730, 474, 986, 58, 570, 314, 826, 186, 698, 442, 954, 122, 634, 378, 890, 250, 762, 506, 1018, 6, 518, 262, 774, 134, 646, 390, 902, 70, 582, 326, 838, 198, 710, 454, 966, 38, 550, 294, 806, 166, 678, 422, 934, 102, 614, 358, 870, 230, 742, 486, 998, 22, 534, 278, 790, 150, 662, 406, 918, 86, 598, 342, 854, 214, 726, 470, 982, 54, 566, 310, 822, 182, 694, 438, 950, 118, 630, 374, 886, 246, 758, 502, 1014, 14, 526, 270, 782, 142, 654, 398, 910, 78, 590, 334, 846, 206, 718, 462, 974, 46, 558, 302, 814, 174, 686, 430, 942, 110, 622, 366, 878, 238, 750, 494, 1006, 30, 542, 286, 798, 158, 670, 414, 926, 94, 606, 350, 862, 222, 734, 478, 990, 62, 574, 318, 830, 190, 702, 446, 958, 126, 638, 382, 894, 254, 766, 510, 1022, 1, 513, 257, 769, 129, 641, 385, 897, 65, 577, 321, 833, 193, 705, 449, 961, 33, 545, 289, 801, 161, 673, 417, 929, 97, 609, 353, 865, 225, 737, 481, 993, 17, 529, 273, 785, 145, 657, 401, 913, 81, 593, 337, 849, 209, 721, 465, 977, 49, 561, 305, 817, 177, 689, 433, 945, 113, 625, 369, 881, 241, 753, 497, 1009, 9, 521, 265, 777, 137, 649, 393, 905, 73, 585, 329, 841, 201, 713, 457, 969, 41, 553, 297, 809, 169, 681, 425, 937, 105, 617, 361, 873, 233, 745, 489, 1001, 25, 537, 281, 793, 153, 665, 409, 921, 89, 601, 345, 857, 217, 729, 473, 985, 57, 569, 313, 825, 185, 697, 441, 953, 121, 633, 377, 889, 249, 761, 505, 1017, 5, 517, 261, 773, 133, 645, 389, 901, 69, 581, 325, 837, 197, 709, 453, 965, 37, 549, 293, 805, 165, 677, 421, 933, 101, 613, 357, 869, 229, 741, 485, 997, 21, 533, 277, 789, 149, 661, 405, 917, 85, 597, 341, 853, 213, 725, 469, 981, 53, 565, 309, 821, 181, 693, 437, 949, 117, 629, 373, 885, 245, 757, 501, 1013, 13, 525, 269, 781, 141, 653, 397, 909, 77, 589, 333, 845, 205, 717, 461, 973, 45, 557, 301, 813, 173, 685, 429, 941, 109, 621, 365, 877, 237, 749, 493, 1005, 29, 541, 285, 797, 157, 669, 413, 925, 93, 605, 349, 861, 221, 733, 477, 989, 61, 573, 317, 829, 189, 701, 445, 957, 125, 637, 381, 893, 253, 765, 509, 1021, 3, 515, 259, 771, 131, 643, 387, 899, 67, 579, 323, 835, 195, 707, 451, 963, 35, 547, 291, 803, 163, 675, 419, 931, 99, 611, 355, 867, 227, 739, 483, 995, 19, 531, 275, 787, 147, 659, 403, 915, 83, 595, 339, 851, 211, 723, 467, 979, 51, 563, 307, 819, 179, 691, 435, 947, 115, 627, 371, 883, 243, 755, 499, 1011, 11, 523, 267, 779, 139, 651, 395, 907, 75, 587, 331, 843, 203, 715, 459, 971, 43, 555, 299, 811, 171, 683, 427, 939, 107, 619, 363, 875, 235, 747, 491, 1003, 27, 539, 283, 795, 155, 667, 411, 923, 91, 603, 347, 859, 219, 731, 475, 987, 59, 571, 315, 827, 187, 699, 443, 955, 123, 635, 379, 891, 251, 763, 507, 1019, 7, 519, 263, 775, 135, 647, 391, 903, 71, 583, 327, 839, 199, 711, 455, 967, 39, 551, 295, 807, 167, 679, 423, 935, 103, 615, 359, 871, 231, 743, 487, 999, 23, 535, 279, 791, 151, 663, 407, 919, 87, 599, 343, 855, 215, 727, 471, 983, 55, 567, 311, 823, 183, 695, 439, 951, 119, 631, 375, 887, 247, 759, 503, 1015, 15, 527, 271, 783, 143, 655, 399, 911, 79, 591, 335, 847, 207, 719, 463, 975, 47, 559, 303, 815, 175, 687, 431, 943, 111, 623, 367, 879, 239, 751, 495, 1007, 31, 543, 287, 799, 159, 671, 415, 927, 95, 607, 351, 863, 223, 735, 479, 991, 63, 575, 319, 831, 191, 703, 447, 959, 127, 639, 383, 895, 255, 767, 511, 1023 }; gauss_1024_12289 = new long[] { 1283868770400643928L, 6416574995475331444L, 4078260278032692663L, 2353523259288686585L, 1227179971273316331L, 575931623374121527L, 242543240509105209L, 91437049221049666L, 30799446349977173L, 9255276791179340L, 2478152334826140L, 590642893610164L, 125206034929641L, 23590435911403L, 3948334035941L, 586753615614L, 77391054539L, 9056793210L, 940121950L, 86539696L, 7062824L, 510971L, 32764L, 1862L, 94L, 4L, 0L }; MAX_BL_SMALL = new int[] { 1, 1, 2, 2, 4, 7, 14, 27, 53, 106, 209 }; MAX_BL_LARGE = new int[] { 2, 2, 5, 7, 12, 21, 40, 78, 157, 308 }; bitlength_avg = new int[] { 4, 11, 24, 50, 102, 202, 401, 794, 1577, 3138, 6308 }; bitlength_std = new int[] { 0, 1, 1, 1, 1, 2, 4, 5, 8, 13, 25 }; } }