1 // SPDX-License-Identifier: BSD-2-Clause
2 /* LibTomCrypt, modular cryptographic library -- Tom St Denis
3 *
4 * LibTomCrypt is a library that provides various cryptographic
5 * algorithms in a highly modular and flexible manner.
6 *
7 * The library is free for all purposes without any express
8 * guarantee it works.
9 */
10 #include "tomcrypt_private.h"
11
12 /**
13 @file rsa_make_key.c
14 RSA key generation, Tom St Denis
15 */
16
17 #ifdef LTC_MRSA
18
s_rsa_make_key(prng_state * prng,int wprng,int size,void * e,rsa_key * key)19 static int s_rsa_make_key(prng_state *prng, int wprng, int size, void *e, rsa_key *key)
20 {
21 void *p, *q, *tmp1, *tmp2;
22 int err;
23
24 LTC_ARGCHK(ltc_mp.name != NULL);
25 LTC_ARGCHK(key != NULL);
26 LTC_ARGCHK(size > 0);
27
28 if ((err = prng_is_valid(wprng)) != CRYPT_OK) {
29 return err;
30 }
31
32 if ((err = mp_init_multi(&p, &q, &tmp1, &tmp2, NULL)) != CRYPT_OK) {
33 return err;
34 }
35
36 /* make primes p and q (optimization provided by Wayne Scott) */
37
38 /* make prime "p" */
39 do {
40 if ((err = rand_prime( p, size/2, prng, wprng)) != CRYPT_OK) { goto cleanup; }
41 if ((err = mp_sub_d( p, 1, tmp1)) != CRYPT_OK) { goto cleanup; } /* tmp1 = p-1 */
42 if ((err = mp_gcd( tmp1, e, tmp2)) != CRYPT_OK) { goto cleanup; } /* tmp2 = gcd(p-1, e) */
43 } while (mp_cmp_d( tmp2, 1) != 0); /* while e divides p-1 */
44
45 /* make prime "q" */
46 do {
47 if ((err = rand_prime( q, size/2, prng, wprng)) != CRYPT_OK) { goto cleanup; }
48 if ((err = mp_sub_d( q, 1, tmp1)) != CRYPT_OK) { goto cleanup; } /* tmp1 = q-1 */
49 if ((err = mp_gcd( tmp1, e, tmp2)) != CRYPT_OK) { goto cleanup; } /* tmp2 = gcd(q-1, e) */
50 } while (mp_cmp_d( tmp2, 1) != 0); /* while e divides q-1 */
51
52 /* tmp1 = lcm(p-1, q-1) */
53 if ((err = mp_sub_d( p, 1, tmp2)) != CRYPT_OK) { goto cleanup; } /* tmp2 = p-1 */
54 /* tmp1 = q-1 (previous do/while loop) */
55 if ((err = mp_lcm( tmp1, tmp2, tmp1)) != CRYPT_OK) { goto cleanup; } /* tmp1 = lcm(p-1, q-1) */
56
57 /* make key */
58 if ((err = mp_init_multi(&key->e, &key->d, &key->N, &key->dQ, &key->dP, &key->qP, &key->p, &key->q, NULL)) != CRYPT_OK) {
59 goto errkey;
60 }
61
62 if ((err = mp_copy( e, key->e)) != CRYPT_OK) { goto errkey; } /* key->e = e */
63 if ((err = mp_invmod( key->e, tmp1, key->d)) != CRYPT_OK) { goto errkey; } /* key->d = 1/e mod lcm(p-1,q-1) */
64 if ((err = mp_mul( p, q, key->N)) != CRYPT_OK) { goto errkey; } /* key->N = pq */
65
66 /* optimize for CRT now */
67 /* find d mod q-1 and d mod p-1 */
68 if ((err = mp_sub_d( p, 1, tmp1)) != CRYPT_OK) { goto errkey; } /* tmp1 = q-1 */
69 if ((err = mp_sub_d( q, 1, tmp2)) != CRYPT_OK) { goto errkey; } /* tmp2 = p-1 */
70 if ((err = mp_mod( key->d, tmp1, key->dP)) != CRYPT_OK) { goto errkey; } /* dP = d mod p-1 */
71 if ((err = mp_mod( key->d, tmp2, key->dQ)) != CRYPT_OK) { goto errkey; } /* dQ = d mod q-1 */
72 if ((err = mp_invmod( q, p, key->qP)) != CRYPT_OK) { goto errkey; } /* qP = 1/q mod p */
73
74 if ((err = mp_copy( p, key->p)) != CRYPT_OK) { goto errkey; }
75 if ((err = mp_copy( q, key->q)) != CRYPT_OK) { goto errkey; }
76
77 /* set key type (in this case it's CRT optimized) */
78 key->type = PK_PRIVATE;
79
80 /* return ok and free temps */
81 err = CRYPT_OK;
82 goto cleanup;
83 errkey:
84 rsa_free(key);
85 cleanup:
86 mp_clear_multi(tmp2, tmp1, q, p, NULL);
87 return err;
88 }
89
90 /**
91 Create an RSA key based on a long public exponent type
92 @param prng An active PRNG state
93 @param wprng The index of the PRNG desired
94 @param size The size of the modulus (key size) desired (octets)
95 @param e The "e" value (public key). e==65537 is a good choice
96 @param key [out] Destination of a newly created private key pair
97 @return CRYPT_OK if successful, upon error all allocated ram is freed
98 */
rsa_make_key(prng_state * prng,int wprng,int size,long e,rsa_key * key)99 int rsa_make_key(prng_state *prng, int wprng, int size, long e, rsa_key *key)
100 {
101 void *tmp_e;
102 int err;
103
104 if ((e < 3) || ((e & 1) == 0)) {
105 return CRYPT_INVALID_ARG;
106 }
107
108 if ((err = mp_init(&tmp_e)) != CRYPT_OK) {
109 return err;
110 }
111
112 if ((err = mp_set_int(tmp_e, e)) == CRYPT_OK)
113 err = s_rsa_make_key(prng, wprng, size, tmp_e, key);
114
115 mp_clear(tmp_e);
116
117 return err;
118 }
119
120 /**
121 Create an RSA key based on a hexadecimal public exponent type
122 @param prng An active PRNG state
123 @param wprng The index of the PRNG desired
124 @param size The size of the modulus (key size) desired (octets)
125 @param e The "e" value (public key). e==65537 is a good choice
126 @param elen The length of e (octets)
127 @param key [out] Destination of a newly created private key pair
128 @return CRYPT_OK if successful, upon error all allocated ram is freed
129 */
rsa_make_key_ubin_e(prng_state * prng,int wprng,int size,const unsigned char * e,unsigned long elen,rsa_key * key)130 int rsa_make_key_ubin_e(prng_state *prng, int wprng, int size,
131 const unsigned char *e, unsigned long elen, rsa_key *key)
132 {
133 int err;
134 void *tmp_e;
135
136 if ((err = mp_init(&tmp_e)) != CRYPT_OK) {
137 return err;
138 }
139
140 if ((err = mp_read_unsigned_bin(tmp_e, (unsigned char *)e, elen)) == CRYPT_OK)
141 err = rsa_make_key_bn_e(prng, wprng, size, tmp_e, key);
142
143 mp_clear(tmp_e);
144
145 return err;
146 }
147
148 /**
149 Create an RSA key based on a bignumber public exponent type
150 @param prng An active PRNG state
151 @param wprng The index of the PRNG desired
152 @param size The size of the modulus (key size) desired (octets)
153 @param e The "e" value (public key). e==65537 is a good choice
154 @param key [out] Destination of a newly created private key pair
155 @return CRYPT_OK if successful, upon error all allocated ram is freed
156 */
rsa_make_key_bn_e(prng_state * prng,int wprng,int size,void * e,rsa_key * key)157 int rsa_make_key_bn_e(prng_state *prng, int wprng, int size, void *e, rsa_key *key)
158 {
159 int err;
160 int e_bits;
161
162 e_bits = mp_count_bits(e);
163 if ((e_bits > 1 && e_bits < 256) && (mp_get_digit(e, 0) & 1)) {
164 err = s_rsa_make_key(prng, wprng, size, e, key);
165 } else {
166 err = CRYPT_INVALID_ARG;
167 }
168
169 return err;
170 }
171
172 #endif
173
174 /* ref: $Format:%D$ */
175 /* git commit: $Format:%H$ */
176 /* commit time: $Format:%ai$ */
177