# Is SAT the mathematical problem behind SHA-2 and SHA-3?

When I'm convincing non-believers that crypto is secure, I have a hard time with hash functions and the associated block ciphers.

It is easy to show why RSA is hard to crack: I multiply two small primes and ask people to factorize the product. They find it difficult compared to the multiplication step.

It is easy to show how Vernam cipher is secure: I tell them an Alice and Bob story with a flipping coin as an RNG.

But when it comes to the hashing, I am not even sure I know the underlying mathematical problem. It would be great to have a small intuitive example of that problem for illustration.

If it is indeed the boolean satisfiablity problem then I can at least mention that it is the hardest in the NP class, and if we solve it then P=NP, because many have heard about that.

I can use the argument that greed is innate to human nature and if there is at least one person who knows how to reverse hashes, they will incessantly mine crypto out of thin air and the exchange rate will eventually drop. But it is somewhat shaky I think.

• "It is easy to show why RSA is hard to crack: I multiply two small primes and ask people to factorize the product. They find it difficult compared to the multiplication step." That's lie-to-children territory. The hardness of factoring is not known to imply security of RSA. Nov 10, 2022 at 9:20
• We can make a relatively convincing lie-to-children about how secure hashes are possible. For even word width $n$, for any $k\in[1,n/2)$, function\begin{align}f_k:\{0,1\}^n&→\{0,1\}^n\\u\mathbin\|v\;&↦(((u≪k)⊕(u≫(n-k)))+v)\mathbin\|u\end{align}(where $u$ and $v$ are $n/2$-bit bitstrings assimilated to integers modulo $2^{n/2}$) is a bijection. Now fix enough public haphazard $k_0,k_1…k_ℓ$. The function $f_{k_0}∘f_{k_1}∘…∘f_{k_ℓ}$ is an haphazard bijection $g$. Now form\begin{align}h:\{0,1\}^n&→\{0,1\}^n\\w\;&↦w⊕g(w)\end{align}and we have a "clearly" hard to invert haphazard function.
– fgrieu
Nov 10, 2022 at 10:48
• SAT is a mathematical problem behind every algorithm in NP. Both the easy ones and the hard ones. Feb 3, 2023 at 20:39

Cryptographic problems should be hard in average. NP-Complete problems such that SAT are supposed to be hard in the worst case. But, for many practical distributions, SAT is not hard in average.

If it is indeed the boolean satisfiability problem then I can at least mention that it is the hardest in the NP class

This sentence is wrong, if we consider a specific distribution on inputs.

To conclude briefly the answer is no. But, if P=NP, then no efficient cryptographic constructions are possible at all (neither symmetric nor asymmetric).

Here efficient means with asymptotic exponential gap between the standard operations (encryption, decryption, signature, etc), and the cryptanalysis.