Mercurial > dropbear

comparison rsa_make_key.c @ 0:d7da3b1e1540 libtomcrypt

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
put back the 0.95 makefile which was inadvertently merged over
author Matt Johnston <matt@ucc.asn.au>
date Mon, 31 May 2004 18:21:40 +0000
parents
children 6362d3854bb4
comparison
equal deleted inserted replaced
-1:000000000000 0:d7da3b1e1540
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
12 /* RSA Code by Tom St Denis */
13 #include "mycrypt.h"
14
15 #ifdef MRSA
16
17 int rsa_make_key(prng_state *prng, int wprng, int size, long e, rsa_key *key)
18 {
19 mp_int p, q, tmp1, tmp2, tmp3;
20 int err;
21
22 _ARGCHK(key != NULL);
23
24 if ((size < (MIN_RSA_SIZE/8)) || (size > (MAX_RSA_SIZE/8))) {
25 return CRYPT_INVALID_KEYSIZE;
26 }
27
28 if ((e < 3) || ((e & 1) == 0)) {
29 return CRYPT_INVALID_ARG;
30 }
31
32 if ((err = prng_is_valid(wprng)) != CRYPT_OK) {
33 return err;
34 }
35
36 if ((err = mp_init_multi(&p, &q, &tmp1, &tmp2, &tmp3, NULL)) != MP_OKAY) {
37 return mpi_to_ltc_error(err);
38 }
39
40 /* make primes p and q (optimization provided by Wayne Scott) */
41 if ((err = mp_set_int(&tmp3, e)) != MP_OKAY) { goto error; } /* tmp3 = e */
42
43 /* make prime "p" */
44 do {
45 if ((err = rand_prime(&p, size*4, prng, wprng)) != CRYPT_OK) { goto done; }
46 if ((err = mp_sub_d(&p, 1, &tmp1)) != MP_OKAY) { goto error; } /* tmp1 = p-1 */
47 if ((err = mp_gcd(&tmp1, &tmp3, &tmp2)) != MP_OKAY) { goto error; } /* tmp2 = gcd(p-1, e) */
48 } while (mp_cmp_d(&tmp2, 1) != 0); /* while e divides p-1 */
49
50 /* make prime "q" */
51 do {
52 if ((err = rand_prime(&q, size*4, prng, wprng)) != CRYPT_OK) { goto done; }
53 if ((err = mp_sub_d(&q, 1, &tmp1)) != MP_OKAY) { goto error; } /* tmp1 = q-1 */
54 if ((err = mp_gcd(&tmp1, &tmp3, &tmp2)) != MP_OKAY) { goto error; } /* tmp2 = gcd(q-1, e) */
55 } while (mp_cmp_d(&tmp2, 1) != 0); /* while e divides q-1 */
56
57 /* tmp1 = lcm(p-1, q-1) */
58 if ((err = mp_sub_d(&p, 1, &tmp2)) != MP_OKAY) { goto error; } /* tmp2 = p-1 */
59 /* tmp1 = q-1 (previous do/while loop) */
60 if ((err = mp_lcm(&tmp1, &tmp2, &tmp1)) != MP_OKAY) { goto error; } /* tmp1 = lcm(p-1, q-1) */
61
62 /* make key */
63 if ((err = mp_init_multi(&key->e, &key->d, &key->N, &key->dQ, &key->dP,
64 &key->qP, &key->pQ, &key->p, &key->q, NULL)) != MP_OKAY) {
65 goto error;
66 }
67
68 if ((err = mp_set_int(&key->e, e)) != MP_OKAY) { goto error2; } /* key->e = e */
69 if ((err = mp_invmod(&key->e, &tmp1, &key->d)) != MP_OKAY) { goto error2; } /* key->d = 1/e mod lcm(p-1,q-1) */
70 if ((err = mp_mul(&p, &q, &key->N)) != MP_OKAY) { goto error2; } /* key->N = pq */
71
72 /* optimize for CRT now */
73 /* find d mod q-1 and d mod p-1 */
74 if ((err = mp_sub_d(&p, 1, &tmp1)) != MP_OKAY) { goto error2; } /* tmp1 = q-1 */
75 if ((err = mp_sub_d(&q, 1, &tmp2)) != MP_OKAY) { goto error2; } /* tmp2 = p-1 */
76
77 if ((err = mp_mod(&key->d, &tmp1, &key->dP)) != MP_OKAY) { goto error2; } /* dP = d mod p-1 */
78 if ((err = mp_mod(&key->d, &tmp2, &key->dQ)) != MP_OKAY) { goto error2; } /* dQ = d mod q-1 */
79
80 if ((err = mp_invmod(&q, &p, &key->qP)) != MP_OKAY) { goto error2; } /* qP = 1/q mod p */
81 if ((err = mp_mulmod(&key->qP, &q, &key->N, &key->qP)) != MP_OKAY) { goto error2; } /* qP = q * (1/q mod p) mod N */
82
83 if ((err = mp_invmod(&p, &q, &key->pQ)) != MP_OKAY) { goto error2; } /* pQ = 1/p mod q */
84 if ((err = mp_mulmod(&key->pQ, &p, &key->N, &key->pQ)) != MP_OKAY) { goto error2; } /* pQ = p * (1/p mod q) mod N */
85
86 if ((err = mp_copy(&p, &key->p)) != MP_OKAY) { goto error2; }
87 if ((err = mp_copy(&q, &key->q)) != MP_OKAY) { goto error2; }
88
89 /* shrink ram required */
90 if ((err = mp_shrink(&key->e)) != MP_OKAY) { goto error2; }
91 if ((err = mp_shrink(&key->d)) != MP_OKAY) { goto error2; }
92 if ((err = mp_shrink(&key->N)) != MP_OKAY) { goto error2; }
93 if ((err = mp_shrink(&key->dQ)) != MP_OKAY) { goto error2; }
94 if ((err = mp_shrink(&key->dP)) != MP_OKAY) { goto error2; }
95 if ((err = mp_shrink(&key->qP)) != MP_OKAY) { goto error2; }
96 if ((err = mp_shrink(&key->pQ)) != MP_OKAY) { goto error2; }
97 if ((err = mp_shrink(&key->p)) != MP_OKAY) { goto error2; }
98 if ((err = mp_shrink(&key->q)) != MP_OKAY) { goto error2; }
99
100 err = CRYPT_OK;
101 key->type = PK_PRIVATE_OPTIMIZED;
102 goto done;
103 error2:
104 mp_clear_multi(&key->d, &key->e, &key->N, &key->dQ, &key->dP,
105 &key->qP, &key->pQ, &key->p, &key->q, NULL);
106 error:
107 err = mpi_to_ltc_error(err);
108 done:
109 mp_clear_multi(&tmp3, &tmp2, &tmp1, &p, &q, NULL);
110 return err;
111 }
112
113 #endif