Re: Linear factors of very large polynomials

[Bill Allombert <Bill.Allombert@math.u-bordeaux.fr>]

On Fri, Jan 29, 2021 at 12:20:44AM +0000, Neill Clift wrote:
> Hi,
> This is more of a question about the limits of computations pari/gp could do. This is not very important but it might be of interest to some people.
> So a few decades ago I realized eventually the password hashing algorithm in the OpenVMS operating system would be invertible. It was just a matter of machines getting enough memory and being able to do some large GCD's.
> In 2017 I asked a few questions here and got pari to actual find the linear factors of a large polynomial mod 2^64-59. The polynomial looked like this:
> 
> f(x) = x^16777213 - 24 * x^16777153 - 120 * x^3 - 198 * x^2 - 264 * x + 17748126081817865973
> 
> The constant term is different for each password that is to be found. I used FpX_roots(f,2^64-59) to find the factors. I think it took about 12 hours to do.
> Now OpenVMS isn't a seriously used operating system anymore (I don't doubt some people are still using it somewhere). It's developed still by some enthusiasts.
> They haven't fixed this problem. Clearly a modern hash should be put in it's place but they have a field size limitation of 64 bits. It can be changed but it's more work.
> I was thinking we could just increase the degree of the polynomial and
> maybe add more terms. We want the hashing to be slower and of course
> sieving out the linear terms to be impossible with some reasonable
> h/w.

I do not think this is a reasonnable cryptographic approach,
64bit is way too small, it can be brute-forced with rainbow table,
even with the best hash.

Cheers,
Bill.