2 rsagen.c -- RSA key generation and export
3 Copyright (C) 2008-2022 Guus Sliepen <guus@tinc-vpn.org>
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.
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.
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.
20 #include "../system.h"
28 #include "../rsagen.h"
29 #include "../xalloc.h"
32 static size_t der_tag_len(size_t n) {
48 static uint8_t *der_store_tag(uint8_t *p, asn1_tag_t tag, size_t n) {
49 if(tag == TAG_SEQUENCE) {
60 } else if(n < 65536) {
71 static size_t der_fill(uint8_t *derbuf, bool is_private, const gcry_mpi_t mpi[], size_t num_mpi) {
73 size_t lengths[16] = {0};
75 assert(num_mpi > 0 && num_mpi < sizeof(lengths) / sizeof(*lengths));
78 // Add space for the version number.
79 needed += der_tag_len(1) + 1;
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];
87 const size_t derlen = der_tag_len(needed) + needed;
89 uint8_t *der = derbuf;
90 der = der_store_tag(der, TAG_SEQUENCE, needed);
93 // Private key requires storing version number.
94 der = der_store_tag(der, TAG_INTEGER, 1);
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]);
105 assert((size_t)(der - derbuf) == derlen);
109 bool rsa_write_pem_public_key(rsa_t *rsa, FILE *fp) {
110 uint8_t derbuf[8096];
112 gcry_mpi_t params[] = {
117 size_t derlen = der_fill(derbuf, false, params, sizeof(params) / sizeof(*params));
119 return pem_encode(fp, "RSA PUBLIC KEY", derbuf, derlen);
122 // Calculate p/q primes from n/e/d.
123 static void get_p_q(gcry_mpi_t *p,
127 const gcry_mpi_t d) {
128 const size_t nbits = gcry_mpi_get_nbits(n);
130 gcry_mpi_t k = gcry_mpi_new(nbits);
131 gcry_mpi_mul(k, e, d);
132 gcry_mpi_sub_ui(k, k, 1);
136 while(!gcry_mpi_test_bit(k, t)) {
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);
147 gcry_mpi_t kt = gcry_mpi_copy(k);
148 gcry_mpi_randomize(g, nbits, GCRY_STRONG_RANDOM);
152 for(i = 0; i < t; ++i) {
153 gcry_mpi_rshift(kt, kt, 1);
154 gcry_mpi_powm(gk, g, kt, n);
156 if(gcry_mpi_cmp_ui(gk, 1) != 0) {
157 gcry_mpi_mul(sq, gk, gk);
158 gcry_mpi_mod(rem, sq, n);
160 if(gcry_mpi_cmp_ui(rem, 1) == 0) {
166 gcry_mpi_release(kt);
169 gcry_mpi_sub_ui(gk, gk, 1);
170 gcry_mpi_gcd(gcd, gk, n);
172 if(gcry_mpi_cmp_ui(gcd, 1) != 0) {
180 gcry_mpi_release(gk);
181 gcry_mpi_release(sq);
182 gcry_mpi_release(rem);
185 *q = gcry_mpi_new(0);
187 gcry_mpi_div(*q, NULL, n, *p, 0);
190 bool rsa_write_pem_private_key(rsa_t *rsa, FILE *fp) {
191 gcry_mpi_t params[] = {
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
202 // Indexes into params.
210 // Calculate p and q.
211 get_p_q(¶ms[p], ¶ms[q], rsa->n, rsa->e, rsa->d);
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]);
219 gcry_mpi_invm(params[u], params[p], params[q]);
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]);
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]);
229 uint8_t derbuf[8096];
230 const size_t nparams = sizeof(params) / sizeof(*params);
231 size_t derlen = der_fill(derbuf, true, params, nparams);
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]);
239 bool success = pem_encode(fp, "RSA PRIVATE KEY", derbuf, derlen);
240 memzero(derbuf, sizeof(derbuf));
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);
248 fprintf(stderr, "Token %s not found in RSA S-expression.\n", token);
252 gcry_mpi_t mpi = gcry_sexp_nth_mpi(sexp, 1, GCRYMPI_FMT_USG);
253 gcry_sexp_release(sexp);
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,
268 fprintf(stderr, "Error building keygen S-expression: %s.\n", gcry_strerror(err));
273 err = gcry_pk_genkey(&s_key, s_params);
274 gcry_sexp_release(s_params);
277 fprintf(stderr, "Error generating RSA key pair: %s.\n", gcry_strerror(err));
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);
286 fprintf(stderr, "Private key not found in gcrypt result.\n");
287 gcry_sexp_release(s_key);
291 gcry_sexp_t s_rsa = gcry_sexp_find_token(s_priv, "rsa", 0);
294 fprintf(stderr, "RSA not found in gcrypt result.\n");
295 gcry_sexp_release(s_priv);
296 gcry_sexp_release(s_key);
300 rsa_t *rsa = xzalloc(sizeof(*rsa));
302 rsa->n = find_mpi(s_rsa, "n");
303 rsa->e = find_mpi(s_rsa, "e");
304 rsa->d = find_mpi(s_rsa, "d");
306 gcry_sexp_release(s_rsa);
307 gcry_sexp_release(s_priv);
308 gcry_sexp_release(s_key);
310 if(rsa->n && rsa->e && rsa->d) {