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
|
/*
* keygen.cpp
*
*
*/
#include "keygen.h"
#include "miller_rabin.h"
/* 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)
{
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;
/* phi = (p-1)(q-1) */
unsigned long phi = (prime_p-1) * (prime_q-1);
unsigned long fermat_primes[4] = { 3l, 17l, 65537l, 4294967297l };
unsigned long e;
/* find e, 1 < e < phi, such that gcd(e, phi) = 1 */
int i;
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);
}
#ifdef DEBUG
fprintf(stdout, "debug: pubkey = \"%s\"\n"
" prikey = \"%s\"\n"
" p = \"%ld\"\n"
" q = \"%ld\"\n"
" n = \"%lu\"\n"
" phi = \"%lu\"\n"
" e = \"%lu\"\n",
pubkey, prikey, prime_p, prime_q, n, phi, e);
#endif
return 0;
}
|
