Thanks for your questions & comments! On Fri, Oct 11, 2019 at 10:40 PM Andres Valloud <avalloud@smalltalk.comcastbiz.net> wrote:
or that you have 2^40 sets of lower_k and upper_k bounds
This.
The order of 0x88405 mod 2^24 is 2^22, does that induce duplicated or contradicted constraints?
There'll be at most ten clauses ANDed together, so the order isn't an issue.
The constant 0x88405 is invertible mod 2^24, can you multiply each constraint by 0x88405^-1 mod 2^24 sufficient times so that every constraint reads like this, for some j = j(k)?
lower_k * 0x88405^-j <= x < upper_k * 0x88405^-j
No, because the upper and lower bounds are natural numbers. If all of them were elements of Z / 2^24 Z, then bounds wouldn't make sense.
If yes, then could you proceed one constraint at a time hoping the intersection of all possible values for x will shrink to nothing?
Well, shrink to a single value. About 20 years ago I published a ciphertext-only attack on zipcloak when there were five or more files in the archive. Now I've got a client who's only got two files, so there are fewer bits to filter with, and the brute-force I used before would be too much work. I'm guessing whether there's a carry at bit 24 of a 32-bit word. If there is a carry, that sets a lower bound on the low 24 bits, while if there isn't, that sets an upper bound. But then the whole state gets multiplied by 0x08088405 mod 2^32, so it spreads the range out over the whole space. I can work mod 2^24, but I'm hoping there's a way of calculating the answer rather than brute-forcing the space and filtering.
On 10/11/19 11:51 , Mike Stay wrote:
I'd like to efficiently find solutions to constraints of the form
lower1 <= ((x * 0x000001) mod 2^24) < upper1 && lower2 <= ((x * 0x088405) mod 2^24) < upper2 && lower3 <= ((x * 0x652819) mod 2^24) < upper3 && ... where the constants are consecutive powers of 0x088405. Brute-forcing the space isn't much work to do for a single set of upper and lower bounds, but when I've got 2^40 such sets, it's daunting.
Any ideas?
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Mike Stay - metaweta@gmail.com http://math.ucr.edu/~mike https://reperiendi.wordpress.com