Hello everyone!
I am trying to write a program in C for the RSA encryption. I have come this far and can't seem to go further. I don't understand why it is not giving me the desired results. My program style may be a bit naive i am just starting off with C. but please i do need some help.
Any nip and tucking or helpful changes?
I have tried to translate the comments into english.
// FinalProject.
// RSA ENCRYTION REQUIREMENTS
// 'p' and 'q' Primenumbers. n= p*q
// 'e' encryption key 'd' decryption key. [n, e] Public key pair, known to all. [n, d] Private key
//pair known to user alice bob or whoever.
// Encryption function C= M^e mod n. Decryption function M= C^d mod n ; M = message in ASCII code. C= Coded message
// e is greater than 1 und has no prime factors with z in common.
//(e*d)mod z=1
//#include <conio.h>
#include <stdio.h>
#include "stdafx.h"
#define scanf fflush(NULL); scanf
const int maxnum=100;
long z, n, e, d, C, M;
/*Defining functions*/
/*** PRIME GEN ***/
/*is supposed to generate all prime numbers from one to 10000*/
void primegen()
{
int zahlen[10000]; //Array der zu überprüfenden Zahlen
int zaehler = 2; //Zählvariable
int izaehler; //Funktionsinterner Zähler
int x;
zahlen[0] = 0; //Exception
zahlen[1] = 0; //Exception
for (x=2;x<(sizeof(zahlen)/sizeof(int));x++)
{
zahlen[x] = 4;
}
for(zaehler;zaehler <= (sizeof(zahlen)/sizeof(int));zaehler++)
/*All elements of the array are examined*/
{
if(zahlen[zaehler]==4) //Wenn des jeweilige Element der Zählvariable 0 ist, dann ist das jeweilige Element eine Primzahl
{
printf("%i\n",zaehler); //Ausgabe
for(izaehler = 1;(izaehler*zaehler) < (sizeof(zahlen)/sizeof(int));++izaehler) //Setze alle Elemente, die das ganzzahlige Vielfache der Primzahl sind auf 1 -> Dh. dass diese keine Primzahlen sind
{
zahlen[(izaehler*zaehler)] = 1;
}
}
}
//getchar();
}
/***ENCRYPTION FUNCTION***/
void ziffern()
{
int i; //for schleife.
C=1;
for (i=0; i<e; i++)
{
C=C*M%n;
C=C%n;
// text wird auf dem Bildschirm gezeigt. Text displayed on screen
}
printf("\n\t Chiffrierter Text: %ld\n", C);
//[(a mod b)*(b mod n)]mod n = (a*b)mod n.
//1st step.C* M mod n, 2nd Step C*C *M mod n,... eth Step C^e M mod n.
}
/***DECRYPTION FUNCTION***/
void entziffern()
{
int i;
M=1;
for (i=0; i<d; i++)
M=M*C%n;
M=M%n;
printf("\n\t Dechiffrierter Text: %ld\n", M);
}
/***PRIME NUMBER CHECK***/
/*the user chooses prime numbers from the list of numbers generated by PRIMEGEN and in case he makes an error, the NEXTPRIME finds the nearest prime number*/
long nextPrime(long prePrime)
{
/*prePrime is the supposed prime number given in by the user.*/
bool isPrime = true;
long start = prePrime; /*this variable is just meant to hold prePrime for a while*/
while (isPrime)
{
if (prePrime == 0)
break;
else if (prePrime == 1)
break;
for (long i = 2; i <= prePrime; i++)
{
if (start == i)
break;
else if ((prePrime % i) == 0) /*Factor different from 1 found i.e. not prime!*/
{
prePrime++; /*next number is examined*/
i = 2; /*loop is restarted at the initial point.*/
}
}
printf( "Number entered is invalid! The nearest prime ist %ld: prePrime ") ;
isPrime = false; //break loop!
}
/*nextPrimeNum = prePrime;*/
return (prePrime);
}
/***HIGHEST COMMON FACTOR***/
/*using this to make sure ‘e’ has no factors in common with ‘z’*/
long ggT (long zahl1, long zahl2)
{
long x, y, hilf;
long rest=x%y;
if(zahl2>zahl1)
{
hilf=zahl1;
zahl1=zahl2;
zahl2=hilf;
}
if (zahl2>0)
{
x=zahl1;
y=zahl2;
while(rest != 0)
{
rest = x%y;
x=y;
y=rest;
printf("Steps: ggT(%ld, ld%) = %ld\n", x, y, rest);
printf ("ggT (%ld, %ld) = %ld \n", zahl1, zahl2, x);
/*HCF of #1 and #2 equals x*/
}
}
else
{
printf ("Ungültige Eingabe! \n");
}
return (x);
}
// User prompt
/***MAIN PROGRAM***/
void main()
{
long p, q, i;
char wunsch;
printf("primegen: ");
primegen();
printf("Choose the first random prime numbers from the list of numbers: \t");
scanf("%ld ",&p);
p=nextPrime(p);
printf("Choose the second random prime numbers from the list of numbers \t");
scanf("%ld ",&q);
q=nextPrime(q);
z = (p-1)*(q-1);
n = p * q;
printf("\n\t Z = %ld", z);
printf("Please give in a value for e\t: " );
scanf("%ld ",&e);
/*if e value is invalid,the next valid e is choosen*/
do{
for(int i=2; i<=e; i++)
{
e++;
ggT(e, z);
i=2;
}
}while (ggT(e,z)!=1);
printf ("Eingabe ungültig. Den Wert %ld wurde für e ausgesucht!", e);
/*Because e*d mod z =1, we set i to 1, and calculate the value of d.*/
d=1; /*starting point, d=0 makes no sense here*/
do
{
i=(d*e)%z;
d++;
}while(i!=1);
d=d-1;
//User prompt entcrypt or decrypt
printf ("\n\n encrypt or decrypt?(Z\\E):");
wunsch = getchar();
switch (getchar()) {
case 'z': case 'Z':
printf ("\n\n Enter plain text\t:");
scanf("%ld", &M);
ziffern();
break;
case 'e': case 'E':
printf("\n\n Enter encrypted text\t: ");
scanf("%ld", &C);
entziffern();
break;
default : printf("\n Enter z oder e \n");
//getch(); // member of conio.h read xter directly from the console without buffer and without echo.
}
//return 0;
}