GMPbench

[Torbjorn Granlund]

--=-=-=

I plan to release a benchmark for GMP.  The idea is to have
a hierarchy of benchmarks, with RSA signing and verification
of different sizes, multply speed for different sizes, etc.

There will be one GMPbench score, but then separate GMPbench.rsa,
GMPbench.mul, etc, scores.  Then, next level down, there will be
GMPbench.rsa.sign, GMPbench.rsa.verify, then GMPbench.rsa.sign.512,
GMPbench.rsa.sign.1024, GMPbench.rsa.sign.2048.

I've written the benchmark program for GMPbench.rsa.sign:

--=-=-=
Content-Type: application/octet-stream
Content-Disposition: attachment; filename=rsa.c

/* rsa.c -- sign random messages with rsa.

Copyright 2002 Free Software Foundation, Inc.

This file is part of the GNU GMPbench.

This program is free software; you can redistribute it and/or modify it under
the terms of the GNU General Public License as published by the Free Software
Foundation; either version 2 of the License, or (at your option) any later
version.

This program is distributed in the hope that it will be useful, but WITHOUT ANY
WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A
PARTICULAR PURPOSE.  See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License along with
this program; if not, write to the Free Software Foundation, Inc., 59 Temple
Place - Suite 330, Boston, MA 02111-1307, USA.  */


#include <stdlib.h>
#include <stdio.h>
#include "gmp.h"
#include "timing.h"

#define RSA_EXP 0x10001

long cputime (void);
void rsa_sign (mpz_t, mpz_t, mpz_t, mpz_t, mpz_t, mpz_t, mpz_t, mpz_t);

int
main (int argc, char *argv[])
{
  gmp_randstate_t rs;
  mpz_t p, q, pq, pm1, qm1, phi, e, d, p_i_q, dp, dq, msg[1000], smsg;
  unsigned long int n, i, niter, t0, ti;
  double t;

  if (argc != 2)
    {
      fprintf (stderr, "usage: %s n\n", argv[0]);
      fprintf (stderr, "  where n is number of bits in numbers tested\n");
      return -1;
    }

  if (argc == 2)
    n = atoi (argv[1]);

  gmp_randinit_default (rs);
  mpz_init (p);
  mpz_init (q);
  mpz_init (pq);

  printf ("Generating p, q, d..."); fflush (stdout);

  mpz_urandomb (p, rs, n/2);
  mpz_setbit (p, n / 2 - 1);
  mpz_setbit (p, n / 2 - 2);
  mpz_nextprime (p, p);

  mpz_urandomb (q, rs, n/2);
  mpz_setbit (q, n / 2 - 1);
  mpz_setbit (q, n / 2 - 2);
  mpz_nextprime (q, q);

  mpz_mul (pq, p, q);

  mpz_init_set_ui (e, RSA_EXP);
  mpz_init (d);
  mpz_init (pm1);
  mpz_init (qm1);
  mpz_init (phi);

  mpz_sub_ui (pm1, p, 1);
  mpz_sub_ui (qm1, q, 1);
  mpz_mul (phi, pm1, qm1);
  if (mpz_invert (d, e, phi) == 0)
    abort ();

  printf ("done; pq is %d bits\n", (int) mpz_sizeinbase (pq, 2));


  printf ("Precomputing CRT constants\n");

  mpz_init (p_i_q);
  if (mpz_invert (p_i_q, p, q) == 0)
    abort ();

  mpz_init (dp);
  mpz_init (dq);
  mpz_mod (dp, d, pm1);
  mpz_mod (dq, d, qm1);


  printf ("Generating 1000 random messages\n");

  for (i = 0; i < 1000; i++)
    {
      mpz_init (msg[i]);
      mpz_urandomb (msg[i], rs, n);
    }
  mpz_init (smsg);

  
  printf ("Calibrating CPU speed...");  fflush (stdout);
  TIME (t, rsa_sign (smsg, msg[0], p, q, pq, p_i_q, dp, dq));
  printf ("done\n");


  niter = (unsigned long) (1e4 / t);
  printf ("Signing random messages %lu times", niter);
  t0 = cputime ();
  for (i = 0; i < niter; i++)
    {
      if (i % 100 == 0)
	{
	  putchar ('.'); fflush (stdout);
	}
      rsa_sign (smsg, msg[i % 1000], p, q, pq, p_i_q, dp, dq);
    }
  ti = cputime () - t0;
  printf ("done!\n");

  printf ("%.1f signings per second for %lu bit RSA\n",
	  1000.0 * niter / ti, n);
  return 0;
}

void
rsa_sign (mpz_t smsg,
	  mpz_t msg, mpz_t p, mpz_t q, mpz_t pq,
	  mpz_t p_i_q, mpz_t dp, mpz_t dq)
{
  mpz_t  t, o, pr, qr, qr_m_pr;

  mpz_init (pr);
  mpz_init (qr);
  mpz_init (qr_m_pr);
  mpz_init (t);
  mpz_init (o);

  mpz_powm (pr, msg, dp, p);
  mpz_powm (qr, msg, dq, q);
  
  mpz_sub (qr_m_pr, qr, pr);

  mpz_mul (t, qr_m_pr, p_i_q);
  mpz_mod (o, t, q);		/* slow mod */

  mpz_mul (t, o, p);
  mpz_add (smsg, pr, t);
  mpz_mod (smsg, smsg, pq);	/* fast mod */

  mpz_clear (o);
  mpz_clear (t);
  mpz_clear (qr_m_pr);
  mpz_clear (qr);
  mpz_clear (pr);
}

--=-=-=
Content-Type: text/plain; charset=iso-8859-1
Content-Transfer-Encoding: 8bit


Here are some results:

Athlon XP 1460MHz (FreeBSD):
2460.0 signings per second for 512 bit RSA
452.2 signings per second for 1024 bit RSA
73.6 signings per second for 2048 bit RSA

Alpha 21264B 1000MHz (OSF):
3767.0 signings per second for 512 bit RSA
854.9 signings per second for 1024 bit RSA
154.8 signings per second for 2048 bit RSA

Itanium 2 1000MHz (Debian GNU/Linux):
2964.2 signings per second for 512 bit RSA
730.6 signings per second for 1024 bit RSA
142.4 signings per second for 2048 bit RSA

UltraSPARC 3 900MHz (Slowlaris):
989.5 signings per second for 512 bit RSA
201.0 signings per second for 1024 bit RSA
34.7 signings per second for 2048 bit RSA

Comments:

Alpha still holds the lead, but if GMP were optimized for
Itanium, it will be about 2.5 times faster (at the same
clock).  Sun's Ultracomputing(tm) clearly doesn't include
reasonable RSA speed.  :-)

It is interesting to compare GMP to openssl.  I haven't
benchmarked that myself, but from openssl benchmark results
on the Net, openssl is about 2.5 and 3.5 times slower than
GMP in a Pentium 3.

(Note that these results are with the development sources.
GMP 4.1.1 should be the same, except for on Itanium.)

-- 
Torbjörn

--=-=-=--