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;
}

Recommended Answers

All 2 Replies

Member Avatar for iamthwee

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

http://www.swox.com/gmp/

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

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.