fs/mfs: Remove a few assert.h includes
[minix3.git] / crypto / external / bsd / netpgp / dist / src / librsa / rsa.c
blobd25ebb2a2b9e69915205a6966f85ba1623c9b886
1 /*-
2 * Copyright (c) 2012 Alistair Crooks <agc@NetBSD.org>
3 * All rights reserved.
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 * 1. Redistributions of source code must retain the above copyright
9 * notice, this list of conditions and the following disclaimer.
10 * 2. Redistributions in binary form must reproduce the above copyright
11 * notice, this list of conditions and the following disclaimer in the
12 * documentation and/or other materials provided with the distribution.
14 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
15 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
16 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
17 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
18 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
19 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
20 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
21 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
23 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
25 #include <sys/types.h>
26 #include <sys/syslog.h>
28 #ifdef _KERNEL
29 # include <sys/kmem.h>
30 # define logmessage log
31 #else
32 # include <stdio.h>
33 # include <stdlib.h>
34 # include <string.h>
35 # include <unistd.h>
36 #endif
38 #include "misc.h"
39 #include "digest.h"
40 #include "rsa.h"
42 #ifndef USE_ARG
43 #define USE_ARG(x) /*LINTED*/(void)&(x)
44 #endif
46 #define RSA_MAX_MODULUS_BITS 16384
47 #define RSA_SMALL_MODULUS_BITS 3072
48 #define RSA_MAX_PUBEXP_BITS 64 /* exponent limit enforced for "large" modulus only */
50 static int
51 rsa_padding_check_none(uint8_t *to, int tlen, const uint8_t *from, int flen, int num)
53 USE_ARG(num);
54 if (flen > tlen) {
55 printf("r too large\n");
56 return -1;
58 (void) memset(to, 0x0, tlen - flen);
59 (void) memcpy(to + tlen - flen, from, flen);
60 return tlen;
63 static int
64 lowlevel_rsa_private_encrypt(int plainc, const unsigned char *plain, unsigned char *encbuf, RSA *rsa)
66 BIGNUM *decbn;
67 BIGNUM *signedbn;
68 uint8_t *decbuf;
69 int nbytes;
70 int signc;
71 int signedbytes;
72 int r;
74 decbuf = NULL;
75 r = -1;
76 decbn = BN_new();
77 signedbn = BN_new();
78 nbytes = BN_num_bytes(rsa->n);
79 decbuf = netpgp_allocate(1, nbytes);
80 /* add no padding */
81 memcpy(decbuf, plain, plainc);
82 BN_bin2bn(decbuf, nbytes, decbn);
83 if (BN_cmp(decbn, rsa->n) >= 0) {
84 printf("decbn too big\n");
85 goto err;
87 if (!BN_mod_exp(signedbn, decbn, rsa->d, rsa->n, NULL)) {
88 printf("bad mod_exp\n");
89 goto err;
91 signedbytes = BN_num_bytes(signedbn);
92 signc = BN_bn2bin(signedbn, &encbuf[nbytes - signedbytes]);
93 memset(encbuf, 0x0, nbytes - signc);
94 r = nbytes;
95 err:
96 netpgp_deallocate(decbuf, nbytes);
97 BN_clear_free(decbn);
98 BN_clear_free(signedbn);
99 return r;
102 static int
103 lowlevel_rsa_public_encrypt(int plainc, const unsigned char *plain, unsigned char *encbuf, RSA *rsa)
105 BIGNUM *decbn;
106 BIGNUM *encbn;
107 uint8_t *decbuf;
108 int nbytes;
109 int encc;
110 int r;
111 int i;
113 r = -1;
114 decbn = BN_new();
115 encbn = BN_new();
116 nbytes = BN_num_bytes(rsa->n);
117 decbuf = netpgp_allocate(1, nbytes);
118 (void) memcpy(decbuf, plain, plainc);
119 if (BN_bin2bn(decbuf, nbytes, decbn) == NULL) {
120 printf("bin2bn failed\n");
121 goto err;
123 if (BN_cmp(decbn, rsa->n) >= 0) {
124 printf("BN_cmp failed\n");
125 goto err;
127 if (!BN_mod_exp(encbn, decbn, rsa->e, rsa->n, NULL)) {
128 printf("BN_mod_exp failed\n");
129 goto err;
131 encc = BN_num_bytes(encbn);
132 i = BN_bn2bin(encbn, &encbuf[nbytes - encc]);
133 (void) memset(encbuf, 0x0, nbytes - i);
134 r = nbytes;
135 err:
136 if (decbuf) {
137 memset(decbuf, 0x0, nbytes);
138 netpgp_deallocate(decbuf, nbytes);
140 BN_clear_free(decbn);
141 BN_clear_free(encbn);
142 return r;
145 static int
146 lowlevel_rsa_private_decrypt(int enclen, const unsigned char *encbuf, unsigned char *to, RSA *rsa)
148 BIGNUM *encbn;
149 BIGNUM *decbn;
150 uint8_t *buf;
151 int nbytes;
152 int j;
153 int r;
155 r = -1;
156 decbn = encbn = NULL;
157 buf = NULL;
158 if (BN_num_bits(rsa->n) > RSA_MAX_MODULUS_BITS) {
159 return -1;
161 if (BN_cmp(rsa->n, rsa->e) <= 0) {
162 return -1;
164 encbn = BN_new();
165 decbn = BN_new();
166 nbytes = BN_num_bytes(rsa->n);
167 buf = netpgp_allocate(1, nbytes);
168 if (enclen > nbytes) {
169 printf("bad enclen\n");
170 goto err;
172 BN_bin2bn(encbuf, enclen, encbn);
173 if (BN_cmp(encbn, rsa->n) >= 0) {
174 printf("bad encbn\n");
175 goto err;
177 BN_mod_exp(decbn, encbn, rsa->d, rsa->n, NULL);
178 j = BN_bn2bin(decbn, buf);
179 r = rsa_padding_check_none(to, nbytes, buf, j, nbytes);
180 err:
181 BN_clear_free(encbn);
182 BN_clear_free(decbn);
183 netpgp_deallocate(buf, nbytes);
184 return r;
187 static int
188 lowlevel_rsa_public_decrypt(const uint8_t *encbuf, int enclen, uint8_t *dec, const rsa_pubkey_t *rsa)
190 uint8_t *decbuf;
191 BIGNUM *decbn;
192 BIGNUM *encbn;
193 int decbytes;
194 int nbytes;
195 int r;
197 nbytes = 0;
198 r = -1;
199 decbuf = NULL;
200 decbn = encbn = NULL;
201 if (BN_num_bits(rsa->n) > RSA_MAX_MODULUS_BITS) {
202 printf("rsa r modulus too large\n");
203 goto err;
205 if (BN_cmp(rsa->n, rsa->e) <= 0) {
206 printf("rsa r bad n value\n");
207 goto err;
209 if (BN_num_bits(rsa->n) > RSA_SMALL_MODULUS_BITS &&
210 BN_num_bits(rsa->e) > RSA_MAX_PUBEXP_BITS) {
211 printf("rsa r bad exponent limit\n");
212 goto err;
214 if ((encbn = BN_new()) == NULL ||
215 (decbn = BN_new()) == NULL ||
216 (decbuf = netpgp_allocate(1, nbytes = BN_num_bytes(rsa->n))) == NULL) {
217 printf("allocation failure\n");
218 goto err;
220 if (enclen > nbytes) {
221 printf("rsa r > mod len\n");
222 goto err;
224 if (BN_bin2bn(encbuf, enclen, encbn) == NULL) {
225 printf("null encrypted BN\n");
226 goto err;
228 if (BN_cmp(encbn, rsa->n) >= 0) {
229 printf("rsa r data too large for modulus\n");
230 goto err;
232 if (BN_mod_exp(decbn, encbn, rsa->e, rsa->n, NULL) < 0) {
233 printf("BN_mod_exp < 0\n");
234 goto err;
236 decbytes = BN_num_bytes(decbn);
237 (void) BN_bn2bin(decbn, decbuf);
238 if ((r = rsa_padding_check_none(dec, nbytes, decbuf, decbytes, 0)) < 0) {
239 printf("rsa r padding check failed\n");
241 err:
242 BN_free(encbn);
243 BN_free(decbn);
244 if (decbuf != NULL) {
245 (void) memset(decbuf, 0x0, nbytes);
246 netpgp_deallocate(decbuf, nbytes);
248 return r;
251 #if 0
253 @file rsa_make_key.c
254 RSA key generation, Tom St Denis
257 /**
258 Create an RSA key
259 @param prng An active PRNG state
260 @param wprng The index of the PRNG desired
261 @param size The size of the modulus (key size) desired (octets)
262 @param e The "e" value (public key). e==65537 is a good choice
263 @param key [out] Destination of a newly created private key pair
264 @return CRYPT_OK if successful, upon error all allocated ram is freed
266 static int
267 rsa_make_key(prng_state *prng, int wprng, int size, long e, rsa_key *key)
269 void *p, *q, *tmp1, *tmp2, *tmp3;
270 int err;
272 LTC_ARGCHK(ltc_mp.name != NULL);
273 LTC_ARGCHK(key != NULL);
275 if ((size < (MIN_RSA_SIZE/8)) || (size > (MAX_RSA_SIZE/8))) {
276 return CRYPT_INVALID_KEYSIZE;
279 if ((e < 3) || ((e & 1) == 0)) {
280 return CRYPT_INVALID_ARG;
283 if ((err = prng_is_valid(wprng)) != CRYPT_OK) {
284 return err;
287 if ((err = mp_init_multi(&p, &q, &tmp1, &tmp2, &tmp3, NULL)) != CRYPT_OK) {
288 return err;
291 /* make primes p and q (optimization provided by Wayne Scott) */
292 /* tmp3 = e */
293 if ((err = mp_set_int(tmp3, e)) != CRYPT_OK) {
294 goto errkey;
297 /* make prime "p" */
298 do {
299 if ((err = rand_prime( p, size/2, prng, wprng)) != CRYPT_OK) {
300 goto errkey;
302 /* tmp1 = p-1 */
303 if ((err = mp_sub_d( p, 1, tmp1)) != CRYPT_OK) {
304 goto errkey;
306 /* tmp2 = gcd(p-1, e) */
307 if ((err = mp_gcd( tmp1, tmp3, tmp2)) != CRYPT_OK) {
308 goto errkey;
310 } while (mp_cmp_d( tmp2, 1) != 0);
311 /* while e divides p-1 */
313 /* make prime "q" */
314 do {
315 if ((err = rand_prime( q, size/2, prng, wprng)) != CRYPT_OK) {
316 goto errkey;
318 /* tmp1 = q-1 */
319 if ((err = mp_sub_d( q, 1, tmp1)) != CRYPT_OK) {
320 goto errkey;
322 /* tmp2 = gcd(q-1, e) */
323 if ((err = mp_gcd( tmp1, tmp3, tmp2)) != CRYPT_OK) {
324 goto errkey;
326 } while (mp_cmp_d( tmp2, 1) != 0);
327 /* while e divides q-1 */
329 /* tmp1 = lcm(p-1, q-1) */
330 /* tmp2 = p-1 */
331 if ((err = mp_sub_d( p, 1, tmp2)) != CRYPT_OK) {
332 goto errkey;
334 /* tmp1 = q-1 (previous do/while loop) */
335 /* tmp1 = lcm(p-1, q-1) */
336 if ((err = mp_lcm( tmp1, tmp2, tmp1)) != CRYPT_OK) {
337 goto errkey;
340 /* make key */
341 if ((err = mp_init_multi(&key->e, &key->d, &key->N, &key->dQ, &key->dP, &key->qP, &key->p, &key->q, NULL)) != CRYPT_OK) {
342 goto errkey;
345 /* key->e = e */
346 if ((err = mp_set_int( key->e, e)) != CRYPT_OK) {
347 goto errkey;
349 /* key->d = 1/e mod lcm(p-1,q-1) */
350 if ((err = mp_invmod( key->e, tmp1, key->d)) != CRYPT_OK) {
351 goto errkey;
353 /* key->N = pq */
354 if ((err = mp_mul( p, q, key->N)) != CRYPT_OK) {
355 goto errkey;
358 /* optimize for CRT now */
359 /* find d mod q-1 and d mod p-1 */
360 /* tmp1 = q-1 */
361 if ((err = mp_sub_d( p, 1, tmp1)) != CRYPT_OK) {
362 goto errkey;
364 /* tmp2 = p-1 */
365 if ((err = mp_sub_d( q, 1, tmp2)) != CRYPT_OK) {
366 goto errkey;
368 /* dP = d mod p-1 */
369 if ((err = mp_mod( key->d, tmp1, key->dP)) != CRYPT_OK) {
370 goto errkey;
372 /* dQ = d mod q-1 */
373 if ((err = mp_mod( key->d, tmp2, key->dQ)) != CRYPT_OK) {
374 goto errkey;
376 /* qP = 1/q mod p */
377 if ((err = mp_invmod( q, p, key->qP)) != CRYPT_OK) {
378 got oerrkey;
381 if ((err = mp_copy( p, key->p)) != CRYPT_OK) {
382 goto errkey;
384 if ((err = mp_copy( q, key->q)) != CRYPT_OK) {
385 goto errkey;
388 /* set key type (in this case it's CRT optimized) */
389 key->type = PK_PRIVATE;
391 /* return ok and free temps */
392 err = CRYPT_OK;
393 goto cleanup;
394 errkey:
395 mp_clear_multi(key->d, key->e, key->N, key->dQ, key->dP, key->qP, key->p, key->q, NULL);
396 cleanup:
397 mp_clear_multi(tmp3, tmp2, tmp1, p, q, NULL);
398 return err;
400 #endif
402 #define HASHBUF_LEN 512
404 #define DSA_MAX_MODULUS_BITS 10000
406 static int
407 dsa_do_verify(const unsigned char *calculated, int dgst_len, const dsasig_t *sig, mpi_dsa_t *dsa)
409 BIGNUM *M;
410 BIGNUM *W;
411 BIGNUM *t1;
412 int ret = -1;
413 int qbits;
415 if (dsa->p == NULL || dsa->q == NULL || dsa->g == NULL) {
416 return 0;
418 M = W = t1 = NULL;
419 qbits = BN_num_bits(dsa->q);
420 switch(qbits) {
421 case 160:
422 case 224:
423 case 256:
424 /* openssl sources say these are the valid values */
425 /* according to FIPS 186-3 */
426 break;
427 default:
428 printf("dsa: bad # of Q bits\n");
429 return 0;
431 if (BN_num_bits(dsa->p) > DSA_MAX_MODULUS_BITS) {
432 printf("dsa: p too large\n");
433 return 0;
435 /* no love for SHA512? */
436 if (dgst_len > SHA256_DIGEST_LENGTH) {
437 printf("dsa: digest too long\n");
438 return 0;
440 ret = 0;
441 if ((M = BN_new()) == NULL ||
442 (W = BN_new()) == NULL ||
443 (t1 = BN_new()) == NULL) {
444 goto err;
446 if (BN_is_zero(sig->r) ||
447 BN_is_negative(sig->r) ||
448 BN_cmp(sig->r, dsa->q) >= 0) {
449 goto err;
451 if (BN_is_zero(sig->s) ||
452 BN_is_negative(sig->s) ||
453 BN_cmp(sig->s, dsa->q) >= 0) {
454 goto err;
456 if (BN_mod_inverse(W, sig->s, dsa->q, NULL) != MP_OKAY) {
457 goto err;
459 if (dgst_len > qbits / 8) {
460 dgst_len = qbits / 8;
462 if (BN_bin2bn(calculated, dgst_len, M) == NULL) {
463 goto err;
465 if (!BN_mod_mul(M, M, W, dsa->q, NULL)) {
466 goto err;
468 if (!BN_mod_mul(W, sig->r, W, dsa->q, NULL)) {
469 goto err;
471 if (!BN_mod_exp(dsa->p, t1, dsa->g, M, NULL)) {
472 goto err;
474 if (!BN_div(NULL, M, t1, dsa->q, NULL)) {
475 goto err;
477 ret = (BN_cmp(M, sig->r) == 0);
478 err:
479 if (M) {
480 BN_free(M);
482 if (W) {
483 BN_free(W);
485 if (t1) {
486 BN_free(t1);
488 return ret;
491 /*************************************************************************/
494 RSA_size(const RSA *rsa)
496 return (rsa == NULL) ? 0 : BN_num_bits(rsa->n);
500 DSA_size(const DSA *dsa)
502 return (dsa == NULL) ? 0 : BN_num_bits(dsa->p);
505 unsigned
506 dsa_verify(const signature_t *signature, const dsa_pubkey_t *pubdsa, const uint8_t *calculated, size_t hash_length)
508 mpi_dsa_t odsa;
509 dsasig_t osig;
510 unsigned qlen;
511 int ret;
513 if (signature == NULL || pubdsa == NULL || calculated == NULL) {
514 return -1;
516 (void) memset(&osig, 0x0, sizeof(osig));
517 (void) memset(&odsa, 0x0, sizeof(odsa));
518 BN_copy(osig.r, signature->dsa.r);
519 BN_copy(osig.s, signature->dsa.s);
520 odsa.p = pubdsa->p;
521 odsa.q = pubdsa->q;
522 odsa.g = pubdsa->g;
523 odsa.pub_key = pubdsa->y;
524 if ((qlen = BN_num_bytes(odsa.q)) < hash_length) {
525 hash_length = qlen;
527 ret = dsa_do_verify(calculated, (int)hash_length, &signature->dsa, &odsa);
528 if (ret < 0) {
529 return 0;
531 BN_free(odsa.p);
532 BN_free(odsa.q);
533 BN_free(odsa.g);
534 BN_free(odsa.pub_key);
535 odsa.p = odsa.q = odsa.g = odsa.pub_key = NULL;
536 BN_free(osig.r);
537 BN_free(osig.s);
538 osig.r = osig.s = NULL;
539 return (unsigned)ret;
542 RSA *
543 RSA_new(void)
545 return netpgp_allocate(1, sizeof(RSA));
548 void
549 RSA_free(RSA *rsa)
551 if (rsa) {
552 netpgp_deallocate(rsa, sizeof(*rsa));
557 RSA_check_key(RSA *rsa)
559 BIGNUM *calcn;
560 int ret;
562 ret = 0;
563 if (rsa == NULL || rsa->p == NULL || rsa->q == NULL || rsa->n == NULL) {
564 return -1;
566 /* check that p and q are coprime, and that n = p*q. */
567 if (!BN_is_prime(rsa->p, 1, NULL, NULL, NULL) ||
568 !BN_is_prime(rsa->q, 1, NULL, NULL, NULL)) {
569 return 0;
571 calcn = BN_new();
572 BN_mul(calcn, rsa->p, rsa->q, NULL);
573 if (BN_cmp(calcn, rsa->n) != 0) {
574 goto errout;
576 /* XXX - check that d*e = 1 mod (p-1*q-1) */
577 ret = 1;
578 errout:
579 BN_clear_free(calcn);
580 return ret;
583 RSA *
584 RSA_generate_key(int num, unsigned long e, void (*callback)(int,int,void *), void *cb_arg)
586 /* STUBBED */
587 USE_ARG(num);
588 USE_ARG(e);
589 USE_ARG(callback);
590 USE_ARG(cb_arg);
591 printf("RSA_generate_key stubbed\n");
592 return RSA_new();
595 /* encrypt */
597 RSA_public_encrypt(int plainc, const unsigned char *plain, unsigned char *encbuf, RSA *rsa, int padding)
599 USE_ARG(padding);
600 if (plain == NULL || encbuf == NULL || rsa == NULL) {
601 return -1;
603 return lowlevel_rsa_public_encrypt(plainc, plain, encbuf, rsa);
606 /* decrypt */
608 RSA_private_decrypt(int flen, const unsigned char *from, unsigned char *to, RSA *rsa, int padding)
610 USE_ARG(padding);
611 if (from == NULL || to == NULL || rsa == NULL) {
612 return -1;
614 return lowlevel_rsa_private_decrypt(flen, from, to, rsa);
617 /* sign */
619 RSA_private_encrypt(int plainc, const unsigned char *plain, unsigned char *encbuf, RSA *rsa, int padding)
621 USE_ARG(padding);
622 if (plain == NULL || encbuf == NULL || rsa == NULL) {
623 return -1;
625 return lowlevel_rsa_private_encrypt(plainc, plain, encbuf, rsa);
628 /* verify */
630 RSA_public_decrypt(int enclen, const unsigned char *enc, unsigned char *dec, RSA *rsa, int padding)
632 rsa_pubkey_t pub;
633 int ret;
635 if (enc == NULL || dec == NULL || rsa == NULL) {
636 return 0;
638 USE_ARG(padding);
639 (void) memset(&pub, 0x0, sizeof(pub));
640 pub.n = BN_dup(rsa->n);
641 pub.e = BN_dup(rsa->e);
642 ret = lowlevel_rsa_public_decrypt(enc, enclen, dec, &pub);
643 BN_free(pub.n);
644 BN_free(pub.e);
645 return ret;
648 /***********************************************************************/
650 DSA *
651 DSA_new(void)
653 return netpgp_allocate(1, sizeof(DSA));
656 void
657 DSA_free(DSA *dsa)
659 if (dsa) {
660 netpgp_deallocate(dsa, sizeof(*dsa));
664 DSA_SIG *
665 DSA_SIG_new(void)
667 return netpgp_allocate(1, sizeof(DSA_SIG));
670 void
671 DSA_SIG_free(DSA_SIG *sig)
673 if (sig) {
674 netpgp_deallocate(sig, sizeof(*sig));
678 DSA_SIG *
679 DSA_do_sign(const unsigned char *dgst, int dlen, DSA *dsa)
681 /* STUBBED */
682 USE_ARG(dgst);
683 USE_ARG(dlen);
684 USE_ARG(dsa);
685 printf("DSA_do_sign stubbed\n");
686 return DSA_SIG_new();
690 DSA_do_verify(const unsigned char *dgst, int dgst_len, DSA_SIG *sig, DSA *dsa)
692 if (dgst == NULL || dgst_len == 0 || sig == NULL || dsa == NULL) {
693 return -1;
695 return dsa_do_verify(dgst, dgst_len, sig, dsa);