RSA program

fwongmc · #1 07-Nov-2004, 06:37

Dear fellows,

I am new to C.My tutor ask us to write a C program with limitations,for decoding and encoding similiar to RSA.

The question are as follows:
-----------------------------------------------------------------------------------------------
To encode a message,one needs n and e.The value n is a product of any two prime numbers p and q.The value e is any number less than n that cannot be evenly divided into y(i.e. y/e would have a reminder),where y=(p-1)*(q-1).The values n and e can be published in a newspaper or posted on the internet,so anybody can encrypt messages.The original character is than encoded to a numerical value c using the formula:

c=m^e mod n
where m is a numerical representation of the original character(65=A,66=B..etc)
Now,to decode a messages,one needs d.The value d is a number that statisfies the formula:

(e*d) mod y ==1
where e and y are the values defined in the encoding step.The original character m can be derived from the encrypted character c by using the formula:
m=c^d mod n
To write a program that encodes and decodes message using this system,you will need to generate the oublic and secret key pairs:
Public key (KU)=(e,n) Secret key KR=(d,n)

Limitations:
1.Only functions is allowed
2.Simple Calculations(+-*/) is allowed.No power (x^y) is allowed
3.For the calculations,((a mod n)*(b mod n)) mod n == (a* mod n

fwongmc Posted: Nov 5 2004, 05:17 PM

Newbie

Group: Members
Posts: 9
Member No.: 683
Joined: 5-November 04

(cont'd)

3.Hints

(a mod n)*(b mod n)) mod n == (a*b)mod n

-----------------------------------------------------------------------------------------------
Sample run:
Do you want to start? (Y/N) y
Please enter the public key e:5
Please enter the common key n:119
Please enter the private key e:77
Encrypt or Decrypt? (E/D) e
Please enter 5 characters.
abcde
The encrypted message in number format is 20 98 29 52 35
Do you want to play again? (y/n)y
Encrypt or Decrypt? (E/D) d
Please enter 5 numbers.
20 98 29 53 33
The decrypted message char format is a b c d e

Do you want to play again? (y/n)n
Thank you for using this program.

------------------------------------------

CPP / C++ / C Code:

#include <stdio.h>

int prime=1;
int i,number;
int num1,num2,num3,num4,num5;
int e,n,d,y,p,q;
int is_prime(int n){
	for (i=2;i<n;i++){
		if(n%i==0)
			return 0;
			}
			return 1;
			}

int decrypt(int num){
int a=1;
int i;
{for (i=1;i<=e;i++){
		a=(num%n)*a;
		}
		num=(a%n);
		return (num);
		}		
		return 0;
		}


int encrypt(int num){
int a=1;
int i;
{for (i=1;i<=d;i++){
		a=(num%n)*a;
		}
		num=(a%n);
		return (num);
		}
		return 0;
		}

int check_div(int x){
int i=1;
int a=0;
{
do {
		a=(n%i);
		i++;  }while (n%i>0);
		return (i);
		}
		return 0;
		 }

 

int main (void){
char choice,choice2;
char choice3='y';
printf ("Do you want to start?");
	scanf("%c",&choice);
if ((choice=='n')||(choice=='N')){
	printf ("Thank you for using this program.");}

if ((choice=='y')||(choice=='Y'))
	printf ("Please enter the Public Key e:");
		scanf ("%d",&e);
	printf ("Please enter the common key n:");
		scanf ("%d",&n);
	printf ("Please enter the private key:");
		scanf ("%d",&d);



/*To find the factors of n QUESTION 2*/
if (check_div(n)>0){
	p=check_div(n);
	q=n/p;}

/*To check if p and q are prime numbers*/
if ((is_prime(p)==1)&&(is_prime(q)==1)){
	y=(p-1)*(q-1);}
if ((is_prime(p)==0)||(is_prime(q)==0)){
	printf ("Check your common key.");}

/*Prompt user to select encrypt nor decrypt*/
printf ("Encrypt or Decrypt? (E/D)");
	scanf ("%c",&choice2);

do {
	if ((choice2=='e')||(choice2=='E')){
		printf ("Please enter 5 characters.");
		scanf ("%d %d %d %d %d",&num1,&num2,&num3,&num4,&num5);
		printf ("The encrypted message in number format is %d %d %d %d %d",decrypt(num1),decrypt(num2),decrypt(num3),decrypt(num4),decrypt(num5));
		printf ("Do you want to play again ?(Y/N)");
		scanf ("%c",&choice3);}

	if ((choice2=='d')||(choice2=='D')){
		printf ("Please enter 5 numbers.");
		scanf ("%d %d %d %d %d",&num1,&num2,&num3,&num4,&num5);
			if ((e*d)%y==1){
				printf ("The decrypted message char format is %c %c %c %c %c",encrypt(num1),encrypt(num2),encrypt(num3),encrypt(num4),encrypt(num5));}
				printf ("Do you want to play again ?(Y/N)");
				scanf ("%c",&choice3);}
	}  while ((choice3=='y')||(choice3=='Y'));
printf ("Thank you for using this program.");
}

but it seems that it can't works...it stop when asking user for decrypt/encrypt.I don't know wether is the condition statement wrong and/or the function wrong(can either be <decrypt>,<encrypt>,<check_div>).Can anyone help me to check check and tell me what the error was?URGENT!Thanks.i

davekw7x · #2 07-Nov-2004, 10:34

Quote:

Originally Posted by fwongmc

but it seems that it can't works...it stop when asking user for decrypt/encrypt.I don't know wether is the condition statement wrong and/or the function wrong(can either be <decrypt>,<encrypt>,<check_div>).Can anyone help me to check check and tell me what the error was?URGENT!Thanks.i

You have discovered the reason that experienced programmers rarely use scanf() for user keyboard input. (Typically they use fgets() to read an entire line, then use atoi(), sscanf(), or some other method to get values for the input variables). Now, you can use scanf(), but you have to be aware of a couple of things.

When you have something like the following, you have to do something special:

CPP / C++ / C Code:

    printf ("Please enter the private key:");
    scanf ("%d",&d);

    printf ("Encrypt or Decrypt? (E/D)");
    scanf ("%c",&choice2);

After the scanf("%d",...) is executed, the input buffer still has at least one character remaining (the newline, '\n').

If the next scanf() is also for %d, the function reads and discards the newline, and waits for another line to be entered by the user, then tries to read a decimal number from the input buffer.

If the next scanf() after the %d is scanf("%c",...), the function reads the newline character into the input variable (not what you had in mind).

One way around this, is something like the following, from a recent thread on this board:

CPP / C++ / C Code:

    printf ("Please enter the private key:");
    scanf ("%d",&d);
     
     while (getchar() != '\n')   /* read and discard all chars up to and including the newline */
         ;
    printf ("Encrypt or Decrypt? (E/D)");
    scanf ("%c",&choice2);

One other extremely important point (after you have tamed the wild and wooly scanf()): In every program that gets user input (from the keyboard or from a file, or whatever), the program must (must) be able to recover from bad data.

So if you tell the user to enter E/D, you must be prepared for something else:

CPP / C++ / C Code:

    if ((choice2=='e')||(choice2=='E')){
    /* do the Encrypt stuff here */
    }

    else if((choice2=='d')||(choice2=='D')){
     /* do the Decrypt stuff here */
    else {
     /* print error message, then go back and give the user */
     /* another chance, or bail out of the program, or ... */
    }

One final point:

When you use scanf() to get a numeric value, what if the user enters something else?

Try your program (after the getchar() fix that I suggested above), and when
the program asks for the public key, enter something that is not a number.

What happens?

You should always check to see if the user entered something numeric. Since scanf() returns an int that is the number of items converted according to the format specifier, you can use something like this:

CPP / C++ / C Code:

   printf ("Please enter the Public Key e:");
      if (scanf ("%d",&e) != 1) {/* since we are looking for one int */
      printf("You must enter an integer value for the key\n");
      /* now you put code here to recover or to end the program */
      /* you coult put the prompt and scanf in a loop or something */
     }

Regards,

Dave

WaltP · #3 07-Nov-2004, 10:45

My guess is improper use of scanf(), improper use being you actually are using it

To read a character as you are doing would be better suited to getchar() function. What is happening is when you enter your character, you are actually entering 2 characters, the second one being a newline (\n). That character is left in the buffer and will cause you no end of trouble. Two solutions:
1) use getchar() -- it's made for reading single characters and therefore you will not be pulling all the unneccesary conversions (string to float, integer, etc) into your program. The newline is still there so you use:

CPP / C++ / C Code:

choice = getchar();
do 
{ 
    dummychar = getchar();
}    while (dummychar != '\n')

This will clear the buffer for next time.
2) convert all your choicex variables to buffers of say 10 characters and read an entire line:

