Re: symbol catenation and montgomery

[Torbjorn Granlund]

address@hidden writes:

          mpz_powm (1024)    16.375ms
  
       That's pretty good!
  
     Isn't an 1024-bit exponent somewhat larger than one usually uses for
     RSA?  What does "openssl speed" do?
  
  1024 bits is the usual size for RSA moduli these days.

That wasn't what I asked.  :-)

  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?

  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.

-- 
Torbjörn