|
3
|
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; |
|
15
|
20 int err; |
|
3
|
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 |
