tinc-vpn.org Git - tinc/blob - src/gcrypt/rsagen.c

   1 /*
   2     rsagen.c -- RSA key generation and export
   3     Copyright (C) 2008-2022 Guus Sliepen <guus@tinc-vpn.org>
   4
   5     This program is free software; you can redistribute it and/or modify
   6     it under the terms of the GNU General Public License as published by
   7     the Free Software Foundation; either version 2 of the License, or
   8     (at your option) any later version.
   9
  10     This program is distributed in the hope that it will be useful,
  11     but WITHOUT ANY WARRANTY; without even the implied warranty of
  12     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13     GNU General Public License for more details.
  14
  15     You should have received a copy of the GNU General Public License along
  16     with this program; if not, write to the Free Software Foundation, Inc.,
  17     51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
  18 */
  19
  20 #include "../system.h"
  21
  22 #include <gcrypt.h>
  23 #include <assert.h>
  24
  25 #include "asn1.h"
  26 #include "rsa.h"
  27 #include "pem.h"
  28 #include "../rsagen.h"
  29 #include "../xalloc.h"
  30 #include "../utils.h"
  31
  32 static size_t der_tag_len(size_t n) {
  33         if(n < 128) {
  34                 return 2;
  35         }
  36
  37         if(n < 256) {
  38                 return 3;
  39         }
  40
  41         if(n < 65536) {
  42                 return 4;
  43         }
  44
  45         abort();
  46 }
  47
  48 static uint8_t *der_store_tag(uint8_t *p, asn1_tag_t tag, size_t n) {
  49         if(tag == TAG_SEQUENCE) {
  50                 tag |= 0x20;
  51         }
  52
  53         *p++ = tag;
  54
  55         if(n < 128) {
  56                 *p++ = n;
  57         } else if(n < 256) {
  58                 *p++ = 0x81;
  59                 *p++ = n;
  60         } else if(n < 65536) {
  61                 *p++ = 0x82;
  62                 *p++ = n >> 8;
  63                 *p++ = n & 0xff;
  64         } else {
  65                 abort();
  66         }
  67
  68         return p;
  69 }
  70
  71 static size_t der_fill(uint8_t *derbuf, bool is_private, const gcry_mpi_t mpi[], size_t num_mpi) {
  72         size_t needed = 0;
  73         size_t lengths[16] = {0};
  74
  75         assert(num_mpi > 0 && num_mpi < sizeof(lengths) / sizeof(*lengths));
  76
  77         if(is_private) {
  78                 // Add space for the version number.
  79                 needed += der_tag_len(1) + 1;
  80         }
  81
  82         for(size_t i = 0; i < num_mpi; ++i) {
  83                 gcry_mpi_print(GCRYMPI_FMT_STD, NULL, 0, &lengths[i], mpi[i]);
  84                 needed += der_tag_len(lengths[i]) + lengths[i];
  85         }
  86
  87         const size_t derlen = der_tag_len(needed) + needed;
  88
  89         uint8_t *der = derbuf;
  90         der = der_store_tag(der, TAG_SEQUENCE, needed);
  91
  92         if(is_private) {
  93                 // Private key requires storing version number.
  94                 der = der_store_tag(der, TAG_INTEGER, 1);
  95                 *der++ = 0;
  96         }
  97
  98         for(size_t i = 0; i < num_mpi; ++i) {
  99                 const size_t len = lengths[i];
 100                 der = der_store_tag(der, TAG_INTEGER, len);
 101                 gcry_mpi_print(GCRYMPI_FMT_STD, der, len, NULL, mpi[i]);
 102                 der += len;
 103         }
 104
 105         assert((size_t)(der - derbuf) == derlen);
 106         return derlen;
 107 }
 108
 109 bool rsa_write_pem_public_key(rsa_t *rsa, FILE *fp) {
 110         uint8_t derbuf[8096];
 111
 112         gcry_mpi_t params[] = {
 113                 rsa->n,
 114                 rsa->e,
 115         };
 116
 117         size_t derlen = der_fill(derbuf, false, params, sizeof(params) / sizeof(*params));
 118
 119         return pem_encode(fp, "RSA PUBLIC KEY", derbuf, derlen);
 120 }
 121
 122 // Calculate p/q primes from n/e/d.
 123 static void get_p_q(gcry_mpi_t *p,
 124                     gcry_mpi_t *q,
 125                     const gcry_mpi_t n,
 126                     const gcry_mpi_t e,
 127                     const gcry_mpi_t d) {
 128         const size_t nbits = gcry_mpi_get_nbits(n);
 129
 130         gcry_mpi_t k = gcry_mpi_new(nbits);
 131         gcry_mpi_mul(k, e, d);
 132         gcry_mpi_sub_ui(k, k, 1);
 133
 134         size_t t = 0;
 135
 136         while(!gcry_mpi_test_bit(k, t)) {
 137                 ++t;
 138         }
 139
 140         gcry_mpi_t g = gcry_mpi_new(nbits);
 141         gcry_mpi_t gk = gcry_mpi_new(0);
 142         gcry_mpi_t sq = gcry_mpi_new(0);
 143         gcry_mpi_t rem = gcry_mpi_new(0);
 144         gcry_mpi_t gcd = gcry_mpi_new(0);
 145
 146         while(true) {
 147                 gcry_mpi_t kt = gcry_mpi_copy(k);
 148                 gcry_mpi_randomize(g, nbits, GCRY_STRONG_RANDOM);
 149
 150                 size_t i;
 151
 152                 for(i = 0; i < t; ++i) {
 153                         gcry_mpi_rshift(kt, kt, 1);
 154                         gcry_mpi_powm(gk, g, kt, n);
 155
 156                         if(gcry_mpi_cmp_ui(gk, 1) != 0) {
 157                                 gcry_mpi_mul(sq, gk, gk);
 158                                 gcry_mpi_mod(rem, sq, n);
 159
 160                                 if(gcry_mpi_cmp_ui(rem, 1) == 0) {
 161                                         break;
 162                                 }
 163                         }
 164                 }
 165
 166                 gcry_mpi_release(kt);
 167
 168                 if(i < t) {
 169                         gcry_mpi_sub_ui(gk, gk, 1);
 170                         gcry_mpi_gcd(gcd, gk, n);
 171
 172                         if(gcry_mpi_cmp_ui(gcd, 1) != 0) {
 173                                 break;
 174                         }
 175                 }
 176         }
 177
 178         gcry_mpi_release(k);
 179         gcry_mpi_release(g);
 180         gcry_mpi_release(gk);
 181         gcry_mpi_release(sq);
 182         gcry_mpi_release(rem);
 183
 184         *p = gcd;
 185         *q = gcry_mpi_new(0);
 186
 187         gcry_mpi_div(*q, NULL, n, *p, 0);
 188 }
 189
 190 bool rsa_write_pem_private_key(rsa_t *rsa, FILE *fp) {
 191         gcry_mpi_t params[] = {
 192                 rsa->n,
 193                 rsa->e,
 194                 rsa->d,
 195                 NULL, // p
 196                 NULL, // q
 197                 gcry_mpi_new(0), // d mod (p-1)
 198                 gcry_mpi_new(0), // d mod (q-1)
 199                 gcry_mpi_new(0), // u = p^-1 mod q
 200         };
 201
 202         // Indexes into params.
 203         const size_t d = 2;
 204         const size_t p = 3;
 205         const size_t q = 4;
 206         const size_t dp = 5;
 207         const size_t dq = 6;
 208         const size_t u = 7;
 209
 210         // Calculate p and q.
 211         get_p_q(&params[p], &params[q], rsa->n, rsa->e, rsa->d);
 212
 213         // Swap p and q if q > p.
 214         if(gcry_mpi_cmp(params[q], params[p]) > 0) {
 215                 gcry_mpi_swap(params[p], params[q]);
 216         }
 217
 218         // Calculate u.
 219         gcry_mpi_invm(params[u], params[p], params[q]);
 220
 221         // Calculate d mod (p - 1).
 222         gcry_mpi_sub_ui(params[dp], params[p], 1);
 223         gcry_mpi_mod(params[dp], params[d], params[dp]);
 224
 225         // Calculate d mod (q - 1).
 226         gcry_mpi_sub_ui(params[dq], params[q], 1);
 227         gcry_mpi_mod(params[dq], params[d], params[dq]);
 228
 229         uint8_t derbuf[8096];
 230         const size_t nparams = sizeof(params) / sizeof(*params);
 231         size_t derlen = der_fill(derbuf, true, params, nparams);
 232
 233         gcry_mpi_release(params[p]);
 234         gcry_mpi_release(params[q]);
 235         gcry_mpi_release(params[dp]);
 236         gcry_mpi_release(params[dq]);
 237         gcry_mpi_release(params[u]);
 238
 239         bool success = pem_encode(fp, "RSA PRIVATE KEY", derbuf, derlen);
 240         memzero(derbuf, sizeof(derbuf));
 241         return success;
 242 }
 243
 244 static gcry_mpi_t find_mpi(const gcry_sexp_t rsa, const char *token) {
 245         gcry_sexp_t sexp = gcry_sexp_find_token(rsa, token, 1);
 246
 247         if(!sexp) {
 248                 fprintf(stderr, "Token %s not found in RSA S-expression.\n", token);
 249                 return NULL;
 250         }
 251
 252         gcry_mpi_t mpi = gcry_sexp_nth_mpi(sexp, 1, GCRYMPI_FMT_USG);
 253         gcry_sexp_release(sexp);
 254         return mpi;
 255 }
 256
 257 rsa_t *rsa_generate(size_t bits, unsigned long exponent) {
 258         gcry_sexp_t s_params;
 259         gcry_error_t err = gcry_sexp_build(&s_params, NULL,
 260                                            "(genkey"
 261                                            "  (rsa"
 262                                            "    (nbits %u)"
 263                                            "    (rsa-use-e %u)))",
 264                                            bits,
 265                                            exponent);
 266
 267         if(err) {
 268                 fprintf(stderr, "Error building keygen S-expression: %s.\n", gcry_strerror(err));
 269                 return NULL;
 270         }
 271
 272         gcry_sexp_t s_key;
 273         err = gcry_pk_genkey(&s_key, s_params);
 274         gcry_sexp_release(s_params);
 275
 276         if(err) {
 277                 fprintf(stderr, "Error generating RSA key pair: %s.\n", gcry_strerror(err));
 278                 return NULL;
 279         }
 280
 281         // `gcry_sexp_extract_param` can replace everything below
 282         // with a single line, but it's not available on CentOS 7.
 283         gcry_sexp_t s_priv = gcry_sexp_find_token(s_key, "private-key", 0);
 284
 285         if(!s_priv) {
 286                 fprintf(stderr, "Private key not found in gcrypt result.\n");
 287                 gcry_sexp_release(s_key);
 288                 return NULL;
 289         }
 290
 291         gcry_sexp_t s_rsa = gcry_sexp_find_token(s_priv, "rsa", 0);
 292
 293         if(!s_rsa) {
 294                 fprintf(stderr, "RSA not found in gcrypt result.\n");
 295                 gcry_sexp_release(s_priv);
 296                 gcry_sexp_release(s_key);
 297                 return NULL;
 298         }
 299
 300         rsa_t *rsa = rsa_new();
 301
 302         rsa->n = find_mpi(s_rsa, "n");
 303         rsa->e = find_mpi(s_rsa, "e");
 304         rsa->d = find_mpi(s_rsa, "d");
 305
 306         gcry_sexp_release(s_rsa);
 307         gcry_sexp_release(s_priv);
 308         gcry_sexp_release(s_key);
 309
 310         if(rsa->n && rsa->e && rsa->d) {
 311                 return rsa;
 312         }
 313
 314         rsa_free(rsa);
 315         return NULL;
 316 }