RSA algorithm C program bug

[amskape]

Hi Dear Friends,

I am looking for a good C program for RSA Algoritm implementation, but my current program is buggy

eg: when I give two prime numbers(p&q) as 11 and 3
and public key (e) as 5
according to RSA i got wrong answer
please help me to correct this issue My code is:

#include<stdio.h>
#include<conio.h>
int phi,C,M,n,e,d,FLAG;
int check() {
int i;
for(i=3;e%i==0&&phi%i==0;i+2)
{
  FLAG = 1;
  return ;
}
FLAG = 0;
}

void encrypt()
{
  int i;
  C = 1;
 for(i=0;i<e;i++)
 C=C*M%n;
  C = C%n;
 printf("\\n\tEncrypted keyword: %d",C);
}
void decrypt()
{
 int i;
 M=1;
for(i=0;i<d;i++)
M = M*C%n;
M=M%n;
printf("\n\tDecrypted keyword: %d",M);
}
void main()
{
 int p,q,s;
clrscr();
printf("Enter two prime numbers\t:");
scanf("%d%d",&p,&q);
n = p*q;
phi = (p-1)*(q-1);
printf("\n\tF(n)\t = %d",phi);
do
{
 printf("\n\nEnter e\t:");
scanf("%d",&e);
check();
}while(FLAG==1);

d  = 1;
do
{
 s = (d*e)%phi;
 d++;
}while(s!=1);
d = d-1;
printf("\n\tPublic key is \t: {%d, %d}",e,n);
printf("\n\tPrivate key is\t: {%d,%d}" ,d,n);
printf("\n\nEnter the Plain Text\t:");
scanf("%d",&M);
encrypt();
printf("\n\nEnter the Cipher text\t: ");
scanf("%d",&C);
decrypt();
getch();
}

Here the "Check()" function is not do anything valuable .

Please help me to remove this issue

[donbock]

What do you expect line 52 (d+++;) to do?

[amskape]

Dear Donbock,

Sorry it's d++ //increment operation.

Please advise in code i given in good manner

Thanks,
Anes

[donbock]

For (p,q) = (11,3), n=33 and phi(n)=20. Does that match what your program reported?

e=5 is not an acceptable value because 5 and phi(n) are not coprime; that is gcd(5,20) != 1.
Where gcd is greatest-common-denominator.

[donbock]

I would add parentheses to lines 19 and 28 to make your intention clear ... even if the hard-to-remember order of operations rules do things the way you want.

You should validate p and q: make sure they are both prime numbers and make sure there is no overflow when you multiply them together.

You should validate e: make sure it is between 1 and phi(n) and that it is coprime with phi(n).

You should validate M: make sure it is between 0 and n.

You should verify that there is no overflow in encrypt() and decrypt().

You should add comments to clarify your intention. It would be especially helpful if the comments referred back to the RSA algorithm and any mathematical shortcuts you are using.

It might be wiser to work with long variables instead of int.

[amskape]

Dear Don,
I am not understand
1. the first point you mention on line 19 & 28
2. What you mean by ' make sure there is no overflow when you multiply them together.'
3. third point of doubt is "You should verify that there is no overflow in encrypt() and decrypt()."

Pls clarify , all other points is really fine for me

Thanks,
Anes

[donbock]

Point 1: I suggest you change line 19 to whichever of the following two forms is the one you intend:

 C=(C*M)%n;
 C=C*(M%n);

Don't rely on your recollection of the precise order of operations.

Points 2 and 3. Computer integer computations are performed on limited-size variables. It is entirely possible for an intermediate calculation to result in a value that cannot be represented in an integer variable. This is problem is known as overflow.

The C size rules for integer types:

• A short is at least 16 bits wide.
• A long is at least 32 bits wide.
• A long long is at least 64 bits wide.
• An int is no narrower than a short and no wider than a long.

[amskape]

Dear Don,
I got your answer and understood. One more doubt do we can
use a STRING Message in RSA algorithm . means as M we can add
"Hello Don", please advise me

Thanks,
Anes

[donbock]

I am not an expert on RSA.
The RSA article on Wikipedia says that the message has to converted into an integer whose value is between 0 and n. This integer is encrypted, sent, decrypted, and then converted back to the original message.

[amskape]

Dear @Don,

you are absolutely right .

IN RSA ALGORITHM IT(e - public key) MUST BE USE PRIME NUMBER WHICH IS NOT THE CONFACTOR OF 'PHI'
Here we input (or randomly insert) two prime numbers p and q
n = pq
phi = (p-1)(q-1)
e = must be a prime number - which we chcek now in this thread - but not cofactor of phi

eg : if we give p = 11 & q = 3

then phi = 10*2 = 20

so we cannot give 5 for e , because it's cofactor of 'phi'(ie 20).
So the value e is a subset of PRIME Numbers .

We need to find the 'd' - Private key from formula

d*e mod phi = 1

Then if M is the Message to encrypt( Here M is integer value in range : 0<M<n)

C- Cipher text , which generate from M

C = M^e mod n[Encryption]

and

M = C^d mod n [Decryption]

This is the criteria(Condit ion) for RSA algorithm

Please look our code in thread :http://bytes.com/topic/c/answers/952...-c#post3758619
and advise me

Thanks,
Anes

[donbock]

I may be wrong, but I was under the impression that e does not need to be prime; although it must be coprime with phi. On the other hand, I believe that it is customary for e to be prime.

[amskape]

Yes donbock you are right.

e must be an integer , 1<e<phi such that gcd(e,phi) = 1
Thanks,
Anes