encryption problem

Hi all,

I hope this isn't overload but I've included code for an implementation of the rsa algorithm below that I've been working on. There are 3 files "keygen.cpp", "numtheory.cpp" and "numtheory.h" and they compile correctly. The problem arises in the encrypt and decrypt functions in "keygen.cpp". The contents of the file to be encrypted are read in correctly to a buffer but it is in the following lines of code that something goes wrong:

for(i = 0; i < charsRead; ++i)
{
output_buffer[i] = powermod( input_buffer[i], exponent, modulus );
fputc(output_buffer[i], output_file);
}


The powermod function is working correctly. The problem arises when writing to file because the program attempts to assign ascii values to every result of powermod. However, powermod can return values well above any ascii value so an incorrect character is written to file. Decryption, therefore, cannot work because the wrong characters are being decrypted. I would very much appreciate it if anyone could help me out and give a look at the code and see where I might be gone wrong. Thanks a lot.



code:--------------------------------------------------------------------------------
-------------keygen.cpp----------------------------
#include "numtheory.h"
#include
#include
#include
#include
#include
#include
#include

using namespace std;

void encrypt(const char* file, number exponent, number modulus);

void decrypt(const char* file, number exponent, number modulus);

void generatePandQ(number minimum, number maximum, number& p, number& q)
{
// pick p and q
p = pickRandomPrime(minimum, maximum);
q = pickRandomPrime(minimum, maximum);

// ensure p and q are not the same.
while(q == p)
{
q = pickRandomPrime(minimum, maximum);
}
}

int main()
{
srand(time(0));

cout << "Enter minimum value for p and q: " << flush;
number minimum; cin >> minimum;

cout << "Enter maximum value for p and q: " << flush;
number maximum; cin >> maximum;

number p, q;
generatePandQ(minimum, maximum, p, q);

number N = p*q;
number c = (p-1)*(q-1);

number e;
for(e = c / 4; gcd(c, e) != 1; ++e);

number d = modinverse(e, c);

cout << "p is " << p << endl;
cout << "q is " << q << endl;
cout << "N is " << N << endl;
cout << "c is " << c << endl;
cout << "e is " << e << endl;
cout << "d is " << d << endl;

char fileEncrypt[50];
char fileDecrypt[50];

cout<<"Enter name of file: " << endl;

cin>>fileEncrypt;

encrypt(fileEncrypt, e, N);

cout << "Enter name of file to decrypt: " << endl;

cin >> fileDecrypt;

decrypt(fileDecrypt, d, N);

return 0;
}


void encrypt(const char file[], number exponent, number modulus)
{
cout << "Encrypting: exponent is " << exponent << ", N is " << modulus << endl;

const int BUF_SIZE = 8192;
int charsRead = 0, i;
char input_char;
char file_out[30];

unsigned char input_buffer[BUF_SIZE];
unsigned int output_buffer[BUF_SIZE];

FILE* input_file;
FILE* output_file;

strcpy(file_out, file);
strcat(file_out, ".encrypted");

input_file = fopen(file, "r");
if (input_file==NULL) {
cout << "Error opening file";
exit(-1);
}
else {
output_file = fopen(file_out, "w");

while(1)
{
charsRead = 0;
// Step 1: Read BUF_SIZE bytes of file into input buffer.

for (i = 0; i <BUF_SIZE; i++)
{
input_char = fgetc(input_file);
if(input_char == EOF)
break;
else {
input_buffer = input_char;
charsRead++;
}
}

if (charsRead == 0)
{
// done with file.
break;
}

// Step 2: Encrypt this block of data and store in output buffer.

for(i = 0; i < charsRead * sizeof(unsigned int); ++i)
{
output_buffer = powermod( input_buffer, exponent, modulus );
fputc(output_buffer, output_file);
}

}
}

cout << "Done encrypting." << endl;

fclose(input_file);
fclose(output_file);
}


