Every secret key starts as random numbers. If the dice are loaded, an attacker can guess the key without breaking any math.
The idea: The math assumes an attacker has to search every possible key: for a 128-bit key that's about 3.4 × 10^38 options. That only holds if every key was equally likely. If a key generator only had 32,767 possible starting states, as in the Debian bug, the attacker just tries them all in seconds. So randomness is a silent assumption under everything on the map, including the boxes that need no math at all.
Why it matters: Weak randomness has leaked keys and caused real thefts, even when the cryptography itself was perfect.
The details
On the map: keys, nonces, IVs: silently required by everything (one reused ECDSA nonce leaks the private key)
Every key, nonce and initialization vector must be unpredictable. The mathematics of cryptography assumes secrets are chosen uniformly at random. If the random number generator is weak or repeats itself, attackers skip the hard math entirely.
The Debian OpenSSL bug (2006-2008) left only 32,767 possible keys per key type and size: the process ID was the only entropy[1].
A reused ECDSA nonce exposed Sony's PlayStation 3 signing key (2010)[2]. A broken Android random generator let thieves drain Bitcoin wallets (2013)[3].
Dual_EC_DRBG, a NIST-standardized generator, used a constant that could hide a backdoor (Shumow and Ferguson, 2007)[4]. 2013 reports said the NSA engineered it, and in 2015 an unauthorized change to that constant in Juniper's firewalls exposed their VPN traffic[5].
Even unconditional schemes like the one-time pad are only as strong as their randomness. Operating systems gather physical noise and condition it with extractors and cryptographic generators.
Rests on
If any of these breaks, this breaks too.
Nothing below it on the map: this is a starting point that the rest builds on.
If it falls
If this breaks, these break with it.
Needed by everything in the unconditional box (and everything else): 12 boxes show them
Scott Yilek, Eric Rescorla, Hovav Shacham et al. When private keys are public: results from the 2008 Debian OpenSSL vulnerability. Proceedings of the 9th ACM SIGCOMM conference on Internet measurement, 2009. doi:10.1145/1644893.1644896
Dan Shumow and Niels Ferguson. On the Possibility of a Back Door in the NIST SP800-90 Dual Ec Prng. CRYPTO 2007 rump session. rump2007.cr.yp.to/15-shumow.pdf
Stephen Checkoway, Jacob Maskiewicz, Christina Garman et al. A Systematic Analysis of the Juniper Dual EC Incident. Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security. doi:10.1145/2976749.2978395