From 63ae19daee4ac682a72730b66d8be0a3a38d41be Mon Sep 17 00:00:00 2001
From: Kyle K <kylek389@gmail.com>
Date: Thu, 17 Feb 2011 14:16:26 -0600
Subject: do some work

---
 keygen.cpp      | 72 +++++++++++++++++++++++++++++++++++++++++++++++++++------
 keygen_args.cpp | 37 ++++++++++++++++++-----------
 2 files changed, 89 insertions(+), 20 deletions(-)

diff --git a/keygen.cpp b/keygen.cpp
index 9f827f6..560d45b 100644
--- a/keygen.cpp
+++ b/keygen.cpp
@@ -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;
 }
diff --git a/keygen_args.cpp b/keygen_args.cpp
index 174227d..cc47447 100644
--- a/keygen_args.cpp
+++ b/keygen_args.cpp
@@ -8,6 +8,7 @@
  */
 
 #include "keygen_args.h"
+#include "miller_rabin.h"
 
 char *pubkey;
 char *prikey;
@@ -21,7 +22,6 @@ int keygen_args(int argc, char **argv)
     int primep_f  = 0;
     int primeq_f  = 0;
     int fname_f   = 0;
-    int random_f  = 0;
     int usage_f   = 0;
     random_f      = 0;
     int primep_args = 0;
@@ -155,6 +155,7 @@ int keygen_args(int argc, char **argv)
 
     if (primep_f)
     {
+	    /* if number was not specified or it's not a prime ask for the number */
         if (primep_args == 0)
         {
             printf("please provide a value for prime p: ");
@@ -166,18 +167,27 @@ int keygen_args(int argc, char **argv)
                 args_parsed = sscanf(line_ptr, "%ld", &prime_p);
                 if (args_parsed != 1)
                     fprintf(stderr, "invalid input, please try again: ");
-            } while (args_parsed != 1);
+                if (!miller_rabin_16(prime_p))
+                    fprintf(stderr, "not a prime number, please try again: ");
+            } while (args_parsed != 1 || !miller_rabin_16(prime_p));
         }
         else
+        {
             prime_p = atol(argv[primep_f+1]);
-
+            if (!miller_rabin_16(prime_p))
+            {
+                fprintf(stderr, "prime p on the command line is not prime\n");
+                exit(EXIT_FAILURE);
+            }
+        }
     }
 
     if (primeq_f)
     {
+	    /* if number was not specified or it's not a prime ask for the number */
         if (primeq_args == 0)
         {
-            printf("please provide a value for prime p: ");
+            printf("please provide a value for prime q: ");
 
             do
             {
@@ -186,20 +196,21 @@ int keygen_args(int argc, char **argv)
                 args_parsed = sscanf(line_ptr, "%ld", &prime_q);
                 if (args_parsed != 1)
                     fprintf(stderr, "invalid input, please try again: ");
-            } while (args_parsed != 1);
+                if (!miller_rabin_16(prime_q))
+                    fprintf(stderr, "not a prime number, please try again: ");
+            } while (args_parsed != 1 || !miller_rabin_16(prime_q));
         }
         else
+        {
             prime_q = atol(argv[primeq_f+1]);
+            if (!miller_rabin_16(prime_q))
+            {
+                fprintf(stderr, "prime q on the command line is not prime\n");
+                exit(EXIT_FAILURE);
+            }
+        }
     }
 
-#ifdef DEBUG
-    fprintf(stdout, "debug: pubkey = \"%s\"\n"
-                    "       prikey = \"%s\"\n"
-                    "       primep = \"%ld\"\n"
-                    "       primeq = \"%ld\"\n",
-            pubkey, prikey, prime_p, prime_q);
-#endif
-
     return 0;
 }
 
-- 
cgit v1.2.3