Initial import

7 files changed, 402 insertions, 0 deletions

diff --git a/Makefile b/Makefile
new file mode 100644
index 0000000..e2ed920
--- /dev/null
+++ b/Makefile
@@ -0,0 +1,35 @@
+# Kamil Kaminski
+# NetID: kkamin8
+#
+# CS340
+# Project 2, RSA Encryption
+#
+# Makefile
+
+PROG1 = keygen
+OBJS1 = keygen.o keygen_args.o miller_rabin.o
+CC = g++
+DBGFLAGS = -g -O0
+ifdef DEBUG
+    CFLAGS = $(DBGFLAGS) -D DEBUG -std=c++98 -pedantic-errors -Wall
+else
+    CFLAGS = -O2 -std=c++98 -pedantic-errors -Wall
+endif
+LDFLAGS = -lm
+
+$(PROG1): $(OBJS1)
+	$(CC) $(LDFLAGS) $(OBJS1) -o $(PROG1)
+
+keygen.o: %.o: %.cpp
+	$(CC) -c $(CFLAGS) $<
+
+keygen_args.o: %.o: %.cpp %.h
+	$(CC) -c $(CFLAGS) $<
+
+miller_rabin.o: %.o: %.cpp %.h
+	$(CC) -c $(CFLAGS) $<
+
+.PHONY: clean
+
+clean:
+	rm -f ./$(OBJS1) ./$(PROG1)
diff --git a/keygen.cpp b/keygen.cpp
new file mode 100644
index 0000000..9f827f6
--- /dev/null
+++ b/keygen.cpp
@@ -0,0 +1,37 @@
+/*
+ * 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;
+
+int main(int argc, char **argv)
+{
+    /* seed rand() */
+    srand((unsigned int ) time(NULL));
+
+    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);
+
+    /* tips from http://www.di-mgt.com.au/rsa_alg.html */
+    x |= LOW_BIT_ON;
+    x |= FIRST_TWO_BITS_ON;
+
+    printf("x after masking : %10hu 0x%08x\n", x, x);
+    printf(miller_rabin_16(x) ? "x is prime!\n" : "x is not prime\n");
+
+    return 0;
+}
+
diff --git a/keygen.h b/keygen.h
new file mode 100644
index 0000000..9258265
--- /dev/null
+++ b/keygen.h
@@ -0,0 +1,25 @@
+#ifndef _KEYGEN_H_
+#define _KEYGEN_H_
+
+#include <iostream>
+#include <ctime>
+#include "keygen_args.h"
+
+/* use as am aid in prime number creation */
+#define LOW_BIT_ON        1 << 0
+#define FIRST_TWO_BITS_ON 3 << ((sizeof(unsigned short) * 8) - 2)
+
+using namespace std;
+
+class keygen
+{
+    protected:
+
+    private:
+
+    public:
+        keygen() {};
+};
+
+#endif
+
diff --git a/keygen_args.cpp b/keygen_args.cpp
new file mode 100644
index 0000000..174227d
--- /dev/null
+++ b/keygen_args.cpp
@@ -0,0 +1,205 @@
+/*
+ * keygen_args.cpp
+ *
+ * Notes: since argv[] array contains c-style char strings, I chose to use C
+ *        functions to work on them instead of dealing with C++ class string
+ *        conversions.
+ *
+ */
+
+#include "keygen_args.h"
+
+char *pubkey;
+char *prikey;
+long prime_p;
+long prime_q;
+int random_f;
+
+int keygen_args(int argc, char **argv)
+{
+    /* flags */
+    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;
+    int primeq_args = 0;
+    int fname_args  = 0;
+    int opt_args    = 0;
+
+    int i;
+    for (i = 1; i < argc; i++)
+    {
+        if (argc > 9)
+        {
+            fprintf(stderr, "too many options\n");
+            usage_f = 1;
+            break;
+        }
+
+        /* skip non option arguments */
+        if (!strchr(argv[i], '-'))
+        {
+            opt_args++;
+
+            if (primep_f)
+            {
+                if (i-1 == primep_f)
+                    primep_args++;
+
+                /* not allowed to have 2 args */
+                if ((i-2 == primep_f) && argv[i-1][0] != '-')
+                {
+                    fprintf(stderr, "too many arguments to \"-p\" option\n");
+                    usage_f = 1;
+                    break;
+                }
+            }
+
+            if (primeq_f)
+            {
+                if (i-1 == primeq_f)
+                    primeq_args++;
+
+                /* not allowed to have 2 args */
+                if ((i-2 == primeq_f) && argv[i-1][0] != '-')
+                {
+                    fprintf(stderr, "too many arguments to \"-q\" option\n");
+                    usage_f = 1;
+                    break;
+                }
+            }
+
+            if (fname_f)
+            {
+                if ((i-1 == fname_f) || (i-2 == fname_f))
+                    fname_args++;
+
+                if ((i-3 == fname_f)) /* not allowed to have 3 args */
+                {
+                    fprintf(stderr, "too many arguments to \"-o\" option\n");
+                    usage_f = 1;
+                    break;
+                }
+            }
+
+            continue;
+        }
+        else if (strcmp(argv[i], "-p") == 0)
+            primep_f = i;
+        else if (strcmp(argv[i], "-q") == 0)
+            primeq_f = i;
+        else if (strcmp(argv[i], "-o") == 0)
+            fname_f = i;
+        else if (strcmp(argv[i], "-c") == 0)
+            random_f = i;
+        else
+        {
+            fprintf(stderr, "unknown option \"%s\"\n", argv[i]);
+            usage_f = 1;
+            break;
+        }
+    }
+
+    /* error checking */
+    if (usage_f || opt_args > 4 || fname_args == 1)
+    {
+        if (fname_args == 1)
+            fprintf(stderr, "too few arguments to \"-o\" option\n");
+        printf("usage: %s [-p] [-q] [-o pubkey prikey] [-c]\n", argv[0]);
+        exit(EXIT_FAILURE);
+    }
+
+    ssize_t amount_read = 0;
+    int args_parsed = 0;
+    size_t line_sz = 80;
+    char *line_ptr = (char *) malloc(sizeof(char) * line_sz);
+
+    /* handle key filenames */
+    if (fname_args == 2)
+    {
+        pubkey = strdup(argv[fname_f+1]);
+        prikey = strdup(argv[fname_f+2]);
+    }
+    else if (fname_f) /* fname_args equals 0 here */
+    {
+        /* ask user for the filenames */
+        puts("please provide pubkey and prikey filenames separated by a space");
+        printf("e.g. \"pubkey.xml prikey.xml\": ");
+
+
+        pubkey = (char *) malloc(sizeof(char) * 100);
+        prikey = (char *) malloc(sizeof(char) * 100);
+        if (!line_ptr || !pubkey || !prikey)
+        {
+            perror("malloc");
+            exit(EXIT_FAILURE);
+        }
+
+        do
+        {
+            fflush(stdin);
+            amount_read = getline(&line_ptr, &line_sz, stdin);
+            args_parsed = sscanf(line_ptr, "%s %s", pubkey, prikey);
+            if (args_parsed != 2)
+                fprintf(stderr, "invalid input, please try again: ");
+        } while (args_parsed != 2);
+    }
+    else
+    {
+        pubkey = strdup("pubkey.xml");
+        prikey = strdup("prikey.xml");
+    }
+
+    if (primep_f)
+    {
+        if (primep_args == 0)
+        {
+            printf("please provide a value for prime p: ");
+
+            do
+            {
+                fflush(stdin);
+                amount_read = getline(&line_ptr, &line_sz, stdin);
+                args_parsed = sscanf(line_ptr, "%ld", &prime_p);
+                if (args_parsed != 1)
+                    fprintf(stderr, "invalid input, please try again: ");
+            } while (args_parsed != 1);
+        }
+        else
+            prime_p = atol(argv[primep_f+1]);
+
+    }
+
+    if (primeq_f)
+    {
+        if (primeq_args == 0)
+        {
+            printf("please provide a value for prime p: ");
+
+            do
+            {
+                fflush(stdin);
+                amount_read = getline(&line_ptr, &line_sz, stdin);
+                args_parsed = sscanf(line_ptr, "%ld", &prime_q);
+                if (args_parsed != 1)
+                    fprintf(stderr, "invalid input, please try again: ");
+            } while (args_parsed != 1);
+        }
+        else
+            prime_q = atol(argv[primeq_f+1]);
+    }
+
+#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;
+}
+
diff --git a/keygen_args.h b/keygen_args.h
new file mode 100644
index 0000000..c9d0bce
--- /dev/null
+++ b/keygen_args.h
@@ -0,0 +1,19 @@
+#ifndef _KEYGEN_ARGS_
+#define _KEYGEN_ARGS_
+
+#include <cstdio>
+#include <cstdlib>
+#include <cstring>
+
+/* global variables */
+extern char *pubkey;
+extern char *prikey;
+extern long prime_p;
+extern long prime_q;
+extern int random_f;
+
+/* function protypes */
+int keygen_args(int, char **);
+
+#endif
+
diff --git a/miller_rabin.cpp b/miller_rabin.cpp
new file mode 100644
index 0000000..4d2249e
--- /dev/null
+++ b/miller_rabin.cpp
@@ -0,0 +1,72 @@
+/* Source:
+ * http://en.literateprograms.org/Miller-Rabin_primality_test_%28C%29
+ *
+ */
+
+#include <stdio.h>
+#include <stdlib.h>
+
+#define COMPOSITE 0
+#define PRIME     1
+
+unsigned short modular_exponent_16(unsigned short base, unsigned short power,
+                                   unsigned short modulus)
+{
+    unsigned long result = 1;
+
+    int i;
+    for (i = 15; i >= 0; i--)
+    {
+        result = (result*result) % modulus;
+
+        if (power & (1 << i))
+            result = (result*base) % modulus;
+    }
+
+    return (unsigned short) result; /* will not truncate since modulus is a unsigned short */
+}
+
+int miller_rabin_pass_16(unsigned short a, unsigned short n)
+{
+    unsigned short a_to_power, s, d, i;
+
+    s = 0;
+    d = n - 1;
+    while ((d % 2) == 0)
+    {
+        d /= 2;
+        s++;
+    }
+
+    a_to_power = modular_exponent_16(a, d, n);
+
+    if (a_to_power == 1)
+        return PRIME;
+
+    for (i = 0; i < s-1; i++)
+    {
+        if (a_to_power == n-1)
+            return PRIME;
+        a_to_power = modular_exponent_16(a_to_power, 2, n);
+    }
+
+    if (a_to_power == n-1)
+        return PRIME;
+
+    return COMPOSITE;
+}
+
+int miller_rabin_16(unsigned short n)
+{
+    if (n <= 1)
+        return COMPOSITE;
+    if (n == 2)
+        return PRIME;
+    if (miller_rabin_pass_16( 2, n) == PRIME &&
+        (n <= 7  || miller_rabin_pass_16( 7, n) == PRIME) &&
+        (n <= 61 || miller_rabin_pass_16(61, n) == PRIME))
+        return PRIME;
+    else
+        return COMPOSITE;
+}
+
diff --git a/miller_rabin.h b/miller_rabin.h
new file mode 100644
index 0000000..f6d162e
--- /dev/null
+++ b/miller_rabin.h
@@ -0,0 +1,9 @@
+#ifndef _MILLER_RABIN_H_
+#define _MILLER_RABIN_H_
+
+unsigned short modular_exponent_16(unsigned short, unsigned short, unsigned short);
+int miller_rabin_pass_16(unsigned short, unsigned short);
+int miller_rabin_16(unsigned short);
+
+#endif
+