/sci/ - Science & Math

[Anonymous No.9858011]

I'm trying to break a 64 bits Truncated Linear Congruential Generator truncated to its high 32 bits.

It is in the form of a * x + c % m. a, c and m are all known, but here is the catch: the 32 bits generated are randomly truncated even further to an observable output ranging from 1 to 9 bits (and I'm able to know how many significant bits there are in each output). The goal here is of course, to find any state x using as few bits as possible.

I suck at math obviously so I tried looking up how to break it.
Apparently a TLCG can be solved in polynomial time by applying LLL to a matrix derived from a and a vector made of the truncated values and doing some shit beyond my reach. But I struggle to adapt it to fit my exact problem because of the following reasons:
- The numbers needs to be truncated down to at least 5 significant bits, no matter how many numbers I have, if they're below 5 significant bits, it simply doesn't work and I don't know why.
- The algorithm implementation I tested assumed c = 0, but when c != 0 it fails no matter how many significant bits are in the truncated output.
- I think this algorithm simply cannot work when the number of significant bits varies between successive outputs.

I've thought about only using outputs with a lot of significant bits, but I this algorithm probably won't work because it assumes consecutive values.

Any clue on what should I look into, or am I trying to do something literally impossible?

[Anonymous No.9858019]

Sorry, I don't know cryptography.