StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>In theory, it doesn't have to be. The encryption and decryption algorithms are essentially identical. Given:</p> <pre><code>d = decryption key e = encryption key n = modulus (product of primes) c = encrypted code group m = plaintext code group </code></pre> <p>Then:</p> <ol> <li>Encryption c<sub>i</sub> = m<sub>i</sub><sup>e</sup> (mod n)</li> <li>Decryption m<sub>i</sub> = c<sub>i</sub><sup>d</sup> (mod n)</li> </ol> <p>The normal algorithm for raising to a power is iterative, so the time taken depends on the size of the exponent. In most cases, the pair works out with the decryption key being (usually considerably) larger than the encryption key.</p> <p>It is possible to reverse that though. Just for a toy example, consider:</p> <pre><code>p=17 q=23 n=391 </code></pre> <p>Here's a list of some valid encryption/decryption key pairs for this particular pair of primes:</p> <pre><code>e = 17, d = 145 e = 19, d = 315 e = 21, d = 285 e = 23, d = 199 e = 25, d = 169 e = 27, d = 339 e = 29, d = 85 e = 31, d = 159 e = 35, d = 171 e = 37, d = 333 e = 39, d = 343 e = 41, d = 249 e = 43, d = 131 e = 45, d = 133 e = 47, d = 15 e = 49, d = 273 e = 51, d = 283 e = 53, d = 93 e = 57, d = 105 e = 59, d = 179 </code></pre> <p>Out of those 20 key pairs, only <em>one</em> has a decryption key smaller than the encryption key. In the other cases, the decryption key ranges from just under twice as big to almost 17 times as large. Of course, when the modulus is tiny like this, it's quick and easy to generate a lot of key pairs, so finding a small decryption key would be fairly easy -- with a real RSA key, however, it's not quite so trivial, and we generally just accept the first pair we find. As you can see from the list above, in that case, you're quite likely to end up with a decryption key that's considerably larger than your encryption key, and therefore decryption will end up slower than encryption. When working with ~100 digit numbers, we'd have to be quite patient to find a pair for which decryption was going to be (even close to) as fast as encryption.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload