Asymmetric Keys & Randomness

TL;DR

Generally, no. Asymmetric algorithms (like RSA and ECC) need significantly more randomness than just the key size to be secure. Using only a key-sized amount of randomness severely weakens them, making them vulnerable to attacks.

Understanding the Problem

Asymmetric cryptography relies on mathematical problems that are hard to solve without special information (the private key). Randomness is crucial for creating this special information. Think of it like picking a secret number – if you don’t pick randomly, someone might guess it.

Why Key-Sized Randomness Isn’t Enough

1. RSA: RSA key generation involves choosing two large prime numbers (p and q). If your randomness is limited to the key size, you’re likely to generate primes that are too close together or have predictable structures. This allows attackers to factor the modulus (N = p * q) using algorithms like Pollard’s rho algorithm or Lenstra elliptic-curve factorization.
2. ECC: Elliptic Curve Cryptography involves choosing a random point on an elliptic curve. Insufficient randomness means points can be predicted, leading to attacks that reveal your private key. The discrete logarithm problem is the foundation of ECC security; poor randomness makes this much easier to solve.

How Much Randomness *Is* Enough?

The required amount of randomness depends on the specific algorithm and desired security level, but it’s generally significantly larger than the key size.

• RSA: For a 2048-bit RSA key, you typically need at least 512 bits (and often more) of truly random input to find suitable primes.
• ECC: For a 256-bit ECC key, you’ll usually require around 320-512 bits of randomness.

These are guidelines; consult the relevant standards (e.g., NIST recommendations) for precise requirements.

What Happens If You Use Too Little Randomness?

• Key Reuse: The same key might be generated multiple times, allowing an attacker to compromise all communications using that key.
• Predictable Keys: Attackers can predict future keys based on the limited randomness source.
• Weak Key Generation: The resulting keys may have mathematical weaknesses that make them easier to break.

How to Get Enough Randomness

1. Hardware Random Number Generators (HRNGs): These use physical phenomena (like thermal noise or radioactive decay) to generate truly random numbers. They are the most secure option, but can be slower and more expensive.
2. Pseudo-Random Number Generators (PRNGs): These algorithms produce sequences of numbers that appear random, but are actually deterministic based on a seed value. Cryptographically Secure PRNGs (CSPRNGs) are designed to be resistant to attacks, even if the seed is known.

• Linux: Use /dev/urandom or /dev/random.

  cat /dev/urandom | head -c 32

  (for 32 bytes of randomness)

• OpenSSL: Use the RAND_bytes() function in your code.

Entropy Collection: Collect entropy from various system sources (e.g., keyboard timings, mouse movements, network activity) to seed a PRNG.

Mitigation if you suspect insufficient randomness

If you’ve already generated keys with potentially weak randomness, do not use them. Regenerate the keys using a strong random source. If the key has been used for signing, revoke it immediately.