CPP / C++ / C Code:

fgets(choice2, 10, stdin);

This will read up to 9 characters, including the newline. Then choice2[0] will be the character you want.

Now with your integer reads

CPP / C++ / C Code:

printf ("Please enter the common key n:");
scanf ("%d",&n);

use

CPP / C++ / C Code:

printf ("Please enter the common key n:");
fgets (dummybuffer, 20, stdin);  // read a line
n = atoi(dummy buffer);  Convert to integer

This will keep your input buffer clean of all the junk scanf leaves in the buffer. Of course you have to define dummybuffer to be a character array of 20...

WaltP · #4 07-Nov-2004, 10:51

Dave, I have only one issue with what you recommended. That is:

CPP / C++ / C Code:

    printf ("Please enter the private key:");
    scanf ("%d",&d);
     
     while (getchar() != '\n')   /* read and discard all chars up to and including the newline */
         ;
    printf ("Encrypt or Decrypt? (E/D)");
    scanf ("%c",&choice2);

Many times the scanf() in this scenario (reading ints) will actually read off the whitespace (\n in this case) so the program will hang waiting for input. Better to just avoid scanf() like the plague it is...

davekw7x · #5 07-Nov-2004, 11:49

Quote:

Originally Posted by WaltP

Dave, I have only one issue with what you recommended. That is:

