Page MenuHome GnuPG

(Constant-time) modular reduction
Closed, ResolvedPublic

Description

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.

  • We can only do partial multiplication for q2 = q1 * y, because lower bits will be removed, and ignoring part of computation can have an error at most 1.
  • We can only do partial multiplication for q3 * m, because higher bits will be removed.

Event Timeline

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

gniibe renamed this task from (Constant-time) Barret modular reduction to (Constant-time) modular reduction.Jul 14 2017, 4:42 AM
gniibe updated the task description. (Show Details)

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).

werner added a subscriber: werner.

@gniibe: This is a pretty old bug; given all the changes of the last year, should we close it now?

OK. When we will need and do, I will open new one.