1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
|
/*
* keygen.cpp
*
*
*/
#include "keygen.h"
#include "miller_rabin.h"
#ifndef DEBUG
#define DEBUG
#endif
/* forward declaration of variables from keygen_args.h */
extern char *pubkey;
extern char *prikey;
extern long prime_p;
extern long prime_q;
extern int random_f;
unsigned long gcd(unsigned long x, unsigned long y)
{
while (x != y)
{
if (x > y)
x -= y;
else
y -= x;
}
return x;
}
unsigned short gen_prime(void)
{
unsigned short prime_gen = rand();
/* tips from http://www.di-mgt.com.au/rsa_alg.html */
prime_gen |= LOW_BIT_ON;
prime_gen |= FIRST_TWO_BITS_ON;
while (!miller_rabin_16(prime_gen))
prime_gen += 2;
return prime_gen;
}
int main(int argc, char **argv)
{
/* seed rand() */
srand((unsigned int ) time(NULL));
if (keygen_args(argc, argv) == 0)
cout << "read arguments successfully" << endl;
if (random_f)
{
printf("generating random primes...\n");
prime_p = gen_prime();
printf("generated p: %hu\n", (unsigned short) prime_p);
prime_q = gen_prime();
printf("generated q: %hu\n", (unsigned short) prime_q);
}
/* n = p * q */
unsigned long n = prime_p * prime_q;
if (n <= 127)
{
fprintf(stderr, "p * q needs to be bigger than 127\n");
exit(EXIT_FAILURE);
}
/* phi = (p-1)(q-1) */
unsigned long phi = (prime_p-1) * (prime_q-1);
unsigned long fermat_primes[4] = { 3l, 17l, 19l, 31l };
unsigned long e;
/* find e, 1 < e < phi, such that gcd(e, phi) = 1 */
int i;
printf("computing e... ");
for (i = 0; i < 4; i++)
{
e = fermat_primes[i];
if (gcd(e, phi) == 1)
break;
}
if (i == 4)
{
fprintf(stderr, "error, could not find e\n");
exit(EXIT_FAILURE);
}
printf("done\n");
/* find d */
printf("computing d... (might take a while) ");
fflush(stdout);
unsigned long d = 1;
while (1)
{
if ( ((e*d) % phi) == 1 )
break;
d++;
}
printf("done\n");
#ifdef DEBUG
printf("debug: pubkey = \"%s\"\n"
" prikey = \"%s\"\n"
" p = \"%ld\"\n"
" q = \"%ld\"\n"
" n = \"%lu\"\n"
" phi = \"%lu\"\n"
" e = \"%lu\"\n"
" d = \"%lu\"\n",
pubkey, prikey, prime_p, prime_q, n, phi, e, d);
#endif
/* save to xml files */
FILE *public_key = fopen(pubkey, "w");
FILE *private_key = fopen(prikey, "w");
if (public_key == NULL || private_key == NULL)
{
perror("fopen");
exit(EXIT_FAILURE);
}
fprintf(public_key, "<rsakey>\n");
fprintf(public_key, "\t<evalue>%lu</evalue>\n", e);
fprintf(public_key, "\t<nvalue>%lu</nvalue>\n", n);
fprintf(public_key, "</rsakey>\n");
printf("wrote \"%s\" file\n", pubkey);
fprintf(private_key, "<rsakey>\n");
fprintf(private_key, "\t<dvalue>%lu</dvalue>\n", d);
fprintf(private_key, "\t<nvalue>%lu</nvalue>\n", n);
fprintf(private_key, "</rsakey>\n");
printf("wrote \"%s\" file\n", prikey);
fclose(public_key);
fclose(private_key);
return 0;
}
|
