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