Mercurial > dropbear

annotate genrsa.c @ 382:0cbe8f6dbf9e

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 2af22fb4e878750b88f80f90d439b316d229796f) to branch 'au.asn.ucc.matt.dropbear' (head 02c413252c90e9de8e03d91e9939dde3029f5c0a)
author Matt Johnston <matt@ucc.asn.au>
date Thu, 11 Jan 2007 02:41:05 +0000
parents c9483550701b
children 740e782679be 657c045054ab
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
4
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1 /*
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
2 * Dropbear - a SSH2 server
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
3 *
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
4 * Copyright (c) 2002,2003 Matt Johnston
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
5 * All rights reserved.
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
6 *
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
7 * Permission is hereby granted, free of charge, to any person obtaining a copy
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
8 * of this software and associated documentation files (the "Software"), to deal
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
9 * in the Software without restriction, including without limitation the rights
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
10 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
11 * copies of the Software, and to permit persons to whom the Software is
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
12 * furnished to do so, subject to the following conditions:
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
13 *
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
14 * The above copyright notice and this permission notice shall be included in
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
15 * all copies or substantial portions of the Software.
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
16 *
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
17 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
18 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
19 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
20 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
21 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
22 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
23 * SOFTWARE. */
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
24
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
25 #include "includes.h"
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
26 #include "dbutil.h"
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
27 #include "bignum.h"
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
28 #include "random.h"
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
29 #include "rsa.h"
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
30 #include "genrsa.h"
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
31
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
32 #define RSA_E 65537
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
33
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
34 #ifdef DROPBEAR_RSA
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
35
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
36 static void getrsaprime(mp_int* prime, mp_int *primeminus,
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
37 mp_int* rsa_e, unsigned int size);
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
38
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
39 /* mostly taken from libtomcrypt's rsa key generation routine */
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
40 rsa_key * gen_rsa_priv_key(unsigned int size) {
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
41
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
42 rsa_key * key;
84
29a5c7c62350 default initialisers for mp_ints
Matt Johnston <matt@ucc.asn.au>
parents: 4
diff changeset
43 DEF_MP_INT(pminus);
29a5c7c62350 default initialisers for mp_ints
Matt Johnston <matt@ucc.asn.au>
parents: 4
diff changeset
44 DEF_MP_INT(qminus);
29a5c7c62350 default initialisers for mp_ints
Matt Johnston <matt@ucc.asn.au>
parents: 4
diff changeset
45 DEF_MP_INT(lcm);
4
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
46
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
47 key = (rsa_key*)m_malloc(sizeof(rsa_key));
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
48
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
49 key->e = (mp_int*)m_malloc(sizeof(mp_int));
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
50 key->n = (mp_int*)m_malloc(sizeof(mp_int));
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
51 key->d = (mp_int*)m_malloc(sizeof(mp_int));
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
52 key->p = (mp_int*)m_malloc(sizeof(mp_int));
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
53 key->q = (mp_int*)m_malloc(sizeof(mp_int));
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
54
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
55 m_mp_init_multi(key->e, key->n, key->d, key->p, key->q,
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
56 &pminus, &lcm, &qminus, NULL);
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
57
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
58 seedrandom();
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
59
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
60 if (mp_set_int(key->e, RSA_E) != MP_OKAY) {
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
61 fprintf(stderr, "rsa generation failed\n");
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
62 exit(1);
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
63 }
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
64
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
65 /* PuTTY doesn't like it if the modulus isn't a multiple of 8 bits,
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
66 * so we just generate them until we get one which is OK */
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
67 getrsaprime(key->p, &pminus, key->e, size/2);
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
68 do {
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
69 getrsaprime(key->q, &qminus, key->e, size/2);
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
70
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
71 if (mp_mul(key->p, key->q, key->n) != MP_OKAY) {
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
72 fprintf(stderr, "rsa generation failed\n");
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
73 exit(1);
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
74 }
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
75 } while (mp_count_bits(key->n) % 8 != 0);
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
76
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
77 /* lcm(p-1, q-1) */
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
78 if (mp_lcm(&pminus, &qminus, &lcm) != MP_OKAY) {
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
79 fprintf(stderr, "rsa generation failed\n");
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
80 exit(1);
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
81 }
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
82
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
83 /* de = 1 mod lcm(p-1,q-1) */
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
84 /* therefore d = (e^-1) mod lcm(p-1,q-1) */
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
85 if (mp_invmod(key->e, &lcm, key->d) != MP_OKAY) {
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
86 fprintf(stderr, "rsa generation failed\n");
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
87 exit(1);
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
88 }
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
89
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
90 mp_clear_multi(&pminus, &qminus, &lcm, NULL);
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
91
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
92 return key;
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
93 }
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
94
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
95 /* return a prime suitable for p or q */
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
96 static void getrsaprime(mp_int* prime, mp_int *primeminus,
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
97 mp_int* rsa_e, unsigned int size) {
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
98
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
99 unsigned char *buf;
84
29a5c7c62350 default initialisers for mp_ints
Matt Johnston <matt@ucc.asn.au>
parents: 4
diff changeset
100 DEF_MP_INT(temp_gcd);
4
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
101
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
102 buf = (unsigned char*)m_malloc(size+1);
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
103
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
104 m_mp_init(&temp_gcd);
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
105 do {
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
106 /* generate a random odd number with MSB set, then find the
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
107 the next prime above it */
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
108 genrandom(buf, size+1);
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
109 buf[0] |= 0x80; /* MSB set */
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
110
188
c9483550701b - refactored random mp_int generation and byte->mp_int code
Matt Johnston <matt@ucc.asn.au>
parents: 84
diff changeset
111 bytes_to_mp(prime, buf, size+1);
4
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
112
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
113 /* find the next integer which is prime, 8 round of miller-rabin */
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
114 if (mp_prime_next_prime(prime, 8, 0) != MP_OKAY) {
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
115 fprintf(stderr, "rsa generation failed\n");
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
116 exit(1);
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
117 }
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
118
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
119 /* subtract one to get p-1 */
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
120 if (mp_sub_d(prime, 1, primeminus) != MP_OKAY) {
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
121 fprintf(stderr, "rsa generation failed\n");
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
122 exit(1);
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
123 }
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
124 /* check relative primality to e */
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
125 if (mp_gcd(primeminus, rsa_e, &temp_gcd) != MP_OKAY) {
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
126 fprintf(stderr, "rsa generation failed\n");
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
127 exit(1);
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
128 }
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
129 } while (mp_cmp_d(&temp_gcd, 1) != MP_EQ); /* while gcd(p-1, e) != 1 */
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
130
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
131 /* now we have a good value for result */
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
132 mp_clear(&temp_gcd);
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
133 m_burn(buf, size+1);
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
134 m_free(buf);
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
135 }
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
136
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
137 #endif /* DROPBEAR_RSA */