jmrsa.c

mobile ip 在linux下的一种实现

/* $Id: jmrsa.c,v 1.9 2000/04/06 07:26:53 jm Exp $
 * Core RSA functions
 *
 * Dynamic hierarchial IP tunnel
 * Copyright (C) 1998-2000, Dynamics group
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License version 2 as
 * published by the Free Software Foundation. See README and COPYING for
 * more details.
 */

#ifdef HAVE_CONFIG_H
#include <config.h>
#endif

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <assert.h>
#include "jmrsa.h"


void rsa_encrypt(rsa_public_key *pub, mpz_t in, mpz_t out)
{
	mpz_powm(out, in, pub->e, pub->n);
}

void rsa_decrypt(rsa_secret_key *sec, mpz_t in, mpz_t out)
{
	mpz_t pp, qq, t;

	/* direct modular exponentiation:
	mpz_powm(out, in, &sec->d, &sec->n);
	*/

	/* the decryption is faster using Chinese Remainder Theorem: */

	mpz_init(pp);
	mpz_init(qq);
	mpz_init(t);

	/* pq = (in mod p) ^ dp mod p */
	mpz_mod(pp, in, sec->p);
	mpz_powm(pp, pp, sec->dp, sec->p);

	/* qq = (in mod q) ^ dq mod q */
	mpz_mod(qq, in, sec->q);
	mpz_powm(qq, qq, sec->dq, sec->q);

	/* t = (qq - pp) * u mod q */
	mpz_sub(t, qq, pp);
	mpz_mul(t, t, sec->u);
	mpz_mmod(t, t, sec->q);

	/* out = pp + p * t */
	mpz_mul(out, sec->p, t);
	mpz_add(out, out, pp);

	mpz_clear(pp);
	mpz_clear(qq);
	mpz_clear(t);
}

void rsa_debug_print_sec(rsa_secret_key *sec)
{
	printf("n=");
	mpz_out_str(stdout, 16, sec->n);
	printf("\ne=");
	mpz_out_str(stdout, 16, sec->e);
	printf("\nd=");
	mpz_out_str(stdout, 16, sec->d);
	printf("\np=");
	mpz_out_str(stdout, 16, sec->p);
	printf("\nq=");
	mpz_out_str(stdout, 16, sec->q);
	printf("\nu=");
	mpz_out_str(stdout, 16, sec->u);
	printf("\ndp=");
	mpz_out_str(stdout, 16, sec->dp);
	printf("\ndq=");
	mpz_out_str(stdout, 16, sec->dq);
	printf("\n");
}

void rsa_debug_print_pub(rsa_public_key *pub)
{
	printf("n=");
	mpz_out_str(stdout, 16, pub->n);
	printf("\ne=");
	mpz_out_str(stdout, 16, pub->e);
	printf("\n");
}

void rsa_init_sec(rsa_secret_key *sec)
{
	mpz_init(sec->n);
	mpz_init(sec->e);
	mpz_init(sec->d);
	mpz_init(sec->p);
	mpz_init(sec->q);
	mpz_init(sec->u);
	mpz_init(sec->dp);
	mpz_init(sec->dq);
}

void rsa_clear_sec(rsa_secret_key *sec)
{
	mpz_clear(sec->n);
	mpz_clear(sec->e);
	mpz_clear(sec->d);
	mpz_clear(sec->p);
	mpz_clear(sec->q);
	mpz_clear(sec->u);
	mpz_clear(sec->dp);
	mpz_clear(sec->dq);
}

void rsa_init_pub(rsa_public_key *pub)
{
	mpz_init(pub->n);
	mpz_init(pub->e);

}

void rsa_clear_pub(rsa_public_key *pub)
{
	mpz_clear(pub->n);
	mpz_clear(pub->e);
}

/* write a RSA secret key to a portable key file
 * return 0 on success or 1 on failure
 */
int rsa_write_file_sec(FILE *f, rsa_secret_key *sec)
{
	if (mpz_out_raw(f, sec->n) == 0) return 1;
	if (mpz_out_raw(f, sec->e) == 0) return 1;
	if (mpz_out_raw(f, sec->d) == 0) return 1;
	if (mpz_out_raw(f, sec->p) == 0) return 1;
	if (mpz_out_raw(f, sec->q) == 0) return 1;
	if (mpz_out_raw(f, sec->u) == 0) return 1;
	if (mpz_out_raw(f, sec->dp) == 0) return 1;
	if (mpz_out_raw(f, sec->dq) == 0) return 1;

	return 0;
}

/* read RSA secret key from a key file
 * return 0 on success or 1 on failure
 */
