bug-gmp
[Top][All Lists]

## Re: symbol catenation and montgomery

 From: phr-2000 Subject: Re: symbol catenation and montgomery Date: 29 Sep 2000 11:24:36 -0000

```     The decryption operation is x = y^d mod N, where N=pq and p,q are
the secret prime factors, so N is 1024 bits and p and q are 512
bits.  You normally separately compute the residues of y^d mod p and
q separately, and then combine them to get the residue mod N.  So
you turn a 1024 bit modexp into two 512-bit modexps and some other
arithmetic.  This is about 3x faster than a full 1024-bit modexp.

How large is d in your notation?  Not 1024 bits, right?

Yes, d=1024 bits.  But y^d mod p = y^(d mod p) mod p, so you convert
the 1024^1024 modexp into two 512^512 bit modexps using your knowledge of
p and q.  Usually you precompute the CRT coefficients at key generation
time, so you don't have to do a big GCD computation with every modexp.
Am I making sense?

the exponent is normally chosen as a small fixed number, usually
65537 but sometimes as small as 3.  The decryption exponent is a
structureless number the same size as the modulus.

What does "openssl speed" use for the exponent?  With 65537, GMP goes
down to 0.33ms per modexp.  With 3, we're down to 0.11ms.

65537 I'm pretty sure.

```

reply via email to