The short answer is that such numbers $N$ (that are generated pseudo-randomly) have to be infeasibly large, even if you accept numbers that might be only partially hard to factor.
Define a b-smooth integer as an integer with only primes less than $2^b$ in its factorization. Observe that all integers less than $2^b$ are b-smooth.
Define an integer that is b-hard to factor as an integer $N$ that meets the following criteria:
- $N$ is not a prime.
- $N$ is not the product of a single prime times a b-smooth integer.
- $N$ is not a b-smooth integer.
This leaves us with integers $N$ that are the product of two or more primes greater than $2^b$, possibly times a b-smooth integer. Most candidates will fall into this category, but unfortunately the number of candidates that don't, is hard to make small enough to get cryptographically acceptable guarantees the candidate cannot be factored.
Testing $N$ for primality is relatively cheap, so it might be presumed that the entity generating $N$ is discarding any candidates that are prime.
Still, if $N$ is composite, an estimate of the number of candidates that are a product of a large prime times a b-smooth integer, is that this number is roughly equal to the number $\pi(N)$ of primes less than $N$. Most of those primes are greater than $2^{n-b}$ and for candidates $N$ with such a prime in the factorization, the other factor will be a b-smooth integer. Since $\pi(N) \approx N/\log(N)$, and $N = 2^{\log(N)\log(2)}$ this means $N$ has to be infeasibly large if you want guarantees that $N$ is equally infeasible to factor, say $N \gt 2^{2^{128}}$.
Edit: It should be noted that the main reason numbers $N$ that are generated this way have to unrealistically large, is because that is the only way to ensure a low probability of a prime factor that is almost as large as $N$ itself. A more feasible way to ensure that $N$ does not have any large prime factor, is to construct $N$ as a product of smaller random integers, as suggested in the paper cited in this answer. However, $N$ would still have to huge.
A completely different approach, considering that the reason for the question is to find suitable parameters for a hash function, would be to generate a sequence of random integers $N_i$, but not multiply them together, but instead use them for successive RSA operations. Select the exponent $e$ as a mid-sized prime, of a size relative to each $N_i$ such that both the probability that $e \ge \phi(N_i)$ is low, and the probability that $GCD(e,\phi(N_i)) \ne 1$ is low. You should probably also ensure $e$ is not a Sophie-Germain prime.
Now define the function $H(m)$, for $2 \le m \lt N_0$, as
- $H_0(m,e) = m^e \mod N_0$
- $H_i(m,e) = {H_{i-1}(m,e)}^e \mod N_i$, for $0 \lt i \le n$
- $H(m,e) = H_n(m,e)$
If $e$ is selected as described above, the probability can be made arbitrarily high that each $H_i()$ function is a permutation, save for the few bits that are lost due to the different values of the moduli. The probability that at least one of the functions $H_i()$ is one-way (and hence $H()$ is one-way), depends on the choice of parameter $n$ and parameter $k$ such that each $2^{k-1} \lt N_i \lt 2^k$. For instance, I guess that selecting parameters such that $k = 4096$, $2^{191} < e < 2^{192}$ and $n = 256$ would be adequate.
The downside is of course that the above function $H()$ can't easily be used for comparing hashes with different salts. It is however possible to modify it slightly, to give it this feature:
- $H_0(m,e) = m^e \mod N_0$
- $H_i(m,e) = {H_{i-1}(m,e)}^e \mod N_i$, for $0 \lt i \lt n$
- $N'_n = f(N_n + H_{n-1}(m,e))$
- $H'(m,salt) = m^{2salt} \mod N'_n$.
The function $f()$ might be selected in such way that statistical analysis of realistic number of differently salted hashes of the same message $m$, is unlikely to leak bits about the exact value of $N'_n$.
Such a function $H'(m,salt)$ might arguably be potentially useful as a building block of challenge-response protocols, but would present few benefits over plain $H()$ in terms of rainbow table attack prevention.
