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"
37 static size_t der_tag_len(size_t n) {
53 static uint8_t *der_store_tag(uint8_t *p, asn1_tag_t tag, size_t n) {
54 if(tag == TAG_SEQUENCE) {
65 } else if(n < 65536) {
76 static size_t der_fill(uint8_t *derbuf, bool is_private, const gcry_mpi_t mpi[], size_t num_mpi) {
78 size_t lengths[16] = {0};
80 assert(num_mpi > 0 && num_mpi < sizeof(lengths) / sizeof(*lengths));
83 // Add space for the version number.
84 needed += der_tag_len(1) + 1;
87 for(size_t i = 0; i < num_mpi; ++i) {
88 gcry_mpi_print(GCRYMPI_FMT_STD, NULL, 0, &lengths[i], mpi[i]);
89 needed += der_tag_len(lengths[i]) + lengths[i];
92 const size_t derlen = der_tag_len(needed) + needed;
94 uint8_t *der = derbuf;
95 der = der_store_tag(der, TAG_SEQUENCE, needed);
98 // Private key requires storing version number.
99 der = der_store_tag(der, TAG_INTEGER, 1);
103 for(size_t i = 0; i < num_mpi; ++i) {
104 const size_t len = lengths[i];
105 der = der_store_tag(der, TAG_INTEGER, len);
106 gcry_mpi_print(GCRYMPI_FMT_STD, der, len, NULL, mpi[i]);
110 assert((size_t)(der - derbuf) == derlen);
114 bool rsa_write_pem_public_key(rsa_t *rsa, FILE *fp) {
115 uint8_t derbuf[8096];
117 gcry_mpi_t params[] = {
122 size_t derlen = der_fill(derbuf, false, params, sizeof(params) / sizeof(*params));
124 return pem_encode(fp, "RSA PUBLIC KEY", derbuf, derlen);
127 // Calculate p/q primes from n/e/d.
128 static void get_p_q(gcry_mpi_t *p,
132 const gcry_mpi_t d) {
133 const size_t nbits = gcry_mpi_get_nbits(n);
135 gcry_mpi_t k = gcry_mpi_new(nbits);
136 gcry_mpi_mul(k, e, d);
137 gcry_mpi_sub_ui(k, k, 1);
141 while(!gcry_mpi_test_bit(k, t)) {
145 gcry_mpi_t g = gcry_mpi_new(nbits);
146 gcry_mpi_t gk = gcry_mpi_new(0);
147 gcry_mpi_t sq = gcry_mpi_new(0);
148 gcry_mpi_t rem = gcry_mpi_new(0);
149 gcry_mpi_t gcd = gcry_mpi_new(0);
152 gcry_mpi_t kt = gcry_mpi_copy(k);
153 gcry_mpi_randomize(g, nbits, GCRY_STRONG_RANDOM);
157 for(i = 0; i < t; ++i) {
158 gcry_mpi_rshift(kt, kt, 1);
159 gcry_mpi_powm(gk, g, kt, n);
161 if(gcry_mpi_cmp_ui(gk, 1) != 0) {
162 gcry_mpi_mul(sq, gk, gk);
163 gcry_mpi_mod(rem, sq, n);
165 if(gcry_mpi_cmp_ui(rem, 1) == 0) {
171 gcry_mpi_release(kt);
174 gcry_mpi_sub_ui(gk, gk, 1);
175 gcry_mpi_gcd(gcd, gk, n);
177 if(gcry_mpi_cmp_ui(gcd, 1) != 0) {
185 gcry_mpi_release(gk);
186 gcry_mpi_release(sq);
187 gcry_mpi_release(rem);
190 *q = gcry_mpi_new(0);
192 gcry_mpi_div(*q, NULL, n, *p, 0);
195 bool rsa_write_pem_private_key(rsa_t *rsa, FILE *fp) {
196 gcry_mpi_t params[] = {
202 gcry_mpi_new(0), // d mod (p-1)
203 gcry_mpi_new(0), // d mod (q-1)
204 gcry_mpi_new(0), // u = p^-1 mod q
207 // Indexes into params.
215 // Calculate p and q.
216 get_p_q(¶ms[p], ¶ms[q], rsa->n, rsa->e, rsa->d);
218 // Swap p and q if q > p.
219 if(gcry_mpi_cmp(params[q], params[p]) > 0) {
220 gcry_mpi_swap(params[p], params[q]);
224 gcry_mpi_invm(params[u], params[p], params[q]);
226 // Calculate d mod (p - 1).
227 gcry_mpi_sub_ui(params[dp], params[p], 1);
228 gcry_mpi_mod(params[dp], params[d], params[dp]);
230 // Calculate d mod (q - 1).
231 gcry_mpi_sub_ui(params[dq], params[q], 1);
232 gcry_mpi_mod(params[dq], params[d], params[dq]);
234 uint8_t derbuf[8096];
235 const size_t nparams = sizeof(params) / sizeof(*params);
236 size_t derlen = der_fill(derbuf, true, params, nparams);
238 gcry_mpi_release(params[p]);
239 gcry_mpi_release(params[q]);
240 gcry_mpi_release(params[dp]);
241 gcry_mpi_release(params[dq]);
242 gcry_mpi_release(params[u]);
244 bool success = pem_encode(fp, "RSA PRIVATE KEY", derbuf, derlen);
245 memzero(derbuf, sizeof(derbuf));
249 static gcry_mpi_t find_mpi(const gcry_sexp_t rsa, const char *token) {
250 gcry_sexp_t sexp = gcry_sexp_find_token(rsa, token, 1);
253 fprintf(stderr, "Token %s not found in RSA S-expression.\n", token);
257 gcry_mpi_t mpi = gcry_sexp_nth_mpi(sexp, 1, GCRYMPI_FMT_USG);
258 gcry_sexp_release(sexp);
262 rsa_t *rsa_generate(size_t bits, unsigned long exponent) {
263 gcry_sexp_t s_params;
264 gcry_error_t err = gcry_sexp_build(&s_params, NULL,
273 fprintf(stderr, "Error building keygen S-expression: %s.\n", gcry_strerror(err));
278 err = gcry_pk_genkey(&s_key, s_params);
279 gcry_sexp_release(s_params);
282 fprintf(stderr, "Error generating RSA key pair: %s.\n", gcry_strerror(err));
286 // `gcry_sexp_extract_param` can replace everything below
287 // with a single line, but it's not available on CentOS 7.
288 gcry_sexp_t s_priv = gcry_sexp_find_token(s_key, "private-key", 0);
291 fprintf(stderr, "Private key not found in gcrypt result.\n");
292 gcry_sexp_release(s_key);
296 gcry_sexp_t s_rsa = gcry_sexp_find_token(s_priv, "rsa", 0);
299 fprintf(stderr, "RSA not found in gcrypt result.\n");
300 gcry_sexp_release(s_priv);
301 gcry_sexp_release(s_key);
305 rsa_t *rsa = xzalloc(sizeof(*rsa));
307 rsa->n = find_mpi(s_rsa, "n");
308 rsa->e = find_mpi(s_rsa, "e");
309 rsa->d = find_mpi(s_rsa, "d");
311 gcry_sexp_release(s_rsa);
312 gcry_sexp_release(s_priv);
313 gcry_sexp_release(s_key);
315 if(rsa->n && rsa->e && rsa->d) {