Re: symbol catenation and montgomery

[phr-2000]

     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.