CPP / C++ / C Code:

    printf ("Please enter the private key:");
    scanf ("%d",&d);
     
     while (getchar() != '\n')   /* read and discard all chars up to and including the newline */
         ;
    printf ("Encrypt or Decrypt? (E/D)");
    scanf ("%c",&choice2);

Many times the scanf() in this scenario (reading ints) will actually read off the whitespace (\n in this case) so the program will hang waiting for input. Better to just avoid scanf() like the plague it is... ;)

You are, of course, correct. That's why most experienced users don't use scanf(). I heartily dis-recommend scanf() for user input.

At the beginning of a class, or for beginning programmers studying on their own, scanf() may be all that they know about. Careful use of scanf() can at least let the programmer get started and run some programs.

So, it is possible to use scanf(), but after a few trials, the new programmer sees what problems can arise, and is then more receptive to suggestions about fgets().

C++ programmers have the same issues with cin>>, and usually end up begging for something better (and we give them getline());

Now, I have a point about fgets().

If you have something like

CPP / C++ / C Code:

  char choice2[10];

   /* stuff here */

  fgets(choice2, 10, stdin);

This guarantees that no more than 10 characters will be written to the array, so we avoid the dreaded "buffer overflow", but what if the user enters 10 or more characters? The first nine are written into the array (and a terminating '\0' ).The remaining input characters are still in the input buffer waiting for the next fgets(), scanf() or getchar(). It still beats the heck out of scanf("%c",...)

(Also about another point in your post: what if the user enters a space before the 'Y', 'N' or whatever? Then choice2[0] contains the space, not the 'Y', etc. You can use sscanf(%s) to omit leading whitespace, or just step through the buffer with a loop that ignores whitespace)

Try this

CPP / C++ / C Code:

/* Try this program, and at the first prompt, enter the following    */
/*   " Well, I can't decide"                                         */

#include <stdio.h>

int main()
{
  char buffer[10];

  printf("Enter your choice (Y or N): ");
  fgets(buffer, 10, stdin);
  printf("buffer: <%s>\n", buffer);
  printf("buffer[0]: <%c> (0x%02x hex)\n", buffer[0], buffer[0]);

  printf("Now, please make another choice(Y or N): ");
  fgets(buffer, 10, stdin);
  printf("buffer: <%s>\n", buffer);

  return 0;
}

If you want to limit the length of input string being used by fgets(), be prepared to do something to eat the rest of the line. Many people just use a very large buffer (BUFSIZ from stdio.h) and assume that the user will "never" enter more than that many characters.

