Mercurial > dropbear

comparison genrsa.c @ 640:76097ec1a29a dropbear-tfm

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
- Bring in original tomsfastmath patch against 0.52 from Peter Turczak in 2008
author Matt Johnston <matt@ucc.asn.au>
date Mon, 21 Nov 2011 19:19:57 +0800
parents 657c045054ab
children 2b1bb792cd4d
comparison
equal deleted inserted replaced
518:ce104c8b0be1 640:76097ec1a29a
31 31
32 #define RSA_E 65537 32 #define RSA_E 65537
33 33
34 #ifdef DROPBEAR_RSA 34 #ifdef DROPBEAR_RSA
35 35
36 static void getrsaprime(mp_int* prime, mp_int *primeminus, 36 static void getrsaprime(fp_int* prime, fp_int *primeminus,
37 mp_int* rsa_e, unsigned int size); 37 fp_int* rsa_e, unsigned int size);
38 38
39 /* mostly taken from libtomcrypt's rsa key generation routine */ 39 /* mostly taken from libtomcrypt's rsa key generation routine */
40 rsa_key * gen_rsa_priv_key(unsigned int size) { 40 rsa_key * gen_rsa_priv_key(unsigned int size) {
41 41
42 rsa_key * key; 42 rsa_key * key;
43 DEF_MP_INT(pminus); 43 DEF_FP_INT(pminus);
44 DEF_MP_INT(qminus); 44 DEF_FP_INT(qminus);
45 DEF_MP_INT(lcm); 45 DEF_FP_INT(lcm);
46 46
47 key = (rsa_key*)m_malloc(sizeof(rsa_key)); 47 key = (rsa_key*)m_malloc(sizeof(rsa_key));
48 48
49 key->e = (mp_int*)m_malloc(sizeof(mp_int)); 49 key->e = (fp_int*)m_malloc(sizeof(fp_int));
50 key->n = (mp_int*)m_malloc(sizeof(mp_int)); 50 key->n = (fp_int*)m_malloc(sizeof(fp_int));
51 key->d = (mp_int*)m_malloc(sizeof(mp_int)); 51 key->d = (fp_int*)m_malloc(sizeof(fp_int));
52 key->p = (mp_int*)m_malloc(sizeof(mp_int)); 52 key->p = (fp_int*)m_malloc(sizeof(fp_int));
53 key->q = (mp_int*)m_malloc(sizeof(mp_int)); 53 key->q = (fp_int*)m_malloc(sizeof(fp_int));
54 54
55 m_mp_init_multi(key->e, key->n, key->d, key->p, key->q, 55 m_fp_init_multi(key->e, key->n, key->d, key->p, key->q,
56 &pminus, &lcm, &qminus, NULL); 56 &pminus, &lcm, &qminus, NULL);
57 57
58 seedrandom(); 58 seedrandom();
59 59
60 if (mp_set_int(key->e, RSA_E) != MP_OKAY) { 60 fp_set(key->e, RSA_E);
61
62 getrsaprime(key->p, &pminus, key->e, size/2);
63 getrsaprime(key->q, &qminus, key->e, size/2);
64
65 fp_mul(key->p, key->q, key->n);
66
67 /* lcm(p-1, q-1) */
68 fp_lcm(&pminus, &qminus, &lcm);
69
70 /* de = 1 mod lcm(p-1,q-1) */
71 /* therefore d = (e^-1) mod lcm(p-1,q-1) */
72 if (fp_invmod(key->e, &lcm, key->d) != FP_OKAY) {
61 fprintf(stderr, "rsa generation failed\n"); 73 fprintf(stderr, "rsa generation failed\n");
62 exit(1); 74 exit(1);
63 } 75 }
64 76
65 getrsaprime(key->p, &pminus, key->e, size/2); 77 m_fp_zero_multi(&pminus, &qminus, &lcm, NULL);
66 getrsaprime(key->q, &qminus, key->e, size/2);
67
68 if (mp_mul(key->p, key->q, key->n) != MP_OKAY) {
69 fprintf(stderr, "rsa generation failed\n");
70 exit(1);
71 }
72
73 /* lcm(p-1, q-1) */
74 if (mp_lcm(&pminus, &qminus, &lcm) != MP_OKAY) {
75 fprintf(stderr, "rsa generation failed\n");
76 exit(1);
77 }
78
79 /* de = 1 mod lcm(p-1,q-1) */
80 /* therefore d = (e^-1) mod lcm(p-1,q-1) */
81 if (mp_invmod(key->e, &lcm, key->d) != MP_OKAY) {
82 fprintf(stderr, "rsa generation failed\n");
83 exit(1);
84 }
85
86 mp_clear_multi(&pminus, &qminus, &lcm, NULL);
87 78
88 return key; 79 return key;
89 } 80 }
90 81
91 /* return a prime suitable for p or q */ 82 /* return a prime suitable for p or q */
92 static void getrsaprime(mp_int* prime, mp_int *primeminus, 83 static void getrsaprime(fp_int* prime, fp_int *primeminus,
93 mp_int* rsa_e, unsigned int size) { 84 fp_int* rsa_e, unsigned int size) {
94 85
95 unsigned char *buf; 86 unsigned char *buf;
96 DEF_MP_INT(temp_gcd); 87 DEF_FP_INT(temp_gcd);
97 88
98 buf = (unsigned char*)m_malloc(size+1); 89 buf = (unsigned char*)m_malloc(size+1);
99 90
100 m_mp_init(&temp_gcd); 91 m_fp_init(&temp_gcd);
101 do { 92 do {
102 /* generate a random odd number with MSB set, then find the 93 /* generate a random odd number with MSB set, then find the
103 the next prime above it */ 94 the next prime above it */
104 genrandom(buf, size+1); 95 genrandom(buf, size+1);
105 buf[0] |= 0x80; /* MSB set */ 96 buf[0] |= 0x80; /* MSB set */
106 97
107 bytes_to_mp(prime, buf, size+1); 98 bytes_to_fp(prime, buf, size+1);
108 99
109 /* find the next integer which is prime, 8 round of miller-rabin */ 100 /* find the next integer which is prime, 8 round of miller-rabin */
110 if (mp_prime_next_prime(prime, 8, 0) != MP_OKAY) { 101 if (fp_prime_next_prime(prime, 8, 0) != FP_OKAY) {
111 fprintf(stderr, "rsa generation failed\n"); 102 fprintf(stderr, "rsa generation failed\n");
112 exit(1); 103 exit(1);
113 } 104 }
114 105
115 /* subtract one to get p-1 */ 106 /* subtract one to get p-1 */
116 if (mp_sub_d(prime, 1, primeminus) != MP_OKAY) { 107 fp_sub_d(prime, 1, primeminus);
117 fprintf(stderr, "rsa generation failed\n"); 108
118 exit(1);
119 }
120 /* check relative primality to e */ 109 /* check relative primality to e */
121 if (mp_gcd(primeminus, rsa_e, &temp_gcd) != MP_OKAY) { 110 fp_gcd(primeminus, rsa_e, &temp_gcd);
122 fprintf(stderr, "rsa generation failed\n"); 111 } while (fp_cmp_d(&temp_gcd, 1) != FP_EQ); /* while gcd(p-1, e) != 1 */
123 exit(1);
124 }
125 } while (mp_cmp_d(&temp_gcd, 1) != MP_EQ); /* while gcd(p-1, e) != 1 */
126 112
127 /* now we have a good value for result */ 113 /* now we have a good value for result */
128 mp_clear(&temp_gcd); 114 fp_zero(&temp_gcd);
129 m_burn(buf, size+1); 115 m_burn(buf, size+1);
130 m_free(buf); 116 m_free(buf);
131 } 117 }
132 118
133 #endif /* DROPBEAR_RSA */ 119 #endif /* DROPBEAR_RSA */