15,936,119 members

C++

// Provides the key generation functions //MAX and MIN values for random numbers unsigned int MAX=256; unsigned int MIN=1; //function to calculate the multiplicative inverse of e mod r, using the extended Euclidean algorithm int gencongrel (unsigned int e, unsigned int r) { long temp, u, v, quotient, previous_u, previous_v; u = 0; previous_u = 1; v = 1; previous_v = 0; while (r != 0) //keep calculating until it reaches 0 { temp = r; //store the old value quotient = e / r; //quotient of e and r r = e % r; //calculate the new value, e mod r e = temp; //restore the old value temp = u; //store the old value u = previous_u - quotient * u; //calculate the new u using the previous one and quotient previous_u = temp; //restore the old value temp = v; //store the old value v = previous_v - quotient * v; //calculate the new v using the previous one and exponent previous_v = temp; //restore the old value } return (previous_u); } //function to calculate the greatest common denominator of two numbers, using the Euclidean algorithm int gcd(unsigned int number, unsigned int r) { unsigned int temp; while (r != 0 ) //keep calculating until it reaches 0 { temp = r; //store the old value r = number % r; //calculate the new value, number mod r number = temp; //restore the old value } return number; } //function to generate a number coprime to r called from gen_keys int gencoprime(unsigned int r) { unsigned int number; do { do //Generate a random number between MIN and MAX { number = rand() % MAX; } while (number < 3); } while (gcd(number, r) != 1); //keep generating numbers until the gcd of the generated number and r is 1 return (number); } //function to generate prime numbers, called from gen_keys int genprime (void) { unsigned int modulus, modulus_squared, prime, number, result; prime = 0; //Assume the number is not prime result = 0; while (prime == 0) //While it is not prime { modulus = 2; //Can start at 2 dividing by 1 not needed modulus_squared = 4; do //Generate a random number between MIN and MAX { number=rand() % MAX; } while (number < MIN); while (modulus_squared < number) //Only need to check up to the square root of the number { result = number % modulus; //The result is the remainder after dividing the number by the current modulus if (result == 0) //If the remainder is 0 { prime = 0; //The number is not prime break; } modulus_squared = modulus * modulus; if (modulus == 2) //If the current modulus is 2 { modulus++; //Add one to make next modulus 3 } else { modulus++; //Otherwise add 2 to keep modulus odd modulus++; } } if (result != 0) //If the result is 0 when divided by all numbers up to the square root of the number { prime = 1; //Number must be prime } } return (number); } //key generation function called from menu.c int gen_keys (void) { unsigned int p, q, e, n, r; long d; int error; srand(time(NULL)); //randomise the random number generator error = 1; do //generate two different prime numbers { p = genprime(); q = genprime(); } while (q == p); n = p * q; //n is the product of p and q r = (p - 1) * (q - 1); //r is the totient of p and q e = gencoprime(r); //e is coprime to r d = gencongrel(e, r); //d is the multiplicative inverse of e mod r if (d <= 0) { d = d + r; //d must be positive so calculate d + r to get d mod r } //Write the key files FILE *fptr; fptr = fopen("private_key.txt","w"); if (fptr != NULL) //check the file was opened correctly { fprintf(fptr,"%ld %d\n", d, n); //write the values fflush(fptr); fclose(fptr); error = 0; } fptr = fopen("public_key.txt","w"); if ((fptr != NULL) || (error == 0)) //check the file was opened correctly fprintf(fptr,"%d %d\n", e, n); //write the values out fflush(fptr); fclose(fptr); error = 0; } else { error = 1; } if (error == 0) { printf("\nKEY GENERATION SUCCESSFULL\n\n\n"); //if there wasn't an error } else { printf("\nERROR: KEY GENERATION UNSUCCESSFULL\n\n\n"); //if there was an error return(1); } return(0); }

Comments

You'll need to do this on your own. If you get stuck on a specific concept please come back and ask.

Permalink

Share this answer

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

CodeProject,
20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8
+1 (416) 849-8900

—SA