diff options
Diffstat (limited to 'keygen.cpp')
| -rw-r--r-- | keygen.cpp | 72 |
1 files changed, 65 insertions, 7 deletions
@@ -14,6 +14,33 @@ 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() */ @@ -22,15 +49,46 @@ int main(int argc, char **argv) if (keygen_args(argc, argv) == 0) cout << "read arguments successfully" << endl; - unsigned short x = rand(); - printf("x before masking: %10hu 0x%08x\n", x, x); + if (random_f) + { + prime_p = gen_prime(); + printf("generated p: %hu\n", (unsigned short) prime_p); - /* tips from http://www.di-mgt.com.au/rsa_alg.html */ - x |= LOW_BIT_ON; - x |= FIRST_TWO_BITS_ON; + 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); + } - printf("x after masking : %10hu 0x%08x\n", x, x); - printf(miller_rabin_16(x) ? "x is prime!\n" : "x is not prime\n"); +#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; } |