Mercurial > dropbear

comparison libtomcrypt/src/pk/rsa/rsa_make_key.c @ 285:1b9e69c058d2

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
propagate from branch 'au.asn.ucc.matt.ltc.dropbear' (head 20dccfc09627970a312d77fb41dc2970b62689c3) to branch 'au.asn.ucc.matt.dropbear' (head fdf4a7a3b97ae5046139915de7e40399cceb2c01)
author Matt Johnston <matt@ucc.asn.au>
date Wed, 08 Mar 2006 13:23:58 +0000
parents
children 0cbe8f6dbf9e
comparison
equal deleted inserted replaced
281:997e6f7dc01e 285:1b9e69c058d2
1 /* LibTomCrypt, modular cryptographic library -- Tom St Denis
2 *
3 * LibTomCrypt is a library that provides various cryptographic
4 * algorithms in a highly modular and flexible manner.
5 *
6 * The library is free for all purposes without any express
7 * guarantee it works.
8 *
9 * Tom St Denis, [email protected], http://libtomcrypt.org
10 */
11 #include "tomcrypt.h"
12
13 /**
14 @file rsa_make_key.c
15 RSA key generation, Tom St Denis
16 */
17
18 #ifdef MRSA
19
20 /**
21 Create an RSA key
22 @param prng An active PRNG state
23 @param wprng The index of the PRNG desired
24 @param size The size of the modulus (key size) desired (octets)
25 @param e The "e" value (public key). e==65537 is a good choice
26 @param key [out] Destination of a newly created private key pair
27 @return CRYPT_OK if successful, upon error all allocated ram is freed
28 */
29 int rsa_make_key(prng_state *prng, int wprng, int size, long e, rsa_key *key)
30 {
31 mp_int p, q, tmp1, tmp2, tmp3;
32 int err;
33
34 LTC_ARGCHK(key != NULL);
35
36 if ((size < (MIN_RSA_SIZE/8)) || (size > (MAX_RSA_SIZE/8))) {
37 return CRYPT_INVALID_KEYSIZE;
38 }
39
40 if ((e < 3) || ((e & 1) == 0)) {
41 return CRYPT_INVALID_ARG;
42 }
43
44 if ((err = prng_is_valid(wprng)) != CRYPT_OK) {
45 return err;
46 }
47
48 if ((err = mp_init_multi(&p, &q, &tmp1, &tmp2, &tmp3, NULL)) != MP_OKAY) {
49 return mpi_to_ltc_error(err);
50 }
51
52 /* make primes p and q (optimization provided by Wayne Scott) */
53 if ((err = mp_set_int(&tmp3, e)) != MP_OKAY) { goto error; } /* tmp3 = e */
54
55 /* make prime "p" */
56 do {
57 if ((err = rand_prime(&p, size*4, prng, wprng)) != CRYPT_OK) { goto done; }
58 if ((err = mp_sub_d(&p, 1, &tmp1)) != MP_OKAY) { goto error; } /* tmp1 = p-1 */
59 if ((err = mp_gcd(&tmp1, &tmp3, &tmp2)) != MP_OKAY) { goto error; } /* tmp2 = gcd(p-1, e) */
60 } while (mp_cmp_d(&tmp2, 1) != 0); /* while e divides p-1 */
61
62 /* make prime "q" */
63 do {
64 if ((err = rand_prime(&q, size*4, prng, wprng)) != CRYPT_OK) { goto done; }
65 if ((err = mp_sub_d(&q, 1, &tmp1)) != MP_OKAY) { goto error; } /* tmp1 = q-1 */
66 if ((err = mp_gcd(&tmp1, &tmp3, &tmp2)) != MP_OKAY) { goto error; } /* tmp2 = gcd(q-1, e) */
67 } while (mp_cmp_d(&tmp2, 1) != 0); /* while e divides q-1 */
68
69 /* tmp1 = lcm(p-1, q-1) */
70 if ((err = mp_sub_d(&p, 1, &tmp2)) != MP_OKAY) { goto error; } /* tmp2 = p-1 */
71 /* tmp1 = q-1 (previous do/while loop) */
72 if ((err = mp_lcm(&tmp1, &tmp2, &tmp1)) != MP_OKAY) { goto error; } /* tmp1 = lcm(p-1, q-1) */
73
74 /* make key */
75 if ((err = mp_init_multi(&key->e, &key->d, &key->N, &key->dQ, &key->dP,
76 &key->qP, &key->p, &key->q, NULL)) != MP_OKAY) {
77 goto error;
78 }
79
80 if ((err = mp_set_int(&key->e, e)) != MP_OKAY) { goto error2; } /* key->e = e */
81 if ((err = mp_invmod(&key->e, &tmp1, &key->d)) != MP_OKAY) { goto error2; } /* key->d = 1/e mod lcm(p-1,q-1) */
82 if ((err = mp_mul(&p, &q, &key->N)) != MP_OKAY) { goto error2; } /* key->N = pq */
83
84 /* optimize for CRT now */
85 /* find d mod q-1 and d mod p-1 */
86 if ((err = mp_sub_d(&p, 1, &tmp1)) != MP_OKAY) { goto error2; } /* tmp1 = q-1 */
87 if ((err = mp_sub_d(&q, 1, &tmp2)) != MP_OKAY) { goto error2; } /* tmp2 = p-1 */
88 if ((err = mp_mod(&key->d, &tmp1, &key->dP)) != MP_OKAY) { goto error2; } /* dP = d mod p-1 */
89 if ((err = mp_mod(&key->d, &tmp2, &key->dQ)) != MP_OKAY) { goto error2; } /* dQ = d mod q-1 */
90 if ((err = mp_invmod(&q, &p, &key->qP)) != MP_OKAY) { goto error2; } /* qP = 1/q mod p */
91
92 if ((err = mp_copy(&p, &key->p)) != MP_OKAY) { goto error2; }
93 if ((err = mp_copy(&q, &key->q)) != MP_OKAY) { goto error2; }
94
95 /* shrink ram required */
96 if ((err = mp_shrink(&key->e)) != MP_OKAY) { goto error2; }
97 if ((err = mp_shrink(&key->d)) != MP_OKAY) { goto error2; }
98 if ((err = mp_shrink(&key->N)) != MP_OKAY) { goto error2; }
99 if ((err = mp_shrink(&key->dQ)) != MP_OKAY) { goto error2; }
100 if ((err = mp_shrink(&key->dP)) != MP_OKAY) { goto error2; }
101 if ((err = mp_shrink(&key->qP)) != MP_OKAY) { goto error2; }
102 if ((err = mp_shrink(&key->p)) != MP_OKAY) { goto error2; }
103 if ((err = mp_shrink(&key->q)) != MP_OKAY) { goto error2; }
104
105 /* set key type (in this case it's CRT optimized) */
106 key->type = PK_PRIVATE;
107
108 /* return ok and free temps */
109 err = CRYPT_OK;
110 goto done;
111 error2:
112 mp_clear_multi(&key->d, &key->e, &key->N, &key->dQ, &key->dP,
113 &key->qP, &key->p, &key->q, NULL);
114 error:
115 err = mpi_to_ltc_error(err);
116 done:
117 mp_clear_multi(&tmp3, &tmp2, &tmp1, &p, &q, NULL);
118 return err;
119 }
120
121 #endif
122
123 /* $Source: /cvs/libtom/libtomcrypt/src/pk/rsa/rsa_make_key.c,v $ */
124 /* $Revision: 1.3 $ */
125 /* $Date: 2005/05/05 14:35:59 $ */