Optimize HACL* Raw RSA Encryption to use non-constant-time operations.

[franziskuskiefer]

PR coming for HACL this week.

[karthikbhargavan]

Did not manage to get this done last week. This week is the target (for sure this time!)

[karthikbhargavan]

Finally made good progress on this, after many disproved hypotheses. Now, we have a 2-3x perf improvement.

[karthikbhargavan]

Made the modifications, now looking into CRT decryption before sending to CF

[karthikbhargavan]

Tested on multiple platforms and compilers.

Some observations:

• compiling with gcc on x64 does not appear to enable HACL_CAN_COMPILE_INTRINSICS in lib_intrinsics.h, leading to a performance degradation. enabling this flag provides a significant boos.
• optimizing at -O2 (like the Linux Kernel) vs -O3 does not make much difference to this code
• recent GCCs (e.g. 13) are better at optimizing this code than GCC-11
• recent clang is still about 10-15% faster than recent GCC
• the optimizations that work differ for x64 and ARM likely because of the difference in mul instructions and pipelining
• with targeted optimizations for ARM our enc code is within 10-20% of optimized OpenSSL assembly on M1 Max
• with intrinsics for x64, our code is within 75-90% of optimized OpenSSL on core i7

[karthikbhargavan]

Next steps: Send update to CF by June 5th on status and plans.

[franziskuskiefer]

Next steps: push upstream to HACL and to consumers