1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
|
/* LibTomCrypt, modular cryptographic library -- Tom St Denis
*
* LibTomCrypt is a library that provides various cryptographic
* algorithms in a highly modular and flexible manner.
*
* The library is free for all purposes without any express
* guarantee it works.
*
* Tom St Denis, tomstdenis@gmail.com, http://libtom.org
*/
#include "tomcrypt.h"
/**
@file rsa_make_key.c
RSA key generation, Tom St Denis
*/
#ifdef LTC_MRSA
/**
Create an RSA key
@param size The size of the modulus (key size) desired (octets)
@param e The "e" value (public key). e==65537 is a good choice
@param key [out] Destination of a newly created private key pair
@return CRYPT_OK if successful, upon error all allocated ram is freed
*/
int rsa_make_key(int size, long e, rsa_key * key)
{
mp_int p, q, tmp1, tmp2, tmp3;
int err;
LTC_ARGCHK(key != NULL);
if ((size < (MIN_RSA_SIZE / 8)) || (size > (MAX_RSA_SIZE / 8))) {
return CRYPT_INVALID_KEYSIZE;
}
if ((e < 3) || ((e & 1) == 0)) {
return CRYPT_INVALID_ARG;
}
if ((err =
mp_init_multi(&p, &q, &tmp1, &tmp2, &tmp3, NULL)) != CRYPT_OK) {
return err;
}
/* make primes p and q (optimization provided by Wayne Scott) */
if ((err = mp_set_int(&tmp3, e)) != CRYPT_OK) {
goto cleanup;
}
/* tmp3 = e */
/* make prime "p" */
do {
if ((err = rand_prime(&p, size / 2)) != CRYPT_OK) {
goto cleanup;
}
if ((err = mp_sub_d(&p, 1, &tmp1)) != CRYPT_OK) {
goto cleanup;
} /* tmp1 = p-1 */
if ((err = mp_gcd(&tmp1, &tmp3, &tmp2)) != CRYPT_OK) {
goto cleanup;
} /* tmp2 = gcd(p-1, e) */
} while (mp_cmp_d(&tmp2, 1) != 0); /* while e divides p-1 */
/* make prime "q" */
do {
if ((err = rand_prime(&q, size / 2)) != CRYPT_OK) {
goto cleanup;
}
if ((err = mp_sub_d(&q, 1, &tmp1)) != CRYPT_OK) {
goto cleanup;
} /* tmp1 = q-1 */
if ((err = mp_gcd(&tmp1, &tmp3, &tmp2)) != CRYPT_OK) {
goto cleanup;
} /* tmp2 = gcd(q-1, e) */
} while (mp_cmp_d(&tmp2, 1) != 0); /* while e divides q-1 */
/* tmp1 = lcm(p-1, q-1) */
if ((err = mp_sub_d(&p, 1, &tmp2)) != CRYPT_OK) {
goto cleanup;
}
/* tmp2 = p-1 */
/* tmp1 = q-1 (previous do/while loop) */
if ((err = mp_lcm(&tmp1, &tmp2, &tmp1)) != CRYPT_OK) {
goto cleanup;
}
/* tmp1 = lcm(p-1, q-1) */
/* make key */
if ((err =
mp_init_multi(&key->e, &key->d, &key->N, &key->dQ, &key->dP,
&key->qP, &key->p, &key->q, NULL)) != CRYPT_OK) {
goto cleanup;
}
if ((err = mp_set_int(&key->e, e)) != CRYPT_OK) {
goto errkey;
} /* key->e = e */
if ((err = mp_invmod(&key->e, &tmp1, &key->d)) != CRYPT_OK) {
goto errkey;
} /* key->d = 1/e mod lcm(p-1,q-1) */
if ((err = mp_mul(&p, &q, &key->N)) != CRYPT_OK) {
goto errkey;
}
/* key->N = pq */
/* optimize for CRT now */
/* find d mod q-1 and d mod p-1 */
if ((err = mp_sub_d(&p, 1, &tmp1)) != CRYPT_OK) {
goto errkey;
} /* tmp1 = q-1 */
if ((err = mp_sub_d(&q, 1, &tmp2)) != CRYPT_OK) {
goto errkey;
} /* tmp2 = p-1 */
if ((err = mp_mod(&key->d, &tmp1, &key->dP)) != CRYPT_OK) {
goto errkey;
} /* dP = d mod p-1 */
if ((err = mp_mod(&key->d, &tmp2, &key->dQ)) != CRYPT_OK) {
goto errkey;
} /* dQ = d mod q-1 */
if ((err = mp_invmod(&q, &p, &key->qP)) != CRYPT_OK) {
goto errkey;
}
/* qP = 1/q mod p */
if ((err = mp_copy(&p, &key->p)) != CRYPT_OK) {
goto errkey;
}
if ((err = mp_copy(&q, &key->q)) != CRYPT_OK) {
goto errkey;
}
/* set key type (in this case it's CRT optimized) */
key->type = PK_PRIVATE;
/* return ok and free temps */
err = CRYPT_OK;
goto cleanup;
errkey:
mp_clear_multi(&key->d, &key->e, &key->N, &key->dQ, &key->dP, &key->qP,
&key->p, &key->q, NULL);
cleanup:
mp_clear_multi(&tmp3, &tmp2, &tmp1, &p, &q, NULL);
return err;
}
#endif
/* $Source: /cvs/libtom/libtomcrypt/src/pk/rsa/rsa_make_key.c,v $ */
/* $Revision: 1.16 $ */
/* $Date: 2007/05/12 14:32:35 $ */
|