void decrypt(const char file[], number exponent, number modulus)
{

cout << "Decrypting: exponent is " << exponent << ", N is " << modulus << endl;

const int BUF_SIZE = 8192;

int charsRead = 0, i;
char input_char;
char file_out[30];

unsigned int input_buffer[BUF_SIZE];
unsigned char output_buffer[BUF_SIZE];

FILE* input_file;
FILE* output_file;

strcpy(file_out, file);
strcat(file_out, ".decrypted");

input_file = fopen(file, "r");
if (input_file==NULL) {
cout << "Error opening file";
exit(-1);
}
else {
output_file = fopen(file_out, "w");

while(1)
{
charsRead = 0;
// Step 1: Read BUF_SIZE bytes of file into input buffer.

for (i = 0; i <BUF_SIZE * sizeof(number); i++)
{
input_char = fgetc(input_file);
if(input_char == EOF)
break;
else {
input_buffer = input_char;
charsRead++;
}
}

if (charsRead == 0)
{
// done with file.
break;
}

// Step 2: Encrypt this block of data and store in output buffer.

for(i = 0; i < charsRead / sizeof(number); ++i)
{
output_buffer = (unsigned char)powermod( input_buffer, exponent, modulus );
fputc(output_buffer, output_file);
}

}
}

cout << "Done encrypting." << endl;

fclose(input_file);
fclose(output_file);
}--------------------------------------------------------------------------------



code:--------------------------------------------------------------------------------
---------------numtheory.cpp------------------------
#include "numtheory.h"
#include <assert.h>
#include
#include
#include

number mod(number x, number modulus)
{
assert(modulus > 0);
x %= modulus;
if (x < 0)
x += modulus;
return x;
}

//
// powermod function
// -----------------
// this function raises a number to a power, under a given modulus.
// it can handle huge exponentiation... basically as long as modulus
// squared won't overflow the number, powermod won't overflow it.
//

number powermod(number value, number power, number modulus)
{
int temp;
number ret(1);
number t_value;

for(unsigned int i = 0;i < (sizeof(power)*8);++i)
{
if (i == 0)
{
t_value = value;
}

else
{
t_value *= t_value;
t_value %= modulus;
}

temp =((power >> i) & 1);
if ( temp == 1)
{
// the ith bit is 1, so we are going to
// need to include this t value in our
// answer.

ret *= t_value;
ret %= modulus;
}
}

return ret;
}




//
// gcd function
// ------------
// this is a function that calculates the gcd between 2
// numbers using the euclidian greatest common divisor method.
//
number gcd(number high, number low)
{
if (high < low)
{
number temp(high);
high = low;
low = temp;
}

number z(0);

while(low > 0)
{
z = high % low;
high = low;
low = z;
}

return high;
}



//
// gcd_combination function
// ------------------------
// this is a function that takes the gcd of two numbers, a and
// b, and also returns the coefficients to create a linear
// combination of a and b, using the euclidian common divisor
// method.
//
number gcd_combination(number high, number low, number& s, number& t)
{
//
// We require that high is greater than low.
//
assert(high > low);
assert(high > 0 && low > 0);

//
// If low divides high, our algorithm won't return the
// correct s and t values. So, we handle this case
// right now.
//
if (high % low == 0)
{
s = 1;
t = -1 * ((high / low) - 1);
return low;
}

//
// We need to seed the s and t values with their correct
// starting values.
//
s = 1;
t = 0;

//
// We store the last two t's and s's that were calculated
// for use in computing future t's and s's.
//
number old_t[2];
number old_s[2];

//
// The q array is where we store our quotients.
// q[2] is the current quotient, q[1] is one back from
// that, and q[0] is one back from q[1].
//
number q[3];

for(number j = 0; (true); ++j)
{
q[0] = q[1];
q[1] = q[2];

old_s[0] = old_s[1];
old_s[1] = s;

old_t[0] = old_t[1];
old_t[1] = t;

if (j == 1)
{
s = 0;
t = 1;
}

else if (j > 1)
{
s = old_s[0] - (q[0] * old_s[1]);
t = old_t[0] - (q[0] * old_t[1]);
}

q[2] = number(high / low);
number remainder(high - (low * q[2]));

if (remainder == 0)
{
old_s[0] = old_s[1];
old_s[1] = s;

old_t[0] = old_t[1];
old_t[1] = t;

q[0] = q[1];
q[1] = q[2];

s = old_s[0] - (q[0] * old_s[1]);
t = old_t[0] - (q[0] * old_t[1]);

return low;
}

high = low;
low = remainder;
}
}



