diff options
| -rw-r--r-- | Makefile | 35 | ||||
| -rw-r--r-- | keygen.cpp | 37 | ||||
| -rw-r--r-- | keygen.h | 25 | ||||
| -rw-r--r-- | keygen_args.cpp | 205 | ||||
| -rw-r--r-- | keygen_args.h | 19 | ||||
| -rw-r--r-- | miller_rabin.cpp | 72 | ||||
| -rw-r--r-- | miller_rabin.h | 9 |
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 + |