userapps/opensource/sshd/genrsa.c

   1 /*
   2  * Dropbear - a SSH2 server
   3  *
   4  * Copyright (c) 2002,2003 Matt Johnston
   5  * All rights reserved.
   6  *
   7  * Permission is hereby granted, free of charge, to any person obtaining a copy
   8  * of this software and associated documentation files (the "Software"), to deal
   9  * in the Software without restriction, including without limitation the rights
  10  * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
  11  * copies of the Software, and to permit persons to whom the Software is
  12  * furnished to do so, subject to the following conditions:
  13  *
  14  * The above copyright notice and this permission notice shall be included in
  15  * all copies or substantial portions of the Software.
  16  *
  17  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  18  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  19  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  20  * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  21  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  22  * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
  23  * SOFTWARE. */
  24
  25 #include "includes.h"
  26 #include "dbutil.h"
  27 #include "bignum.h"
  28 #include "random.h"
  29 #include "rsa.h"
  30 #include "genrsa.h"
  31
  32 #define RSA_E 65537
  33
  34 #ifdef DROPBEAR_RSA
  35
  36 static void getrsaprime(mp_int* prime, mp_int *primeminus,
  37                 mp_int* rsa_e, unsigned int size);
  38
  39 /* mostly taken from libtomcrypt's rsa key generation routine */
  40 rsa_key * gen_rsa_priv_key(unsigned int size) {
  41
  42         rsa_key * key;
  43         DEF_MP_INT(pminus);
  44         DEF_MP_INT(qminus);
  45         DEF_MP_INT(lcm);
  46
  47         key = (rsa_key*)m_malloc(sizeof(rsa_key));
  48
  49         key->e = (mp_int*)m_malloc(sizeof(mp_int));
  50         key->n = (mp_int*)m_malloc(sizeof(mp_int));
  51         key->d = (mp_int*)m_malloc(sizeof(mp_int));
  52         key->p = (mp_int*)m_malloc(sizeof(mp_int));
  53         key->q = (mp_int*)m_malloc(sizeof(mp_int));
  54
  55         m_mp_init_multi(key->e, key->n, key->d, key->p, key->q,
  56                         &pminus, &lcm, &qminus, NULL);
  57
  58         seedrandom();
  59
  60         if (mp_set_int(key->e, RSA_E) != MP_OKAY) {
  61                 fprintf(stderr, "rsa generation failed\n");
  62                 exit(1);
  63         }
  64
  65         /* PuTTY doesn't like it if the modulus isn't a multiple of 8 bits,
  66          * so we just generate them until we get one which is OK */
  67         getrsaprime(key->p, &pminus, key->e, size/2);
  68         do {
  69                 getrsaprime(key->q, &qminus, key->e, size/2);
  70
  71                 if (mp_mul(key->p, key->q, key->n) != MP_OKAY) {
  72                         fprintf(stderr, "rsa generation failed\n");
  73                         exit(1);
  74                 }
  75         } while (mp_count_bits(key->n) % 8 != 0);
  76
  77         /* lcm(p-1, q-1) */
  78         if (mp_lcm(&pminus, &qminus, &lcm) != MP_OKAY) {
  79                 fprintf(stderr, "rsa generation failed\n");
  80                 exit(1);
  81         }
  82
  83         /* de = 1 mod lcm(p-1,q-1) */
  84         /* therefore d = (e^-1) mod lcm(p-1,q-1) */
  85         if (mp_invmod(key->e, &lcm, key->d) != MP_OKAY) {
  86                 fprintf(stderr, "rsa generation failed\n");
  87                 exit(1);
  88         }
  89
  90         mp_clear_multi(&pminus, &qminus, &lcm, NULL);
  91
  92         return key;
  93 }
  94
  95 /* return a prime suitable for p or q */
  96 static void getrsaprime(mp_int* prime, mp_int *primeminus,
  97                 mp_int* rsa_e, unsigned int size) {
  98
  99         unsigned char *buf;
 100         DEF_MP_INT(temp_gcd);
 101
 102         buf = (unsigned char*)m_malloc(size+1);
 103
 104         m_mp_init(&temp_gcd);
 105         do {
 106                 /* generate a random odd number with MSB set, then find the
 107                    the next prime above it */
 108                 genrandom(buf, size+1);
 109                 buf[0] |= 0x80; /* MSB set */
 110
 111                 bytes_to_mp(prime, buf, size+1);
 112
 113                 /* find the next integer which is prime, 8 round of miller-rabin */
 114                 if (mp_prime_next_prime(prime, 8, 0) != MP_OKAY) {
 115                         fprintf(stderr, "rsa generation failed\n");
 116                         exit(1);
 117                 }
 118
 119                 /* subtract one to get p-1 */
 120                 if (mp_sub_d(prime, 1, primeminus) != MP_OKAY) {
 121                         fprintf(stderr, "rsa generation failed\n");
 122                         exit(1);
 123                 }
 124                 /* check relative primality to e */
 125                 if (mp_gcd(primeminus, rsa_e, &temp_gcd) != MP_OKAY) {
 126                         fprintf(stderr, "rsa generation failed\n");
 127                         exit(1);
 128                 }
 129         } while (mp_cmp_d(&temp_gcd, 1) != MP_EQ); /* while gcd(p-1, e) != 1 */
 130
 131         /* now we have a good value for result */
 132         mp_clear(&temp_gcd);
 133         m_burn(buf, size+1);
 134         m_free(buf);
 135 }
 136
 137 #endif /* DROPBEAR_RSA */