In libgcrypt 1.7.8, for modular exponentiation, it simply uses _gcry_mpih_divrem.
We can use Barret or Montgomery modular reduction here.
We have _gcry_mpi_mod_barrett in mpi/mpi-mod.c, but it requires optimization.
| Status | Assigned | Task | ||
|---|---|---|---|---|
| Invalid | • gniibe | T3264 Possible RSA improvement | ||
| Resolved | • gniibe | T3269 (Constant-time) modular reduction |
Intel has patent application for folding technique for Barret reduction: US20070297601
and it is granted as: US8229109
It is described in this paper: https://www.lirmm.fr/arith18/papers/hasenplaugh-FastModularReduction.pdf
Intel has patent application for folding technique for Montgomery reduction: US8392494
which is described in this paper: https://www.cse.buffalo.edu/srds2009/escs2009_submission_Gopal.pdf
I found US patent which is expired due to fee: https://patents.google.com/patent/US7080109B2/en
The technique is described in : https://koclab.cs.ucsb.edu/docs/koc/j56.pdf
This is related paper: https://koclab.cs.ucsb.edu/docs/koc/j47.pdf
And this technique is evaluated in this paper: https://eprint.iacr.org/2011/239.pdf
According to the paper of 239, it seems good (as same as fold technique).
@gniibe: This is a pretty old bug; given all the changes of the last year, should we close it now?