There is a more rigorous way: check to see if choice2[] contains a '\n' after the fgets(). If fewer than 10 characters (including the newline) were entered, then the newline will be in choice2[]. If 10 or more characters were entered, nine input characters and a '\0' are written to the array.

Additional dummy fgets() or getchar() or whatever can be used to empty out the input buffer. (No, fflush(stdin) does not work, as much as some people would like it to!)

Regards,

Dave

WaltP · #6 07-Nov-2004, 16:30

All excellent points, Dave

Quote:

Originally Posted by davekw7x

At the beginning of a class, or for beginning programmers studying on their own, scanf() may be all that they know about. Careful use of scanf() can at least let the programmer get started and run some programs.

So, it is possible to use scanf(), but after a few trials, the new programmer sees what problems can arise, and is then more receptive to suggestions about fgets().

IMAO, at the beginning of a course, I feel the instructor is justified giving good information right off the bat and giving the students a worthwhile set of instructions to do their input. I therefore would start them out with

CPP / C++ / C Code:

char tmpbuf[256];
...
fgets(tmpbuf,256,stdin);
sscanf(tmpbuf,...);

and not even mention scanf() until someone says "I just read about scanf. What's that for?" I would simply give them the sscanf() command in it's entirety (a black box as it were) and when ready explain how to actually use the formatting.

It's very obvious with the plethora of posts on all these boards that instructors do NOT explain the problems with scanf() so the students end up here when they want to get a program running when not in class.

Quote:

Originally Posted by davekw7x

C++ programmers have the same issues with cin>>, and usually end up begging for something better (and we give them getline());

Yep...

Quote:

Originally Posted by davekw7x

Now, I have a point about fgets().

If you have something like

CPP / C++ / C Code:

  char choice2[10];

   /* stuff here */

  fgets(choice2, 10, stdin);

This guarantees that no more than 10 characters will be written to the array, so we avoid the dreaded "buffer overflow", but what if the user enters 10 or more characters? The first nine are written into the array (and a terminating '\0' ).The remaining input characters are still in the input buffer waiting for the next fgets(), scanf() or getchar(). It still beats the heck out of scanf("%c",...)

Very true. You do have to make a few assumptions. And if you ask for a number between 10 and 20, and the user enters 2543, you do have to program for this type of problem. You should define a buffer you feel is more than large enough for whatever they might type in. 256 is usually a good value. (more below).

Quote:

Originally Posted by davekw7x

(Also about another point in your post: what if the user enters a space before the 'Y', 'N' or whatever? Then choice2[0] contains the space, not the 'Y', etc. You can use sscanf(%s) to omit leading whitespace, or just step through the buffer with a loop that ignores whitespace)

True. I like the loop idea myself. The first character that matches is the winner! If none match, process the default state.

The 'laws' I follow,
1) If you make your program absolutely foolproof, then only a fool will want to use it
2) Fools are extremely ingenious

Therefore, do what you can. And fgets() is the best you can do.

If you enter more than the maximum characters into fgets(), the last character will not be \n, therefore you know there's more junk in the buffer. Dummy-read the rest until you get the \n, as you mentioned.

davekw7x · #7 07-Nov-2004, 17:17

Quote:

Originally Posted by WaltP

All excellent points, Dave

IMAO, at the beginning of a course, I feel the instructor is justified giving good information right off the bat and giving the students a worthwhile set of instructions to do their input. I therefore would start them out with

CPP / C++ / C Code:

char tmpbuf[256];
...
fgets(tmpbuf,256,stdin);
sscanf(tmpbuf,...);

and not even mention scanf() until someone says "I just read about scanf. What's that for?" I would simply give them the sscanf() command in it's entirety (a black box as it were) and when ready explain how to actually use the formatting.

It's very obvious with the plethora of posts on all these boards that instructors do NOT explain the problems with scanf() so the students end up here when they want to get a program running when not in class.

Yep...

The 'laws' I follow,
1) If you make your program absolutely foolproof, then only a fool will want to use it
2) Fools are extremely ingenious

Therefore, do what you can. And fgets() is the best you can do.

If you enter more than the maximum characters into fgets(), the last character will not be \n, therefore you know there's more junk in the buffer. Dummy-read the rest until you get the \n, as you mentioned.

