The RSA Homonym
We are RSA®, the security company, also known as RSA Security, a Dell Technologies company. We offer software solutions to mitigate security risk in this ever-changing digital world and economy. We also organize one of the largest security conferences in the world: RSA Conference. Our 2020 edition is just about to start.
There is also RSA, the algorithm. It is used to encrypt and protect data in a wide range of applications, from data in transit to data at rest. The algorithm can be used to encrypt or generate digital signatures. That digital signature can then be incorporated within a simple file, and some other metadata, to create what is an RSA certificate. The RSA algorithm is among the most widely used encryption and signature algorithms in the world, if not the most widely used.
Did RSA – the company – invent RSA – the algorithm? No. Ron Rivest, Adi Shamir and Leonard Adleman invented the RSA algorithm in the late '70s while at Massachusetts Institute of Technology (MIT). The subsequent patent for the algorithm was issued to MIT on Sept. 20, 1983 and licensed exclusively to RSA Security. The patent expired in September 2000.
Over the years, there has been much confusion between RSA Security and RSA the algorithm, including claims that "RSA certificates" or "RSA keys" are vulnerable. It is important to clarify that vulnerability claims are not about RSA Security nor are they about the RSA certificates issued in RSA Security products, but rather about poorly implemented cryptography resulting in insecure fundamental elements of the RSA algorithm.
That confusion, between the "RSAs", worries people. It's ok. We are here to help.
Randomness and the RSA Algorithm
Entropy is randomness used by cryptographic systems to generate cryptographic keys. Good entropy is necessary to generate strong keys.
A recent story highlights the results of using bad entropy on the RSA key generation itself. The report concludes that "device manufacturers, website and network administrators, and the public at large [need] to consider security, and especially secure random number generation, as a paramount requirement of any connected system". The fact of the matter is, this has been known for decades and is the foundation of secure cryptographic systems. However, the importance of good entropy and randomness in secure cryptographic systems to be explained.
The effectiveness of the RSA algorithm relies on, among other things, the ability to randomly select two large prime numbers that we call p and q.
A prime number is one that can only be divided evenly by 1 and itself, like 19.
But what exactly is a large number? Let's see...
A 32-bit number is a number represented using 32 binary digits. Its maximum value is (232 - 1) = 4294967295. That number contains 10 decimal digits.
A 2048-bit number is a number represented using 2048 bits. Its maximum value is (22048 - 1) = ~3.23e+616. That number is too long to be written here and contains 617 digits.
For the purpose of this example a "large number" is a number that contains 617 digits.
If there are 50 Million known primes for a 10-digit number, how many primes are there for numbers made of 617 digits? I don't have the answer, but there are a lot of possibilities. Now, randomly pick two primes in this immense pool of prime numbers. These are your p and q. The probability of randomly picking the same p or q repeatedly is very unlikely, unless what you believed to be random is not actually random.
In computer programming, good randomness comes from algorithms known as Deterministic Random Bit Generators (DRBGs). These algorithms are thoroughly reviewed by security researchers, mathematicians, universities, etc., as well as the National Institute of Standards and Technology (NIST). NIST adds approved DRBGs to a whitelist, requiring US and Canadian Federal Agencies to use these whitelisted DRBGs.
DRBGs require input data, referred to as entropy seed, which comes from a source (or sources) generating events that don't present any sign of pattern similarity or predictability. If the source meets these simple criteria, it is known to be a "good entropy source". Easier said than done, though. We'll come back to that later. When using a good entropy source to seed a DRBG, the output produced by the DRBG can be considered cryptographically safe random. This cryptographically safe random can be used to generate encryption keys, or randomly selecting p and q. If the seed to your DRBG is always the same, p and q will always be the same, resulting in the same RSA key. If the seed to your DRBG can be predicted, then p and q can be predicted, making it easy to calculate your RSA key that ought to be kept private.
As said earlier, it is easier said than done to have a source that shows no signs of pattern similarity or predictability. When one million webcams are built the same way, with the same cheap components to keep the price down, how can one webcam be different enough from the next one and produce different entropy? If they can't produce different entropy, it means those webcams will seed the same predictable entropy data to the DRBG, generating the same output, hence generating identical and predictable random numbers. Actually, "predictable numbers" leading to predictable or identical RSA keys is the topic of the recent article mentioned earlier.
The RSA Algorithm Requires Good Entropy; RSA Products Use Good Entropy
What is a good source of entropy then? As of today, a good source of entropy is one that will pass the NIST Entropy Assessment test. NIST built a test suite that will run statistical tests on your entropy source. The source code of this tool is available at https://github.com/usnistgov/SP800-90B_EntropyAssessment. If a source passes the test, it is considered a good source.
How about RSA Security products? What entropy sources do they use? This is a really good question. RSA Security products use a variety of cryptographic modules, including but not limited to RSA BSAFE® Crypto-C Micro Edition (Crypto-C ME) that has its entropy source tested against NIST's tests), and RSA BSAFE Crypto-J (Crypto-J) that relies on the Java Virtual Machine it runs in for entropy. As software cryptographic modules, the BSAFE toolkits must rely on what is available on the system to gather entropy. In Crypto-C ME, all noise sources are individually tested with NIST's tool. If a source does not generate enough entropy, we remove it. If we were to rely on a single source, this would become a single point of failure. Should this source become bad, or predictable, or compromised, the whole security falls apart. When multiple good entropy sources are combined and conditioned before being seeded to the DRBG, the risk of having your DRBG compromised is reduced. Crypto-C ME will not generate DRBG output unless sufficient entropy has been obtained to seed the DRBG fully. In other words, Crypto-C ME should never generate weak keys. Crypto-J will, by default, force a reseeding using the JVM's implementation-specific entropy source to ensure a random is created with sufficient entropy for the requested DRBG algorithm.
Not only do BSAFE toolkits ensure they have good entropy on all supported platforms, they also provide DRBG algorithms that have been approved and validated by NIST. Application developers can have peace of mind when generating RSA keys, or any secure random number, when BSAFE toolkits are used correctly.
Remember, RSA (the company) and RSA (the algorithm) are homonyms. Please don't get them confused.