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