number modinverse(number x, number modulus)
{
x = mod(x, modulus);

number s, t;
number gcd = gcd_combination(modulus, x, s, t);

assert(gcd == 1);

return mod(t, modulus);
}



number pickRandomPrime(number low, number high)
{
// Pick a random odd number in our interval.
number x = (low + (rand() % (high - low))) | 1;

while( (powermod(2, x-1, x) != 1) ||
(powermod(3, x-1, x) != 1) ||
(powermod(5, x-1, x) != 1) ||
(powermod(7, x-1, x) != 1) ||
(powermod(11, x-1, x) != 1) )
{
// If any of those conditions are true, we have
// found a composite number. Try the next one.
x += 2;
}

// once we get here, we have found a prime.
return x;
}




//
// factor_trialdiv function
// ------------------------
//
// This is a function that attempts to find a factor of a number
// using the trial division method.
//
// It returns the first factor found, or 1 if the number is prime.
//
number factor_trialdiv(number n)
{
for(number i = 2;i <= sqrt(n);++i)
{
if ((n % i) == 0)
{
return i;
}
}

return 1;
}--------------------------------------------------------------------------------



code:---------------------------------------------------------------------------------------------------------numtheory.h--------------------
#ifndef INCLUDED_NUMBER_THEORY_H
#define INCLUDED_NUMBER_THEORY_H

typedef long number;

number mod(number x, number modulus);
number powermod(number value, number power, number modulus);
number gcd(number high, number low);
number gcd_combination(number high, number low, number& s, number& t);
number modinverse(number x, number modulus);
number pickRandomPrime(number low, number high);
number factor_trialdiv(number n);

#endif // INCLUDED_NUMBER_THEORY_H

---------------------END-------------------------------------------------------------------------------------------------------------

Comments

  • I didn't check your code (sorry).

    The problem you are describing is a common one: Overflow.

    You must mathematically take care of it, so that it never happens. As I have no knowledge about the RSA algorhithm, I don't know if it's actually supposed to handle overflow ve e.g. clipping, but I seriously doubt it.

    Normally, to avoid overflow, one scales before saving.

    E.g. if you are sampling with a 16 bit sampler and want to store the results as 8 bit samples, you wouldn't save the LSB of the sample, but rather the MSB (i.e. divide the sample value by 256 before saving it).

    Of course, if you later want to output this 8 bit sample with a 16 bit D/A converter, you would probably scale it back to 16 bit, by multiplying with 256. This of course means that you have lost precision (i.e. the LSB), but there is really no way out of that.

    If the RSA algorithm needs the precision delivered from the power function, you probably need to save something else than 8bit chars to your character buffer. (And correspondingly load something else than 8 bit chars when decrypting). One way could be saving doubles.
    e.g. saving 16 doubles with themselves raised to themselves (i.e. n^n) could look like this:

    [code]
    int n;
    char SaveToThisArray[16*(sizeof(double)/sizeof(char))];
    for(n=0;n<16;n++)
    {
    *((double*)&(SaveToThisArray[n*(sizeof(double)/sizeof(char))]))=pow(n,n);
    }
    [/code]

    Of course, you'd be better of by using an array of the type you need. The above implementation is for demonstrational purposes only...
Sign In or Register to comment.

Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

Categories

In this Discussion