1/*	$NetBSD$	*/
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
38#include <stdio.h>
39#include <stdlib.h>
40#include <krb5/krb5-types.h>
41#include <assert.h>
42
43#include <rsa.h>
44
45#include <krb5/roken.h>
46
47#ifdef USE_HCRYPTO_TFM
48
49#include "tfm.h"
50
51static void
52BN2mpz(fp_int *s, const BIGNUM *bn)
53{
54    size_t len;
55    void *p;
56
57    fp_init(s);
58
59    len = BN_num_bytes(bn);
60    p = malloc(len);
61    BN_bn2bin(bn, p);
62    fp_read_unsigned_bin(s, p, len);
63    free(p);
64}
65
66static int
67tfm_rsa_private_calculate(fp_int * in, fp_int * p,  fp_int * q,
68			  fp_int * dmp1, fp_int * dmq1, fp_int * iqmp,
69			  fp_int * out)
70{
71    fp_int vp, vq, u;
72
73    fp_init_multi(&vp, &vq, &u, NULL);
74
75    /* vq = c ^ (d mod (q - 1)) mod q */
76    /* vp = c ^ (d mod (p - 1)) mod p */
77    fp_mod(in, p, &u);
78    fp_exptmod(&u, dmp1, p, &vp);
79    fp_mod(in, q, &u);
80    fp_exptmod(&u, dmq1, q, &vq);
81
82    /* C2 = 1/q mod p  (iqmp) */
83    /* u = (vp - vq)C2 mod p. */
84    fp_sub(&vp, &vq, &u);
85    if (fp_isneg(&u))
86	fp_add(&u, p, &u);
87    fp_mul(&u, iqmp, &u);
88    fp_mod(&u, p, &u);
89
90    /* c ^ d mod n = vq + u q */
91    fp_mul(&u, q, &u);
92    fp_add(&u, &vq, out);
93
94    fp_zero_multi(&vp, &vq, &u, NULL);
95
96    return 0;
97}
98
99/*
100 *
101 */
102
103static int
104tfm_rsa_public_encrypt(int flen, const unsigned char* from,
105			unsigned char* to, RSA* rsa, int padding)
106{
107    unsigned char *p, *p0;
108    int res;
109    size_t size, padlen;
110    fp_int enc, dec, n, e;
111
112    if (padding != RSA_PKCS1_PADDING)
113	return -1;
114
115    size = RSA_size(rsa);
116
117    if (size < RSA_PKCS1_PADDING_SIZE || size - RSA_PKCS1_PADDING_SIZE < flen)
118	return -2;
119
120    BN2mpz(&n, rsa->n);
121    BN2mpz(&e, rsa->e);
122
123    p = p0 = malloc(size - 1);
124    if (p0 == NULL) {
125	fp_zero_multi(&e, &n, NULL);
126	return -3;
127    }
128
129    padlen = size - flen - 3;
130
131    *p++ = 2;
132    if (RAND_bytes(p, padlen) != 1) {
133	fp_zero_multi(&e, &n, NULL);
134	free(p0);
135	return -4;
136    }
137    while(padlen) {
138	if (*p == 0)
139	    *p = 1;
140	padlen--;
141	p++;
142    }
143    *p++ = 0;
144    memcpy(p, from, flen);
145    p += flen;
146    assert((p - p0) == size - 1);
147
148    fp_init_multi(&enc, &dec, NULL);
149    fp_read_unsigned_bin(&dec, p0, size - 1);
150    free(p0);
151
152    res = fp_exptmod(&dec, &e, &n, &enc);
153
154    fp_zero_multi(&dec, &e, &n, NULL);
155
156    if (res != 0)
157	return -4;
158
159    {
160	size_t ssize;
161	ssize = fp_unsigned_bin_size(&enc);
162	assert(size >= ssize);
163	fp_to_unsigned_bin(&enc, to);
164	size = ssize;
165    }
166    fp_zero(&enc);
167
168    return size;
169}
170
171static int
172tfm_rsa_public_decrypt(int flen, const unsigned char* from,
173		       unsigned char* to, RSA* rsa, int padding)
174{
175    unsigned char *p;
176    int res;
177    size_t size;
178    fp_int s, us, n, e;
179
180    if (padding != RSA_PKCS1_PADDING)
181	return -1;
182
183    if (flen > RSA_size(rsa))
184	return -2;
185
186    BN2mpz(&n, rsa->n);
187    BN2mpz(&e, rsa->e);
188
189#if 0
190    /* Check that the exponent is larger then 3 */
191    if (mp_int_compare_value(&e, 3) <= 0) {
192	fp_zero_multi(&e, &n, NULL);
193	return -3;
194    }
195#endif
196
197    fp_init_multi(&s, &us, NULL);
198    fp_read_unsigned_bin(&s, rk_UNCONST(from), flen);
199
200    if (fp_cmp(&s, &n) >= 0) {
201	fp_zero_multi(&e, &n, NULL);
202	return -4;
203    }
204
205    res = fp_exptmod(&s, &e, &n, &us);
206
207    fp_zero_multi(&s, &e, &n, NULL);
208
209    if (res != 0)
210	return -5;
211    p = to;
212
213
214    size = fp_unsigned_bin_size(&us);
215    assert(size <= RSA_size(rsa));
216    fp_to_unsigned_bin(&us, p);
217
218    fp_zero(&us);
219
220    /* head zero was skipped by fp_to_unsigned_bin */
221    if (*p == 0)
222	return -6;
223    if (*p != 1)
224	return -7;
225    size--; p++;
226    while (size && *p == 0xff) {
227	size--; p++;
228    }
229    if (size == 0 || *p != 0)
230	return -8;
231    size--; p++;
232
233    memmove(to, p, size);
234
235    return size;
236}
237
238static int
239tfm_rsa_private_encrypt(int flen, const unsigned char* from,
240			unsigned char* to, RSA* rsa, int padding)
241{
242    unsigned char *p, *p0;
243    int res;
244    int size;
245    fp_int in, out, n, e;
246
247    if (padding != RSA_PKCS1_PADDING)
248	return -1;
249
250    size = RSA_size(rsa);
251
252    if (size < RSA_PKCS1_PADDING_SIZE || size - RSA_PKCS1_PADDING_SIZE < flen)
253	return -2;
254
255    p0 = p = malloc(size);
256    *p++ = 0;
257    *p++ = 1;
258    memset(p, 0xff, size - flen - 3);
259    p += size - flen - 3;
260    *p++ = 0;
261    memcpy(p, from, flen);
262    p += flen;
263    assert((p - p0) == size);
264
265    BN2mpz(&n, rsa->n);
266    BN2mpz(&e, rsa->e);
267
268    fp_init_multi(&in, &out, NULL);
269    fp_read_unsigned_bin(&in, p0, size);
270    free(p0);
271
272    if(fp_isneg(&in) || fp_cmp(&in, &n) >= 0) {
273	size = -3;
274	goto out;
275    }
276
277    if (rsa->p && rsa->q && rsa->dmp1 && rsa->dmq1 && rsa->iqmp) {
278	fp_int p, q, dmp1, dmq1, iqmp;
279
280	BN2mpz(&p, rsa->p);
281	BN2mpz(&q, rsa->q);
282	BN2mpz(&dmp1, rsa->dmp1);
283	BN2mpz(&dmq1, rsa->dmq1);
284	BN2mpz(&iqmp, rsa->iqmp);
285
286	res = tfm_rsa_private_calculate(&in, &p, &q, &dmp1, &dmq1, &iqmp, &out);
287
288	fp_zero_multi(&p, &q, &dmp1, &dmq1, &iqmp, NULL);
289
290	if (res != 0) {
291	    size = -4;
292	    goto out;
293	}
294    } else {
295	fp_int d;
296
297	BN2mpz(&d, rsa->d);
298	res = fp_exptmod(&in, &d, &n, &out);
299	fp_zero(&d);
300	if (res != 0) {
301	    size = -5;
302	    goto out;
303	}
304    }
305
306    if (size > 0) {
307	size_t ssize;
308	ssize = fp_unsigned_bin_size(&out);
309	assert(size >= ssize);
310	fp_to_unsigned_bin(&out, to);
311	size = ssize;
312    }
313
314 out:
315    fp_zero_multi(&e, &n, &in, &out, NULL);
316
317    return size;
318}
319
320static int
321tfm_rsa_private_decrypt(int flen, const unsigned char* from,
322			unsigned char* to, RSA* rsa, int padding)
323{
324    unsigned char *ptr;
325    int res;
326    int size;
327    fp_int in, out, n, e;
328
329    if (padding != RSA_PKCS1_PADDING)
330	return -1;
331
332    size = RSA_size(rsa);
333    if (flen > size)
334	return -2;
335
336    fp_init_multi(&in, &out, NULL);
337
338    BN2mpz(&n, rsa->n);
339    BN2mpz(&e, rsa->e);
340
341    fp_read_unsigned_bin(&in, rk_UNCONST(from), flen);
342
343    if(fp_isneg(&in) || fp_cmp(&in, &n) >= 0) {
344	size = -2;
345	goto out;
346    }
347
348    if (rsa->p && rsa->q && rsa->dmp1 && rsa->dmq1 && rsa->iqmp) {
349	fp_int p, q, dmp1, dmq1, iqmp;
350
351	BN2mpz(&p, rsa->p);
352	BN2mpz(&q, rsa->q);
353	BN2mpz(&dmp1, rsa->dmp1);
354	BN2mpz(&dmq1, rsa->dmq1);
355	BN2mpz(&iqmp, rsa->iqmp);
356
357	res = tfm_rsa_private_calculate(&in, &p, &q, &dmp1, &dmq1, &iqmp, &out);
358
359	fp_zero_multi(&p, &q, &dmp1, &dmq1, &iqmp, NULL);
360
361	if (res != 0) {
362	    size = -3;
363	    goto out;
364	}
365
366    } else {
367	fp_int d;
368
369	if(fp_isneg(&in) || fp_cmp(&in, &n) >= 0)
370	    return -4;
371
372	BN2mpz(&d, rsa->d);
373	res = fp_exptmod(&in, &d, &n, &out);
374	fp_zero(&d);
375	if (res != 0) {
376	    size = -5;
377	    goto out;
378	}
379    }
380
381    ptr = to;
382    {
383	size_t ssize;
384	ssize = fp_unsigned_bin_size(&out);
385	assert(size >= ssize);
386	fp_to_unsigned_bin(&out, ptr);
387	size = ssize;
388    }
389
390    /* head zero was skipped by mp_int_to_unsigned */
391    if (*ptr != 2) {
392	size = -6;
393	goto out;
394    }
395    size--; ptr++;
396    while (size && *ptr != 0) {
397	size--; ptr++;
398    }
399    if (size == 0)
400	return -7;
401    size--; ptr++;
402
403    memmove(to, ptr, size);
404
405 out:
406    fp_zero_multi(&e, &n, &in, &out, NULL);
407
408    return size;
409}
410
411static BIGNUM *
412mpz2BN(fp_int *s)
413{
414    size_t size;
415    BIGNUM *bn;
416    void *p;
417
418    size = fp_unsigned_bin_size(s);
419    p = malloc(size);
420    if (p == NULL && size != 0)
421	return NULL;
422
423    fp_to_unsigned_bin(s, p);
424
425    bn = BN_bin2bn(p, size, NULL);
426    free(p);
427    return bn;
428}
429
430static int
431random_num(fp_int *num, size_t len)
432{
433    unsigned char *p;
434
435    len = (len + 7) / 8;
436    p = malloc(len);
437    if (p == NULL)
438	return 1;
439    if (RAND_bytes(p, len) != 1) {
440	free(p);
441	return 1;
442    }
443    fp_read_unsigned_bin(num, p, len);
444    free(p);
445    return 0;
446}
447
448#define CHECK(f, v) if ((f) != (v)) { goto out; }
449
450static int
451tfm_rsa_generate_key(RSA *rsa, int bits, BIGNUM *e, BN_GENCB *cb)
452{
453    fp_int el, p, q, n, d, dmp1, dmq1, iqmp, t1, t2, t3;
454    int counter, ret, bitsp;
455
456    if (bits < 789)
457	return -1;
458
459    bitsp = (bits + 1) / 2;
460
461    ret = -1;
462
463    fp_init_multi(&el, &p, &q, &n, &n, &d, &dmp1, &dmq1, &iqmp, &t1, &t2, &t3, NULL);
464
465    BN2mpz(&el, e);
466
467    /* generate p and q so that p != q and bits(pq) ~ bits */
468    counter = 0;
469    do {
470	BN_GENCB_call(cb, 2, counter++);
471	CHECK(random_num(&p, bitsp), 0);
472	CHECK(fp_find_prime(&p), FP_YES);
473
474	fp_sub_d(&p, 1, &t1);
475	fp_gcd(&t1, &el, &t2);
476    } while(fp_cmp_d(&t2, 1) != 0);
477
478    BN_GENCB_call(cb, 3, 0);
479
480    counter = 0;
481    do {
482	BN_GENCB_call(cb, 2, counter++);
483	CHECK(random_num(&q, bits - bitsp), 0);
484	CHECK(fp_find_prime(&q), FP_YES);
485
486	if (fp_cmp(&p, &q) == 0) /* don't let p and q be the same */
487	    continue;
488
489	fp_sub_d(&q, 1, &t1);
490	fp_gcd(&t1, &el, &t2);
491    } while(fp_cmp_d(&t2, 1) != 0);
492
493    /* make p > q */
494    if (fp_cmp(&p, &q) < 0) {
495	fp_int c;
496	fp_copy(&p, &c);
497	fp_copy(&q, &p);
498	fp_copy(&c, &q);
499    }
500
501    BN_GENCB_call(cb, 3, 1);
502
503    /* calculate n,  		n = p * q */
504    fp_mul(&p, &q, &n);
505
506    /* calculate d, 		d = 1/e mod (p - 1)(q - 1) */
507    fp_sub_d(&p, 1, &t1);
508    fp_sub_d(&q, 1, &t2);
509    fp_mul(&t1, &t2, &t3);
510    fp_invmod(&el, &t3, &d);
511
512    /* calculate dmp1		dmp1 = d mod (p-1) */
513    fp_mod(&d, &t1, &dmp1);
514    /* calculate dmq1		dmq1 = d mod (q-1) */
515    fp_mod(&d, &t2, &dmq1);
516    /* calculate iqmp 		iqmp = 1/q mod p */
517    fp_invmod(&q, &p, &iqmp);
518
519    /* fill in RSA key */
520
521    rsa->e = mpz2BN(&el);
522    rsa->p = mpz2BN(&p);
523    rsa->q = mpz2BN(&q);
524    rsa->n = mpz2BN(&n);
525    rsa->d = mpz2BN(&d);
526    rsa->dmp1 = mpz2BN(&dmp1);
527    rsa->dmq1 = mpz2BN(&dmq1);
528    rsa->iqmp = mpz2BN(&iqmp);
529
530    ret = 1;
531
532out:
533    fp_zero_multi(&el, &p, &q, &n, &d, &dmp1,
534		  &dmq1, &iqmp, &t1, &t2, &t3, NULL);
535
536    return ret;
537}
538
539static int
540tfm_rsa_init(RSA *rsa)
541{
542    return 1;
543}
544
545static int
546tfm_rsa_finish(RSA *rsa)
547{
548    return 1;
549}
550
551const RSA_METHOD hc_rsa_tfm_method = {
552    "hcrypto tfm RSA",
553    tfm_rsa_public_encrypt,
554    tfm_rsa_public_decrypt,
555    tfm_rsa_private_encrypt,
556    tfm_rsa_private_decrypt,
557    NULL,
558    NULL,
559    tfm_rsa_init,
560    tfm_rsa_finish,
561    0,
562    NULL,
563    NULL,
564    NULL,
565    tfm_rsa_generate_key
566};
567
568#endif
569
570const RSA_METHOD *
571RSA_tfm_method(void)
572{
573#ifdef USE_HCRYPTO_TFM
574    return &hc_rsa_tfm_method;
575#else
576    return NULL;
577#endif
578}
579
580