I have a number which is 615 digits long. Throughout it, there are 8 places where digits are missing. I have to find out what the digits are. There are 10^8 possibilities.
It is for an RSA problem. The number in question is the private key, and I am trying to find out what it is. To help me, I have the public key pair (n, e), both of which are also 615 digits long, and also a plaintext and corresponding ciphertext.
So the only way to figure out d is to bruteforce it. I am trying to use gmpy2 in python to figure it out. I had to jump through a lot of hoops to get it to work. I do not even know if I correctly did it. I had to download Python2.7 so I could run the gmpy2 installer just to not get an error message. But I think it works now, as I can type
>>>import gmpy2
in the terminal and it doesnt give me an error.
Before I try to loop through 10^8 possibilities, I want to know if its possible to do so in a relatively short amount of time, considering my situation. I do not want to fry my computer or freeze it trying to compute this. I also want to know if I am using the right tools for this, or is gmpy2 not the correct version, or Python2.7 is not good/fast enough. I am running gmpy2 on Python2.7 on a laptop.
In the end I suppose I want to take all 10^8 answers and raise such that C^d = M mod n. So thats an (already) large number to the power of number 615 digits long, 10^8 times. Is this possible? If it is, how can I do this using gmpy2? Is there a more efficient way to compute this?
I sincerely apologize if this is not the right place to ask this. Thank you for any help.
I'm the gmpy2 maintainer.
To calculate C**d mod n, you should use the builtin pow() and specify all three values. pow(C,d,n) will be much faster than C**d % n.
Using gmpy2 should be easy for this. Instead of using int() to covert a string to a Python integer, you just need to use gmpy2.mpz(). You can use pow() with mpz instances. (And if even one of the three values to pow() is an mpz, gmpy2 will be used to for the calculation.)
I estimate running time with gmpy2 to be range from less than an hour to a few hours. Python's native integers might be 10x slower.