Cryptography is a cornerstone of modern computing to enforce security and reliability for various digital applications. Unfortunately, quantum computers are a realistic threat that can disturb this peace. In this tutorial, we will go over some basics of cryptography and then dive into its vulnerabilities to quantum computing.

For a higher level summary and a recommended course of action please refer to our Executive Summary on Cryptography.

DISCLAIMER: This is information is provided for educational and informational purposes only. By using this material, you acknowledge and agree to assume full responsibility for the risks and damages that may arise from your actions. HiDi Corporation is not responsible or liable for any errors, omissions, or outcomes from the use of this information. Always consult with a qualified professional for your specific cryptographic needs.

Traces of cryptography can be seen throughout history. The Rosetta Stone translation can be viewed as an ancient example of a cipher; before its discovery by Napoleon’s armies in 1799 the lost language of ancient Egyptian hieroglyphs from Before Common Era was undecipherable. The contents of the yet older Indus script remain elusive without such a translation.

The legendary story of the Enigma cipher used by the Axis in WWII and its decryption by the Allies using the Bombe machine evokes parallels to developments in quantum computing and exploitable vulnerabilities in modern cryptography. Even though the Allies cracked the Enigma cipher, they strategically ignored intercepted messages to avoid the Axis from suspecting that their communications were compromised. This is food for thought about potential quantum technology capabilities kept hidden from the public.

Cryptography 101

Cryptography has 4 core tasks: confidentiality, integrity, authentication, and non-repudiation.

The 4 Cryptography Tasks

These tasks can be carried out through a combination of 3 primitives: hash functions, symmetric encryption, and asymmetric encryption. The table below summarizes the keys, algorithms, useful features, what makes them secure, and their level of vulnerability to quantum computers.

The 3 Cryptography Primitives

Let’s investigate each of these primitives in detail.

Hash Functions

A hash function takes any arbitrary data and computes a fixed-length string of bits (often called a hash, hashstring, or checksum) which appears to be completely random with no correlation to the input data. NIST standards for hashing are almost universally used now, with the SHA-2 standard being the most widely used.

As an example, you can compute the SHA256 checksum (256 bits) for “Hello world!” by typing into a Linux bash terminal:

>>> echo 'Hello world!' | sha256
0ba904eae8773b70c75333db4de2f3ac45a8ad4ddba1b242f0b3cfc199391dd8

or for even stricter checks compute the SHA512 hash (512 bits):

>>> echo 'Hello world!' | sha512
32c07a0b3a3fd0dd8f28021b4eea1c19d871f4586316b394124f3c99fb68e59579e05039c3bd9aab9841214f1c132f7666eb8800f14be8b9b091a7dba32bfe6f

For a more useful scenario, you may want to verify the contents of a legal document. The SHA256 checksum for the .txt version of the Declaration of Independence on Project Gutenberg is

8fc7483413518ecf182d982a2e61289894e7fa3ccb1fa3d1db4c1be55debb1f0

Perhaps you want to verify that your software was not corrupted during the download process, or a copy of software has not been tampered to inject malicious code. Ubuntu provides various checksums to verify their installation files.

Since hash functions can map any arbitrarily long data to a fixed length bitstring two different inputs may produce the same checksum, causing a hash collision. For a well-designed hashing algorithm it is both astronomically unlikely for a collision to accidentally happen, and impossibly difficult to prepare a different input (pre-image) to match a checksum.

While hash functions are quite secure, they are also predictable in some scenarios. As an example, “123456” and “password” are very common passwords, which produce the hashes

>>> echo "123456" | sha256
e150a1ec81e8e93e1eae2c3a77e66ec6dbd6a3b460f89c1d08aecf422ee401a0
>>> echo "password" | sha256
6b3a55e0261b0304143f805a24924d0c1c44524821305f31d9277843b8a10f4e

Precomputed hashes of common passwords, a.k.a. rainbow tables, are commonly used to attack such accounts. These issues can be prevented by using good hashing practices for passwords like salting, peppering, memory-hard algorithms, etc.

Note: SHA-1 has been deprecated and the newer SHA-3 is (as of yet) less adopted.

Symmetric Key Encryption

Symmetric key encryption is a more familiar process of encrypting data. A single secret key is used to scramble data into ciphertext, and the same key can unscramble it back to plaintext. The de facto standard for symmetric key encryption is AES as described by NIST. The official variations are AES-128, AES-192, and AES-256, which have key lengths of 128, 192, and 256 bits respectively.

A symmetric key encryption scheme must possess a few desirable properties:

• Plaintext must not bear any resemblance to ciphertext
• Flipping any plaintext/ciphertext bit should flip on average half the bits in ciphertext/plaintext (diffusion)
• Each bit of the ciphertext should depend on multiple bits of the key (confusion)
• Encryption/decryption should be fast

AES is a block cipher, meaning it transforms 128 bits of plaintext data into 128 bits of ciphertext using the chosen key. Naively implementing a block cipher can lead to compromised security! A famous example is the AES-ECB (Electronic Code Book) Penguin weakness, which we have recreated using the HiDi logo:

