Does somebody know a cryptographic/mathematic operation, that needs much computing power to be "encrypted"/"created" but doesn't need much power to be "decrypted"/"solved"?

  • $\begingroup$ That's pretty much the basis of much of cryptography. $\endgroup$ Commented Oct 23, 2014 at 19:36
  • $\begingroup$ @StephenTouset : $\:$ How? $\;\;\;\;$ $\endgroup$
    – user991
    Commented Oct 23, 2014 at 20:35
  • 1
    $\begingroup$ @stereo_ Why is that "hard to compute" part necessary? It seems like all that would do would be to make it hard to generate games. Can you maybe describe how you want the game to work? $\endgroup$
    – sju
    Commented Oct 23, 2014 at 22:55
  • 1
    $\begingroup$ The "just a little to be solved" part is easy: declare that 0 is always a solution. $\;$ $\endgroup$
    – user991
    Commented Oct 24, 2014 at 0:25
  • 3
    $\begingroup$ I'd like to answer, but I've got a sudoku to solve. $\endgroup$
    – Maarten Bodewes
    Commented Oct 24, 2014 at 0:58

2 Answers 2


Lots of problems are hard to solve but easy to check. For example:

  1. finding hash pre-images of particular values such as 0
  2. calculating discrete logs of small numbers modulo a prime
  3. finding the factors of a large composite of a special form like $2^p-1$

I don't think there's an essential difference between solving and checking they're just arbitrary descriptions of the operations.

I imagine an unstated requirement of your question is that it should not be possible to pretend to have solved hard problems by generating random solutions and then saying that you arrived at the solution by solving the hard reverse problem. This is a bit like shooting arrows randomly into a wood and then painting targets round the arrows wherever they have stuck in the trees.


Play with SBOX in AES. The encryption using the standard one is faster than the decryption. If you search you can find one with your specifications.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.