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"
27 #include "../rsagen.h"
28 #include "../xalloc.h"
36 static size_t der_tag_len(size_t n) {
52 static uint8_t *der_store_tag(uint8_t *p, asn1_tag_t tag, size_t n) {
53 if(tag == TAG_SEQUENCE) {
64 } else if(n < 65536) {
75 static size_t der_fill(uint8_t *derbuf, bool is_private, const gcry_mpi_t mpi[], size_t num_mpi) {
77 size_t lengths[16] = {0};
79 assert(num_mpi > 0 && num_mpi < sizeof(lengths) / sizeof(*lengths));
82 // Add space for the version number.
83 needed += der_tag_len(1) + 1;
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];
91 const size_t derlen = der_tag_len(needed) + needed;
93 uint8_t *der = derbuf;
94 der = der_store_tag(der, TAG_SEQUENCE, needed);
97 // Private key requires storing version number.
98 der = der_store_tag(der, TAG_INTEGER, 1);
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]);
109 assert((size_t)(der - derbuf) == derlen);
113 bool rsa_write_pem_public_key(rsa_t *rsa, FILE *fp) {
114 uint8_t derbuf[8096];
116 gcry_mpi_t params[] = {
121 size_t derlen = der_fill(derbuf, false, params, sizeof(params) / sizeof(*params));
123 return pem_encode(fp, "RSA PUBLIC KEY", derbuf, derlen);
126 // Calculate p/q primes from n/e/d.
127 static void get_p_q(gcry_mpi_t *p,
131 const gcry_mpi_t d) {
132 const size_t nbits = gcry_mpi_get_nbits(n);
134 gcry_mpi_t k = gcry_mpi_new(nbits);
135 gcry_mpi_mul(k, e, d);
136 gcry_mpi_sub_ui(k, k, 1);
140 while(!gcry_mpi_test_bit(k, t)) {
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);
151 gcry_mpi_t kt = gcry_mpi_copy(k);
152 gcry_mpi_randomize(g, nbits, GCRY_STRONG_RANDOM);
156 for(i = 0; i < t; ++i) {
157 gcry_mpi_rshift(kt, kt, 1);
158 gcry_mpi_powm(gk, g, kt, n);
160 if(gcry_mpi_cmp_ui(gk, 1) != 0) {
161 gcry_mpi_mul(sq, gk, gk);
162 gcry_mpi_mod(rem, sq, n);
164 if(gcry_mpi_cmp_ui(rem, 1) == 0) {
170 gcry_mpi_release(kt);
173 gcry_mpi_sub_ui(gk, gk, 1);
174 gcry_mpi_gcd(gcd, gk, n);
176 if(gcry_mpi_cmp_ui(gcd, 1) != 0) {
184 gcry_mpi_release(gk);
185 gcry_mpi_release(sq);
186 gcry_mpi_release(rem);
189 *q = gcry_mpi_new(0);
191 gcry_mpi_div(*q, NULL, n, *p, 0);
194 bool rsa_write_pem_private_key(rsa_t *rsa, FILE *fp) {
195 gcry_mpi_t params[] = {
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
206 // Indexes into params.
214 // Calculate p and q.
215 get_p_q(¶ms[p], ¶ms[q], rsa->n, rsa->e, rsa->d);
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]);
223 gcry_mpi_invm(params[u], params[p], params[q]);
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]);
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]);
233 uint8_t derbuf[8096];
234 const size_t nparams = sizeof(params) / sizeof(*params);
235 size_t derlen = der_fill(derbuf, true, params, nparams);
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]);
243 return pem_encode(fp, "RSA PRIVATE KEY", derbuf, derlen);
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);
250 fprintf(stderr, "Token %s not found in RSA S-expression.\n", token);
254 gcry_mpi_t mpi = gcry_sexp_nth_mpi(sexp, 1, GCRYMPI_FMT_USG);
255 gcry_sexp_release(sexp);
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,
270 fprintf(stderr, "Error building keygen S-expression: %s.\n", gcry_strerror(err));
275 err = gcry_pk_genkey(&s_key, s_params);
276 gcry_sexp_release(s_params);
279 fprintf(stderr, "Error generating RSA key pair: %s.\n", gcry_strerror(err));
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);
288 fprintf(stderr, "Private key not found in gcrypt result.\n");
289 gcry_sexp_release(s_key);
293 gcry_sexp_t s_rsa = gcry_sexp_find_token(s_priv, "rsa", 0);
296 fprintf(stderr, "RSA not found in gcrypt result.\n");
297 gcry_sexp_release(s_priv);
298 gcry_sexp_release(s_key);
302 rsa_t *rsa = xzalloc(sizeof(*rsa));
304 rsa->n = find_mpi(s_rsa, "n");
305 rsa->e = find_mpi(s_rsa, "e");
306 rsa->d = find_mpi(s_rsa, "d");
308 gcry_sexp_release(s_rsa);
309 gcry_sexp_release(s_priv);
310 gcry_sexp_release(s_key);
312 if(rsa->n && rsa->e && rsa->d) {