305 lines · c
1/*2 Name: rsakey.c3 Purpose: Generate keys for the RSA cryptosystem.4 Author: M. J. Fromberger5 6 Usage: rsakey [-e <expt>] <modbits> [<outfile>]7 8 Generates an RSA key pair with a modulus having <modbits> significant bits,9 and writes it to the specified output file, or to the standard output. The10 -e option allows the user to specify an encryption exponent; otherwise, an11 encryption exponent is chosen at random.12 13 Primes p and q are obtained by reading random bits from /dev/random, setting14 the low-order bit, and testing for primality. If the first candidate is not15 prime, successive odd candidates are tried until a probable prime is found.16 17 Copyright (C) 2002-2008 Michael J. Fromberger, All Rights Reserved.18 19 Permission is hereby granted, free of charge, to any person obtaining a copy20 of this software and associated documentation files (the "Software"), to deal21 in the Software without restriction, including without limitation the rights22 to use, copy, modify, merge, publish, distribute, sublicense, and/or sell23 copies of the Software, and to permit persons to whom the Software is24 furnished to do so, subject to the following conditions:25 26 The above copyright notice and this permission notice shall be included in27 all copies or substantial portions of the Software.28 29 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR30 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,31 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE32 AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER33 LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,34 OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE35 SOFTWARE.36 */37 38#include <errno.h>39#include <limits.h>40#include <stdio.h>41#include <stdlib.h>42#include <string.h>43 44#include <getopt.h>45#include <unistd.h>46 47#include "imath.h"48#include "iprime.h"49 50typedef struct {51 mpz_t p;52 mpz_t q;53 mpz_t n;54 mpz_t e;55 mpz_t d;56} rsa_key;57 58/* Load the specified buffer with random bytes */59int randomize(unsigned char *buf, size_t len);60 61/* Overwrite the specified value with n_bits random bits */62mp_result mp_int_randomize(mp_int a, mp_size n_bits);63 64/* Find a prime starting from the given odd seed */65mp_result find_prime(mp_int seed, FILE *fb);66 67/* Initialize/destroy an rsa_key structure */68mp_result rsa_key_init(rsa_key *kp);69void rsa_key_clear(rsa_key *kp);70void rsa_key_write(rsa_key *kp, FILE *ofp);71 72int main(int argc, char *argv[]) {73 int opt, modbits;74 FILE *ofp = stdout;75 char *expt = NULL;76 rsa_key the_key;77 mp_result res;78 79 /* Process command-line arguments */80 while ((opt = getopt(argc, argv, "e:")) != EOF) {81 switch (opt) {82 case 'e':83 expt = optarg;84 break;85 default:86 fprintf(stderr, "Usage: rsakey [-e <expt>] <modbits> [<outfile>]\n");87 return 1;88 }89 }90 91 if (optind >= argc) {92 fprintf(stderr, "Error: You must specify the number of modulus bits.\n");93 fprintf(stderr, "Usage: rsakey [-e <expt>] <modbits> [<outfile>]\n");94 return 1;95 }96 modbits = (int)strtol(argv[optind++], NULL, 0);97 if (modbits < CHAR_BIT) {98 fprintf(stderr, "Error: Invalid value for number of modulus bits.\n");99 return 1;100 }101 if (modbits % 2 == 1) ++modbits;102 103 /* Check if output file is specified */104 if (optind < argc) {105 if ((ofp = fopen(argv[optind], "wt")) == NULL) {106 fprintf(stderr,107 "Error: Unable to open output file for writing.\n"108 " - Filename: %s\n"109 " - Error: %s\n",110 argv[optind], strerror(errno));111 return 1;112 }113 }114 115 if ((res = rsa_key_init(&the_key)) != MP_OK) {116 fprintf(stderr,117 "Error initializing RSA key structure:\n"118 " - %s (%d)\n",119 mp_error_string(res), res);120 return 1;121 }122 123 /* If specified, try to load the key exponent */124 if (expt != NULL) {125 if ((res = mp_int_read_string(&(the_key.e), 10, expt)) != MP_OK) {126 fprintf(stderr,127 "Error: Invalid value for encryption exponent.\n"128 " - %s (%d)\n",129 mp_error_string(res), res);130 goto EXIT;131 }132 }133 134 if ((res = mp_int_randomize(&(the_key.p), (modbits / 2))) != MP_OK) {135 fprintf(stderr,136 "Error: Unable to randomize first prime.\n"137 " - %s (%d)\n",138 mp_error_string(res), res);139 goto EXIT;140 }141 fprintf(stderr, "p: ");142 find_prime(&(the_key.p), stderr);143 144 if ((res = mp_int_randomize(&(the_key.q), (modbits / 2))) != MP_OK) {145 fprintf(stderr,146 "Error: Unable to randomize second prime.\n"147 " - %s (%d)\n",148 mp_error_string(res), res);149 goto EXIT;150 }151 fprintf(stderr, "\nq: ");152 find_prime(&(the_key.q), stderr);153 fputc('\n', stderr);154 155 /* Temporarily, the key's "n" field will be (p - 1) * (q - 1) for156 purposes of computing the decryption exponent.157 */158 mp_int_mul(&(the_key.p), &(the_key.q), &(the_key.n));159 mp_int_sub(&(the_key.n), &(the_key.p), &(the_key.n));160 mp_int_sub(&(the_key.n), &(the_key.q), &(the_key.n));161 mp_int_add_value(&(the_key.n), 1, &(the_key.n));162 163 if (expt == NULL &&164 (res = mp_int_randomize(&(the_key.e), (modbits / 2))) != MP_OK) {165 fprintf(stderr,166 "Error: Unable to randomize encryption exponent.\n"167 " - %s (%d)\n",168 mp_error_string(res), res);169 goto EXIT;170 }171 while ((res = mp_int_invmod(&(the_key.e), &(the_key.n), &(the_key.d))) !=172 MP_OK) {173 if (expt != NULL) {174 fprintf(stderr,175 "Error: Unable to compute decryption exponent.\n"176 " - %s (%d)\n",177 mp_error_string(res), res);178 goto EXIT;179 }180 if ((res = mp_int_randomize(&(the_key.e), (modbits / 2))) != MP_OK) {181 fprintf(stderr,182 "Error: Unable to re-randomize encryption exponent.\n"183 " - %s (%d)\n",184 mp_error_string(res), res);185 goto EXIT;186 }187 }188 189 /* Recompute the real modulus, now that exponents are done. */190 mp_int_mul(&(the_key.p), &(the_key.q), &(the_key.n));191 192 /* Write completed key to the specified output file */193 rsa_key_write(&the_key, ofp);194 195EXIT:196 fclose(ofp);197 rsa_key_clear(&the_key);198 return 0;199}200 201int randomize(unsigned char *buf, size_t len) {202 FILE *rnd = fopen("/dev/random", "rb");203 size_t nr;204 205 if (rnd == NULL) return -1;206 207 nr = fread(buf, sizeof(*buf), len, rnd);208 fclose(rnd);209 210 return (int)nr;211}212 213mp_result mp_int_randomize(mp_int a, mp_size n_bits) {214 mp_size n_bytes = (n_bits + CHAR_BIT - 1) / CHAR_BIT;215 unsigned char *buf;216 mp_result res = MP_OK;217 218 if ((buf = malloc(n_bytes)) == NULL) return MP_MEMORY;219 220 if ((mp_size)randomize(buf, n_bytes) != n_bytes) {221 res = MP_TRUNC;222 goto CLEANUP;223 }224 225 /* Clear bits beyond the number requested */226 if (n_bits % CHAR_BIT != 0) {227 unsigned char b_mask = (1 << (n_bits % CHAR_BIT)) - 1;228 unsigned char t_mask = (1 << (n_bits % CHAR_BIT)) >> 1;229 230 buf[0] &= b_mask;231 buf[0] |= t_mask;232 }233 234 /* Set low-order bit to insure value is odd */235 buf[n_bytes - 1] |= 1;236 237 res = mp_int_read_unsigned(a, buf, n_bytes);238 239CLEANUP:240 memset(buf, 0, n_bytes);241 free(buf);242 243 return res;244}245 246mp_result find_prime(mp_int seed, FILE *fb) {247 mp_result res;248 int count = 0;249 250 if (mp_int_is_even(seed))251 if ((res = mp_int_add_value(seed, 1, seed)) != MP_OK) return res;252 253 while ((res = mp_int_is_prime(seed)) == MP_FALSE) {254 ++count;255 256 if (fb != NULL && (count % 50) == 0) fputc('.', fb);257 258 if ((res = mp_int_add_value(seed, 2, seed)) != MP_OK) return res;259 }260 261 if (res == MP_TRUE && fb != NULL) fputc('+', fb);262 263 return res;264}265 266mp_result rsa_key_init(rsa_key *kp) {267 mp_int_init(&(kp->p));268 mp_int_init(&(kp->q));269 mp_int_init(&(kp->n));270 mp_int_init(&(kp->e));271 mp_int_init(&(kp->d));272 273 return MP_OK;274}275 276void rsa_key_clear(rsa_key *kp) {277 mp_int_clear(&(kp->p));278 mp_int_clear(&(kp->q));279 mp_int_clear(&(kp->n));280 mp_int_clear(&(kp->e));281 mp_int_clear(&(kp->d));282}283 284void rsa_key_write(rsa_key *kp, FILE *ofp) {285 int len;286 char *obuf;287 288 len = mp_int_string_len(&(kp->n), 10);289 obuf = malloc(len);290 mp_int_to_string(&(kp->p), 10, obuf, len);291 fprintf(ofp, "p = %s\n", obuf);292 mp_int_to_string(&(kp->q), 10, obuf, len);293 fprintf(ofp, "q = %s\n", obuf);294 mp_int_to_string(&(kp->e), 10, obuf, len);295 fprintf(ofp, "e = %s\n", obuf);296 mp_int_to_string(&(kp->d), 10, obuf, len);297 fprintf(ofp, "d = %s\n", obuf);298 mp_int_to_string(&(kp->n), 10, obuf, len);299 fprintf(ofp, "n = %s\n", obuf);300 301 free(obuf);302}303 304/* Here there be dragons */305