Mercurial > dropbear

comparison libtomcrypt/src/pk/rsa/rsa_make_key.c @ 293:9d110777f345 contrib-blacklist

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
propagate from branch 'au.asn.ucc.matt.dropbear' (head 7ad1775ed65e75dbece27fe6b65bf1a234db386a) to branch 'au.asn.ucc.matt.dropbear.contrib.blacklist' (head 1d86a4f0a401cc68c2670d821a2f6366c37af143)
author Matt Johnston <matt@ucc.asn.au>
date Fri, 10 Mar 2006 06:31:29 +0000
parents 1b9e69c058d2
children 0cbe8f6dbf9e
comparison
equal deleted inserted replaced
247:c07de41b53d7 293:9d110777f345
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 $ */