int rsa_read_file_sec(FILE *f, rsa_secret_key *sec)
{
	rsa_init_sec(sec);
	if (mpz_inp_raw(sec->n, f) == 0) return 1;
	if (mpz_inp_raw(sec->e, f) == 0) return 1;
	if (mpz_inp_raw(sec->d, f) == 0) return 1;
	if (mpz_inp_raw(sec->p, f) == 0) return 1;
	if (mpz_inp_raw(sec->q, f) == 0) return 1;
	if (mpz_inp_raw(sec->u, f) == 0) return 1;
	if (mpz_inp_raw(sec->dp, f) == 0) return 1;
	if (mpz_inp_raw(sec->dq, f) == 0) return 1;

	/* check that all the parameters are positive */
	if (mpz_cmp_ui(sec->n, 1) < 0 ||
	    mpz_cmp_ui(sec->e, 1) < 0 ||
	    mpz_cmp_ui(sec->d, 1) < 0 ||
	    mpz_cmp_ui(sec->p, 1) < 0 ||
	    mpz_cmp_ui(sec->q, 1) < 0 ||
	    mpz_cmp_ui(sec->u, 1) < 0 ||
	    mpz_cmp_ui(sec->dp, 1) < 0 ||
	    mpz_cmp_ui(sec->dq, 1) < 0)
		return 1;

	return 0;
}

/* get a random number of given number of bits
 * return 0 on success or 1 on failure
 */
static int rsa_random_int(mpz_t res, int bits)
{
	FILE *f;
	int i, bytes;
	char *s;

	bytes = (bits + 7) / 8;
	s = (char *) malloc(bytes * 2 + 1);
	if (s == NULL) {
		fprintf(stderr, "Not enough memory for number buffer\n");
		return 1;
	}

	/* generate hex presentation of the random number using /dev/random
	 * and then convert the number into a mpz_t */
	f = fopen("/dev/random", "rb");
	if (f == NULL) {
		fprintf(stderr, "Cannot open /dev/random.\n");
		free(s);
		return 1;
	}
	for (i = 0; i < bytes; i++) {
		int tmp = fgetc(f);
		if (tmp < 0 || tmp > 255) {
			fprintf(stderr, "Cannot read /dev/random.\n");
			free(s);
			fclose(f);
			return 1;
		}
		sprintf(s+2*i, "%02x", tmp);
	}
	fclose(f);
	assert(mpz_set_str(res, s, 16) == 0);

	/* don't leave traces of the random number and free temporary space */
	memset(s, 0, 2*bytes);
	free(s);

	/* reduce the number if it was too big */
	mpz_mod_2exp(res, res, bits);

	return 0;
}

/* get a random prime of given number of bits
 * return 0 on success or 1 on failure
 */
int rsa_random_prime(mpz_t res, int bits)
{
	mpz_t tmp;

	/* - get a random integer of requested size
	 * - set its two highest to make sure that the n (=p*q) will be long
	 *   enough
	 * - set its lowest bit to make it odd
	 */

	if (rsa_random_int(res, bits) != 0)
		return 1;

	mpz_init(tmp);
	mpz_set_ui(tmp, 3);
	mpz_mul_2exp(tmp, tmp, bits-2);
	mpz_ior(res, res, tmp);

	mpz_set_ui(tmp, 1);
	mpz_ior(res, res, tmp);

	/* check every odd number, until we get a probable prime */
	while(!mpz_probab_prime_p(res, 25)) {
		fprintf(stderr, ".");
		/* was composite, try next odd number */
		mpz_add_ui(res, res, 2);
	}
	/* ok, prime with probability 1-2^-50 */

	mpz_clear(tmp);

	return 0;
}

/* mpz_invert with results normalized to 0..mod-1 */
static int rsa_mpz_invert_pos(mpz_t res, mpz_t op, mpz_t mod)
{
	int ret = mpz_invert(res, op, mod);

	if (ret == 0)
		return 0;

	if (mpz_cmp_ui(res, 0) < 0)
		mpz_add(res, res, mod);

	return ret;
}


/* generate a RSA key
 * return 0 on success or 1 on failure
 * some extra checks for security of the keys might be added in the future
 */
int rsa_generate_key(int bits, rsa_secret_key *sec)
{
	mpz_t p_1, q_1, phi, tmp;
	int p_bits;
	int q_bits;

	assert(bits > 1 && bits < 65536);

	p_bits = bits / 2;
	q_bits = bits - p_bits;

	rsa_init_sec(sec);

	fprintf(stderr, "generating p: ");
	if (rsa_random_prime(sec->p, p_bits) != 0) {
		rsa_clear_sec(sec);
		return 1;
	}

	fprintf(stderr, "\ngenerating q: ");
	if (rsa_random_prime(sec->q, q_bits) != 0) {
		rsa_clear_sec(sec);
		return 1;
	}

	fprintf(stderr, "\n");

	mpz_mul(sec->n, sec->p, sec->q);

	mpz_init(p_1);
	mpz_init(q_1);
	mpz_init(phi);
	mpz_init(tmp);

	/* phi = (p-1) * (q-1) */
	mpz_sub_ui(p_1, sec->p, 1);
	mpz_sub_ui(q_1, sec->q, 1);
	mpz_mul(phi, p_1, q_1);

	/* e must be relatively prime with phi
	 * start with e = 2^5 + 1 and add 2 until e is relatively prime
	 * to phi */
	mpz_set_ui(sec->e, 31); /* e = 2^5 + 1 - 2 */
	do {
		mpz_add_ui(sec->e, sec->e, 2);
		mpz_gcd(tmp, sec->e, phi);
	} while(mpz_cmp_ui(tmp, 1) != 0);

	/* d = e^-1 mod phi */
	assert(rsa_mpz_invert_pos(sec->d, sec->e, phi) != 0);

	/* u = p^-1 mod q */
	assert(rsa_mpz_invert_pos(sec->u, sec->p, sec->q) != 0);

	/* dp = d mod p-1 */
	mpz_sub_ui(sec->dp, sec->p, 1);
	mpz_mod(sec->dp, sec->d, sec->dp);

	/* dq = d mod q-1 */
	mpz_sub_ui(sec->dq, sec->q, 1);
	mpz_mod(sec->dq, sec->d, sec->dq);

	assert(mpz_cmp(sec->e, phi) < 0);
	assert(mpz_cmp(sec->d, phi) < 0);

	mpz_clear(p_1);
	mpz_clear(q_1);
	mpz_clear(phi);
	mpz_clear(tmp);

	return 0;
}