I agree: The very first "hello world" contains things that we always say "will be explained later". #include, printf(), etc. I think the fgets()-scanf() could also be presented as an idiom for program input: you don't have to understand everything now; just do it. Don't let yourself get sucked into the dark side of the scanf() zombies.

I like the idea of giving meaningful and correct examples as early as possible rather than just giving some "quick and dirty" method that the students will remember forever, even after they have been given more elegant and more robust methods later in the course.

As for making programs foolproof, my philosophy is that the program should give meaningful prompts ("Enter a positive integer"), and try to handle reasonable inputs properly. If someone decides to enter a 513-digit integer, my program doesn't have to do anything worthwhile with it, but the program shouldn't crash with an infinite loop of scrolling text or with an operating system message that asks if I would like to send an error report to Microsoft.

fgets() followed by sscanf() or atoi() or some such thing does it for me.

Regards,

Dave

fwongmc · #8 07-Nov-2004, 17:18

and how about my functions?DO es they do right stuff?Can you guys check it for me?The question is just on top of the answers.This is my thired lesson and I anm new to C,thus I don't know if I define something right.Please?

Quote:

Originally Posted by WaltP

All excellent points, Dave

IMAO, at the beginning of a course, I feel the instructor is justified giving good information right off the bat and giving the students a worthwhile set of instructions to do their input. I therefore would start them out with

CPP / C++ / C Code:

char tmpbuf[256];
...
fgets(tmpbuf,256,stdin);
sscanf(tmpbuf,...);

and not even mention scanf() until someone says "I just read about scanf. What's that for?" I would simply give them the sscanf() command in it's entirety (a black box as it were) and when ready explain how to actually use the formatting.

It's very obvious with the plethora of posts on all these boards that instructors do NOT explain the problems with scanf() so the students end up here when they want to get a program running when not in class.

Yep...

Very true. You do have to make a few assumptions. And if you ask for a number between 10 and 20, and the user enters 2543, you do have to program for this type of problem. You should define a buffer you feel is more than large enough for whatever they might type in. 256 is usually a good value. (more below).

True. I like the loop idea myself. The first character that matches is the winner! If none match, process the default state.

The 'laws' I follow,
1) If you make your program absolutely foolproof, then only a fool will want to use it
2) Fools are extremely ingenious

Therefore, do what you can. And fgets() is the best you can do.

If you enter more than the maximum characters into fgets(), the last character will not be \n, therefore you know there's more junk in the buffer. Dummy-read the rest until you get the \n, as you mentioned.

WaltP · #9 07-Nov-2004, 22:57

Read my first post and change your program as suggested. If it still gives you problems, explain the new problems and post the new code.

The rest of the posts are Dave & I discussing
1) why scanf() is rotten
2) other options
3) things your instructor should know, but doen't seem to have our concept of what a student should do. It's not that he's wrong -- he has a different agenda than we'd use.

These discussions may be helpful later once you have more understanding of how input and output works "under the hood".

fwongmc · #10 08-Nov-2004, 06:56

CPP / C++ / C Code:

#include <stdio.h>

int prime=1;
int i,number;
int num1,num2,num3,num4,num5;
int e,n,d,y,p,q;
int is_prime(int n){
	for (i=2;i<n;i++){
		if(n%i==0)
			return 0;
			}
			return 1;
			}

int decrypt(int num){
int a,f=1;
int b,c,i,j;
{
	b=check_div(e);
	c=e/b;
	for (i=1;i<=b;i++){
		a=(num%n)*a;
		}
	for (j=1;j<=c;j++){
		f=(num%n)*f;}

		number=((a*f)%n);
		return (num);
		}		
		return 0;
		}


int encrypt(int num){
int a,f=1;
int b,c,i,j;
{
	b=check_div(d);
	c=d/b;
	
	for (i=1;i<=b;i++){
		a=(num%n)*a;
	}
	for (j=1;j<=c;j++){
		f=(num%n)*f;}

		number=((a*f)%n);
		return (num);
		}		
		return 0;
		}


int check_div(int x){
int i=2;
int a=0;
{
do {
		a=(n%i);
		i++;  }while (n%i>0);
		return (i);
		}
		return 0;
		 }

 

