# RSA like problem with unknown e and d

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

• For pulling out factors of numbers this size, I like gmp-ecm.
– fgrieu
Commented Jul 11 at 21:26

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...

• Addition: in the expression $\mathrm{base}^{(p-1)/r} \ne 1 \bmod p$, $r$ is the $p_i$ to be tested. When an appropriate factorization of $p-1$ is known, next step is Pohlig-Hellman. Even in the worst case of $p$ a safe prime, a DLP modulo a 510-bit $p$ is tractable; the record is 795-bit.
– fgrieu
Commented Jul 11 at 19:42
• @fgrieu: true, two safe primes would be the worse case - however, if the implementors were careful enough to select safe primes, they would have likely picked two primes that weren't that close... Commented Jul 11 at 19:58
• @fgrieu: and, it isn't straight PH - large prime factors of $p-1, q-1$ are of little use (and so you end up needing to do a partial DLog), however with the two prime factors, you can use partial information from both... Commented Jul 11 at 20:13
• @poncho Thanks. I've put the info about p-1, q-1 factorisation in the original posts. Should I try to factor full the (p-1) and (q-1) numbers? How can your easier approach can be used, when (q-1) is a safe prime? Commented Jul 11 at 20:29