/* convert a secret RSA key to a public key
 * function initializes the public key
 */
void rsa_secret_public(rsa_secret_key *sec, rsa_public_key *pub)
{
	mpz_init(pub->n);
	mpz_init(pub->e);

	mpz_set(pub->n, sec->n);
	mpz_set(pub->e, sec->e);
}

/* convert mpz_t number to a character buffer */
int jm_mpz_to_buf(mpz_t num, unsigned char *buf)
{
	int bits, hexs;
	char *tmp;
	int in, len, byte;

	bits = mpz_sizeinbase(num, 2);
	hexs = mpz_sizeinbase(num, 16);

	assert(bits <= 65535);

	tmp = (char*) malloc(hexs + 2);
	if (tmp == NULL)
		return -1;
	mpz_get_str(tmp, 16, num);
	in = len = 0;

	/* put length of the number in the buffer, msb first */
	buf[len++] = bits >> 8;
	buf[len++] = bits & 255;

	/* put the possible odd hex digit to the buffer */
	if (hexs & 1) {
		sscanf(tmp + in, "%1x", &byte);
		buf[len++] = byte;
		in++;
	}

	/* put the remaining hex digits to the buffer (two into one byte) */
	for (; in < hexs; in += 2) {
		sscanf(tmp + in, "%2x", &byte);
		buf[len++] = byte;
	}

	memset(tmp, 0, hexs + 2);
	free(tmp);

	assert(len == 2 + (bits + 7) / 8);
	return len;
}

/* convert a character buffer to a mpz_t number */
int jm_buf_to_mpz(const unsigned char *buf, int max_len, mpz_t num)
{
	int bits, bytes, used, i;
	char *tmp;

	if (buf == NULL || max_len < 2)
		return -1;

	used = 0;
	bits = buf[0] * 256 + buf[1];
	bytes = (bits + 7) / 8;
	used += 2;

	if (bytes + used > max_len) {
		printf("bytes=%i + used=%i > max_len=%i\n", bytes, used,
		       max_len);
		return -1; /* not enough data in the buffer */
	}

	tmp = malloc(2 * bytes + 1);
	if (tmp == NULL)
		return -1;

	for (i = 0; i < bytes; i++) {
		sprintf(tmp + i * 2, "%02x", (unsigned char) buf[used + i]);
	}
	used += bytes;

	mpz_set_str(num, tmp, 16);

	memset(tmp, 0, 2 * bytes + 1);
	free(tmp);

	return used;
}

/* convert a public key to a character buffer */
unsigned char *rsa_public_key_buffer(rsa_public_key *pub,
				     unsigned int *buf_len)
{
	int len, used;
	unsigned char *buf;

	if (pub == NULL || buf_len == NULL)
		return NULL;

	len = (mpz_sizeinbase(pub->n, 2) + 7) / 8 + 2 +
		(mpz_sizeinbase(pub->e, 2) + 7) / 8 + 2;
	buf = malloc(len);
	if (buf == NULL)
		return NULL;
	used = jm_mpz_to_buf(pub->n, buf);
	used += jm_mpz_to_buf(pub->e, buf + used);
	assert(used == len);
	*buf_len = len;
	return buf;
}

/* convert a character buffer to a public key */
int rsa_buffer_public_key(const unsigned char *buf, unsigned int max_len,
			  rsa_public_key *pub)
{
	int used, res;

	if (buf == NULL || pub == NULL || max_len < 4)
		return -1;

	mpz_init(pub->n);
	used = res = jm_buf_to_mpz(buf, max_len, pub->n);
	if (res < 0) {
		mpz_clear(pub->n);
		return -1;
	}

	mpz_init(pub->e);
	res = jm_buf_to_mpz(buf + used, max_len - used, pub->e);
	if (res < 0) {
		mpz_clear(pub->n);
		mpz_clear(pub->e);
		return -1;
	}
	used += res;

	assert(used <= max_len);
	return used;
}