Quantum resilience: locking down digital secrets long-term (Part 1)

Part 1: Symmetric and public-key cryptography. 

RSA, ECC and what is vulnerable against a quantum computer. 

 Cryptography is the art of making data obscure by converting a casual “Hello!” to something which is readable but not understandable like “ag2sk53b”. The idea is that it would be difficult to go backwards from “ag2sk53b” to “Hello!” even using a powerful computer without knowing a secret key. 

To go from “Hello!” to “ag2sk53b” requires a key which is supplied to the algorithm with “Hello!”. This process is called encryption. To go backwards from “ag2sk53b” to “Hello!” also requires a key. This process is called decryption. The original message is called “plaintext” and the encrypted message is called “cyphertext”. The key looks like a string of characters of a certain length or as a binary number.

When the keys for encryption and decryption are the same, it is called symmetric cryptography which is fast and compact. It is omnipresent for exchanging data at the Internet, and can be found e g in the Transport Layer Security (TLS) protocol. An example of a modern symmetric cryptography algorithm is the Advanced Encryption Standard (AES). Symmetric cryptography is in principle safe against an attack from a quantum computer. 

A challenge with the symmetric cryptography is that the key is the same for encryption and decryption, and the communication parties need to exchange the key in a secure way before they can start communicating securely. This can be solved using another type of encryption which uses different keys for encryption and decryption. This type of cryptography is called public-key or asymmetric because the keys, called private and public keys, are not the same. The data encrypted with a public key can only be decrypted with a private key, so one can send own public key to the communication partners or simply publish it on a website. The communication partner can do the same with another public-private key pair to communicate securely in return. 

The size of keys and resulting cyphertext for public-key cryptography are as a rule larger than those of the symmetric cryptography, so a more efficient way for secure communication is to use the bulkier public-key method to exchange the secret key for a lighter and faster symmetric encryption and then communicate securely using the symmetric encryption/decryption. The procedure of exchanging the keys is called the “key exchange”. 

Another application of public-key cryptography is digital signatures, where an algorithm can produce a message footprint called a signature using a private key. The message with its signature can be verified for integrity using a public key.  

Examples of widely-used of public-key cryptographic algorithms include Rivest–Shamir–Adleman (RSA) algorithm and elliptic curve cryptography (ECC).  These two algorithms are also omnipresent on the Internet and used for the key exchange and digital signing.  RSA and ECC algorithms are not safe against a quantum computer, and it applies to all data exchange which uses those two algorithms, whether they are used to encrypt data, for key exchange (for example the Diffie-Hellmann key exchange) or to digitally sign documents or verify identity. 

Why RSA and ECC are vulnerable, how safe are our digital secrets today,  and why a quantum computer can be a threat will be addressed in Part 2 of the blog.