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