fwongmc

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*B) mod n

fwongmc

(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.

fwongmc

However,when I start to write this program,I don't know how to check if the inputted numbers are prime or not.I declar it as
for (n%2==0) but it doesn't work.also,I don't know how to find the quotient of the inputted n as well.Hence the calculations.

Can anyone here give me some help?I need your help.and it is a bit urgent.Thanks.

Ooble

I posted a method that checked numbers to see if they were prime or not - here it is:


From the thread Prime Numbers In C.

__________________
Me :: You :: Them

fwongmc

Excuse me,but how can I check for the quotient and the divsor from the number entered?

Eg:
quotient
---------------------
|num
divisor |x
======================
reminder

what I knew is the number that user entered.

fwongmc

if user enter a number(n) into my program,but I need to find out which two numbers ,b are the factors of n (n=a*B)
assume that n is a interger >0

n is entered by the user.

Ooble

Let's see what ya got before we go about helping. I'm not doing it for ya, but I'll help whenever I can.

__________________
Me :: You :: Them

Benoit

Lets see your code so far

__________________
Johnny was a chemist's son but Johnny is no more, for what Johnny thought was H2O was H2SO4

kurifu

Here is the deal with prime numbers... there is noa actua known algorithm which can be used to describe the pattern of prime numbers to this date, though scientists are still trying to figure this one out, so there becomes only 1 way you can figure out if a number is prime (other than hand coding a large lookup table which only works in a finite range probably limited by the amount of memory you have available).

ITERATION

You need to create a program that starts at the number 3, increments by 2, (we will call this n) and attempts to divide it by every number between 2 and n. If the division produces a remainder, than continue dividing because the number could still be prime. If the number does not produce a remainder than the number is instantly validated as non-prime.

Any division that yeilds a whole integer will also give you your factors. If you need to figure out if it is prime or not, stop when you hit a whole integer and return false (not prime), return true of all the divisions complete without producing a whole integer.

If you need to find factors, store all the whole integer and the divisor into a list for all division the return a whole integer.

I find it interesting that you are tackling a crypto problem without knowing how to compute a prime number, most school do this as one of their very first assignments, crypto is not something you usually jump right into, even if it is only RSA based.

__________________
Clifford Matthew Roche <geek@cliffordroche.com>
Web Hosting: http://www.crd-hosting.com
Consulting: http://www.crdev-consulting.com

fwongmc

With reference to your post about prime numbers in C,I am experiencing some difficulties with merging it with functions.

The original program can be run and return reasonable answer,as follows:
#include <stdio.h>

int prime = 1;
int i;
int number;
int main(void)
{
printf("enter possible prime number");

scanf("%d", &number);


for(i = 2; i<number; i++)
{
if(number%i==0)
{
prime = 0;
}
}
if(number == 2)
{
prime = 1;
}

if(prime)
{
printf("%d is a prime number", number);
}
else
{
printf("%d isn't a prime number", number);
}
return 0;
}


The program tha tIwrote with function:
#include <stdio.h>
int a;

int is_prime(int n)
{ int i,prime;
for (i=2;i<n;i++)
{
if(n%i==0)
{
prime=0;
}
}
if (n==2)
{
prime=1;
if(prime)
{
printf("%d is a prme number",n);
}
else
{
printf ("%d isn't a prime number",n);
}
return 0;
}
}

void main(void)
{
printf "Enter your input:");
scanf ("%d",&a);
is_prime(a);
}

It can't reply me for any answers.It even cannot be run.Can you tell me what errors do I make and how to Irect this errors?