Re: [Taler] [CFRG] Call for adoption for draft-wood-cfrg-rsa-blind-signatures

[Jeff Burdges]

> On 29 Apr 2021, at 06:38, Jacob Bachmeyer <jcb62281@gmail.com> wrote:
> What are the consequences of using a "bad" value?

You inherently perform the GCD test when computing the modular multiplicative 
inverse.  
https://en.wikipedia.org/wiki/Modular_multiplicative_inverse#Extended_Euclidean_algorithm

You could compute m (r^{-1})^e mod N when initially blinding and use sigma * r 
mod N when unblinding.  In this form, if r turns out not to be invertible then 
I guess you pick another r in a loop, but it’s fine if your code just panics. 

or

You could compute m r^e mod N when initially blinding and use sigma * r^{-1} 
mod N when unblinding.  In this form, if r turns out to not be invertible then 
it’s fine if your code just panics and the user looses their money.  

I’ve now forgotten if I was clever enough to use the first form in Taler or if 
I stupidly computed r^{-1} twice.

> Does the GCD test itself cause a timing leak or is it completed in constant 
> time?

It's a computation that should only happen once, but yes leaking even one bit 
sucks.  I’m unsure about the one-off leakage characteristics of RSA 
implementations. 

It’s likely you withdraw many coins at once so you batch inversion helps 
enormously, especially with one throw away element probably.  Again this favors 
the m (r^{-1})^e mod N form.

Jeff