Algorithms, key size and digital certificates


On the surface the digital certificates are not complicated — a third-party (a certificate authority) verifies some evidence and produces a piece of identification that can be presented at a later date to prove that the verification has taken place.

As is usually the case when we look a little deeper things are not that simple. In the this case we have to care about a few other things, for example what are the qualifications of the third-party, what are their practices and what cryptographic algorithms did they use to produce the digital certificate?

As an administrator using digital certificates like in the case of SSL these things also can have impact on your operational environment – by using a certificate from a certificate authority you take dependencies on their practices and operational environment.

This is especially true when it comes to decisions relating to what cryptographic algorithms and key lengths are accepted and used by that third-party.

Thankfully you do not need to be a cryptographer to make good decisions on this topic, first we need to start with an understanding of the history, future and then considerations.


In recent history the industry has relied on two algorithms, the first being an encryption algorithm called RSA the second being a hash algorithm called SHA-1. Both of which have are considered weaker now due to advances in cryptanalysis.

RSA’s strength and performance is based on the size of the key used with it, the larger the key the stronger and slower it is.

These advances in cryptanalysis have driven the increase in key size used with this algorithm which in turn has increased the amount of computing power necessary to maintain the same effective strength.

The problem with this is that that every time we double the size of an RSA key the decryption operations with that key become 6-7 times slower.

As a result as of all of this as of January 2011 trustworthy Certificate Authorities have aimed to comply with NIST (National Institute of Standards and Technology) recommendations by ensuring certificates all new RSA certificates have keys of 2048 bits in length or longer.

Unfortunately this ever increasing key size game cannot continue forever, especially if we ever intend do see SSL make up the majority of traffic on the internet – the computational costs are simply too great.

That takes us to SHA-1, hash algorithms take a variable amount of input and reduce it to a typically shorter and fixed length output the goal of which being to provide a unique identifier for that input. The important thing to understand is that hash algorithms are always susceptible to collisions and the advances in the cryptanalysis have made it more likely that such a collision can be made.

The problem here is that there is no parameter to tweak that makes this problem harder for an attacker, the only way to address this issue is to change to a stronger algorithm to produce the hash.


For the last decade or so there has been slow and steady movement towards using two new algorithms to address these advances — SHA-2 and ECC.

ECC has the potential for significant performance benefits over RSA without reducing security and SHA-2 has three versions each with progressively longer lengths which help it both address the current risks and give it some longevity.


Our goal in configuring SSL is enabling users to communicate with us securely; to accomplish this goal we need to be able to do this with the fewest hassles, lowest costs and comply with any associated standards.

Interoperability is the key that ensures the fewest hassles — if it was not for this we would simply switch to these new algorithms and be done with it. As is normally the case when it comes to security this is where Windows XP rears its ugly head, SHA-2 was added to XP in Windows XP Service Pack 2 and ECC in Windows Vista.

These facts set the adoption clock for these new algorithms; if you care about XP (about 30% of the Internet today) you can’t adopt ECC and SHA-2 in full for about 5 years.

This leaves us with RSA 2048 and SHA-1 which thankfully is broadly considered sufficient for the next decade.

Performance is always a concern as well — a RSA 2048-bit RSA certificate used in SSL will result in around a 10% CPU overhead not huge but something to keep in mind.

As mentioned previously we can’t forget compliance — whether it is the Payment Card Industry / Data Security Standards (PCI/DSS), Federal Information Processing Standards (FIPS) 140-2 or some other set of criteria you need to meet this always needs to be considered.


The decision of what algorithm’s and key lengths to use in your digital certificates is dependent on a number of factors including security, interoperability, performance and compliance. Each situation may require a different trade-off to be made however a rule of thumb if you stick with SHA-2 and RSA 2048-bit certificates and keys you should be fine for now.



[1]   BlueKrypt Cryptographic Key Length Recommendations

[2]   Recommendation for Key Management, Special Publication 800-57 Part 1 Rev. 3, NIST, 05/2011

[3]   Fact Sheet Suite B Cryptography, NSA, 11/2010

[4]   Worldwide Operating System Statistics, Stat Counter, 9/2012

[5]   RSA Algorithm, Wikipedia

[6]   RSA Key Lengths, Javamex

[7]   ECC Algorithm, Wikipedia

[8]   Performance Analysis of Elliptic Curve Cryptography for SSL, Sun

[9]   Using ECC keys in X509 certificates, UnmitigatedRisk

[10] Using SHA2 based signatures in X509 certificates, UnmitigatedRisk

[11]Payment Card Industry / Data Security Standards – PCI

[12]Federal Information Processing Standards 140-2 – NIST

Leave a Reply

Your email address will not be published. Required fields are marked *