Computing A^x (mod n)

[Décio Luiz Gazzoni Filho]

On Monday 04 October 2004 01:41, Philip Lee wrote:
> >PS: it's almost insulting to suggest that the GMP guys would have
> > implemented modular exponentiation without reduction after each step.
> > Better put your asbestos suit on
>
> Sorry for the insult. The function just seems very simple to me, and
> it's not working. I mean, there's not too much I can screw up about
> it...all the numbers I give it are what I intended to pass, all valid
> mpz_t's of correct values. Just tell me what would be wrong about:
>
> mpz_powm( plaintext, cipher, d, n );
>
> Where ciper, d, and n are all about 576 bits. I mean, surely it
> wouldn't overflow if at each step it's doing it modulo n right? Again,
> sorry if I made somebody mad; it's just that I'M the mad one right now

Remember, GMP is a very advanced library and it's quite unlikely the 
maintainers would have left out something as simple as that. Thus, you might 
assume there's something wrong with your code, and try to debug it instead of 
conjuring up such an unlikely theory.

Anyway, from just that 1 line of code, I can't tell that there's anything 
wrong. It would have helped if you included all of it (assuming it's not too 
big). Here's my own implementation of RSA, whipped up using the C++ class 
interface for GMP in about 5 minutes:

#include <iostream>
#include <gmpxx.h>

int main()
{
  mpz_class p, q, n, phi, e, d, m, c;
  int e_temp = 3;
  gmp_randclass r(gmp_randinit_default);

  p = r.get_z_bits(288);
  q = r.get_z_bits(288);
  mpz_nextprime(p.get_mpz_t(), p.get_mpz_t());
  mpz_nextprime(q.get_mpz_t(), q.get_mpz_t());
  n = p*q;
  phi = (p-1)*(q-1);
  std::cout << "p = " << p << "\nq = " << q << std::endl;
  std::cout << "n = " << n << "\nphi = " << phi << std::endl;

  while (mpz_gcd_ui(NULL, phi.get_mpz_t(), e_temp) != 1)
    e_temp += 2;
  e = e_temp;
  mpz_invert(d.get_mpz_t(), e.get_mpz_t(), phi.get_mpz_t());
  std::cout << "e = " << e << "\nd = " << d << std::endl;

  m = r.get_z_range(n);
  std::cout << "m = " << m << std::endl;
  mpz_powm(c.get_mpz_t(), m.get_mpz_t(), e.get_mpz_t(), n.get_mpz_t());
  std::cout << "c = " << c << std::endl;
  mpz_powm(m.get_mpz_t(), c.get_mpz_t(), d.get_mpz_t(), n.get_mpz_t());
  std::cout << "m = " << m << std::endl;

  return 0;
}

It seems to work. Hope it helps.

(By the way, these member calls to get_mpz_t() get boring quickly. Wouldn't it 
be possible to write something like

mpz_t mpz_class::operator mpz_t()
{
  return get_mpz_t();
}

and spare this useless verbosity from C++ coders?)

Décio
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 190 bytes
Desc: not available
Url : /list-archives/gmp-discuss/attachments/20041004/d05fa2e4/attachment.bin