1 /*
2 * Copyright (c) 2000, 2002 X-Way Rights BV
3 *
4 * This library is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU Lesser General Public
6 * License as published by the Free Software Foundation; either
7 * version 2.1 of the License, or (at your option) any later version.
8 *
9 * This library is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12 * Lesser General Public License for more details.
13 *
14 * You should have received a copy of the GNU Lesser General Public
15 * License along with this library; if not, write to the Free Software
16 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
17 *
18 */
19
20 /*!\file rsakp.c
21 * \brief RSA keypair.
22 * \author Bob Deblier <bob.deblier@telenet.be>
23 * \ingroup IF_m IF_rsa_m
24 */
25
26 #define BEECRYPT_DLL_EXPORT
27
28 #if HAVE_CONFIG_H
29 # include "config.h"
30 #endif
31
32 #include "beecrypt/rsakp.h"
33 #include "beecrypt/mpprime.h"
34
35 /*!\addtogroup IF_rsa_m
36 * \{
37 */
38
rsakpMake(rsakp * kp,randomGeneratorContext * rgc,size_t bits)39 int rsakpMake(rsakp* kp, randomGeneratorContext* rgc, size_t bits)
40 {
41 /*
42 * Generates an RSA Keypair for use with the Chinese Remainder Theorem
43 */
44
45 size_t pbits = (bits+1) >> 1;
46 size_t qbits = (bits - pbits);
47 size_t nsize = MP_BITS_TO_WORDS(bits+MP_WBITS-1);
48 size_t psize = MP_BITS_TO_WORDS(pbits+MP_WBITS-1);
49 size_t qsize = MP_BITS_TO_WORDS(qbits+MP_WBITS-1);
50 size_t pqsize = psize+qsize;
51 mpw* temp = (mpw*) malloc((16*pqsize+6)*sizeof(mpw));
52
53 if (temp)
54 {
55 mpbarrett psubone, qsubone;
56 mpnumber phi, min;
57 mpw* divmod = temp;
58 mpw* dividend = divmod+nsize+1;
59 mpw* workspace = dividend+nsize+1;
60 int shift;
61
62 /* set e to default value if e is empty */
63 if (kp->e.size == 0 && !kp->e.data)
64 mpnsetw(&kp->e, 65537U);
65
66 /* generate a random prime p, so that gcd(p-1,e) = 1 */
67 mpprnd_w(&kp->p, rgc, pbits, mpptrials(pbits), &kp->e, temp);
68
69 /* find out how big q should be */
70 shift = MP_WORDS_TO_BITS(nsize) - bits;
71 mpzero(nsize, dividend);
72 dividend[0] |= MP_MSBMASK;
73 dividend[nsize-1] |= MP_LSBMASK;
74 mpndivmod(divmod, nsize+1, dividend, psize, kp->p.modl, workspace);
75 mprshift(nsize+1, divmod, shift);
76
77 mpnzero(&min);
78 mpnset(&min, nsize+1-psize, divmod);
79
80 /* generate a random prime q, with min/max constraints, so that gcd(q-1,e) = 1 */
81 if (mpprndr_w(&kp->q, rgc, qbits, mpptrials(qbits), &min, (mpnumber*) 0, &kp->e, temp))
82 {
83 /* shouldn't happen */
84 mpnfree(&min);
85 free(temp);
86 return -1;
87 }
88
89 mpnfree(&min);
90
91 mpbzero(&psubone);
92 mpbzero(&qsubone);
93 mpnzero(&phi);
94
95 /* set n = p*q, with appropriate size (pqsize may be > nsize) */
96 mpmul(temp, psize, kp->p.modl, qsize, kp->q.modl);
97 mpbset(&kp->n, nsize, temp+pqsize-nsize);
98
99 /* compute p-1 */
100 mpbsubone(&kp->p, temp);
101 mpbset(&psubone, psize, temp);
102
103 /* compute q-1 */
104 mpbsubone(&kp->q, temp);
105 mpbset(&qsubone, qsize, temp);
106
107 /* compute phi = (p-1)*(q-1) */
108 mpmul(temp, psize, psubone.modl, qsize, qsubone.modl);
109 mpnset(&phi, nsize, temp);
110
111 /* compute d = inv(e) mod phi; if gcd(e, phi) != 1 then this function will fail
112 */
113 if (mpninv(&kp->d, &kp->e, &phi) == 0)
114 {
115 /* shouldn't happen, since gcd(p-1,e) = 1 and gcd(q-1,e) = 1 ==> gcd((p-1)(q-1),e) = 1 */
116 mpnfree(&phi);
117 free(temp);
118 return -1;
119 }
120
121 /* compute dp = d mod (p-1) */
122 mpnsize(&kp->dp, psize);
123 mpbmod_w(&psubone, kp->d.data, kp->dp.data, temp);
124
125 /* compute dq = d mod (q-1) */
126 mpnsize(&kp->dq, qsize);
127 mpbmod_w(&qsubone, kp->d.data, kp->dq.data, temp);
128
129 /* compute qi = inv(q) mod p */
130 mpninv(&kp->qi, (mpnumber*) &kp->q, (mpnumber*) &kp->p);
131
132 mpnfree(&phi);
133 free(temp);
134
135 return 0;
136 }
137 return -1;
138 }
139
rsakpInit(rsakp * kp)140 int rsakpInit(rsakp* kp)
141 {
142 memset(kp, 0, sizeof(rsakp));
143 /* or
144 mpbzero(&kp->n);
145 mpnzero(&kp->e);
146 mpnzero(&kp->d);
147 mpbzero(&kp->p);
148 mpbzero(&kp->q);
149 mpnzero(&kp->dp);
150 mpnzero(&kp->dq);
151 mpnzero(&kp->qi);
152 */
153
154 return 0;
155 }
156
rsakpFree(rsakp * kp)157 int rsakpFree(rsakp* kp)
158 {
159 /* wipe all secret key components */
160 mpbfree(&kp->n);
161 mpnfree(&kp->e);
162 mpnwipe(&kp->d);
163 mpnfree(&kp->d);
164 mpbwipe(&kp->p);
165 mpbfree(&kp->p);
166 mpbwipe(&kp->q);
167 mpbfree(&kp->q);
168 mpnwipe(&kp->dp);
169 mpnfree(&kp->dp);
170 mpnwipe(&kp->dq);
171 mpnfree(&kp->dq);
172 mpnwipe(&kp->qi);
173 mpnfree(&kp->qi);
174
175 return 0;
176 }
177
rsakpCopy(rsakp * dst,const rsakp * src)178 int rsakpCopy(rsakp* dst, const rsakp* src)
179 {
180 mpbcopy(&dst->n, &src->n);
181 mpncopy(&dst->e, &src->e);
182 mpncopy(&dst->d, &src->d);
183 mpbcopy(&dst->p, &src->p);
184 mpbcopy(&dst->q, &src->q);
185 mpncopy(&dst->dp, &src->dp);
186 mpncopy(&dst->dp, &src->dp);
187 mpncopy(&dst->qi, &src->qi);
188
189 return 0;
190 }
191
192 /*!\}
193 */
194