One-way function and factoring

Question

I am confused about the hardness of the one-way function behind cryptography -- if someone could factor the large number produced back into two primes quickly then the one-way function would be broken? TIA

Answer 1

Well, there are lots of one-way functions in cryptography. For most of them, it is not known how being able to factor is of any use in inverting them. For example, even if you have black box that can instantly factor any number, we still don't know how to practically find a preimage for SHA-512 (where, by preimage, I mean that, given the value of a hash, can you find a string that hashes to that value).

On the other hand, there are a few one-way functions for which being able to factor allows you to find preimages. The most common one (and the one you're probably thinking of) is RSA. In raw RSA, you're given the values $N$ and $e$ (and these two values are jointly known as the 'RSA public key'); the one way function is $RSA_{N,e}(M) = (M^e \bmod N)$.

Now, in RSA, $N$ is a large composite number; if you don't know the factorization of $N$, it's hard to invert; that is, given a random value $X$, it is usually hard to find an $M$ such that $RSA_{N,e}(M) = X$. However, it turns out that if you do know the factorization of $N$, it's easy.

Answer 2

There is an interesting distinction to be made here:

On one hand, we have the ideal one-way function, which one can easily calculate in one direction, but not invert at all (other than by brute force).

Hash functions like MD5, SHA-1, SHA-2 etc. are trying to approximate this (with more or less success).

On the other hand, we have trap-door one-way functions - these are functions which are easy to calculate, but which can be inverted easily only with help of some hidden information. You normally want a whole family of such functions for use in cryptography (otherwise you call it a backdoor, if you are the only one knowing it).

In the case of RSA, a product $n = p · q$ of two large primes, together with a public exponent $e$, forms a public key, which gives you an one-way function by modular exponentiation. The inverse operation needs (as far as we know) another (private) exponent $d$, which is not easily derivable from the public one and the modulus $n$, but can be easily calculated from the two prime factors $p$ and $q$ (and $e$). The private exponent (or the two primes) can thus be seen as the trap door for the one-way function.

Thus, here the hardness of the factoring problem is necessary for the one-way property of RSA.

Other asymmetric encryption schemes use other trap-door one-way functions, which are not related to the factoring problem (or sometimes one-way functions without a trapdoor).