OSEC

Neohapsis is currently accepting applications for employment. For more information, please visit our website www.neohapsis.com or email hr@neohapsis.com
 
Subject: Re: I would like to see some big integer examples of GMP code
From: Jim Gillogly (jimacm.org)
Date: Fri Jul 21 2000 - 22:44:52 CDT

"Peter D. Junger" wrote:
>
> I am, I fear, no programmer. But I would like to see if I can
> implement the RSA algorithm using the GMP library. Before I
> tackle this I would like to see one or two simple examples of
> programs using some of the relevant integer functions.

I'm attaching a few simple ones. The first two I sent you a little
while ago as an example of how to do RSA in GMP (enc-rsa and dec-rsa
using the SQUEAMISH OSSIFRAGE example). The third is a bog-simple
implementation of Pollard's Rho factoring algorithm. I don't claim
elegance or efficiency points for any of them, but they should give
you an idea of the level at which GMP operates. 

-- 
	Jim Gillogly
	29 Afterlithe S.R. 2000, 03:39
	12.19.7.7.3, 4 Akbal 6 Xul, Eighth Lord of Night

/* dec-rsa * Decrypt an RSA message given the private key. * Use SQUEAMISH OSSIFRAGE example, RSA-129. * Jim Gillogly, 8 Oct 1999. */

#include <stdio.h> #include <gmp.h>

main(int argc, char *argv[]) { mpz_t m; /* Public modulus */ mpz_t expon; /* Public exponent */ mpz_t d; /* Private exponent */ mpz_t ct; /* The ciphertext we're given. */ mpz_t pt; /* The plaintext message. */

mpz_init(m); /* Some space for the variables. */ mpz_init(expon); mpz_init(d); mpz_init(ct); mpz_init(pt);

/* m is the pub key published in Sci Am. */ mpz_set_str(m, "11438162575788886766923577997614661201021829672124236256256184293" "5706935245733897830597123563958705058989075147599290026879543541", 0); mpz_set_ui(expon, 9007); /* Public exponent given in Sci Am. */ mpz_set_str(ct, /* Ciphertext given in Sci Am. */ "968696137546220614771409222543558829057599911245743198746951209" "30816298225145708356931476622883989628013391990551829945157815154", 0);

/* Plaintext = ciphertext ** d mod m * * To decrypt, we need the private key, i.e. the exponent d, * given the private factors and the public exponent e. * ed = 1 (mod (p-1)(q-1)) * d is the private key; p and q may be thrown away. */ mpz_set_str(d, /* Private key, calculated from p, q, e. */ "106698614368578024442868771328920154780709906633937862801226224" "496631063125911774470873340168597462306553968544513277109053606095", 0); mpz_powm(pt, ct, d, m);

printf("Plaintext "); mpz_out_str(stdout, 10, pt); printf("\nT = 20, H = 08, E = 05, sp = 00, etc.\n"); return 0; }

/* enc-rsa * Encrypt an RSA message given the public modulus and exponent. * Use SQUEAMISH OSSIFRAGE example, RSA-129. * Jim Gillogly, 8 Oct 1999. */

#include <stdio.h> #include <gmp.h>

main(int argc, char *argv[]) { mpz_t m; /* Public key */ mpz_t expon; /* Public exponent */ mpz_t pt; /* The plaintext message. */ mpz_t ct; /* The ciphertext we're making. */

mpz_init(m); /* Some space for the variables. */ mpz_init(expon); mpz_init(pt); mpz_init(ct);

/* m is the pub key published in Sci Am. */ mpz_set_str(m, "11438162575788886766923577997614661201021829672124236256256184293" "5706935245733897830597123563958705058989075147599290026879543541", 0); mpz_set_si(expon, 9007); /* Public exponent given in Sci Am. */ mpz_set_str(pt, /* T = 20, H = 08, E = 05, sp = 00, etc. */ "200805001301070903002315180419000118050019172105011309190800151" "919090618010705", 0);

/* Ciphertext = plaintext ** exponent modulo m * * This is the encryption. All of it. The rest of this file * is simply framing to tell gmp where to find the parts. * We could use mpz_powm_ui for an exponent this short. */ mpz_powm(ct, pt, expon, m);

/* That was tough. Let's go home. */

printf("Ciphertext: "); mpz_out_str(stdout, 10, ct); printf("\nThis may be compared with the Sci Am challenge msg.\n");

return 0; }

/* rho: pollard rho * Jim Gillogly, May 2000 */ #include <stdio.h> #include <gmp.h>

typedef unsigned long int ulong;

main(int argc, char *argv[]) { mpz_t num, x, y, x1, q, sub, p; ulong a; long iters;

mpz_init(num); mpz_init(x); mpz_init(y); mpz_init(x1); mpz_init(q); mpz_init(sub); mpz_init(p);

if (argc != 4) { fprintf(stderr, "Usage: rho num x1 a\n"); fprintf(stderr, "x1, a start the prng.\n"); return 1; } mpz_set_str(num, argv[1], 0); mpz_set_str(x1, argv[2], 0); a = atoi(argv[3]);

if (mpz_probab_prime_p(num, 25)) { printf("Probably prime.\n"); return 0; }

mpz_set(x, x1); mpz_set(y, x1); mpz_set_ui(q, 1); for (iters = 1; iters > 0; iters++) { if ((iters % 1000000) == 0) { printf("%dM\n", iters / 1000000); fflush(stdout); } mpz_mul(x, x, x); mpz_add_ui(x, x, a); mpz_mod(x, x, num); mpz_mul(y, y, y); mpz_add_ui(y, y, a); mpz_mod(y, y, num); mpz_mul(y, y, y); mpz_add_ui(y, y, a); mpz_mod(y, y, num); mpz_sub(sub, y, x); mpz_abs(sub, sub); mpz_mul(q, q, sub); mpz_mod(q, q, num); if (iters % 20 == 0) { mpz_gcd(p, q, num); if (mpz_cmp_ui(p, 1) > 0) { printf("p = "); mpz_out_str(stdout, 10, p); printf("\n"); fflush(stdout); mpz_divexact(num, num, p); if (mpz_cmp_ui(num, 1) == 0) return 0; if (mpz_probab_prime_p(num, 25)) { printf("prm "); mpz_out_str(stdout, 10, num); printf("\n"); return 0; } } if ((iters % 100000) == 0) { printf("iters = %dK, q = ", iters / 1000); mpz_out_str(stdout, 10, q); printf("\n"); fflush(stdout); } } } printf("Didn't find a factor.\n"); return 1; }