Mercurial > dropbear

annotate genrsa.c @ 994:5c5ade336926

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Prefer stronger algorithms in algorithm negotiation. Prefer diffie-hellman-group14-sha1 (2048 bit) over diffie-hellman-group1-sha1 (1024 bit). Due to meet-in-the-middle attacks the effective key length of three key 3DES is 112 bits. AES is stronger and faster then 3DES. Prefer to delay the start of compression until after authentication has completed. This avoids exposing compression code to attacks from unauthenticated users. (github pull request #9)
author Fedor Brunner <fedor.brunner@azet.sk>
date Fri, 23 Jan 2015 23:00:25 +0800
parents ae766a2c8fa7
children 750ec4ec4cbe
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"
858
220f55d540ae rename random.h to dbrandom.h since some OSes have a system random.h
Matt Johnston <matt@ucc.asn.au>
parents: 805
diff changeset
28 #include "dbrandom.h"
4
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,
794
d386defb5376 more ecdsa signkey work, not correct
Matt Johnston <matt@ucc.asn.au>
parents: 689
diff changeset
37 mp_int* rsa_e, unsigned int size_bytes);
4
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 */
586
b50f0107e505 Rename rsa_key to dropbear_rsa_key (and same for dss too) so
Matt Johnston <matt@ucc.asn.au>
parents: 477
diff changeset
40 dropbear_rsa_key * gen_rsa_priv_key(unsigned int size) {
4
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
41
586
b50f0107e505 Rename rsa_key to dropbear_rsa_key (and same for dss too) so
Matt Johnston <matt@ucc.asn.au>
parents: 477
diff changeset
42 dropbear_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
794
d386defb5376 more ecdsa signkey work, not correct
Matt Johnston <matt@ucc.asn.au>
parents: 689
diff changeset
47 if (size < 512 || size > 4096 || (size % 8 != 0)) {
d386defb5376 more ecdsa signkey work, not correct
Matt Johnston <matt@ucc.asn.au>
parents: 689
diff changeset
48 dropbear_exit("Bits must satisfy 512 <= bits <= 4096, and be a"
d386defb5376 more ecdsa signkey work, not correct
Matt Johnston <matt@ucc.asn.au>
parents: 689
diff changeset
49 " multiple of 8");
d386defb5376 more ecdsa signkey work, not correct
Matt Johnston <matt@ucc.asn.au>
parents: 689
diff changeset
50 }
d386defb5376 more ecdsa signkey work, not correct
Matt Johnston <matt@ucc.asn.au>
parents: 689
diff changeset
51
586
b50f0107e505 Rename rsa_key to dropbear_rsa_key (and same for dss too) so
Matt Johnston <matt@ucc.asn.au>
parents: 477
diff changeset
52 key = m_malloc(sizeof(*key));
805
724c3e0c8734 Add m_mp_alloc_init_multi() helper
Matt Johnston <matt@ucc.asn.au>
parents: 794
diff changeset
53 m_mp_alloc_init_multi(&key->e, &key->n, &key->d, &key->p, &key->q, NULL);
724c3e0c8734 Add m_mp_alloc_init_multi() helper
Matt Johnston <matt@ucc.asn.au>
parents: 794
diff changeset
54 m_mp_init_multi(&pminus, &lcm, &qminus, NULL);
4
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
55
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
56 if (mp_set_int(key->e, RSA_E) != MP_OKAY) {
594
a98a2138364a Improve capitalisation for all logged strings
Matt Johnston <matt@ucc.asn.au>
parents: 586
diff changeset
57 fprintf(stderr, "RSA generation failed\n");
4
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
58 exit(1);
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
892
ae766a2c8fa7 generate RSA keys of exact length
Matt Johnston <matt@ucc.asn.au>
parents: 858
diff changeset
61 while (1) {
ae766a2c8fa7 generate RSA keys of exact length
Matt Johnston <matt@ucc.asn.au>
parents: 858
diff changeset
62 getrsaprime(key->p, &pminus, key->e, size/16);
ae766a2c8fa7 generate RSA keys of exact length
Matt Johnston <matt@ucc.asn.au>
parents: 858
diff changeset
63 getrsaprime(key->q, &qminus, key->e, size/16);
4
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
64
892
ae766a2c8fa7 generate RSA keys of exact length
Matt Johnston <matt@ucc.asn.au>
parents: 858
diff changeset
65 if (mp_mul(key->p, key->q, key->n) != MP_OKAY) {
ae766a2c8fa7 generate RSA keys of exact length
Matt Johnston <matt@ucc.asn.au>
parents: 858
diff changeset
66 fprintf(stderr, "RSA generation failed\n");
ae766a2c8fa7 generate RSA keys of exact length
Matt Johnston <matt@ucc.asn.au>
parents: 858
diff changeset
67 exit(1);
ae766a2c8fa7 generate RSA keys of exact length
Matt Johnston <matt@ucc.asn.au>
parents: 858
diff changeset
68 }
ae766a2c8fa7 generate RSA keys of exact length
Matt Johnston <matt@ucc.asn.au>
parents: 858
diff changeset
69
ae766a2c8fa7 generate RSA keys of exact length
Matt Johnston <matt@ucc.asn.au>
parents: 858
diff changeset
70 if ((unsigned int)mp_count_bits(key->n) == size) {
ae766a2c8fa7 generate RSA keys of exact length
Matt Johnston <matt@ucc.asn.au>
parents: 858
diff changeset
71 break;
ae766a2c8fa7 generate RSA keys of exact length
Matt Johnston <matt@ucc.asn.au>
parents: 858
diff changeset
72 }
477
657c045054ab Remove workaround forcing rsa mpint to exactly a 8 bits multiple for putty (see
Matt Johnston <matt@ucc.asn.au>
parents: 188
diff changeset
73 }
4
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 /* lcm(p-1, q-1) */
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
76 if (mp_lcm(&pminus, &qminus, &lcm) != MP_OKAY) {
594
a98a2138364a Improve capitalisation for all logged strings
Matt Johnston <matt@ucc.asn.au>
parents: 586
diff changeset
77 fprintf(stderr, "RSA generation failed\n");
4
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
78 exit(1);
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
79 }
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
80
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
81 /* de = 1 mod lcm(p-1,q-1) */
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
82 /* 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
83 if (mp_invmod(key->e, &lcm, key->d) != MP_OKAY) {
594
a98a2138364a Improve capitalisation for all logged strings
Matt Johnston <matt@ucc.asn.au>
parents: 586
diff changeset
84 fprintf(stderr, "RSA generation failed\n");
4
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
85 exit(1);
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
86 }
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
87
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
88 mp_clear_multi(&pminus, &qminus, &lcm, NULL);
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 return key;
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
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
93 /* return a prime suitable for p or q */
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
94 static void getrsaprime(mp_int* prime, mp_int *primeminus,
794
d386defb5376 more ecdsa signkey work, not correct
Matt Johnston <matt@ucc.asn.au>
parents: 689
diff changeset
95 mp_int* rsa_e, unsigned int size_bytes) {
4
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
96
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
97 unsigned char *buf;
84
29a5c7c62350 default initialisers for mp_ints
Matt Johnston <matt@ucc.asn.au>
parents: 4
diff changeset
98 DEF_MP_INT(temp_gcd);
4
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
99
892
ae766a2c8fa7 generate RSA keys of exact length
Matt Johnston <matt@ucc.asn.au>
parents: 858
diff changeset
100 buf = (unsigned char*)m_malloc(size_bytes);
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 m_mp_init(&temp_gcd);
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
103 do {
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
104 /* 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
105 the next prime above it */
892
ae766a2c8fa7 generate RSA keys of exact length
Matt Johnston <matt@ucc.asn.au>
parents: 858
diff changeset
106 genrandom(buf, size_bytes);
ae766a2c8fa7 generate RSA keys of exact length
Matt Johnston <matt@ucc.asn.au>
parents: 858
diff changeset
107 buf[0] |= 0x80;
4
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
108
892
ae766a2c8fa7 generate RSA keys of exact length
Matt Johnston <matt@ucc.asn.au>
parents: 858
diff changeset
109 bytes_to_mp(prime, buf, size_bytes);
4
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
110
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
111 /* 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
112 if (mp_prime_next_prime(prime, 8, 0) != MP_OKAY) {
594
a98a2138364a Improve capitalisation for all logged strings
Matt Johnston <matt@ucc.asn.au>
parents: 586
diff changeset
113 fprintf(stderr, "RSA generation failed\n");
4
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
114 exit(1);
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
115 }
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
116
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
117 /* subtract one to get p-1 */
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
118 if (mp_sub_d(prime, 1, primeminus) != MP_OKAY) {
594
a98a2138364a Improve capitalisation for all logged strings
Matt Johnston <matt@ucc.asn.au>
parents: 586
diff changeset
119 fprintf(stderr, "RSA generation failed\n");
4
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
120 exit(1);
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
121 }
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
122 /* check relative primality to e */
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
123 if (mp_gcd(primeminus, rsa_e, &temp_gcd) != MP_OKAY) {
594
a98a2138364a Improve capitalisation for all logged strings
Matt Johnston <matt@ucc.asn.au>
parents: 586
diff changeset
124 fprintf(stderr, "RSA generation failed\n");
4
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
125 exit(1);
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
126 }
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
127 } 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
128
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
129 /* now we have a good value for result */
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
130 mp_clear(&temp_gcd);
892
ae766a2c8fa7 generate RSA keys of exact length
Matt Johnston <matt@ucc.asn.au>
parents: 858
diff changeset
131 m_burn(buf, size_bytes);
4
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
132 m_free(buf);
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
133 }
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
134
fe6bca95afa7 Makefile.in contains updated files required
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
135 #endif /* DROPBEAR_RSA */