coppersmith timings vary a lot

[dani0104]

Hey it's me from the email again. I've been trying to solve corrupt-key-2 from PicoGym

I'm using an example I generated myself, I added the code below to the end of the coppersmith.py file

exa_N  = 174689501556974852774692456662282428651334567739483151394730366472723757343603695946018382897568356669603128108034723257753348635879786275267108581170688382291283798632863388202044928301928828912510733489700352690675873162118680451826827914903826567505877313658436202501645891375370591464209179799149746598607
exa_p = "ff5a380b8894d65327b9ef6af157b365e8bb1cff346e98a7c5c7f022123f890f7324c6b096c4516e769fd6e6ee8fe88fd901b33d9fd1e717ed777ee137d51175"
exapm = "ff5a380b8894d65327b9ef6af157b3??????????346e98a7c5c7f022123f????????c6b096c4516e769fd6e6ee8fe88fd901b33d9fd1e717ed????????d51175"
print(factorize_p(exa_N, PartialInteger.from_hex_be(exapm), m=5, t=1))

My question is why at times these lines seem to get executed in less than half a minute, and other times they take way too long for me to measure? I'm asking this because I'm trying to bruteforce bits of the prime, but I can't figure out which bits should I bruteforce for most efficiency These are the actual values I have (the ones above are just for testing):

orig_p= "fe8984407b0816cc28e5ccc6bb7379??????????ca3806dd2cfdfc8d616b????????6109a4dbe3876b8d1b8adc9175dfba0e1ef318801648d6??????????a05b"
orig_N =  0xc20d4f0792f162e3f3486f47c2c5b05696ba5c81ec09f5386bf741b7289b85e2d744559825a23b0ae094da214f3158344e5d5ba86fb1ecd1f40c8682a7bee55021eba772e23793001a38b9cccbfdc1d9316cccc3b79acd045c512b44e0f3697383958113a280791e17c23fe80fa38099e4907f70f4d228285aac69ed2d3bcf99

[jvdsn]

You don't need to brute force any bits for this challenge, you've got enough bits to solve it. If you want to debug whether it would work or not, you can do the following:

import logging
logging.basicConfig(format='%(asctime)s.%(msecs)03d %(levelname)s {%(module)s} [%(funcName)s] %(message)s', datefmt='%Y-%m-%d,%H:%M:%S', level=logging.DEBUG)

from shared import small_roots
small_roots.DEBUG_ROOTS = [0x777ee137, 0x890f7324, 0x65e8bb1cff] # Note the order is reversed here

You'll then get an output similar to this:

2022-02-11,19:00:34.016 INFO {coppersmith} [factorize_p] Trying m = 5, t = 1...
2022-02-11,19:00:34.023 DEBUG {herrmann_may_multivariate} [modular_multivariate] Generating shifts...
2022-02-11,19:00:34.025 DEBUG {__init__} [fill_lattice] Filling the lattice (56 x 56)...
2022-02-11,19:00:34.269 DEBUG {__init__} [reduce] Executing the LLL algorithm...
2022-02-11,19:00:52.405 DEBUG {__init__} [reconstruct_polynomials] Reconstructing polynomials...
2022-02-11,19:00:52.418 DEBUG {__init__} [reconstruct_polynomials] Original polynomial divides reconstructed polynomial at row 0, dividing...
2022-02-11,19:00:52.418 DEBUG {__init__} [reconstruct_polynomials] Polynomial at row 0 is constant, ignoring...
2022-02-11,19:00:52.425 DEBUG {__init__} [reconstruct_polynomials] Polynomial at row 1 roots check: 0
2022-02-11,19:00:52.432 DEBUG {__init__} [reconstruct_polynomials] Polynomial at row 2 roots check: 0
2022-02-11,19:00:52.438 DEBUG {__init__} [reconstruct_polynomials] Polynomial at row 3 roots check: 0
...

This tells you which reconstructed polynomials have integer roots in the provided roots. If all of them are non-zero, then you should select a higher m value (or maybe a higher t value, but this works rarely). If most of them (excluding the couple last ones) are 0, then the Groebner basis method will automatically find the roots. If most of them are 0, but there are a couple of non-zero ones first, you can manually pick the right polynomials and perform the Groebner basis reduction yourself. However, this requires a lot of hacking in the code.

Once you can solve it for the example values (without brute forcing here), it shouldn't be too hard to solve the actual challenge

[dani0104]

Wow! after debugging I realized all I needed to do was change m from 5 to 6, for whatever reason 5 takes much much longer than 6 on the actual values I need (and example values too), like it should still work with 5 based on my testing, but it's so much slower it's unbelievable (contrary to what I expected).

Challenged solved now, but care to explain why it might work much faster on m=6 than m=5 ? (at least with both values I provided, example values and challenge values)

[dani0104]

Never mind after some more debugging I noticed that when m=5 another sneaky number besides the last few was non zero, I get why it failed.

[jvdsn]

Never mind after some more debugging I noticed that when m=5 another sneaky number besides the last few was non zero, I get why it failed.

Right, the issue is that the root finding method can't know that without also knowing the roots. Heuristically, the first ones should always be zero, but sometimes it's not the case.