LaptoniC

October 10th, 2011, 08:13

Hi,

I am trying to reverse a program which uses RSA-512. I checked how this program generated its keys and found out that it uses component. This component creates the key like this.

Random function is standard delphi random function. RandSeed is calculated by using QueryPerformanceCounter.

After we get the random string, we search the next prime number by using Rabin-Miller algorithm by doing 4 iterations.

There is no randomization function between each key so if we find the seed we can recover both keys at the same time.

So key space is actually FFFFFFFFh however again this is something takes very long time due to big number calculations. I am using drizz's big number library.

So, I am not so good about cryptography. Is there any kind of optimizations that will help me to decrease the time for key search. For now searching 1000 seeds take around 1 minute 6 seconds.

I will appreciate any optimizations and opinions. Thanks.

I am trying to reverse a program which uses RSA-512. I checked how this program generated its keys and found out that it uses component. This component creates the key like this.

Code:

MakeRandom proc uses esi ebx szOutWORD, szLen

mov esi,szOut

mov ebx,szLen

@loop:

mov eax, 0DFh

call Random ; System::Random(int)

add al, 20h

mov [esi], al

inc esi

dec ebx

jnz @loop

ret

MakeRandom endp

Random proc

xor ecx, ecx

imul edx, RandSeed[ecx], 8088405h

inc edx

mov RandSeed[ecx], edx

mul edx

mov eax, edx

ret

Random endp

After we get the random string, we search the next prime number by using Rabin-Miller algorithm by doing 4 iterations.

Code:

invoke MakeRandom,addr szKey1,20h

invoke MakeRandom,addr szKey2,20h

There is no randomization function between each key so if we find the seed we can recover both keys at the same time.

So key space is actually FFFFFFFFh however again this is something takes very long time due to big number calculations. I am using drizz's big number library.

So, I am not so good about cryptography. Is there any kind of optimizations that will help me to decrease the time for key search. For now searching 1000 seeds take around 1 minute 6 seconds.

I will appreciate any optimizations and opinions. Thanks.