3

I have a number which is 615 digits in length. Throughout the number, there 8 fixed places where a digit is missing. I have to find what those missing digits are. So there are 10^8 possibilities. After computing them I have to raise a ciphetext to each possible number, and see what the output is (mod N), and see which number gives the correct output. In other words, I am trying to find the decryption key in an RSA problem. My main concern right now is how to efficiently/properly create all 10^8 possible answers.

I am using gmpy2, and to get that to work, I had to download Python2.7 just to not get an error when trying to install gmpy2. I hope they are adequate enough to tackle this problem. If not, I would really appreciate someone pointing me in the correct direction.

I have not tried anything yet, as Im sure this will take hours to compute. So I really want to make sure I am doing everything correct so that if I let my laptop run for a couple hours, I do not mess up the insides, nor will it freeze and I will be sitting here not knowing if my laptop messed up, or if its still computing.

So I suppose I am trying to seek advice on how I should proceed further.

In terms of actual code, I suppose looping through 0-9 8 times is not that hard, but I dont know how to a number into another number. In Python, how do I make it so that a number will only be inserted into the position I need it to? The number looks like this example: 

X = 124621431523_13532535_62635292 //this is only 30 digits long, mine is 615 digits long

where each "_" is where a number is missing.

I am completely at a loss on how to do this.

Once all the numbers are generated, I aim to loop through them all and raise them until I get the answer required. This part seems to be a bit easier, as it seems like just a simple loop.

So I guess my main question is how to loop through 10^8 numbers but placing them in a specific spot inside a number that is already 615 digits long? I am seeking advice on technical as well as code design so as to not take too long to generate them all.

Thank you for reading.

trev
  • 33
  • 2
  • Do you know at which point is the number "missing". If you do, you can assume that those digits are zero. Then create an array `arr` of length 8. N-th element of the array is the number between 0-9 that you want to try out on N-th digit. If the N-th digit is at position M, then X = X + 10^M where M is counted as 0 from the least significant digit. Then you need to generate all possible permutations of arr, loop through them, and check whether it solves the cipher – Aditya Santoso Apr 10 '19 at 06:34
  • The key is that `x**(a+b) mod N` can be factored into `x**a * x**b mod N` so you need only do one with zeros that being a and then do some work for each of the bs – Dan D. Apr 10 '19 at 07:12

2 Answers2

2

Turn the number into a string, use the format method, use itertools.product to generate numbers to fill the holes, then turn it back.

Example:

from itertools import product

def make_seed(n, replace_positions):
    seed = str(n)
    to_replace = [-1] + replace_positions
    substrings = [seed[start + 1:end] 
                  for start, end 
                  in zip(to_replace, to_replace[1:])] + [seed[to_replace[-1] + 1:]]
    return '{}'.join(substrings)

def make_number(seed):
    n = seed.count('{}')
    for numbers in product([0, 1, 2, 3, 4, 5, 6, 7, 8, 9], repeat=n):
        yield int(seed.format(*numbers))


seed = make_seed(123456789, [3, 5, 7])
# seed = '123{}5{}7{}9'

for i in make_number(seed):
    print(i)

Output:

123050709
123050719
123050729
123050739
123050749
123050759
123050769
123050779
123050789
123050799
123051709
123051719
123051729
...
gmds
  • 19,325
  • 4
  • 32
  • 58
  • Thanks. How long do you think it would take for a number that is 615 digits long and is missing 8 numbers? – trev Apr 11 '19 at 09:49
  • To *generate* the numbers? Probably at least hours. – gmds Apr 11 '19 at 10:14
  • Can I ask why you emphasized 'generate'? How long do you think it would to generate, do a check, then move on to the next number? – trev Apr 12 '19 at 10:21
  • Can I ask how you would modify this so that I can start it at various points? e.g. generate number from 0-10,000,000 then another from 10,000,000-20,000,000 so that I can run them concurrently? Bc at the moment, running from 0-100,000,000 will take days for me. – trev Apr 14 '19 at 06:49
  • About running time: beats me, but you could probably do some simple time profiling. About running: I suppose you could assign the generator to a variable and use another loop with `yield from`? – gmds Apr 14 '19 at 06:50
1

Since a decimal digit is just summation of digit * pow(10, n), you can assume the unknown digits to be zero, and add it with the digit-products 

#   124621431523_13532535_62635292 this is the original digit
x = 124621431523013532535062635292
positions = [8,17] # the missing digits are the 8th and 17th digits from the right

from itertools import product
trials = product(range(0,10), repeat=2)
for t in trials:
    x_prime = x
    for (digit, pos) in zip(t, positions):
        x_prime = x_prime + digit * pow(10, pos)
    print(x_prime) # do your checking here

outputs:

124621431523013532535062635292
124621431523113532535062635292
124621431523213532535062635292
124621431523313532535062635292
...
etc
Aditya Santoso
  • 1,031
  • 6
  • 19
  • yes, it will be repeat=8. Basically the `product` is to give you a stream of decimal digits of length N where N is the number of missing digits – Aditya Santoso Apr 11 '19 at 03:00
  • If I were to amend this to 8 unknown, would I change "repeat=2" to "repeate=8"? I also changed the print statement to an if statement which will print the number and then break. I am running this with those amendments right now, and it has been 2hrs. Are there any other amendments for 8 unknowns? – trev Apr 11 '19 at 03:01
  • btw, take note that this feels like a very naive enumeration approach. There might be a more optimized approach that doesn't require enumeration of the whole 10^8 answer space. – Aditya Santoso Apr 13 '19 at 07:34