1 Attachment(s)
RSA modular exponentation sending out wrong modules
Hi guys, it's the first time for me in this forum and i hope you could help me somehow.
Right now i'm trying the first step of RSA: generating prime numbers (4 digits, as a start).
I allocate the memory, I random generate an uneven number, and now i have to do the 2^n % n-1 = 1 to see if the number is actually prime.
That's the code:
Code:
void PotenzaModulare(struct Vector* Esp, struct Vector* Base, struct Vector* result, struct Vector* Mod)
{
int i2;
int i;
struct Vector tmp;
struct Vector tmpBaseBase;
struct Vector tmpBase;
for (i2=0; i2<Esp->Dim; i2++)
{
tmpBase.Dim= DIM_PRIME;
tmpBase.Num = (int *)malloc(sizeof(int)*tmpBase.Dim);
Riempi(&tmpBase, 1);
tmpBaseBase.Dim= DIM_PRIME*6;
tmpBaseBase.Num = (int *)malloc(sizeof(int)*tmpBaseBase.Dim);
Riempi(&tmpBaseBase, 1);
tmp.Dim= DIM_PRIME*6;
tmp.Num = (int *)malloc(sizeof(int)*tmp.Dim);
Riempi(&tmp, 1);
for (i=0; i<DIM_PRIME;i++) tmpBase.Num[i] = Base->Num[i];
if(Esp->Num[i2]==1) //ESP IS A BINARY NUMBER
{
Riempi(&tmp, 1);
InitMoltiplicazione(result, Base, &tmp); //KARATSUBA MOLTIPLICATION
tmp.Dim=DIM_PRIME*2;
InvertiNumero(&tmp, tmp.Dim);
int i;
for(i=tmp.Dim-1; i>-1; i--)
if (tmp.Num[i] ==0) tmp.Dim--;
else break;
InvertiNumero(Mod, Mod->Dim); //REVERSE A NUMBER
if(tmp.Dim<Mod->Dim)
{
for(i=0; i<tmp.Dim; i++)
result->Num[result->Dim-1-i]=tmp.Num[i];
}
else
{
result->Num = LongMod(tmp.Num, Mod->Num, tmp.Dim, Mod->Dim);
SistemaModulo(result); //CLEANUP THE MODULE
PareggiaModulazione(result, DIM_PRIME); //ADDS 0s FOR NEXT KARATSUBA
}
tmp.Dim=DIM_PRIME*6;
InvertiNumero(Mod, Mod->Dim);
}
Riempi(&tmp, 1); //RESET A "Vector"
InitMoltiplicazione(&tmpBase, Base, &tmp);
tmp.Dim=DIM_PRIME*2;
InvertiNumero(&tmp, tmp.Dim);
for(i=tmp.Dim-1; i>-1; i--)
if (tmp.Num[i] ==0) tmp.Dim--;
else break;
if(tmp.Dim>=Mod->Dim)
{
InvertiNumero(Mod, Mod->Dim);
Base->Num = LongMod(tmp.Num, Mod->Num, tmp.Dim, Mod->Dim); <------*****
SistemaModulo(Base);
PareggiaModulazione(Base, DIM_PRIME);
InvertiNumero(Mod, Mod->Dim);
}
else
{
int IndiceWrite= Base->Dim-tmp.Dim;
for (int i=tmp.Dim-1; i>=0; i--)
Base->Num[IndiceWrite++]=tmp.Num[i];
}
}
*Useless things*
}
It's not really cleaned up, i know... sorry for that. Anyway what I'm trying to do here is this:
Code:
function modular_pow(base, exponent, modulus)
result := 1
while exponent > 0
if (exponent mod 2 == 1):
result := (result * base) mod modulus
exponent := exponent >> 1
base = (base * base) mod modulus
return result
"Vector" is a struct described as follows
Code:
struct Vector
{
int* Num; //Vettore di numeri, rappresentano un operando
int Dim;
};
and the "DIM_PRIME" variable is a #define with value 4
Now what's happening here is: the code works perfectly until a random run when he reaches the line with the <------*****
Sometimes it works, sometimes it doesn't and i really can't understand why.
I have a test project where to run the LongMod method and there it works perfectly with the provided inputs.
Here a screen of the situation:
Attachment 30117
"Qui sbaglia" = Here it fails
"Qui no" = Here it doesn't
I'm starting to think that some memory leak is currupting my program causing the LongMod to fail but i don't really know where to look at... any help is greatly appreciated!
Re: RSA modular exponentation sending out wrong modules
Did you try to debug your code?
Re: RSA modular exponentation sending out wrong modules
Sure i did. Everything is just fine untile the call to that LongMod.
Sometimes it works and sometimes the result get messed up, even if inside that function everything works properly.
Re: RSA modular exponentation sending out wrong modules
Quote:
Originally Posted by
EmaGht
Sure i did. Everything is just fine untile the call to that LongMod.
Sometimes it works and sometimes the result get messed up, even if inside that function everything works properly.
If everything would be "just fine" then you hadn't got any problems at all! If you get - then something is NOT fine. :cool:
Besides:
- You mentioned some function, but haven't shown it.
- Your PotenzaModulare function produces memory leaks (a lot of malloc calls but there is no any free)
- Is there any very important reason for you to write plain C code avoiding all the advantages (like std and/or MFC container classes) that C++/VC++ give you?
Re: RSA modular exponentation sending out wrong modules
Quote:
Originally Posted by
EmaGht
Sure i did.
If you debugged your ccde, then you would have identified the problem. Debugging doesn't mean just have your program run and report on CodeGuru what doesn't work. Debugging means to actually go into the functions that do not work and fix them.
Secondly, why are you writing your own RSA routines? Wouldn't it be more wise to use a library that is fully debugged, works correctly, and written by experts who know exactly what they're doing? If you write your own RSA functions and you don't even have the ability to debug them, imagine if someone finds a hole in your implementation, exploits that hole, and you now have a big mess on your hands?
Victor identified memory leaks, and I wouldn't be the least bit surprised if there are buffer overruns and other errors that can be exploited by persons that do not have good intentions.
Regards,
Paul McKenzie
Re: RSA modular exponentation sending out wrong modules
Quote:
Originally Posted by
VictorN
If everything would be "just fine" then you hadn't got any problems at all! If you get - then something is NOT fine. :cool:
Besides:
- You mentioned some function, but haven't shown it.
- Your PotenzaModulare function produces memory leaks (a lot of malloc calls but there is no any free)
- Is there any very important reason for you to write plain C code avoiding all the advantages (like std and/or MFC container classes) that C++/VC++ give you?
1) If you mean LongMod, on my way posting it :)
2) Ye, i cutted off the part where frees were issued, since the problem lies within the for loop
3) Is being new to C an important reason? :)
About the "debugging" thing, maybe i wasn't clear enough.
I did debugged the entire code, and every line works how it should, EXCEPT in this ("<---***");
Code:
int* LongMod(int* x, int* y, int n, int m)
{
int* mod = (int*)malloc(m*sizeof(int));
Init_To_Zero(mod, m);
int* d = (int*)malloc(m*sizeof(int));
Init_To_Zero(d, m);
int* dq = (int*)malloc(n*sizeof(int));
Init_To_Zero(dq, n);
int* r = (int*)malloc(n*sizeof(int));
Init_To_Zero(r, n);
int f, qt;
f = 10/(y[m-1]+1);
r = Product(x, f, n);
d = Product(y, f, m);
for(int k = n-m; k > -1; k--)
{
qt = First_Digit(r, d, k, m);
dq = Product(d, qt, m);
if(Smaller(r, dq, k, m))
{
qt = qt - 1;
dq = Product(d, qt, m);
}
r = Difference(r, dq, k, m);
}
mod = Quotient(r, f, m-1); <---***
printf("Modulo Done!!!\n");
return mod;
}
...line of LongMod. The result from Quotient is right, but mod is not (I don't know why) well assigned.
My idea wasn't to ask anybody for help in the first place. If i did, it's because i really can't think about a better idea to find what's wrong with this code.
And i don't understand why i shouldn't write my own RSA routine. It's a fascinating thing to me and to see it working would be lovely :).
Anyway this is the PotenzaModulare function "free" included, it may actually not be a bad idea to see the whole picture.
Code:
void PotenzaModulare(struct Vector* Esp, struct Vector* Base, struct Vector* result, struct Vector* Mod)
{
int i2;
int i;
struct Vector tmp;
struct Vector tmpBaseBase;
struct Vector tmpBase;
for (i2=0; i2<Esp->Dim; i2++)
{
tmpBase.Dim= DIM_PRIME;
tmpBase.Num = (int *)malloc(sizeof(int)*tmpBase.Dim);
Riempi(&tmpBase, 1);
tmpBaseBase.Dim= DIM_PRIME*6;
tmpBaseBase.Num = (int *)malloc(sizeof(int)*tmpBaseBase.Dim);
Riempi(&tmpBaseBase, 1);
tmp.Dim= DIM_PRIME*6;
tmp.Num = (int *)malloc(sizeof(int)*tmp.Dim);
Riempi(&tmp, 1);
for (i=0; i<DIM_PRIME;i++) tmpBase.Num[i] = Base->Num[i];
if(Esp->Num[i2]==1) //ESP IS A BINARY NUMBER
{
Riempi(&tmp, 1);
InitMoltiplicazione(result, Base, &tmp); //KARATSUBA MOLTIPLICATION
tmp.Dim=DIM_PRIME*2;
InvertiNumero(&tmp, tmp.Dim);
int i;
for(i=tmp.Dim-1; i>-1; i--)
if (tmp.Num[i] ==0) tmp.Dim--;
else break;
InvertiNumero(Mod, Mod->Dim); //REVERSE A NUMBER
if(tmp.Dim<Mod->Dim)
{
for(i=0; i<tmp.Dim; i++)
result->Num[result->Dim-1-i]=tmp.Num[i];
}
else
{
result->Num = LongMod(tmp.Num, Mod->Num, tmp.Dim, Mod->Dim);
SistemaModulo(result); //CLEANUP THE MODULE
PareggiaModulazione(result, DIM_PRIME); //ADDS 0s FOR NEXT KARATSUBA
}
tmp.Dim=DIM_PRIME*6;
InvertiNumero(Mod, Mod->Dim);
}
Riempi(&tmp, 1); //RESET A "Vector"
InitMoltiplicazione(&tmpBase, Base, &tmp);
tmp.Dim=DIM_PRIME*2;
InvertiNumero(&tmp, tmp.Dim);
for(i=tmp.Dim-1; i>-1; i--)
if (tmp.Num[i] ==0) tmp.Dim--;
else break;
if(tmp.Dim>=Mod->Dim)
{
InvertiNumero(Mod, Mod->Dim);
Base->Num = LongMod(tmp.Num, Mod->Num, tmp.Dim, Mod->Dim); <------*****
SistemaModulo(Base);
PareggiaModulazione(Base, DIM_PRIME);
InvertiNumero(Mod, Mod->Dim);
}
else
{
int IndiceWrite= Base->Dim-tmp.Dim;
for (int i=tmp.Dim-1; i>=0; i--)
Base->Num[IndiceWrite++]=tmp.Num[i];
}
}
*Useless things*
free(tmp.Num);
free(tmpBaseBase.Num);
free(tmpBase.Num);
}
I'm sorry for not being as clear as i'd like to be, and thanks for all the help you are giving me.
Re: RSA modular exponentation sending out wrong modules
Quote:
Originally Posted by
EmaGht
... The result from Quotient is right, but mod is not (I don't know why) well assigned.
What is Quotient? How is it implemented?
What is in this line
Quote:
Code:
mod = Quotient(r, f, m-1);
"right" if the result (mod) "is not"?
Re: RSA modular exponentation sending out wrong modules
After all your exhortations to debug my code the better way possible i was like... "oh well, one more run can't be bad"
[lolmode]
Then Jesus came down from the sky pointing me a "-5" that should have been 0;
[/lolmode]
And yea... i was sending all the right inputs, but during the "Moltiplica" function i used an extra integer memory slot that resulted not inizialized.
This, plus a if(a[NotInitializedCell] != 0
screwed the last+1 digit of the operands in LongMod and since i always checked "last" digits i never saw it.
The code doesn't still work, but from now on it's my job ^_^
Thanks for all the time you spent for me, you pointed me out the right way!
"You debugged and it still doesn't work? Debug again"
Gonna remember this ;)