int main (void){
char choice,choice2;
char choice3='y';
printf ("Do you want to start?");
	scanf("%c",&choice);
if ((choice=='n')||(choice=='N')){
	printf ("Thank you for using this program.");}

if ((choice=='y')||(choice=='Y')){
	printf ("Please enter the Public Key e:");
		scanf ("%d",&e);
	printf ("Please enter the common key n:");
		scanf ("%d",&n);
	printf ("Please enter the private key:");
	scanf ("%d",&d);
/*Prompt user to select encrypt nor decrypt*/
do {
printf ("Encrypt or Decrypt? (E/D)");
fflush(stdin);
scanf ("%c",&choice2);}



/*To find the factors of n QUESTION 2*/
if (check_div(n)>0){
	p=check_div(n);
	q=n/p;}

/*To check if p and q are prime numbers*/
if ((is_prime(p)==1)&&(is_prime(q)==1)){
	y=(p-1)*(q-1);}
if ((is_prime(p)==0)||(is_prime(q)==0)){
	printf ("Check your common key.");}



	if ((choice2=='e')||(choice2=='E')){
		printf ("Please enter 5 characters.");
		scanf ("%d %d %d %d %d",&num1,&num2,&num3,&num4,&num5);
		printf ("The encrypted message in number format is %d %d %d %d %d",decrypt(num1),decrypt(num2),decrypt(num3),decrypt(num4),decrypt(num5));
		printf ("Do you want to play again ?(Y/N)");
		fflush(stdin);
		scanf ("%c",&choice3);}
	

	if ((choice2=='d')||(choice2=='D')){
		printf ("Please enter 5 numbers.");
		scanf ("%d %d %d %d %d",&num1,&num2,&num3,&num4,&num5);
			if ((e*d)%y==1){
				printf ("The decrypted message char format is %c %c %c %c %c",encrypt(num1),encrypt(num2),encrypt(num3),encrypt(num4),encrypt(num5));}
				printf ("Do you want to play again ?(Y/N)");
				fflush(stdin);
				scanf ("%c",&choice3);}
	
	}  while ((choice3=='y')||(choice3=='Y'));
printf ("Thank you for using this program.");
}

The above is my new code.I get stuck with the calculations.Here is little discreption of the three functions(excluding is_prime)
1.For check_div,is to check the two factors of the user input 'n'.I used a for loop to count on n%i and stops if the result are 0.But I don't know if I wrote it right.
2.For the function decryption,is counting on (m^e)%n,/For the function encryptionmis counting on (c^d)%n,using of power function is not allowed in this program by out tutor,thus I use a for loop again to accumlate e times for (m mod n).But since the output may out of range which C can store,thus I use the check_div function to find the two factors of e,and calculation it seperatly.(i.e.: ((a mod n)*(b mod n))mod n==(a*b) mod n
3.Since i used the check_div function in the decrypt/encrypt,but the Vc++ told me that it is a warning,why this happen,and what should I do for it?
4.I get stuck with the do-while loop.The question want us to continue to ask the user for encryption/decryption and do unless if the user enter 'n'.But whether I enter,for example,if I enter e for encryption,therefore if I enter yes,it will prompt to ask for thee same type only..

I did tried one night and I cannot figure out what's the problem,can you help me to debug my program? I will be very pleased if you do so.

Quote:

Originally Posted by WaltP

Read my first post and change your program as suggested. If it still gives you problems, explain the new problems and post the new code.

The rest of the posts are Dave & I discussing
1) why scanf() is rotten
2) other options
3) things your instructor should know, but doen't seem to have our concept of what a student should do. It's not that he's wrong -- he has a different agenda than we'd use.

These discussions may be helpful later once you have more understanding of how input and output works "under the hood".

Thread Tools	Search this Thread
Show Printable Version Email this Page	Search this Thread: Advanced Search
Rate This Thread
Rate This Thread:

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
[TUTORIAL] Calling an external program in C (Linux)	dsmith	C Programming Language	4	22-Apr-2005 13:30
Anyone can write a program code for this???	chriskan76	C Programming Language	1	19-Oct-2004 20:25
Need help with a C program (Long)	McFury	C Programming Language	3	29-Apr-2004 20:06
error during program	rjd72285	C++ Forum	0	11-Nov-2003 18:49
one program access another?	dgoulston	C++ Forum	1	07-Oct-2003 11:26

RSA program

and the functions?

Get stuck again