Hello,

I'm having a pretty weird problem with a program i created,
it's going to be a RSA encrypter...

I've made a BigNum class that is able to do multiplications, additions, decreament, divisions and modulo on very large numbers...

The size of these numbers is defined by a contant (named range),
everything works fine if the range <= 5104 bytes, but for some sort of reason when i go above this number it won't work correctly anymore, i have a system("PAUSE"); at the end of my code, but it will just go past it and past some other calculations in my function main()... Lets say range=6104, than it will only show input, not output of other calculations, but if i delete the multiplication and division from the main() it will show the output of the modulo correctly!

I guess it has to do with memory/buffer overflow of some kind, but if it where a normal overflow of some sort it should also give errors using a number other than 512 ('cause at first i didn't use a constant for the size of the numbers, but just 512)...

I haven't got a clue what is wrong...
Help is very much appreciated!

Here is the code (sorry it's a bit long):
BTW: I'm using Borland C++ 5.0, but should compile using other compilers

``````#include <iostream>
#include <stdlib>
#include <stdio>
#include <memory>
#include <string>

const int range=5104;
char strnum[range*2+1];

class BigNum{
public:
unsigned char num[range];
int len;
BigNum(){memset(num, 0, range); len=1;}
BigNum(char*);
BigNum operator + (BigNum);
BigNum operator - (BigNum);
BigNum operator * (BigNum);
BigNum operator / (BigNum);
BigNum operator % (BigNum);
BigNum operator << (int);
bool operator < (BigNum);
char* print();
};

BigNum::BigNum(char* param){  //Convert hex input to char number array
memset(num, 0, range);
int tmp=strlen(param);
len=tmp/2;
for(int i=0;i<tmp;i++){
if((param[tmp-i-1]>=48)&&(param[tmp-i-1]<=57)){param[tmp-i-1]-=48;}
if((param[tmp-i-1]>=65)&&(param[tmp-i-1]<=70)){param[tmp-i-1]-=55;}
if((i%2)==1){num[(range-1)-i/2]|=param[tmp-i-1]<<4;}
else{num[(range-1)-i/2]=param[tmp-i-1];}
}
}

BigNum BigNum::operator + (BigNum param){
int tmpi;
unsigned char tmpc;
BigNum tmp;
memcpy(tmp.num, num, range); tmp.len=len;

for(int i=0;i<param.len;i++){
if(tmp.len<i+1){tmp.len++;}
tmpc=tmp.num[(range-1)-i];
tmp.num[(range-1)-i]+=param.num[(range-1)-i];
if(tmpc>tmp.num[(range-1)-i]){
tmpi=0;
while(tmp.num[(range-1)-i-1-tmpi]==0xFF){tmp.num[(range-1)-i-1-tmpi]=0; tmpi++;}
tmp.num[(range-1)-i-1-tmpi]++;
if(tmp.len<i+2+tmpi){tmp.len++;}
}
}

return tmp;
}

BigNum BigNum::operator - (BigNum param){
int tmpi;
unsigned char tmpc;
BigNum tmp;
memcpy(tmp.num, num, range); tmp.len=len;

for(int i=0;i<param.len;i++){
tmpc=tmp.num[(range-1)-i];
tmp.num[(range-1)-i]-=param.num[(range-1)-i];
if(tmpc<tmp.num[(range-1)-i]){
tmpi=0;
while(tmp.num[(range-1)-i-1-tmpi]==0x00){tmp.num[(range-1)-i-1-tmpi]=0xFF; tmpi++;}
tmp.num[(range-1)-i-1-tmpi]--;
}
for(tmpi=0;((tmpi<range)&&(tmp.num[tmpi]==0));tmpi++){}
tmp.len=range-tmpi;
}

return tmp;
}

bool BigNum::operator < (BigNum param){
int tmpi=0;
if(len<param.len){return true;}
if(len==param.len){
while((tmpi<len)&&(num[range-len+tmpi]==param.num[range-param.len+tmpi])){tmpi++;}
if(num[range-len+tmpi]<param.num[range-param.len+tmpi]){return true;}
}
return false;
}

BigNum BigNum::operator << (int shl){
BigNum tmp;
int tmpi;
unsigned char and, tmpc;
memcpy(tmp.num+range-len-shl/8, num+range-len, len);
tmp.len=len+shl/8;
if((shl%8)>0){
tmpi=shl%8;
and=(2<<tmpi)-1;
and<<=8-tmpi;

for(int i=0;i<tmp.len;i++){
tmpc=(tmp.num[range-tmp.len+i]&and)>>8-tmpi;
tmp.num[range-tmp.len+i]<<=tmpi;
tmp.num[(range-1)-tmp.len+i]|=tmpc;
}
if(tmp.num[(range-1)-tmp.len]>0){tmp.len++;}
}
return tmp;
}

BigNum BigNum::operator * (BigNum param){
BigNum tmp, out;
memcpy(tmp.num, num, range); tmp.len=len;

for(int i=0;i<param.len;i++){
for(int ix=0;ix<8;ix++){
if((param.num[(range-1)-i]&1)==1){
out=out+(tmp<<(i*8+ix));
}
param.num[(range-1)-i]>>=1;
}
}
for(int i=0;((i<range)&&(out.num[i]==0));i++){out.len=(range-1)-i;}

return out;
}

BigNum BigNum::operator / (BigNum param){
int tmpi;
BigNum tmp, out, one=BigNum("01");
memcpy(tmp.num, num, range); tmp.len=len;
if(tmp<param){return BigNum("00");}

while(param<tmp){
tmpi=0;
while((param<<tmpi)<tmp){tmpi++;}
if(tmpi==0){break;}
tmpi--;
tmp=tmp-(param<<tmpi);
out=out+(one<<tmpi);
}
if(!(tmp<param)){
out=out+one;
tmp=tmp-param;
}
return out;
}

BigNum BigNum::operator % (BigNum param){
int tmpi;
BigNum tmp, out, one=BigNum("01");
memcpy(tmp.num, num, range); tmp.len=len;
if(tmp<param){return BigNum("00");}

while(param<tmp){
tmpi=0;
while((param<<tmpi)<tmp){tmpi++;}
if(tmpi==0){break;}
tmpi--;
tmp=tmp-(param<<tmpi);
out=out+(one<<tmpi);
}
if(!(tmp<param)){
out=out+one;
tmp=tmp-param;
}
return tmp;
}

char* BigNum::print(){
int tmp=0;
char *hex="0123456789ABCDEF";

for(int i=0;i<len;i++){
strnum[tmp]=hex[(num[range-len+i]&0xF0)>>4];
strnum[tmp+1]=hex[(num[range-len+i]&0x0F)];
tmp+=2;
}
strnum[tmp]=0;

return strnum;
}

int main(){
BigNum tmp("123456789ABCDEF7");
BigNum test("3F12");
BigNum c;

cout << "----INPUT:----\n";
printf("A:%s: %d Bytes\n", tmp.print(), tmp.len);
printf("B:%s: %d Bytes\n--------------\n\n", test.print(), test.len);
c=tmp*test;
printf("--MULTIPLY(A*B)--\n%s\n%d Bytes\n\n", c.print(), c.len);
c=tmp/test;
printf("--DIVIDE(A/B)--\n%s\n%d Bytes\n\n", c.print(), c.len);
c=tmp%test;
printf("--MODULO(A MOD B)--\n%s\n%d Bytes\n", c.print(), c.len);

system("PAUSE");
return 0;
}``````
2
Contributors
2
Replies
3
Views
11 Years
Discussion Span
Last Post by MAGiC333X

This may not be of help if this is homework...

why bother trying to reinvent the wheel?

It's sort of homework...
So that's no help for me, but thanks anyway...

BTW: reinventing the wheel rocks :p

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.