Computing A^x (mod n)
Décio Luiz Gazzoni Filho
decio at decpp.net
Mon Oct 4 16:20:17 CEST 2004
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
More information about the gmp-discuss
mailing list