From 6bc6e3dc56d78aed381e844269226dcab80bfca7 Mon Sep 17 00:00:00 2001 From: Peter Dettman Date: Sat, 16 Jul 2022 01:25:37 +0700 Subject: SIKE performance --- crypto/src/pqc/crypto/sike/Fpx.cs | 111 ++++++++++++++------------------------ 1 file changed, 41 insertions(+), 70 deletions(-) (limited to 'crypto') diff --git a/crypto/src/pqc/crypto/sike/Fpx.cs b/crypto/src/pqc/crypto/sike/Fpx.cs index cdaf8dc85..c2a1f1972 100644 --- a/crypto/src/pqc/crypto/sike/Fpx.cs +++ b/crypto/src/pqc/crypto/sike/Fpx.cs @@ -1,6 +1,6 @@ using System; using System.Diagnostics; -#if NETSTANDARD1_0_OR_GREATER +#if NETSTANDARD1_0_OR_GREATER || NET5_0_OR_GREATER using System.Runtime.CompilerServices; #endif @@ -137,7 +137,7 @@ namespace Org.BouncyCastle.Pqc.Crypto.Sike } // Is x < y? -#if NETSTANDARD1_0_OR_GREATER +#if NETSTANDARD1_0_OR_GREATER || NET5_0_OR_GREATER [MethodImpl(MethodImplOptions.AggressiveInlining)] #endif private ulong is_digit_lessthan_ct(ulong x, ulong y) @@ -146,7 +146,7 @@ namespace Org.BouncyCastle.Pqc.Crypto.Sike } // Is x != 0? -#if NETSTANDARD1_0_OR_GREATER +#if NETSTANDARD1_0_OR_GREATER || NET5_0_OR_GREATER [MethodImpl(MethodImplOptions.AggressiveInlining)] #endif private ulong is_digit_nonzero_ct(ulong x) @@ -154,7 +154,7 @@ namespace Org.BouncyCastle.Pqc.Crypto.Sike return ((x | (0-x)) >> (int)(Internal.RADIX -1)); } // Is x = 0? -#if NETSTANDARD1_0_OR_GREATER +#if NETSTANDARD1_0_OR_GREATER || NET5_0_OR_GREATER [MethodImpl(MethodImplOptions.AggressiveInlining)] #endif private ulong is_digit_zero_ct(ulong x) @@ -186,7 +186,7 @@ namespace Org.BouncyCastle.Pqc.Crypto.Sike { for (int i = (int)engine.param.NWORDS_FIELD-1; i >= 0; i--) { - if (x[i] < y[i] ) + if (x[i] < y[i] ) { return true; } @@ -194,16 +194,6 @@ namespace Org.BouncyCastle.Pqc.Crypto.Sike { return false; } - - // //todo : find lt for unsigned ulongs - // if (x[i] < y[i]) - // { - // return true; - // } - // else if (x[i] > y[i]) - // { - // return false; - // } } return false; } @@ -250,24 +240,25 @@ namespace Org.BouncyCastle.Pqc.Crypto.Sike } // Partial Montgomery inversion via the binary GCD algorithm. - private void fpinv_mont_bingcd_partial(ulong[] a, ulong[] x1, uint[] k) + private uint fpinv_mont_bingcd_partial(ulong[] a, ulong[] x1) { + // TODO Use faster (and optionally constant-time) inversion in Org.BouncyCastle.Math.Raw.Mod + ulong[] u = new ulong[engine.param.NWORDS_FIELD], v = new ulong[engine.param.NWORDS_FIELD], x2 = new ulong[engine.param.NWORDS_FIELD]; - uint cwords; // Number of words necessary for x1, x2 - fpcopy(a, 0, u); fpcopy(engine.param.PRIME, 0, v); fpzero(x1); x1[0] = 1; fpzero(x2); - k[0] = 0; + uint k = 0; while (!is_felm_zero(v)) { - cwords = ((k[0] + 1) / Internal.RADIX) + 1; - if ((cwords < engine.param.NWORDS_FIELD)) + // Number of words necessary for x1, x2 + uint cwords = (++k / Internal.RADIX) + 1; + if (cwords < engine.param.NWORDS_FIELD) { if (is_felm_even(v)) { @@ -321,13 +312,14 @@ namespace Org.BouncyCastle.Pqc.Crypto.Sike mp_shiftl1(x2, engine.param.NWORDS_FIELD); } } - k[0] += 1; } if (is_felm_lt(engine.param.PRIME, x1)) { mp_sub(x1, engine.param.PRIME, x1, engine.param.NWORDS_FIELD); } + + return k; } // Set up the value 2^mark. @@ -355,21 +347,20 @@ namespace Org.BouncyCastle.Pqc.Crypto.Sike // operations not involving any secret data. private void fpinv_mont_bingcd(ulong[] a) { - ulong[] x = new ulong[engine.param.NWORDS_FIELD], - t = new ulong[engine.param.NWORDS_FIELD]; - uint[] k = new uint[1]; - if (is_felm_zero(a)) return; - fpinv_mont_bingcd_partial(a, x, k); - if (k[0] <= engine.param.MAXBITS_FIELD) + ulong[] x = new ulong[engine.param.NWORDS_FIELD], + t = new ulong[engine.param.NWORDS_FIELD]; + + uint k = fpinv_mont_bingcd_partial(a, x); + if (k <= engine.param.MAXBITS_FIELD) { fpmul_mont(x, engine.param.Montgomery_R2, x); - k[0] += engine.param.MAXBITS_FIELD; + k += engine.param.MAXBITS_FIELD; } fpmul_mont(x, engine.param.Montgomery_R2, x); - power2_setup(t, 2*(int)engine.param.MAXBITS_FIELD - (int)k[0], engine.param.NWORDS_FIELD); + power2_setup(t, 2*(int)engine.param.MAXBITS_FIELD - (int)k, engine.param.NWORDS_FIELD); fpmul_mont(x, t, a); } @@ -1078,7 +1069,7 @@ namespace Org.BouncyCastle.Pqc.Crypto.Sike // Is x even? return 1 (TRUE) if condition is true, 0 (FALSE) otherwise. private bool is_even_mod_order(ulong[] x) { - return ((x[0] & 1) ^ 1) == 1; + return (x[0] & 1UL) == 0UL; } // Is x < y? return 1 (TRUE) if condition is true, 0 (FALSE) otherwise. @@ -1117,7 +1108,7 @@ namespace Org.BouncyCastle.Pqc.Crypto.Sike // Partial Montgomery inversion modulo order. - private void Montgomery_inversion_mod_order_bingcd_partial(ulong[] a, ulong[] x1, uint[] k, ulong[] order) + private uint Montgomery_inversion_mod_order_bingcd_partial(ulong[] a, ulong[] x1, ulong[] order) { ulong[] u = new ulong[engine.param.NWORDS_ORDER], v = new ulong[engine.param.NWORDS_ORDER], @@ -1128,11 +1119,11 @@ namespace Org.BouncyCastle.Pqc.Crypto.Sike copy_words(order, v, engine.param.NWORDS_ORDER); copy_words(x2, x1, engine.param.NWORDS_ORDER); x1[0] = 1; - k[0] = 0; - + uint k = 0; + while (!is_zero_mod_order(v)) { - cwords = ((k[0] + 1) / Internal.RADIX) + 1; + cwords = (++k / Internal.RADIX) + 1; if ((cwords < engine.param.NWORDS_ORDER)) { if (is_even_mod_order(v)) @@ -1186,13 +1177,14 @@ namespace Org.BouncyCastle.Pqc.Crypto.Sike mp_shiftl1(x2, engine.param.NWORDS_ORDER); } } - k[0] += 1; } - + if (is_lt_mod_order(order, x1)) { mp_sub(x1, order, x1, engine.param.NWORDS_ORDER); } + + return k; } // Montgomery inversion modulo order, c = a^(-1)*R mod order. @@ -1200,7 +1192,6 @@ namespace Org.BouncyCastle.Pqc.Crypto.Sike { ulong[] x = new ulong[engine.param.NWORDS_ORDER], t = new ulong[engine.param.NWORDS_ORDER]; - uint[] k = new uint[1]; if (is_zero(a, engine.param.NWORDS_ORDER)) { @@ -1208,15 +1199,15 @@ namespace Org.BouncyCastle.Pqc.Crypto.Sike return; } - Montgomery_inversion_mod_order_bingcd_partial(a, x, k, order); - if (k[0] <= engine.param.NBITS_ORDER) + uint k = Montgomery_inversion_mod_order_bingcd_partial(a, x, order); + if (k <= engine.param.NBITS_ORDER) { Montgomery_multiply_mod_order(x, Montgomery_Rprime, x, order, Montgomery_rprime); - k[0] += engine.param.NBITS_ORDER; + k += engine.param.NBITS_ORDER; } Montgomery_multiply_mod_order(x, Montgomery_Rprime, x, order, Montgomery_rprime); - power2_setup(t, 2*(int)engine.param.NBITS_ORDER - (int)k[0], engine.param.NWORDS_ORDER); + power2_setup(t, 2*(int)engine.param.NBITS_ORDER - (int)k, engine.param.NWORDS_ORDER); Montgomery_multiply_mod_order(x, t, c, order, Montgomery_rprime); } @@ -1233,24 +1224,14 @@ namespace Org.BouncyCastle.Pqc.Crypto.Sike // The input is assumed to be NWORDS_ORDER ulong protected internal uint mod3(ulong[] a) { - ulong temp; - uint r = 0; - uint[] val = Pack.LE_To_UInt32(Pack.UInt64_To_LE(a), 0, a.Length*2); - - for (int i = (2*(int)engine.param.NWORDS_ORDER-1); i >= 0; i--) + ulong result = 0; + for (int i = 0; i < engine.param.NWORDS_ORDER; ++i) { - // System.out.pruintln("i: " + i); - // System.out.pruintf("val: %016x\n", val[i]); - // System.out.pruintf("val: %016x\n", a[i/2]); - // System.out.pruintf("r<<: %016x\n", ( ((ulong)r << (4*8)))); - temp = ((ulong)r << (4*8)) | ((ulong)val[i]) & 0x00000000ffffffffL; - // System.out.pruintf("temp: %016x\n", temp); - r = (uint)(temp % 3); - // System.out.pruintf("r: %d\n", r); + result += a[i] >> 32; + result += a[i] & 0xFFFFFFFFUL; } - - return r; - } + return (uint)(result % 3); + } // Conversion of a GF(p^2) element to Montgomery representation, // mc_i = a_i*R^2*R^(-1) = a_i*R in GF(p^2). @@ -1628,26 +1609,16 @@ namespace Org.BouncyCastle.Pqc.Crypto.Sike // SECURITY NOTE: This function does not run in constant-time. protected internal bool is_orderelm_lt(ulong[] x, ulong[] y) { - for (int i = (int)engine.param.NWORDS_ORDER-1; i >= 0; i--) { - - if (x[i] < y[i] ) + if (x[i] < y[i] ) { return true; } - else if (x[i] > y[i] ) + else if (x[i] > y[i] ) { return false; } - // if (x[i] < y[i]) - // { - // return true; - // } - // else if (x[i] > y[i]) - // { - // return false; - // } } return false; } -- cgit 1.4.1