# Building a hard to factor number without knowing its factorization

It is possible to find an efficient algorithm for constructing a provably hard to factor number $N$, together with a witness that shows that it is indeed hard to factor. EDIT, since it was not clear: I also want to be sure that even the person that constructed the number cannot factor it.

Of course, a random large enough integer is going to be hard to factor with high probability, but we might be unlucky.

There are also multi-party protocols for shared generation of RSA moduli (such as http://crypto.stanford.edu/~dabo/abstracts/sharing.html), but I would like a non interactive technique.

Motivation: This was suggested by Poncho's answer to Compare two hashes with different salt

-
AFAIK it is only possible with huge (and thus very inefficient) primes. –  CodesInChaos Jul 12 '13 at 21:03
For any algorithm that constructs integers, there exists a simple way to have it construct a number which can be easily factored by the person who constructed it. $\:$ Thus, such an algorithm can only be possible $\hspace{.1 in}$ in the sense that a collision-resistant hash function is possible. $\;\;\;$ –  Ricky Demer Jul 13 '13 at 2:29
@RickyDemer "For any algorithm that constructs integers, there exists a simple way to have it construct a number which can be easily factored by the person who constructed it." I fail to see what you are exactly saying here. Care to explain? –  nightcracker Jul 13 '13 at 5:04
I would be happy with a solution in the random oracle model. For example, if you don't want a proof that $N$ is hard to factor and accept to rely on luck, then constructing $N$ as a concatenation of $H(IV,0) \cdots H(IV, count-1)$ and publishing $IV$ together with $N$ to allow for verification should be fine. –  minar Jul 13 '13 at 6:00
If you accept an output of fixed bit length $n$ that, with high probability $\pi$, contains at least two factors, each of at least $b$ bits (e.g. $b=512$), but might contain one or more factors of bit length less than $b$, it is just a question to make $n$ large enough to match $\pi$. A formula might be constructed based on estimates of the number $\Pi_{2^{n-b}}$ of primes less than $2^{n-b}$, the fundamental theorem of arithmetic, and combinatorics. If the output does not have at least two factors greater than $2^{b-1}$, it will have a b-smooth factor greater than $2^{n-b}$. –  Henrick Hellström Jul 13 '13 at 9:19

The zerocoin paper mentions such a technique:

implementers can use the technique of Sander for generating so-called RSA UFOs for accumulator parameters without a trapdoor

and refers to:

T. Sander, “Efficient accumulators without trapdoor extended abstract,” in Information and Communication Security, vol. 1726 of LNCS, 1999, pp. 252–262.

I can't access it since it's behind a paywall, but according to a comment by Hal Finney they're rather large:

As far as the Sander paper, trust can be minimized by seeding a random number generator from a public headline. The real problem with this approach is that it generates ridiculously large RSA moduli. One example they give in their paper is 40,000 bits!

-
A version is available on citeseer: citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.28.4015 –  minar Jul 15 '13 at 6:13
The last comment is misquote of the paper. The claim made in the paper is worded as follows "Our basic algorithm sketched above will yield an output of bit length (much) greater then (sic!) 40.000 bits for these parameters, and may thus be too large for practical applications." The "much" part of the quote is significant, since the formula contains an $O()$ term that is never resolved (because the intention is only to prove the existence of certain composite number, not exactly how large they have to be). –  Henrick Hellström Jul 15 '13 at 7:47
Not fully satisfactory, but it is apparently the best that can be done at present. I'll accept this answer. –  minar Jul 16 '13 at 5:28

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.

-
One could have the entity do trial division and then Pollard's rho factorization on $N$, and discard any candidates that it finds a non-trivial factor of (since the cofactor would be smaller than another random $N$). $\:$ (The numbers would still have to be way too large, though.) $\;\;\;$ –  Ricky Demer Jul 14 '13 at 8:59
This is a nice analysis of why generating $N$ randomly is not a giving a good solution to my question and I will vote it up for this reason. However, it does not really answer the question. Typically, for discrete logarithm systems, it is easy to build an number $x$ modulo $p$ without gaining extra knowledge about $\log(x)$ (at least in the random oracle model). Just construct $x$ as a hash and give the input the the hash function as witness. –  minar Jul 14 '13 at 9:00
That's because generating $x$ randomly does not give knowledge about $\operatorname{log}(x)$, and discrete logarithm is supposed to be hard for random inputs. $\:$ –  Ricky Demer Jul 14 '13 at 9:02
I get your main point, a random number may be "easy" to factor with not so small probability, unless the numbers are huge. I still don't see how you are balancing your parameters. The cost to factor a $2^b$-smooth number (using classical terminology, $b$-smooth in your notation) using ECM is $L(1/2)$, i.e. $2^{(c+o(1))\cdot \sqrt{b\log{b}}}$ for some constant $c$. So how do you set $k$ to equalize everything ? –  minar Jul 14 '13 at 17:37
Another interesting point, which still does not answer the original question in a satisfactory way. Your analysis also shows that if $N$ is constructed as a product $\prod_{i=1}^{\ell} N_i$, where $N_i$ is a long enoungh hash of $IV$ concatenated with $i$, then $N$ will be hard to factor ($\ell$ need to grow with the size of the $N_i$s) because at least one of the $N_i$ will be hard to factor with overwhelming probability. –  minar Jul 14 '13 at 17:43

Here's a non-interactive technique for shared generation of multi-prime RSA moduli:

Each party $i$ generates and publishes a standard RSA modulus $N_i$.

For any set $Q$ of parties that published a modulus for this purpose, do

$S \: := \: \{N_i : i\hspace{-0.02 in}\in\hspace{-0.02 in}Q\} \;\;\;$ then output $\;\;\; \left\langle \left(\displaystyle\prod_{n\in S} n\right) \hspace{.04 in} , \{\langle i,\hspace{-0.02 in}N_i\rangle : i\hspace{-0.02 in}\in\hspace{-0.02 in}Q\}\hspace{-0.06 in} \right\rangle \;\;\;\;$.

If standard RSA is secure, then $N$ will be hard for any
coalition that $Q$ is not a subset of to completely factor.

If the standard RSA moduli have length $n$, then $\;\; \operatorname{Length}(N\hspace{.015 in}) \: \approx \: \left|Q\hspace{.01 in}\right|\hspace{-0.03 in}\cdot\hspace{-0.02 in}n \;\;\;$.

-