# How are the primes used to generate RSA keys?

I am confused about how keys in RSA asymmetric encryption are generated and what the implications for open communications are. Textbooks say the one-way function is merely two primes (with some critical constraints) -- so how do the two primes generated get turned into keys?

Does this mean that having a public key is simply having one of the primes in a translated or equivalent form? For example, if I were to encrypt a message with someone else's public key and the one-way function could be broken by a third party, then could they decrypt the message with a key generated by the other prime? Does the other prime have to go through some special process to become a key?

To go further, if the encrypted message was posted in a public forum or sniffed off of a wireless network, etc. (and again, the one-way function was broken by a mysterious third party), does that mean the message could be decrypted by the third party? Would it matter which prime was used? What i am wondering is what is the process whereby the primes behind the one-way function are converted into keys and is that process the same regardless of encryption used?

-

## migrated from security.stackexchange.comApr 19 '12 at 20:50

This question came from our site for Information security professionals.

Welcome to Cryptography Stack Exchange. Your question was migrated here because of being not directly related to software development (the topic of Stack Overflow), and being fully on-topic here. Please register your account here, too, to be able to comment and accept an answer. –  Paŭlo Ebermann Apr 20 '12 at 7:40
I edited your title (and the text) to make clear this is about RSA - there are other asymmetric encryption schemes which don't use primes this way. –  Paŭlo Ebermann Apr 20 '12 at 7:43

Textbooks say the one-way function is merely two primes...

Yes, that's the key part.

It turns out that if you have a number that's a product of two large primes, deducing which primes factor that number is quite difficult.

So, what we understand from this is that if you have $n = pq$, and you know $p$ and $q$, you can generate $n$, but if you have only $n$, it is hard to generate $p$ and $q$.

These are not keys by and of themselves - they're parts of a process used to find a key. Specifically, a number $e$ is chosen and then you need to find $de = 1 \mod (p-1)(q-1)$. I've covered the mathematics in detail here, but the essential part to understand is that it is difficult to compute $p-1$ or $q-1$ without $p$ and $q$, which you don't have if you have only $n$. Thus, if you know $e$, you have no way to get to $d$ (it's important to understand it isn't theoretically impossible. It's just very, very hard practically).

$e$ and $d$ form the key - $e$ is chosen and $d$ is usually computed, although not always by the mechanism I described.

...if ... the one-way function could be broken by a third party, then could they decrypt the message with a key generated by the other prime?

Yes. The message wouldn't be generated by another prime in the case of RSA, but if they could somehow undo the one-way function, then the cryptosystem is broken and all your messages would be readable.

Would it matter which prime was used?

There are two cases here:

• In the case of which primes are used for RSA - it does matter. They need to be big! At one time, the choice of prime did matter, for resistance against Pollard's p-1. However, it is now thought that for more advanced methods this is not the case.
• In the case of the keys (which may or may not be prime) - for RSA you can actually interchange the keys, which makes RSA a trapdoor permutation. However, this is unusual and many other one-way functions are just trapdoor functions - which means they don't have this property.

What i am wondering is what is the process whereby the primes behind the one-way function are converted into keys and is that process the same regardless of encryption used?

The $de = 1 \mod (p-1)(q-1)$ process is not the only way to relate $d$ to $e$. You can also use $\lambda(n)$, the Carmichael function, which is what happens in PKCS#1.

Other public key systems have different conversion functions, not all of which rely on the use of prime number factorisation. Common examples are the discrete logarithm problem and point multiplication over elliptic curves.

(You can use this script to render the Mathjax in this answer; it'll automatically render if this Q gets migrated).

-