The image on the right retains some details about the outline of the logo. This phenomenon occurs because 128 bits of white colored pixels in a row (plaintext) produce the same ciphertext (the repeated pattern that forms vertical stripes). Note how the barely visible faint blue circle below the logo is revealed!

Proper usage of the AES encryption involves using adding random nonces or using AES in GBC (Galois Block Counting) or CBC (Cipher Block Chaining) modes among many other techniques.

Asymmetric Key Encryption

Since symmetric key encryption requires establishment of (ideally unique) keys between every pair of parties who may wish to communicate, it is impractical for various tasks like communicating safely over the internet and insufficient for verifying a signature. Asymmetric encryption, also known as public key cryptography) expands the possibilities of cryptography by utilizing public and private keys.

The de facto standard algorithms for asymmetric key cryptography are RSA (Rivest-Shamir-Adleman) and ECDSA (Elliptic Curve Digital Signature Algorithm) and their Diffie Hellman key exchange counterparts. If you visit practically any website with your web browser you can view its HTTPS certificate and will see either RSA or ECDSA as the encryption algorithm.

RSA, ECDSA, and their Diffie Hellman key exchange counterparts are highly vulnerable to quantum computing attacks.

The best way to understand symmetric key protocols is using examples. We will go over three examples: encryption/decryption, signing/verifying, and establishing a shared key using (Diffie Hellman) key exchange.

Encryption and Decryption

Consider a scenario where you would like to send a private message to your friend over the internet. To successfully accomplish this, one may use a procedure as follows:

• Signal to your friend that you want to send a private message
• Your friend will generate a randomized public key and private key
• Your friend will send you the public key
• You will use the public key to encrypt your message
• You will send the encrypted message
• Your friend will decrypt the message using the private key

For this procedure to succeed, we must meet a few requirements:

• The message cannot be decrypted using the public key
• One cannot deduce the private key from the public key
• The encrypted message should be decryptable using only the private key
• The algorithm to realize this procedure must be decided upon

One may use the RSA or ECDSA algorithm to achieve this. Let’s walk through the RSA algorithm to see how this is done.

Encryption/Decryption with RSA

The first step in RSA (like any other asymmetric cryptography protocol) is to generate a randomized public and private key. RSA relies on the fact that it can be very difficult to factor large integers into their prime factors. In particular, RSA establishes security using a semiprime number, i.e. a number that is two prime numbers (besides one) multiplied by each other. There are some restrictions on which prime numbers can be selected, e.g. the prime numbers should be small, not close to each other, and not larger than a limit. Let’s assume prime numbers $p$ and $q$ are chosen to satisfy the requirements, we can compute the semiprime number:

and Euler’s totient (some implementations use Carmichael’s totient instead):

Note: Euler’s totient simply counts the number of integers that are prime to some number. Since $p$ and $q$ are prime numbers, they are only divisible by themselves:

and we can use this to count the number of integers that are prime to $p$ and $q$.

The next step is to pick a number e, the encryption exponent, which satisfies:

that is, e should be co-prime with $\phi(N)$.

Now a second number, $d$, the decryption exponent can be calculated by solving:

which can be done using the extended Euclidean algorithm.

Now all the ingredients to share the public key, encrypt, and decrypt are ready. The public key for this RSA scheme is the pair of numbers $(N,e)$. The private key is the number $d$.

Now let’s revisit the procedure to send and encrypted message, but using the RSA algorithm:

• You signal to your friend that you would like to send a private message
• Your friend generates (using randomization) a public key $(N,e)$ and a private key $d$
• Your friend send you the public key $(N,e)$
• You encrypt your message $M$ as the ciphertext $C=M^e \; \mathrm{mod} \; N$
• You send the ciphertext $C$ to your friend
• Your friend decrypts the ciphertext $C$ back to the message $M=C^d \; \mathrm{mod} \; N$

The security of this algorithm relies on the fact that factoring the number $N$ is difficult. Later we will see how this breaks down in the presence of fault-tolerant quantum computers.

Note that this procedure of encrypting and decrypting messages is using the generated keys is computationally intensive compared to symmetric key encryption.

Signing and Verifying

Consider a scenario where you require a non-repudiable digital signature, akin to someone’s signature on a paper document. This can be achieved using asymmetric key encryption too! A procedure for this goes as follows:

• The person signing the document should have a static public and private key pair associated with their identity
• The public key is published or provided upon request
• The person signing the document will compute the hash of the document and encrypt the hash with their private key, creating the signature
• The person verifying the signature will decrypt the signature using the public key and make sure it matches the hash of the document

Note how this requires reliably publishing and maintaining keys associated with an identity!

Signing and Verifying with ECDSA

Let’s dive into the details of Elliptic Curve Cryptography and apply these ideas to a Bitcoin transaction.

Key Exchange

Quantum Algorithms to Break Cryptography

Breaking Cryptography with Quantum Computers

Random number generation for keys. Quantum random number generation.