Alice proposes the following puzzle to be completed.
Let m be the body of the email message,
let a be the recipient’s email address,
let H( )be the hash function SHA3-256, and
let x be an arbitrary 256-bit value.
The sender must send the value x such that the output of H(m|a|x) is smaller than the following value: $2^{215}$

How many hash functions must Bob compute to find a solution?

  • $\begingroup$ What would you expect? $\endgroup$
    – SEJPM
    Oct 6 '17 at 22:50
  • $\begingroup$ Hints: the question and the rules governing the body of emails allow $m$ to be the value of $x$ in hexadecimal, or even $x$ itself with some restrictions on $x$ that still leave the task feasible. Cryptographers assimilate bistrings to integers (in big-endian order) without even noticing it, e.g. in expressions like "the output of H(..) is smaller than..", except in carefully written standards and some extra-picky textbooks. The base-two logarithm of the answer is likely less than The Answer. $\endgroup$
    – fgrieu
    Oct 7 '17 at 15:40

See the hash as a $256$-bit number. This number is smaller than $2^{215}$ iff the upper $40$ bits are all $0$.

Suppose that a bit of the output of the hash has an equal chance to be $0$ or $1$....

  • $\begingroup$ ..is smaller than $2^{215}$ (give or take some) iff.. $\endgroup$
    – fgrieu
    Oct 7 '17 at 16:51

Your Answer

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

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