# RSA: mulitple key exchanges [closed]

I could be horribly mistaking what the RSA algorithm actually does. So perhaps this question makes no sense, I'm asking this to make sure I got everything right.

Based on the assumption that messages which are encrypted with the public key can only be decrypted with the private key, would exchanging a pair of key pairs after the first plain-text exchange increase the time needed to uncover the plain-text?

-
you might be mistaken but you are definitely off-topic here check security.SE (not sure where this really should be though) – ratchet freak Dec 22 '11 at 19:32
I'm not entirely sure what your proposal is, but what one usually does for confidentiality is encrypt the actual plaintext with a symmetric cryptosystem such as DES or AES using a randomly chosen one-time key, and then encrypt the one-time key with RSA (or another public-key system), such that only one (slow) RSA primitive suffices for an arbitrarily long message. – Henning Makholm Dec 22 '11 at 19:43
@ratchet freak I was expecting this question to have been asked before, but I couldn't find anything anywhere. And I haven't found any documents that state sending multiple keys either. I thought that I must be wrong, and that there would be a mathematical reason why this wouldn't work the way I think it would assuming I'm not mistaking what RSA does in the first place, so that's why I posted it here. @ Henning Makholm, I'm asking the very same thing, I'm only replacing that DES/AES key with another RSA key, wouldn't that provide roughly the same results (time to generate keys excluded)? – Daan Dec 22 '11 at 19:44
@Daan: The point of exchanging a symmetric key is that symmetric algorithms are much faster than public-key ones. So you get a speed benefit by only using the RSA primitive once. If you encrypt an RSA key by RSA itself, it is not clear that you have gained anything. – Henning Makholm Dec 23 '11 at 12:49
@ratchetfreak: Actually, there is a separate site about Cryptography. Though I would oppose migrating this question there (or reasking in the current form), as it is totally unclear what is asked here. – Paŭlo Ebermann Dec 23 '11 at 20:35
show 1 more comment

## closed as off topic by t.b., LVK, Jennifer Dylan, William, tomaszSep 6 '12 at 21:15

Questions on Mathematics Stack Exchange are expected to relate to math within the scope defined in the FAQ. Consider editing the question or leaving comments for improvement if you believe the question can be reworded to fit within the scope. Read more about closed questions here.

actually in rsa algorithm this happens:

two distinct prime numbers are choosen

then n=p*q is calculated

Compute φ(n) = (p – 1)(q – 1), where φ is Euler's totient function.

Choose an integer e such that 1 < e < φ(n) and greatest common denominator of (e,φ(n)) = 1, i.e. e and φ(n) are coprime.

e is released as the public key exponent. e having a short bit-length and small Hamming weight results in more efficient encryption - most commonly 0x10001 = 65537. However, small values of e (such as 3) have been shown to be less secure in some settings.

Determine d = e–1 mod φ(n); i.e. d is the multiplicative inverse of e mod φ(n). This is more clearly stated as solve for d given (d*e)mod φ(n) = 1 This is often computed using the extended Euclidean algorithm. d is kept as the private key exponent.

The public key consists of the modulus n and the public (or encryption) exponent e. The private key consists of the modulus n and the private (or decryption) exponent d which must be kept secret.

Alice transmits her public key (n,e) to Bob and keeps the private key secret. Bob then wishes to send message M to Alice.

He first turns M into an integer m, such that 0 < m < n by using an agreed-upon reversible protocol known as a padding scheme. He then computes the ciphertext c corresponding to c = me (mod n). This can be done quickly using the method of exponentiation by squaring. Bob then transmits c to Alice.

the speed actually depends on the key size

In practical applications, it is common to choose a small public exponent for the public key. In fact, entire groups of users can use the same public exponent, each with a different modulus. (There are some restrictions on the prime factors of the modulus when the public exponent is fixed.) This makes encryption faster than decryption and verification faster than signing. With the typical modular exponentiation algorithms used to implement the RSA algorithm, public key operations take O(k^2) steps, private key operations take O(k^3) steps, and key generation takes O(k^4) steps, where k is the number of bits in the modulus.

Fast multiplication'' techniques, such as methods based on the Fast Fourier Transform (FFT), require asymptotically fewer steps. In practice, however, they are not as common due to their greater software complexity and the fact that they may actually be slower for typical key sizes.

-
 While it's not clear to me exactly what the question was, this is certainly not an answer to it. The OP was asking about what one might use the RSA primitive for, not how it works internally. – Henning Makholm Dec 23 '11 at 12:50 i thought he was asking about time complexity of rsa algorithm – harish.venkat Dec 23 '11 at 18:52