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: Select all

```
MakeRandom proc uses esi ebx szOut :D WORD, 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: Select all

```
invoke MakeRandom,addr szKey1,20h
invoke MakeRandom,addr szKey2,20h
```

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.