1/*	$NetBSD: rsa-tfm.c,v 1.2 2017/01/28 21:31:47 christos Exp $	*/
2
3/*
4 * Copyright (c) 2006 - 2007, 2010 Kungliga Tekniska H��gskolan
5 * (Royal Institute of Technology, Stockholm, Sweden).
6 * All rights reserved.
7 *
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions
10 * are met:
11 *
12 * 1. Redistributions of source code must retain the above copyright
13 *    notice, this list of conditions and the following disclaimer.
14 *
15 * 2. Redistributions in binary form must reproduce the above copyright
16 *    notice, this list of conditions and the following disclaimer in the
17 *    documentation and/or other materials provided with the distribution.
18 *
19 * 3. Neither the name of the Institute nor the names of its contributors
20 *    may be used to endorse or promote products derived from this software
21 *    without specific prior written permission.
22 *
23 * THIS SOFTWARE IS PROVIDED BY THE INSTITUTE AND CONTRIBUTORS ``AS IS'' AND
24 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
25 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
26 * ARE DISCLAIMED.  IN NO EVENT SHALL THE INSTITUTE OR CONTRIBUTORS BE LIABLE
27 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
28 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
29 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
30 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
31 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
32 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
33 * SUCH DAMAGE.
34 */
35
36#include <config.h>
37#include <krb5/roken.h>
38#include <krb5/krb5-types.h>
39#include <assert.h>
40
41#include <rsa.h>
42
43#ifdef USE_HCRYPTO_TFM
44
45#include "tfm.h"
46
47static void
48BN2mpz(fp_int *s, const BIGNUM *bn)
49{
50    size_t len;
51    void *p;
52
53    fp_init(s);
54
55    len = BN_num_bytes(bn);
56    p = malloc(len);
57    BN_bn2bin(bn, p);
58    fp_read_unsigned_bin(s, p, len);
59    free(p);
60}
61
62static int
63tfm_rsa_private_calculate(fp_int * in, fp_int * p,  fp_int * q,
64			  fp_int * dmp1, fp_int * dmq1, fp_int * iqmp,
65			  fp_int * out)
66{
67    fp_int vp, vq, u;
68
69    fp_init_multi(&vp, &vq, &u, NULL);
70
71    /* vq = c ^ (d mod (q - 1)) mod q */
72    /* vp = c ^ (d mod (p - 1)) mod p */
73    fp_mod(in, p, &u);
74    fp_exptmod(&u, dmp1, p, &vp);
75    fp_mod(in, q, &u);
76    fp_exptmod(&u, dmq1, q, &vq);
77
78    /* C2 = 1/q mod p  (iqmp) */
79    /* u = (vp - vq)C2 mod p. */
80    fp_sub(&vp, &vq, &u);
81    if (fp_isneg(&u))
82	fp_add(&u, p, &u);
83    fp_mul(&u, iqmp, &u);
84    fp_mod(&u, p, &u);
85
86    /* c ^ d mod n = vq + u q */
87    fp_mul(&u, q, &u);
88    fp_add(&u, &vq, out);
89
90    fp_zero_multi(&vp, &vq, &u, NULL);
91
92    return 0;
93}
94
95/*
96 *
97 */
98
99static int
100tfm_rsa_public_encrypt(int flen, const unsigned char* from,
101			unsigned char* to, RSA* rsa, int padding)
102{
103    unsigned char *p, *p0;
104    int res;
105    size_t size, padlen;
106    fp_int enc, dec, n, e;
107
108    if (padding != RSA_PKCS1_PADDING)
109	return -1;
110
111    size = RSA_size(rsa);
112
113    if (size < RSA_PKCS1_PADDING_SIZE || size - RSA_PKCS1_PADDING_SIZE < flen)
114	return -2;
115
116    BN2mpz(&n, rsa->n);
117    BN2mpz(&e, rsa->e);
118
119    p = p0 = malloc(size - 1);
120    if (p0 == NULL) {
121	fp_zero_multi(&e, &n, NULL);
122	return -3;
123    }
124
125    padlen = size - flen - 3;
126
127    *p++ = 2;
128    if (RAND_bytes(p, padlen) != 1) {
129	fp_zero_multi(&e, &n, NULL);
130	free(p0);
131	return -4;
132    }
133    while(padlen) {
134	if (*p == 0)
135	    *p = 1;
136	padlen--;
137	p++;
138    }
139    *p++ = 0;
140    memcpy(p, from, flen);
141    p += flen;
142    assert((p - p0) == size - 1);
143
144    fp_init_multi(&enc, &dec, NULL);
145    fp_read_unsigned_bin(&dec, p0, size - 1);
146    free(p0);
147
148    res = fp_exptmod(&dec, &e, &n, &enc);
149
150    fp_zero_multi(&dec, &e, &n, NULL);
151
152    if (res != 0)
153	return -4;
154
155    {
156	size_t ssize;
157	ssize = fp_unsigned_bin_size(&enc);
158	assert(size >= ssize);
159	fp_to_unsigned_bin(&enc, to);
160	size = ssize;
161    }
162    fp_zero(&enc);
163
164    return size;
165}
166
167static int
168tfm_rsa_public_decrypt(int flen, const unsigned char* from,
169		       unsigned char* to, RSA* rsa, int padding)
170{
171    unsigned char *p;
172    int res;
173    size_t size;
174    fp_int s, us, n, e;
175
176    if (padding != RSA_PKCS1_PADDING)
177	return -1;
178
179    if (flen > RSA_size(rsa))
180	return -2;
181
182    BN2mpz(&n, rsa->n);
183    BN2mpz(&e, rsa->e);
184
185#if 0
186    /* Check that the exponent is larger then 3 */
187    if (mp_int_compare_value(&e, 3) <= 0) {
188	fp_zero_multi(&e, &n, NULL);
189	return -3;
190    }
191#endif
192
193    fp_init_multi(&s, &us, NULL);
194    fp_read_unsigned_bin(&s, rk_UNCONST(from), flen);
195
196    if (fp_cmp(&s, &n) >= 0) {
197	fp_zero_multi(&e, &n, NULL);
198	return -4;
199    }
200
201    res = fp_exptmod(&s, &e, &n, &us);
202
203    fp_zero_multi(&s, &e, &n, NULL);
204
205    if (res != 0)
206	return -5;
207    p = to;
208
209
210    size = fp_unsigned_bin_size(&us);
211    assert(size <= RSA_size(rsa));
212    fp_to_unsigned_bin(&us, p);
213
214    fp_zero(&us);
215
216    /* head zero was skipped by fp_to_unsigned_bin */
217    if (*p == 0)
218	return -6;
219    if (*p != 1)
220	return -7;
221    size--; p++;
222    while (size && *p == 0xff) {
223	size--; p++;
224    }
225    if (size == 0 || *p != 0)
226	return -8;
227    size--; p++;
228
229    memmove(to, p, size);
230
231    return size;
232}
233
234static int
235tfm_rsa_private_encrypt(int flen, const unsigned char* from,
236			unsigned char* to, RSA* rsa, int padding)
237{
238    unsigned char *p, *p0;
239    int res;
240    int size;
241    fp_int in, out, n, e;
242
243    if (padding != RSA_PKCS1_PADDING)
244	return -1;
245
246    size = RSA_size(rsa);
247
248    if (size < RSA_PKCS1_PADDING_SIZE || size - RSA_PKCS1_PADDING_SIZE < flen)
249	return -2;
250
251    p0 = p = malloc(size);
252    *p++ = 0;
253    *p++ = 1;
254    memset(p, 0xff, size - flen - 3);
255    p += size - flen - 3;
256    *p++ = 0;
257    memcpy(p, from, flen);
258    p += flen;
259    assert((p - p0) == size);
260
261    BN2mpz(&n, rsa->n);
262    BN2mpz(&e, rsa->e);
263
264    fp_init_multi(&in, &out, NULL);
265    fp_read_unsigned_bin(&in, p0, size);
266    free(p0);
267
268    if(fp_isneg(&in) || fp_cmp(&in, &n) >= 0) {
269	size = -3;
270	goto out;
271    }
272
273    if (rsa->p && rsa->q && rsa->dmp1 && rsa->dmq1 && rsa->iqmp) {
274	fp_int p, q, dmp1, dmq1, iqmp;
275
276	BN2mpz(&p, rsa->p);
277	BN2mpz(&q, rsa->q);
278	BN2mpz(&dmp1, rsa->dmp1);
279	BN2mpz(&dmq1, rsa->dmq1);
280	BN2mpz(&iqmp, rsa->iqmp);
281
282	res = tfm_rsa_private_calculate(&in, &p, &q, &dmp1, &dmq1, &iqmp, &out);
283
284	fp_zero_multi(&p, &q, &dmp1, &dmq1, &iqmp, NULL);
285
286	if (res != 0) {
287	    size = -4;
288	    goto out;
289	}
290    } else {
291	fp_int d;
292
293	BN2mpz(&d, rsa->d);
294	res = fp_exptmod(&in, &d, &n, &out);
295	fp_zero(&d);
296	if (res != 0) {
297	    size = -5;
298	    goto out;
299	}
300    }
301
302    if (size > 0) {
303	size_t ssize;
304	ssize = fp_unsigned_bin_size(&out);
305	assert(size >= ssize);
306	fp_to_unsigned_bin(&out, to);
307	size = ssize;
308    }
309
310 out:
311    fp_zero_multi(&e, &n, &in, &out, NULL);
312
313    return size;
314}
315
316static int
317tfm_rsa_private_decrypt(int flen, const unsigned char* from,
318			unsigned char* to, RSA* rsa, int padding)
319{
320    unsigned char *ptr;
321    int res;
322    int size;
323    fp_int in, out, n, e;
324
325    if (padding != RSA_PKCS1_PADDING)
326	return -1;
327
328    size = RSA_size(rsa);
329    if (flen > size)
330	return -2;
331
332    fp_init_multi(&in, &out, NULL);
333
334    BN2mpz(&n, rsa->n);
335    BN2mpz(&e, rsa->e);
336
337    fp_read_unsigned_bin(&in, rk_UNCONST(from), flen);
338
339    if(fp_isneg(&in) || fp_cmp(&in, &n) >= 0) {
340	size = -2;
341	goto out;
342    }
343
344    if (rsa->p && rsa->q && rsa->dmp1 && rsa->dmq1 && rsa->iqmp) {
345	fp_int p, q, dmp1, dmq1, iqmp;
346
347	BN2mpz(&p, rsa->p);
348	BN2mpz(&q, rsa->q);
349	BN2mpz(&dmp1, rsa->dmp1);
350	BN2mpz(&dmq1, rsa->dmq1);
351	BN2mpz(&iqmp, rsa->iqmp);
352
353	res = tfm_rsa_private_calculate(&in, &p, &q, &dmp1, &dmq1, &iqmp, &out);
354
355	fp_zero_multi(&p, &q, &dmp1, &dmq1, &iqmp, NULL);
356
357	if (res != 0) {
358	    size = -3;
359	    goto out;
360	}
361
362    } else {
363	fp_int d;
364
365	if(fp_isneg(&in) || fp_cmp(&in, &n) >= 0)
366	    return -4;
367
368	BN2mpz(&d, rsa->d);
369	res = fp_exptmod(&in, &d, &n, &out);
370	fp_zero(&d);
371	if (res != 0) {
372	    size = -5;
373	    goto out;
374	}
375    }
376
377    ptr = to;
378    {
379	size_t ssize;
380	ssize = fp_unsigned_bin_size(&out);
381	assert(size >= ssize);
382	fp_to_unsigned_bin(&out, ptr);
383	size = ssize;
384    }
385
386    /* head zero was skipped by mp_int_to_unsigned */
387    if (*ptr != 2) {
388	size = -6;
389	goto out;
390    }
391    size--; ptr++;
392    while (size && *ptr != 0) {
393	size--; ptr++;
394    }
395    if (size == 0)
396	return -7;
397    size--; ptr++;
398
399    memmove(to, ptr, size);
400
401 out:
402    fp_zero_multi(&e, &n, &in, &out, NULL);
403
404    return size;
405}
406
407static BIGNUM *
408mpz2BN(fp_int *s)
409{
410    size_t size;
411    BIGNUM *bn;
412    void *p;
413
414    size = fp_unsigned_bin_size(s);
415    p = malloc(size);
416    if (p == NULL && size != 0)
417	return NULL;
418
419    fp_to_unsigned_bin(s, p);
420
421    bn = BN_bin2bn(p, size, NULL);
422    free(p);
423    return bn;
424}
425
426static int
427random_num(fp_int *num, size_t len)
428{
429    unsigned char *p;
430
431    len = (len + 7) / 8;
432    p = malloc(len);
433    if (p == NULL)
434	return 1;
435    if (RAND_bytes(p, len) != 1) {
436	free(p);
437	return 1;
438    }
439    fp_read_unsigned_bin(num, p, len);
440    free(p);
441    return 0;
442}
443
444#define CHECK(f, v) if ((f) != (v)) { goto out; }
445
446static int
447tfm_rsa_generate_key(RSA *rsa, int bits, BIGNUM *e, BN_GENCB *cb)
448{
449    fp_int el, p, q, n, d, dmp1, dmq1, iqmp, t1, t2, t3;
450    int counter, ret, bitsp;
451
452    if (bits < 789)
453	return -1;
454
455    bitsp = (bits + 1) / 2;
456
457    ret = -1;
458
459    fp_init_multi(&el, &p, &q, &n, &n, &d, &dmp1, &dmq1, &iqmp, &t1, &t2, &t3, NULL);
460
461    BN2mpz(&el, e);
462
463    /* generate p and q so that p != q and bits(pq) ~ bits */
464    counter = 0;
465    do {
466	BN_GENCB_call(cb, 2, counter++);
467	CHECK(random_num(&p, bitsp), 0);
468	CHECK(fp_find_prime(&p), FP_YES);
469
470	fp_sub_d(&p, 1, &t1);
471	fp_gcd(&t1, &el, &t2);
472    } while(fp_cmp_d(&t2, 1) != 0);
473
474    BN_GENCB_call(cb, 3, 0);
475
476    counter = 0;
477    do {
478	BN_GENCB_call(cb, 2, counter++);
479	CHECK(random_num(&q, bits - bitsp), 0);
480	CHECK(fp_find_prime(&q), FP_YES);
481
482	if (fp_cmp(&p, &q) == 0) /* don't let p and q be the same */
483	    continue;
484
485	fp_sub_d(&q, 1, &t1);
486	fp_gcd(&t1, &el, &t2);
487    } while(fp_cmp_d(&t2, 1) != 0);
488
489    /* make p > q */
490    if (fp_cmp(&p, &q) < 0) {
491	fp_int c;
492	fp_copy(&p, &c);
493	fp_copy(&q, &p);
494	fp_copy(&c, &q);
495    }
496
497    BN_GENCB_call(cb, 3, 1);
498
499    /* calculate n,  		n = p * q */
500    fp_mul(&p, &q, &n);
501
502    /* calculate d, 		d = 1/e mod (p - 1)(q - 1) */
503    fp_sub_d(&p, 1, &t1);
504    fp_sub_d(&q, 1, &t2);
505    fp_mul(&t1, &t2, &t3);
506    fp_invmod(&el, &t3, &d);
507
508    /* calculate dmp1		dmp1 = d mod (p-1) */
509    fp_mod(&d, &t1, &dmp1);
510    /* calculate dmq1		dmq1 = d mod (q-1) */
511    fp_mod(&d, &t2, &dmq1);
512    /* calculate iqmp 		iqmp = 1/q mod p */
513    fp_invmod(&q, &p, &iqmp);
514
515    /* fill in RSA key */
516
517    rsa->e = mpz2BN(&el);
518    rsa->p = mpz2BN(&p);
519    rsa->q = mpz2BN(&q);
520    rsa->n = mpz2BN(&n);
521    rsa->d = mpz2BN(&d);
522    rsa->dmp1 = mpz2BN(&dmp1);
523    rsa->dmq1 = mpz2BN(&dmq1);
524    rsa->iqmp = mpz2BN(&iqmp);
525
526    ret = 1;
527
528out:
529    fp_zero_multi(&el, &p, &q, &n, &d, &dmp1,
530		  &dmq1, &iqmp, &t1, &t2, &t3, NULL);
531
532    return ret;
533}
534
535static int
536tfm_rsa_init(RSA *rsa)
537{
538    return 1;
539}
540
541static int
542tfm_rsa_finish(RSA *rsa)
543{
544    return 1;
545}
546
547const RSA_METHOD hc_rsa_tfm_method = {
548    "hcrypto tfm RSA",
549    tfm_rsa_public_encrypt,
550    tfm_rsa_public_decrypt,
551    tfm_rsa_private_encrypt,
552    tfm_rsa_private_decrypt,
553    NULL,
554    NULL,
555    tfm_rsa_init,
556    tfm_rsa_finish,
557    0,
558    NULL,
559    NULL,
560    NULL,
561    tfm_rsa_generate_key
562};
563
564#endif
565
566const RSA_METHOD *
567RSA_tfm_method(void)
568{
569#ifdef USE_HCRYPTO_TFM
570    return &hc_rsa_tfm_method;
571#else
572    return NULL;
573#endif
574}
575
576