I am trying to understand how the physical limits of computation apply to crytography, and came up with the scenario below as a sort of gedanken. I would be grateful to see how others answer it.

Assume that Alice

  1. used the default GnuPG (aka "GPG") settings, except for the following:

    • --s2k-cipher-algo AES256
    • --s2k-digest-algo SHA512
    • --cert-digest-algo SHA512
  2. and then used GPG to create a 4096-bit RSA PGP encryption key pair whose private key is protected by a 10-word Diceware passphrase;

  3. and then used the public key of that key pair to encrypt a plain text 1kB long;

  4. and then stored the resulting ciphertext, along with the key pair, on a CD-ROM which she then gave to Bob, and nowhere else;

  5. and then perished, vaporised by a meteorite along with the laptop she used to perform the above tasks, leaving Bob's CD the only record of her key pair and ciphertext.

Assume also the existence of a computer, bound by the physical limits of computation as presently understood (e.g. these), but otherwise optimised to efficiently perform the tasks in question (e.g. a hypothetical quantum computer).

Finally, assume that this computer is adequately powered, and immune to catastrophes (such as the death of the Sun), during its tasks.

What is the minimum energy, in SI units (i.e. J, or kJ, or MJ, etc), such a computer would require, in order to determine the plaintext, if the CD-ROM's data are available to it?

Please explain your answer, thanks!

P.S. Please migrate this question to security.stackexchange.com if you believe it would be more appropriate there.

  • $\begingroup$ Don't you mean "...in order to determine the plaintext"? The ciphertext is right on Bob's CD, and so it's no work at all to determine that. Also, is Alice's public key available somewhere? $\endgroup$ – poncho May 2 '15 at 18:39
  • $\begingroup$ @poncho, thanks for catching that typo! And for your question. I've clarified my question accordingly :) $\endgroup$ – sampablokuper May 2 '15 at 18:45
  • $\begingroup$ Is the private key really supposed to be on Bob's CD? $\;$ $\endgroup$ – user991 May 3 '15 at 0:37
  • $\begingroup$ @RickyDemer, normally not: one would expect Alice to keep her private key private. But in this contrived scenario, yes, it really is supposed to be on Bob's CD. The point of the scenario is to create a situation in which Kerckhoffs's principle applies (or at least, something close to it): everything is known to the "attacker" except for the passphrase. $\endgroup$ – sampablokuper May 3 '15 at 2:16
  • $\begingroup$ It seems like it would be far more relevant to consider what happens if the "attacker" has the public key and the password-encrypted private key, rather than the key pair. $\;$ $\endgroup$ – user991 May 3 '15 at 2:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.