RSA like problem with unknown e and d

Question

I have encountered a strange source code part in a soon-to-be-decommissioned legacy app, which uses an RSA-like scheme for "one-way hashing" data.

It works like this:

base^input mod N = hash

The input is numeric, actually a numeric form of a 128-bit UUID, usually around 120 bits.

Base and N are hardcoded values, sized around 1020 bits.

Base is a composite; it has a few smaller prime factors (under ~30 bits), but I could not factor it completely.

N is a composite number of two large primes. The factors for N (p, q) are not provided, but I was able to factor them. They are two large primes (around 510 bits each), but their difference was below 10000. (I used Fermat's factoring technique.)

There is no guarantee that the input is coprime with φ = (p-1)*(q-1).

It's obviously not suitable for hashing, but I got curious: How could I construct a valid input for a given hash?

Like an RSA, where I know nearly anything, and looking for a valid e/d pair for a given plaintext/ciphertext pair.

If I understand correctly, it's a DLP (Discrete Logarithm Problem) to find that value. I may make it somewhat easier if I try to solve the DLP for p and q respectively, but for ~500 bits, it's still a hard problem.

Is there any more suitable method to solve it? Does it matter if the input is coprime with φ at all?

Is there any situation where this usage of an "RSA like" algo as a "one-way hashing" is good for anything?

Extra info about p-1 and q-1:

(p-1) has a few small factors: 2, 3, 10709, but above that it has too large ones (may need more time to factor)

$base^{(p-1)/r} \ne 1 \bmod p$ for all factors (and for the remaining composite).

(q-1) has about 12 small factors (2, 7, 103,...), but I can't fully factor it (may need more time)

$base^{(q-1)/r} = 1 \bmod q$ for all known factors. So it's a safe prime.

Thanks, Bill

Answer 1

If I understand correctly, it's a DLP (Discrete Logarithm Problem) to find that value. I may make it somewhat easier if I try to solve the DLP for p and q respectively, but for ~500 bits, it's still a hard problem.

Yes, it is indeed a Discrete Log problem, and has nothing to do with RSA.

And, while computing discrete logs modulo a 510 bit prime is possible, it would appear that there are likely to be easier approaches.

Here are the observations I have:

• You state the problem as looking for $input$ such that $base^{input} = hash \pmod{pq}$; we can summarize this as $base^{input} = hash \pmod p$ and $base^{input} = hash \pmod q$

• For prime $p$, if $p-1$ has a factor $r$ (and $base^{(p-1)/r} \ne 1 \bmod p$), then we can determine $input \bmod r$ in $O(\sqrt{r})$ steps.

You state that you have the $p$ and $q$ factors; have you looked at the factorization of $p-1, q-1$? (We don't care about any prime factors greater than, say, $2^{60}$ or so, and so finding all the smaller factors is easy).

Hence, if $p-1$ has small factors $2, p_1, p_2$, and $q-1$ has small factors $2, q_1, q_2, q_3$, then (assuming that all those factors pass the $base^{(p-1)/r} \ne 1 \bmod p$ test), we can compute $input \bmod \text{lcm}(2p_1p_2, 2q_1q_2q_3)$ relatively quickly.

Hence, depending on how $p-1, q-1$ factors, $\text{lcm}(2p_1p_2, 2q_1q_2q_3)$ can be fairly decent size, and even if it's not enough to give you all 120 bits, it might be quite enough to make a simple search reasonable...