[Gnuk-users] Gnuk on a faster MCU

[Aurelien Jarno]

Hi,

On 2017-09-11 10:17, NIIBE Yutaka wrote:
> I think that 2 seconds is acceptable.  When I started the development of
> OpenPGPcard alternative, it took like 5 seconds for RSA1024 with
> ATmega328 running 20MHz.  I didn't feel it's acceptable for my own use
> cases.  Then, for RSA2048, it was something like 2 seconds with
> STM32F103 with PolarSSL in 2010.  Thus, I started Gnuk.
> 
> BTW, currently we are using p*q modulus.  It is known that multi prime
> modulus can speed up RSA computation (It is patented by US5848159, still
> effective).  There was a technique of p^k*q modulus, which was patented
> by US6396926.  I found that the latter patent was expired in 2010, due
> to failure to pay maintenance fee.  For me, the latter technique seems
> to be covered by more general multi prime modulus technique.  If not, I
> wonder we can use that.

I got a closer look at the US5848159 patent. It seems to me that it has
the same drawback than multi-prime modulus, that is it impose some
constraints at key generation, basically that n is not anymore p*q. It
would mean that it's not possible to use this method on imported keys,
and that it has to be generated on the Gnuk device (or generated the
same way). In addition I guess that specific multi-prime modulus attacks
also apply.

All that said it appears to me that Gnuk doesn't fully exploit the p*q
modulus technique by not saving dp, dq and qp and recomputing them for
each RSA signature or decryption. On recent MCU with enough flash, 
they can be saved with the private key. Alternatively when using a MCU
with enough RAM, they can be kept in memory after a first RSA operation
on this key. I tried this latter method with a quick and dirty hack to 
get some ideas of the gain. It allowed me to reduce the decryption time
for an RSA4096 key from 3.50s to 2.76s on an STM32L432 MCU.

Aurelien

-- 
Aurelien Jarno                          GPG: 4096R/1DDD8C9B
aurelien at aurel32.net                 http://www.aurel32.net