# One-way function and factoring

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

-
Welcome to Crypto Stack Exchange. There is no the one way function. There is a definition of the term one way function, and there are several candidates for such a function, some of them being related to factoring and others not. What do you actually want to know? – Paŭlo Ebermann Apr 10 '12 at 18:35

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.

-
To clarify, my goal is to know what part of the RSA formula to factor (and any other cryptosystem formula that requires factoring a large number). Essentially I need to know the various formula components and how to get them into variables so I can try out some ideas about factoring in general. – Iceberg Hotspot Apr 11 '12 at 4:11
P.S. Is there a way for newbies like me to pay for questions to be answered via donations or something (since I only have one badge)? – Iceberg Hotspot Apr 11 '12 at 4:21
IcebergHotspot: For RSA, what you need to factor is the modulus $N$, which is part of the public key. If you're asking how, given a public key, you find $N$, that rather depends on how the public key is encoded; the most common is rsa.com/rsalabs/node.asp?id=2125 – poncho Apr 11 '12 at 10:46

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

-