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 and show examples with code of how quantum computers can break certain types of cryptography.

This tutorial assumes familiarity with basic linear algebra, modular arithmetic, and symmetric/asymmetric cryptography concepts. Readers seeking higher level summary and a recommended course of action please can refer to our Executive Summary on Cryptography.

DISCLAIMER: This 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. Please consult HiDi Corporation directly for professional advice on your cryptographic security needs.

Traces of cryptography can be seen throughout history. The Rosetta Stone translation can be viewed as an ancient example of a cipher; ancient Egyptian hieroglyphs remained undeciphered until its discovery by Napoleon’s armies in 1799. 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 vulnerabilities of modern cryptography. When the Allies cracked the Enigma cipher, they strategically ignored intercepted messages to prevent the Axis from suspecting that their communications had been 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 three primitives: hash functions, symmetric encryption, and asymmetric encryption. The table below summarizes their operations, standard algorithms, useful features, what makes them secure, and their level of vulnerability to quantum computers.

The 3 Cryptography Primitives

	Hash Functions	Symmetric Key Encryption	Asymmetric Key Encryption
Keys	No keys	One secret key	Two keys: public and private
Algorithm	Compute a fixed-length hash string from arbitrary data	Encrypt-decrypt data between plaintext-ciphertext with a key	Establish security between two entities without a predetermined key
Useful Feature	Computation of the hash string is repeatable	Ciphertext bears no resemblance to plaintext	Various schemes to encrypt/decrypt, sign, or verify data
Security	Generating data to match a bitstring is infeasible	Guessing the key from plaintext and corresponding ciphertext is infeasible	Decrypting or signing data without the private key is infeasible
Quantum Vulnerability	Low	Low	High

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 it 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 prohibitively expensive 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 uses a single secret key to scramble data into ciphertext, the same key to 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, i.e., it transforms blocks of 128 plaintext bits into 128 ciphertext bits using the chosen key. Naively implementing a block cipher leads to compromised security! A famous example is the AES-ECB (Electronic Code Book) Penguin weakness, which we have recreated for the HiDi logo:

The second image retains details of the logo outline. 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 adding a random nonce (number used once) or using AES in GCM (Galois/Counter Mode) or CBC (Cipher Block Chaining) modes among many other techniques.

Asymmetric Key Encryption

Since symmetric key encryption requires establishing (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 (a.k.a., 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.

Asymmetric cryptography uses trapdoor functions, i.e., functions that are easy to compute one way, but difficult to invert without a secret key. This allows encryption of information using a publicly known trapdoor function (interchangeable with the public key), which can then only be decoded using the private key.

The best way to understand asymmetric 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
• Use the public key to encrypt your message (put it through a trapdoor function)
• 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 and parameters for this procedure must be chosen in advance.

RSA or ECDSA are typically used 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 large, not close to each other, and randomly chosen. If prime numbers $p$ and $q$ are chosen to satisfy the requirements, we can compute the semiprime number:

and Euler’s totient:

> Note: Euler’s totient

Euler’s totient $\phi(N)$ simply counts the number of integers that are coprime to $N$. Since $p$ and $q$ are prime numbers, they are only divisible by themselves: $\phi(p) = p-1, \; \phi(q) = q-1$. We can use this to count the number of integers that are coprime to $p\times q$.

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

i.e., $e$ should be co-prime with $\phi(N)$. One may easily check this using Euclid’s algorithm by ensuring that $\mathrm{gcd}(e,\phi(N))=1$.

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 encrypted message-sending procedure, this time using the RSA algorithm:

• 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 sends you the public key $(N,e)$
• Encrypt your message $M$ using the trapdoor function as the ciphertext $C=M^e \; \mathrm{mod} \; N$
• 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 with the existence of fault-tolerant quantum computers.

We can work out a small example of the algorithm by sending “Hello Friend!” encrypted with RSA. In our toy scheme, we will encode each character using RSA (in real RSA implementations padding and various other measures are used for security).

Using standard ASCII codes for each character, the string “Hello World!” in integer representation is

“72 101 108 108 111 32 87 111 114 108 100 33”

and requires a minimum of 7 bits to encode as-is. We can use the 7-bit semiprime number $N=129=3\times43$ (10000001 in binary) with $\phi(N)=2\times42=84$ for our RSA scheme. (Note that this is a bad choice since 3 and 43 are not close to each other!)

Picking $e=5$ to be coprime with $\phi(N)$, we can solve $5\times d \equiv 1 \; \mathrm{mod} \; \phi(N)$ for $d=17$. Now we can encrypt our message as $C = M^e \; \mod \; N$ as

“63 38 39 39 24 113 87 24 48 39 109 18”

which reads “?&”qW0’m” in ASCII. If we decrypt the message using $M= C^d \; \mathrm{mod} \; N$ we get

“72 101 108 108 111 32 87 111 114 108 100 33”

which was the original message.

RSA operations are computationally intensive compared to symmetric encryption. In practice, asymmetric cryptography is only used during the initial handshake to securely exchange a session key. All subsequent data is encrypted using fast symmetric algorithms like AES.

Signing and Verifying

Consider a scenario where you require a non-repudiable digital signature, akin to ink signatures on paper documents. 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 a hash of the document and sign (encrypt) the hash with their private key, creating the signature
• The person verifying the signature will verify (decrypt) the signature using the public key information 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

As the name suggests, ECDSA revolves around the mathematics of elliptic curves, which are used to create the trapdoor function. Unlike RSA, elliptic curve cryptography is not designed to encrypt/decrypt data directly, but is designed for key exchange and signing/verifying data. Using the equation for an elliptic curve,

where the parameters $a,b$ are integers, we can plot the integer values of x. Note how the y coordinates are not necessarily integers. This will be resolved later by performing a modulo operation.

> Note: Projective coordinates

Although we have plotted this curve in Cartesian coordinates, the math for elliptic curve cryptography is done in projective coordinates. Basically this means that one more dimension ($z$) is hidden in the projected equation and plot above. The third dimension can be reintroduced to recover the original equation. The rules for projective coordinates are different from Cartesian coordinates. As an example, parallel lines never intersect in Cartesian coordinates, but in projective coordinates they do intersect!

Elliptic curves are symmetric about the x-axis. What’s also interesting to note is that if a line is drawn between any two points on the top (or bottom) half of the curve, it is bound to intersect at a third point somewhere on the top or bottom half of the curve (a tangent intersection counts as two points!). This fact will be used to define the plus operation for a pair of points $P$,$Q$ as $P + Q$. For a tangent point, this is simply $P + P$ and defines the dot operation $P+P=2\cdot P$.

We will also define the dot operation on a point $G$ (uppercase) performed d times (lowercase) as $d \cdot G$. We may visualize the dot operation on the point $P$ as follows:

Some issues with performing these operations on computers are:

• Points on the curve may end up being very far away from where we started
• $y$ values are not integers.

These can lead to problems on computers like overflow and floating point rounding errors. An elegant solution is to simply apply a modulo operation, i.e., $d \cdot G \; \mathrm{mod} \; n$, where $n$ is the prime order of the curve. More specifically, now the equivalent mathematical steps are:

Given arbitrary $d$ and $P$, $d \cdot P$ can be computed efficiently using the double and add algorithm (which uses the binary representation $d=b_n \dots b_1 b_0=\sum_i{b_i 2^{i}}$ to compute $d \cdot P = \sum_i{ ( b_i 2^{i} \cdot P ) }$)

This bounds the $x$– and $y$-coordinates to manageable integer sizes. The effect of this modulo operation can be visualized for the addition and dot operations on the curve $y^2 = x^3 -4x + 4b$ with a base modulus of $p=17$:

At this point we have made a major digression; although the elliptic curves plotted earlier above serve as visual tools for the operations performed in elliptic curve cryptography, after applying modular operations the visual resemblance disappears (except the horizontal symmetry of all the points on the curve). However, there remains a mathematical connection between elliptic curves over $\mathbb{R}$ and $\mathbb{F}_p$ rooted in group theory.

Given a point $(x,y)=d \cdot G$ with its generator point $G$, it is extremely difficult to figure out $d$. This is known as the discrete logarithm problem, i.e., solve $g^d \equiv h \; \mathrm{mod} \; p$ for $d$, and is hard for classical computers (we will see later that quantum computers excel at it). However, given $d$ and $G$, it is relatively easy to compute $(x,y)=d \cdot G$. This procedure forms our trapdoor function! As an example, the following plot shows the first 2000 points on the P-256 curve. To find $d$ one would have to start from the original point and compute dot operations on it until a matching point is found. This is difficult for arbitrarily large $d$ since $d$ can go up to $2^{256}-1$.

With this information, let’s dive into the practical mechanics of using elliptic curves for cryptography.

The first step is to pick a standardized elliptic curve, e.g., the NIST P-256 curve. This will establish the specific curve used by both parties and establishes the base point and prime order for the modulo operation. Now a random integer will be picked as $d \in [1,n-1]$, which will serve as the private key. The public key will be the $(x,y)$ coordinates of a point on the curve:

This information is used to create the trapdoor function; given $G$ and $Q$, it is extremely difficult to figure out the number of times $d$ the dot operation has been performed on point $G$ to generate $Q$.

To use the private key, it is important to generate a random nonce (“number used once”) $k$. Using the private key without randomly generated nonces makes the encryption vulnerable.

We can now use this to generate the coordinate:

To sign a document, the signer will first compute the hash of the document (e.g., using SHA). The hash $h$ will then be signed (encrypted) using ECDSA by solving the following modular multiplicative inverse problem (using the Extended Euclidean Algorithm) for $s$.

We can now share the signature $s$ and signature component $r$ (along with details of the hashing algorithm, choice of elliptic curve and prime order $n$, and initial point $G$). The receiver can now authenticate the document by verifying (decrypting) the signature through the following procedure:

• Run the document through the hashing algorithm to get the hash $h$
• Solve $w \cdot s \equiv 1 \; \mathrm{mod} \; n$ for $w$ using the extended Euclidean algorithm
• Compute $u_1 = h \cdot w \; \mathrm{mod} \; n$ and $u_2 = r \cdot w \; \mathrm{mod} \; n$
• Compute $(x_1 , y_1 ) = (u_1 \cdot G) + (u_2 \cdot Q)$
• $v=x_1 \; \mathrm{mod} \; n$
• Verify that $v == r$

One may wonder why one should go through such a complicated process in lieu of RSA encryption. The simple answer is that:

• Keys for elliptic curves are shorter
• Elliptic curve computations are faster

These features come at the expense of some trade-offs:

• There are no rigorous proofs guaranteeing the security of elliptic curves
• Some curves may be easily deciphered
• The origin of a curve may be questionable due to the possibility of backdoors designed by the developers

In summary, elliptic curves may be desirable in situations where key length and performance considerations outweigh potential security flaws.

This algorithm’s security relies on the fact that finding the private key $d$ from the public key information $Q,G,n$, and signature component $r$ is difficult. Later we will see how this breaks down in the presence of fault-tolerant quantum computers. As a final remark, many major cryptocurrencies use ECDSA for signing transactions, making them vulnerable in the post-fault-tolerant quantum computing era.

Key Exchange

Prime numbers and elliptic curves can be used to exchange keys over an unsecured channel like the internet too. The two ubiquitous flavors of key exchange protocols using integers and elliptic curves are known as Diffie-Hellman (DH) and Elliptic Curve Diffie-Hellman (ECDH) respectively.

Diffie-Hellman key exchange protocols rely on trapdoor functions to establish a shared secret key. Since we have already covered factoring and elliptic curve based cryptographic techniques, the animation below summarizes a key exchange procedure over HTTPS when connecting to a bank’s website. Both RSA and ECC variants use the same procedure. You can use your web browser to inspect the HTTPS certificate of your bank’s website to get the RSA or ECDSA public key information.

Quantum Algorithms to Break Cryptography

Now that we have reviewed all relevant cryptographic protocols, we will investigate how quantum computers can break their security. In the following sections we will use elementary quantum computing concepts like bras, kets, quantum gates, and quantum Fourier transforms. One may refer to any quantum computing textbook or learning material for these topics.

Classical cryptography relies on mathematical problems that are hard for traditional computers. Quantum computers allow speedups for some specific problems. The two relevant seminal quantum algorithms are Shor’s algorithm (1994) and Grover’s algorithm (1996). Grover’s algorithm weakens the security of hashing and symmetric key encryption, while Shor’s algorithm effectively breaks factoring and elliptic curve based asymmetric cryptography.

The reason behind the effectiveness of Shor’s algorithm is that both factoring and the discrete logarithm problem (the trapdoor function for elliptic curve cryptography) are equivalent to an Abelian hidden subgroup problem, for which quantum computers have an exponential speedup. On the other hand, Grover’s algorithm is an unstructured database search algorithm for which quantum computers admit a quadratic speedup.

While these two results are purely theoretical, we will dive deeper into how pragmatic an implementation of these algorithms can be. We can begin with the main statements of these two quantum algorithms.

Grover’s Algorithm (simplified statement):

Let $N=2^n$ and let $f: \{0,1\}^n \rightarrow \{0,1\}$ be a Boolean function with exactly $k \geq 1$ inputs with $f(x)=1$. Given an $(n+1)$-qubit quantum circuit $U_f$ that maps $|x\rangle|y\rangle \rightarrow |x\rangle |y \oplus f(x)\rangle$, there exists a quantum algorithm that, after $\mathcal{O}(\sqrt{N/k})$ applications of $U_f$, outputs a string $x$ with $f(x)=1$ with probability $2/3$ using $\mathcal{O}(n)$ qubits.

Let’s break down this statement piece by piece. Later we will see how this applies to AES and SHA.

• $N$ is the total number of possible inputs, and they are represented using $n$ bits
• $k$ is the total number of input-output pairs that satisfy our search requirements
• The $(n+1)$-qubit quantum circuit transforms the input to the output, and also “marks” an ancilla qubit if the output is among the input-output pairs we seek
• If we know the procedure that maps an input to the output, and are able to construct a circuit $U’_f$ for it, constructing $U_f$ is rather straightforward
• If we are able to construct $U_f$, the rest of the algorithm is “plug-and-play”, i.e., we need not concern ourselves with constructing circuits beyond this point or analyzing the details of the algorithm
• Classically searching all $N$ input-output pairs requires $\mathcal{O}(N)$ operations, which quantumly requires $\mathcal{O}(\sqrt{N})$ operations

For AES the task would be to find the key that matches plaintext-ciphertext pairs to each other. Without these pairs, Grover’s algorithm is not directly applicable. Since AES-128 and AES-256 use 128 and 256 bits for encryption, $n=128$ and $n=256$ respectively. The key collisions, i.e., a particular key mapping a certain plaintext to the same ciphertext, are very rare for AES-128, and every plaintext-ciphertext pair will on average have $k=1$ keys to satisfy the mapping. For AES-256, this may not be the case. In fact, we expect $k=2^{128}$ possible keys corresponding to a plaintext-ciphertext pair. This can be alleviated by matching two pairs of plaintext-ciphertext data, which brings the average number of keys back down to $k=1$. Note that the (incorrect) colliding keys are practically guaranteed to fail to decrypt the rest of the data correctly.

Putting aside these considerations, let’s analyze the simplest case: AES-128 with one plaintext-ciphertext pair. This will require $\mathcal{O}(\sqrt{N/k})=\mathcal{O}(2^{64}) \approx \mathcal{O}(10^{19})$ (sequential) operations on a quantum computer. Without even considering the cost of implementing the circuit and the additional overheads arising from error correction cycles on quantum computers, this is well beyond the reach of near-term and future error-corrected quantum computers even if they were clocked at 1 GHz (which is also well beyond the sub-MHz CLOPS on current superconducting quantum processors). Simple back-of-the-envelope estimates place this on impractical if not impossible timescales.

We can make similar arguments for SHA. One way of attacking SHA security is to append dummy bits to a forged document so that its hash matches that of an original document (this is known as a preimage attack). SHA-256 and SHA-512 process data in 512 and 1024 bit blocks respectively. This means that to forge a 256 bit hash (for SHA256) a search over $N=2^{256}$ potential inputs is needed. Using the same arguments, we can see how this is infeasible.

In summary, the general rule of thumb for securing AES and SHA against quantum computing attacks is to simply double key lengths and hash sizes.

Shor’s Algorithms (simplified statements):

Factoring: Let $N$ be an odd composite number. There exists a quantum algorithm that outputs a nontrivial factor of $N$ with probability $2/3$ using $\mathcal{O}(\log^3 N)$ elementary quantum gates.

Discrete Logarithm Problem: Given a prime $p$, a generator $g$ of a subgroup of $\mathbb{Z}^\times_p$ (the multiplicative group of integers modulo $p$ for a prime $p$, $\{1,2,3,\dots,p-1\}$), and a value $g^x \equiv h\; \mathrm{mod} \; p$ for some unknown $x$, there exists a quantum algorithm that recovers $x=\log_g{h}$ with probability $2/3$ using $\mathcal{O}(\log^3 N)$ quantum gates.

The connections to factoring and elliptic curve based cryptography are clear:

• The modulus $N$ (a semiprime composite number) used in RSA can easily be factored using Shor’s algorithm
• The discrete logarithm problem, which is the trapdoor function $g^x \equiv h \; \mathrm{mod} \; p$ in ECDSA, can easily be solved using Shor’s algorithm

Since the scaling arguments for Shor’s algorithm are more compelling, it requires a deeper dive!

Breaking RSA Cryptography using Shor’s Algorithm

To understand Shor’s algorithm we must first cover some elementary group theory to uncover the mathematical structure that makes RSA work. We will use this to reduce the factoring problem to an order finding problem. The order finding problem has an efficient quantum algorithm. We will later show how elliptic curve cryptography is vulnerable too by transforming it into a period finding problem.

We can begin with some definitions. Let’s define the group of integers modulo $N$ as $\mathbb{Z}_N$

This is a valid mathematical group under addition since it satisfies the closure, associativity, identity, and inverse requirements for the addition operation. However, if we consider multiplication we can immediately see that $0$ does not satisfy the multiplicative inverse requirement. In fact, if $N$ is not a prime number, any factors of $N$ will also violate this requirement. Therefore, if we are to define the multiplication operation we must consider a subgroup, the multiplicative group modulo $N$ defined as $\mathbb{Z}_N^\times$. We will consider two special cases of $\mathbb{Z}_N^\times$, for prime $N$ and semiprime $N$.

Multiplicative Group Modulo Prime $N$

$\mathbb{Z}_N^\times$ is relatively straightforward for prime $N$:

and $\lvert \mathbb{Z}_N^\times \rvert = N-1$.

> Example

For $N=7$ we get $\mathbb{Z}_N^\times= \{ 1,2,3,4,5,6 \}$.

$\mathbb{Z}_N^\times$ is a cyclic group. There exists at least one $g \in \mathbb{Z}_N^\times$ such that $g^0, g^1, \dots , g^{N-2}$ which enumerates all $N-1$ elements $a \in \mathbb{Z}_N^\times$.

Such an element $g$ is a generator (or primitive root) of $\mathbb{Z}_N^\times$. $\mathbb{Z}_N^\times$ has exactly $\phi(N-1)$ primitive roots where $\phi(\cdot)$ is Euler’s totient. Finding the primitive roots and the number of primitive roots is hard.

> Example

$\phi(7-1)=\phi(6)= (2-1)\times(3-1)=2$, meaning $\mathbb{Z}_N^\times$ has 2 primitive roots. We can try all $a\in\mathbb{Z}_N^\times$ to find that the primitive roots are $g\in \{3,5\}$.

By taking powers we see

$$3^0 \equiv 1$$

$$3^1\equiv3$$

$$3^2\equiv2 \; \mathrm{mod} \; 7$$

$$3^3\equiv6 \; \mathrm{mod} \; 7$$

$$3^4\equiv4 \; \mathrm{mod} \; 7$$

$$3^6\equiv1 \; \mathrm{mod} \; 7$$

which completes the cycle of going through all $a\in \mathbb{Z}_N^\times$.

For any $a \in \mathbb{Z}_N^\times$, $\mathrm{ord}(a)$ is defined as the order of $a$, which is the smallest integer $r$ satisfying

Primitive roots $g$ have $\mathrm{ord}(g)=N-1$ as we saw in the example above. $\mathrm{ord}(a)$ will always be a divisor of $\phi(N-1)$. For each divisor $d$ there is a corresponding subgroup with $\phi(d)$ elements with order $d$.

> Example

We can repeat the previous example for $a=2$.

By taking powers we see

$$2^0 \equiv 1$$

$$2^1\equiv2$$

$$2^2\equiv4 \; \mathrm{mod} \; 7$$

$$2^3\equiv1 \; \mathrm{mod} \; 7$$

which completes a cycle, meaning $r=3=\mathrm{ord}(2)$, which divides $N-1=6$. This subgroup has $\phi(3)=2$ elements of order 3. We can repeat the above for $a=4$ to verify that this subgroup is $\{2,4\}$. We can also predict that there are subgroups of size $\phi(d)$ elements corresponding to each divisor $d\in\{1,2,3,6\}$ of $N-1=6$.

For a primitive root $g$ every $a \in \mathbb{Z}_N^\times$ can be uniquely written as

for some $k \in \{0,1,2,\dots,N-2\}$. $k$ is the discrete logarithm of $a$ base $g$ modulo $N$. Computing $k$ given $a,g,N$ is difficult classically.

> Example

$a=2$ can be written as $2 \equiv 3^2 \; \mathrm{mod} \; 7$, solving the discrete logarithm problem for $k=2$. You can use the previous example cycling through $g=3$ as a lookup table for all other $a\in \mathbb{Z}_N^\times$.

For any $a \in \mathbb{Z}_N^\times$ if $a \equiv g^k$

For some arbitrary $a \in \mathbb{Z}_N^\times$ finding $\mathrm{ord}(a)$ is also difficult.

The subgroups through which $a^k$ cycle form subgroup lattices, i.e., they have an organized structure. Each divisor $d$ of $N-1$ corresponds to a a subgroup of size $d$ generated by taking powers $i\in \{ 1,2,\dots d \}$ as $g^{ \ (\frac{N-1}{d})^i} \; \mathrm{mod} \; N$. These subgroups nest according to divisibility.

> Example

Starting with a primitive root $g=3$, $\mathrm{ord}(g) = 6$ and the elements in the corresponding subgroup are $\{1,2,3,4,5,6\}$.

Now for $a=2$, $\mathrm{ord}(a)=3$ corresponding to the divisor $3$ of $N-1$ and the elements of the subgroup are $\{ 1,2,4 \}$.

For $6$, $\mathrm{ord}(a)=$ corresponding to the divisor $2$ of $N-1$ and the elements of the subgroup are $\{ 1,6 \}$.

Finally, for $a=1$, $\mathrm{ord}(a)=1$ corresponding to the divisor $1$ of $N-1$ and the elements of the subgroup are trivially $\{ 1 \}$.

Multiplicative Group Modulo Semiprime $N$

When $N=p \times q$ is semiprime, with distinct factors $p,q$, the mathematical structure we have seen so far changes. The group excludes more numbers besides $0$ (all factors of $N$ and their multiples are excluded):

and the size of the group is $\lvert \mathbb{Z}_N^\times \rvert= \phi(N)=(p-1)(q-1)$. Unlike the prime case, this group is not guaranteed to be cyclic (it may not have a prime root!). To study the structure of this group we must add a few more definitions.

Chinese Remainder Theorem Isomorphism: $\mathbb{Z}_N^\times \cong \mathbb{Z}_p^\times \times \mathbb{Z}_q^\times$

This implies that each $a \; \mathrm{mod} \; N$ corresponds uniquely to a pair $(a \; \mathrm{mod} \; p, a \; \mathrm{mod} \; q)$.

> Example

Consider the semiprime $N=15=3\times5$.

$$\mathbb{Z}_{15}^\times=\{1,2,4,7,8,11,13,14 \}$$

The isomorphism table for each $a\in \mathbb{Z}_N^\times$ can be constructed as

$a \; \mathrm{mod} \; 15$	$a \; \mathrm{mod} \; 3$	$a \; \mathrm{mod} \; 5$
1	1	1
2	2	2
4	1	4
7	1	2
8	2	3
11	2	1
13	1	3
14	2	4

The order of a pair in this “product” group is

> Example

$a \; \mathrm{mod} \; 15$	$(u,v)=$ $(a \; \mathrm{mod} \; 3 , a \; \mathrm{mod} \; 5 )$	$\mathrm{ord}_3(u)$	$\mathrm{ord}_5(v)$	$\mathrm{lcm} \; (\mathrm{ord}_3(u),\mathrm{ord}_5(v))$
1	(1,1)	1	1	1
2	(2,2)	2	4	4
4	(1,4)	1	2	2
7	(1,2)	1	4	4
8	(2,3)	2	4	4
11	(2,1)	2	1	2
13	(1,3)	1	4	4
14	(2,4)	2	2	2

As we see from the above table, the maximum order of this group is 4, which is smaller than the size of the group. Therefore, this group cannot be cyclic.

Carmichael Function: The maximum order of any $a \in \mathbb{Z}_N^\times$ is

This directly implies that for $\mathbb{Z}_N^\times$ to be cyclic, $p-1$ and $q-1$ must be coprime, which is rare!

A useful property is that $\lambda(N)$ divides $\phi(N)$, and they are equal iff $p-1$ and $q-1$ are coprime.

The subgroup structure differs from the prime case, where the primitive roots generated the entire group and the subgroups are nested according to divisors of the prime order. In the semiprime case, the subgroups are generated by pairs $a\in (u,v)$.

The order of the subgroups is $\mathrm{lcm} ( \mathrm{ord} (u), \mathrm{ord} (v))$. This implies that if $\mathrm{ord} (u), \mathrm{ord} (v)$ are coprime, the overall order is $\mathrm{ord} (u) \times \mathrm{ord} (v)$. Note also that $\mathrm{lcm} ( \mathrm{ord} (u), \mathrm{ord} (v))$ always divides $\phi(N)$, i.e., $\phi(N)$ is guaranteed to be some multiple $m$ of $\mathrm{ord} (a) \; \forall \; a\in \mathbb{Z}_N^\times$. Using the definition of the order of any $a\in \mathbb{Z}_N^\times$, we can arrive at:

We can now rearrange this equation to get

What this tells us is that the exponentiation of every $a\in \mathbb{Z}_N^\times$ is also modular with modulus $\phi(N)$. We can rephrase this as:

for every $w$ satisfying

In RSA we pick $w= e \times d$ such that $\mathrm{gcd}(e,\phi(N))=1$, i.e., $e$ and $\phi(N)$ are coprime. This effectively “scrambles” the message in such a way that $e$ does not accidentally share any common factor with $\phi(N)$ which could either only partially encrypt the message or not encrypt the message at all. After picking $e$ we are at liberty to solve

for any $d$ using the extended Euclidean algorithm. Now we are guaranteed to decrypt the message:

We note that up to this point we have only defined $M\in \mathbb{Z}_N^\times$. However, it turns out that this scheme successfully encrypts and decrypts messages for all $M \in \mathbb{Z}_N = \{ 0,1,2,\dots , N-1 \}$. Since a proof of this fact is not germane to the factoring problem it suffices to conclude our discussion of the properties of groups of integers at this point.

Reducing Factoring to Order Finding

From our previous discussion we have come to the conclusion that factoring semiprime numbers is difficult, and finding the order of the group $\mathbb{Z}_N^\times$ is also difficult. It can be shown that the factoring problem can be reduced to the order finding problem. We can start with a simple observation that a modular arithmetic equation of the form

can simply be read as “$N$ divides $M$“, or “$M$ is an integer multiple of $N$“. If somehow we have some factors of $M$, we could possibly factor $N$.

Let’s start with the first step: pick a random $a\in \mathbb{Z}_N$. We can test if $a$ also belongs to the subset $\mathbb{Z}_N^\times$ by computing $\mathrm{gcd} \; (a,N)$. By definition, if $\mathrm{gcd} \; (a,N) =1$, $a\in \mathbb{Z}_N^\times$. Otherwise, we have been incredibly lucky and found a factor of $N$.

Now that we know we have $a\in\mathbb{Z}_N^\times$ which is not a factor of $N$, let’s study the equation defining $r=\mathrm{ord} (a)$:

i.e., $N$ divides $a^r-1$. Therefore, $a^r-1$ must be composed of at least all the prime factors of $N$. Consider the case when $r$ is even: we can use the elementary “difference of squares” method to get:

This equation tells us that each prime factor of $N$ must divide either one of $a^{r/2}-1$ or $a^{r/2}+1$. Even now, it could be that all the prime factors of $N$ appear in either $a^{r/2}-1$ or $a^{r/2}+1$. However, if $a$ is randomly chosen, this is unlikely.

So we can test our factorization $(a^{r/2} -1) (a^{r/2} +1)$. We first note that for $a^{r/2} -1$:

This directly contradicts the definition of the order: $a^r\equiv 1 \; (\mathrm{mod} \; N)$ must be satisfied for the smallest integer $r$. This means that $(a^{r/2} -1) \not\equiv 0 \; (\mathrm{mod} \; N)$, i.e., $N$ cannot divide $a^{r/2}-1$, so it must be composed of some, but not all, factors of $N$. The shared factor could even be the trivial factor $1$.

Now consider the other factor $(a^{r/2} +1)$. If we test this factor and we see that

is satisfied, then $(a^{r/2} +1)$ contains all the prime factors of $N$ and $(a^{r/2} -1)$ is not necessarily a factor of $N$. However, if $(a^{r/2} +1) \not \equiv 0 \; \mathrm{mod} \; N$ then $(a^{r/2} -1)$ must contain nontrivial factors of $N$ and we will have successfully factored $N$. To find these factors we can simply check if $d = \mathrm{gcd}(a^{r/2}-1,N) \neq 1$, and $d$ will be a factor of $N$.

Note that both $a$ and $r$ may be large for $N$, making $a^{r/2}$ possibly an extremely large number. To avoid this issue we can use the basic modular arithmetic identity $\mathrm{gcd}(A,N) = \mathrm{gcd}(A \; \mathrm{mod} \; N,N)$ when implementing the algorithm on a computer.

Now we can rephrase our current problem. Given $N$, a composite number (product of distinct primes), and a randomly chosen $a\in\mathbb{Z}_N^\times$ what are the chances that

• $r= \mathrm{ord} \; (a)$ is even
• $a^{r/2} -1$ is a nontrivial factor of $N$

Theorem: Given an odd composite number $N$ and a randomly chosen $a\in\mathbb{Z}_N^\times$, the probability that $r=\mathrm{ord} \; (a)$ is even and $a^{r/2} -1$ is a nontrivial factor of $N$ is $1/2$.

We have now established that if we have an efficient method to find the order $r$ of some number a $a$ modulo $N$, we can efficiently factor $N$.

The Order Finding Problem

Now that we have reduced the factoring problem to an order finding problem, we can focus on solving the order finding problem efficiently. This is the last step before we see how a quantum computer can efficiently solve the order finding problem, effectively factoring integers and breaking RSA encryption. To ease our transition towards quantum computing, at this point we will start using the bra-ket notation for operations.

Let’s start our discussion with a simple modular multiplication operator $\mathcal{M}_a$

The operator simply transforms any ket vector $\lvert x \rangle$ to $|ax \; \mathrm{mod} \; N \rangle$ where $x,a,N$ are integers. For brevity we will now assume all ket labels to be modulo $N$, and all the operation of $\mathcal{M}_a$ on all kets $\lvert N\rangle , \lvert N+1 \rangle , \dots , \lvert \lceil \log_2 N \rceil \rangle$ to be equivalent to the identity, e.g., $\mathcal{M}_a \lvert N\rangle = \lvert N\rangle$.

We note that since this operation simply permutes the indices $\lvert x \rangle$, it is a permutation matrix and all permutation matrices are unitary matrices. This means that this operation can directly be implemented on a quantum computer.

Let’s consider a special ket composed of the subgroup of $\mathbb{Z}_N^\times$ through powers of $a$ cycle, i.e.,

Applying $\mathcal{M}_a$ to this ket gives us

which tells us that $\lvert \Psi_0\rangle$ is an eigenvector of $\mathcal{M}_a$ with eigenvalue $1$. Defining $\omega_r= e^{2 \pi i / r }$ helps us identify some more (but not all) eigenvectors of $\mathcal{M}_a$:

Consider the eigenvector $\lvert \Phi_1 \rangle$ with the associated eigenvalue $\omega_r^{1} = e^{2 \pi i/ r }$. If we had a procedure to accurately determine this eigenvalue, we can determine $r$. For any other $\lvert \Phi_j \rangle$ we will observe $\omega_r^{j} = e^{2 \pi i j/ r }$. This is the sort of task for which we shall use a quantum computer, more specifically the quantum phase estimation procedure. The quantum phase estimation procedure will provide us with estimates $j/r$ up to a chosen precision.

Before proceeding with the phase estimation procedure, let’s investigate the eigenstructure of $\mathcal{M}_a$ further. If we consider any arbitrary $\lvert \Phi_j \rangle$, we realize that we will have to estimate the eigenvalue $\omega_r^{j} = e^{2 \pi i j/ r }$ instead. Consider the case when $j$ has common factors with $r$. This can make it difficult to recover $r$ from $j/r$. In fact, the case $j=0$ tell us nothing about $r$.

If we were able to draw $j$ uniformly randomly, how likely is it to avoid these bad cases? It can be shown that we are guaranteed to sample a good case with probability $\frac{1}{\mathrm{poly} \; (\log N)}$. Therefore, if we were to test a recovered $r’$ and it does not successfully factor $N$, we can simply discard $r’$ and restart the algorithm and will still be able to efficiently factor $N$.

Although the probability $\frac{1}{\mathrm{poly} \; (\log N)}$ is satisfactory, a clever way to improve the performance of the algorithm is to draw several samples $v$ for $j \in \{ 0,1, \dots , r-1\}$ and then compute the least common multiple of the $v=j/r$ values we observe (note that we do not know $r$ and do not know how to draw the samples $v$ uniformly randomly yet). This will substantially improve the probability with a minimal overhead (typically 2-4 repetitions are sufficient)! Note that this was not used in Shor’s original paper and does not resolve the issue of drawing an unsatisfactory $a$.

We must address one last issue: how can we access an eigenvector $\lvert \Psi_j \rangle$ without computing the cycle or the order of the subgroup formed by $a$? It conveniently turns out that the sum of all $\lvert \Psi_j \rangle$ can be written as

and $\lvert 1 \rangle$ is a trivial ket vector for computations on a quantum computer. This effectively means that $\lvert 1 \rangle$ is a uniform superposition of all the eigenvectors we are interested in and we can uniformly randomly draw samples $v$. This completes all the required ingredients for moving on to the quantum phase estimation procedure.

Finding Orders using Quantum Phase Estimation

Since the quantum phase estimation procedure is a standard quantum algorithm, we will defer readers to excellent standard textbooks covering this topic (e.g., Chapter 5 of Nielsen and Chuang) for details. In our black box treatment of quantum phase estimation, we note that the inputs are:

• An eigenvector (or an approximation). In our case, we have a superposition of all eigenvectors of interest $\lvert \Psi_j \rangle$
• The desired precision for $j/r\in [0,1) \subset \mathbb{R}$ corresponding to an eigenvalue $e^{2\pi i j/r}$ in the number of bits $m$, where $j/r \approx 0.b_1 b_2 \dots b_m$ is its binary fraction approximation
• A controlled implementation of the unitary operator we want to estimate the eigenvalue of, in our case the operator $\mathcal{M}_a$, and its powers $\mathcal{M}_a^2, \mathcal{M}_a^4, \dots , \mathcal{M}_a^{2^{m-1}}.$ The implementation of the powers needs to be efficient since $m$ is not small in our case and depends on the number of digits in the semiprime number $N$.

For the efficient implementation of the powers of $\mathcal{M}_a$, we can simply exploit the fact that

and $c_k=a^{k}x \; \mathrm{mod} \; N$ is efficiently computable. Therefore, we can simply implement $\mathcal{M}_{c_k} \equiv \mathcal{M}_a^k$ instead!

How can one generate quantum circuits implementing $\mathcal{M}_a$ and various $\mathcal{M}_{c_k}$? The simple answer is that if a Boolean circuit is known to implement these operations, there is a straightforward procedure (outlined in Chapter 1 of Nielsen and Chuang) to translate it into the corresponding quantum circuit! There are well-known procedures for generating Boolean modular multiplication circuits, and some studies have also proposed optimized quantum implementations.

The only remaining problem is an airtight scheme to use the binary fraction approximation $0.b_1 b_2 \dots b_m$ to recover $j/r$ and eventually $r$. If we have a “good enough” binary fraction approximation, which is satisfied by choosing $m=2 \log_2(N) +1$, the continued fraction algorithm can be used to find the fraction $u/v$ closest to $0.b_1 b_2 \dots b_m$ where $u,v \in \{ 0, 1, \dots , N-1 \}$. This fraction $u/v$ will be one of the possible values of $j/r$. By repeating this a few times and (optionally) computing the least common multiple of the various $r/j$ values we will recover the prime factorization of $r$.

Shor’s Factoring Algorithm

We now have all the necessary elements to describe Shor’s factoring algorithm. We will state here the simpler version of the algorithm which only draws one sample from quantum phase estimation, and does not attempt to compute the least common multiple of the recovered $r’$ values.

Given an odd composite number $N$ with distinct prime factors (a semiprime number for RSA), one may compute its factors using the following procedure:

1. Pick a random $a\in \mathbb{Z}_N$
2. Compute $gcd(a,N)$ using the extended Euclidean algorithm
   • If $gcd(a,N)\neq 1$, $a$ is a factor of $N$, terminate the algorithm
   • If $gcd(a,N)=1$, proceed to the next step
3. Set $m=2 \log_2(N) +1$
4. Compute $c_k = a^k \; \mathrm{mod} \; N$ for $k=1,2, \dots , m$
5. Generate (efficient) quantum circuits for $\mathcal{M}_{c_k} \forall \; k$
6. Perform quantum phase estimation on a quantum computer with input state $\lvert 1\rangle$ and (controlled) unitary circuits $\mathcal{M}_{c_k} \forall \; k$ to sample $0.b_1 b_2 \dots b_m$
7. Using the continued fraction algorithm on $0.b_1 b_2 \dots b_m$ get $j/r$, and set $r$
   • If $r$ is odd, restart
   • If $r$ is even compute $d=\mathrm{gcd} (a^{r/2} -1,N)$
     • If $d \neq 1$, it is a factor of $N$, terminate the algorithm
     • If $d=1$, restart

For a semiprime number one successful iteration of this algorithm will factor $N$. For $N$ with more than two distinct prime factors, one may recursively apply this algorithm on the factored components to eventually find the prime factorization.

How can we use this to break RSA encryption? Recall that the public key information in RSA is the semiprime modulus $N$ and an encryption exponent $e$ which is coprime with $\phi(N)$. If we can factor $N$, we can compute $\phi(N)$ and subsequently get the decryption exponent $d$ by solving the following modular equation for $d$ using the extended Euclidean algorithm:

Example: Factoring Numbers Using Qiskit

At this point it should be somewhat clear that the implementation of Shor’s algorithm is rather straightforward. However, current publicly accessible quantum computers are limited in their capacity due to qubit counts, noise levels, and gate errors amongst other factors. These issues are expected to disappear with the development of the first error-corrected (a.k.a., fault-tolerant) quantum computers.

On present-day devices, we can implement toy examples of Shor’s algorithm to demonstrate small integer factorizations. These toy examples do not construct the quantum circuits for modular exponentiation in the way we have described earlier, e.g., translating a Boolean circuit to a quantum circuit. Instead, they “cheat” by observing the modular multiplication operation for some chosen $a$ and hard-code it. Although this approach is not scalable and kills the quantum speedup of Shor’s algorithm, it is mathematically equivalent and yields simpler circuits that are within the operating envelope of present-day devices. We will implement here such a toy example and run it on an IBM quantum computer simulator for demonstration purposes. This is a bare-bones implementation for demonstration purposes and skips many of the optimizations possible (e.g., observing the modes of the sampled bitstrings and computing least common multiples).

#!/usr/bin/env python3
# pip install numpy==1.26.0 qiskit==1.4.2

import numpy as np
from fractions import Fraction
from qiskit.circuit.library import UnitaryGate, QFT
from qiskit.circuit import ControlledGate
from qiskit import QuantumCircuit
from qiskit.transpiler import generate_preset_pass_manager
from qiskit.primitives import StatevectorSampler

if __name__ == "__main__":

    # The number we are interested in factoring
    N=35

    # Number of bits/qubits to represent N
    n = np.ceil(np.log2(N)).astype(int)

    # Number of QPE precision bits
    m = 2*n+1

    # Repeat for random a till success
    while 1:
        # Pick a nontrivial random integer a
        a = np.random.randint(2,N)
        print(f"a: {a}")

        # Check if a has any factors in common with N
        gcd = np.gcd(N,a)
        if gcd!=1:
            print(f"Found a factor of N: {gcd}")
            break

        print("Preparing modular exponentiation unitaries")
        # Compute the powers of a mod N
        c_k = [a]
        for _i in range(2,m+1):
            c_k.append( (c_k[-1]**2) % N )
            assert c_k[-1] == (a**(2**(_i-1))) % N

        # Generate the unitary operators for U_c_k |x> = | c_k * x mod N >
        U_c_k = []
        for _i in range(m):
            # Compute c_k * x mod N for each possible x up to N-1
            _c_k_x_mod_N = [ (c_k[_i] * _x) % N for _x in range(N) ]
            # Create the unitary matrix
            _U = np.zeros((2**n,2**n), dtype=int)
            # Set the elements of the matrix
            for _j, _k in enumerate(_c_k_x_mod_N):
                _U[_k,_j] = 1
            for _j in range(N,2**n):
                _U[_j,_j] = 1
            U_c_k.append(_U)
        
        print("Preparing quantum circuit")
        # Create the quantum circuit
        shor_circuit = QuantumCircuit(n+m,m)
        ## Prepare |1> input state
        shor_circuit.x(m)
        ## Hadamard gates on the QFT register (first m qubits)
        shor_circuit.h(range(m))
        shor_circuit.barrier()
        ## Controlled modular exponentiations
        for _i in range(m):
            ctrl_unitary_gate = UnitaryGate(U_c_k[_i], label=f"{c_k[_i]} x mod {N}").control(1)
            shor_circuit.append(ctrl_unitary_gate, [_i] + list(range(m,m+n)))
        shor_circuit.barrier()
        ## Inverse QFT
        shor_circuit.append(QFT(num_qubits=m, inverse=True), range(m))
        ## Measure the QFT qubits
        shor_circuit.measure(range(m), range(m))

        print("Sampling quantum circuit")
        # Get a sample from the quantum circuit
        pm = generate_preset_pass_manager(optimization_level=1)
        isa_circuit = pm.run(shor_circuit)
        sampler = StatevectorSampler()
        # collect 1 bitstring using Sampler
        job = sampler.run([shor_circuit], shots=1)
        pub_result = job.result()[0]
        bitstring = pub_result.data['c'].get_bitstrings()[0]

        # Compute continued fraction of measured bitstring
        phase = int(bitstring, 2) / (2**m)
        frac = Fraction(phase).limit_denominator(N)
        
        # Get estimated order of a modulo N
        r = int(frac.denominator)
        print(f"r = ord({a}) modulo {N} estimate: {r}")

        # Test r
        if not r%2 == 0:
            print(f"r: {r} is not even or nonzero, restarting")
        d_1 = (pow(a, r//2, N) - 1) % N  # a**(r/2) - 1
        d_2 = (pow(a, r//2, N) + 1) % N  # a**(r/2) + 1
        gcd_1 = np.gcd(d_1,N)
        gcd_2 = np.gcd(d_2,N)
        
        if gcd_1!=1:
            print(f"Found a factor of N: {gcd_1}")
            break
        if gcd_2!=1:
            print(f"Found a factor of N: {gcd_2}")
            break

Running this code a few times outputs the following:

a: 27
r = ord(27) modulo 35 estimate: 2
Found a factor of N: 7

a: 27
r = ord(27) modulo 35 estimate: 4
Found a factor of N: 7

a: 33
r = ord(33) modulo 35 estimate: 6
Found a factor of N: 7

a: 21
Found a factor of N: 7

a: 30
Found a factor of N: 5

It is interesting to note that even if we end up with the case where $j/r$ share factors, sometimes the algorithm will still succeed, which is what we observe in the above output! The correct order for $27$ modulo $35$ is $4$. In fact, for some cases one may get away with choosing much smaller numbers for $m$ (the number of qubits in the QFT register). This very basic implementation can be optimized in many ways, and an excellent reference covering many of these tricks can be found here. Note that in the past decade the resource estimates to break RSA encryption have steadily decreased by several orders of magnitude!

Breaking ECC using Shor’s Algorithm

Like RSA, ECC is also rooted in the mathematics of groups. Instead of the groups of integers $\mathbb{Z}_N$ and $\mathbb{Z}_N^\times$ used in RSA, ECC operates on the mathematical group defined by integer points $x,y\in \mathbb{F}_p$ on an elliptic curve $E$ modulo $p$. An elliptic curve is defined by the Weierstrass equation

where $a,b\in \mathbb{Z}$ and $4a^3+27b^2\neq 0$.

The integer points $(x,y) \; \mathrm{mod} \; p$ that satisfy $E/\mathbb{F}_p$ modulo $p$, are valid points on the curve. We can write out this set of points as:

where $\infty$ is a special point called the point at infinity.

As we have seen earlier, point addition is an operation that can be defined on elliptic curve points. Note that since elliptic curves are horizontally symmetric, we can label the mirror image of a point $P=(x,y)$ as $-P=(x,-y)$. Without getting into the details of projective coordinates and geometry, we can simply describe $\infty$ as having the following properties under point addition.

• $P+ (-P) = \infty$
• $P + \infty = -P$

Point addition between any other points e.g., $P+P, P+Q$ has already been defined earlier.

The total number of points $n=|E(\mathbb{F}_p)|$ can be estimated using Hasse’s Theorem, which estimates that for large $p$, $n \approx p$. There is an efficient polynomial-time algorithm for determining $n$.

By combining the set of elements $E(\mathbb{F}_p)$ with the point addition operation we have formed an Abelian group (we have seen Abelian groups earlier too! $\mathbb{Z}_N$ under addition and $\mathbb{Z}_N^\times$ under multiplication are also Abelian groups).

As we have seen earlier, we can create a convenient shorthand notation for adding a point $P$ to itself $k$ times as the dot operation. This is not a different operation, it is simply a shorthand notation. $0 \cdot P = \infty$ and $(-k) \cdot P=-(k \cdot P)$.

When $n$ happens to be prime, we obtain a special result:

Theorem: If $n=|E(\mathbb{F}_p)|$ is prime, $\forall \; P \in E(\mathbb{F}_p)$ where $P\neq \infty$

i) $n \cdot P = \infty$

ii) The points $\infty, P, 2 \cdot P, \dots , (n-1)\cdot P$ are distinct and $E(\mathbb{F}_p)=\{ \infty, P, 2 \cdot P, \dots , (n-1)\cdot P \}$

We can see that every point $P \in E(\mathbb{F}_p)$ is a generator of $E(\mathbb{F}_p)$. Furthermore, from the symmetry of the curve, we know that $-P$ and $P$ share the same $x$-coordinate, and for prime $n$ this $x$-coordinate is unique to this pair, i.e., it is not shared by any other pair of points.

The important consequence of these properties is that adding $P$ to itself cycles through all the points on the curve before returning to $\infty$! In fact, this also means that picking any arbitrary point on the curve (except the identity element $\infty$) and adding it to itself will also cycle through the entire group of points on the curve before returning to $\infty$.

Mathematically this implies that $k\cdot P = (k \; \mathrm{mod} \; n) \cdot P \; \forall \; k \in \mathbb{F}_p$.

Elliptic Curve Discrete Logarithm Problem

We have seen earlier that given any point $P\in E(\mathbb{F}_p)$, we can efficiently compute $Q=l\cdot P$. However, if we are given $Q,P,p,n$ and the curve parameters, we cannot efficiently compute $l$. The definition of this difficult problem is the elliptic curve discrete logarithm problem:

Given $E/\mathbb{F}_p, p,n$ and $P,Q\in E(\mathbb{F}_p)$ with $P\neq \infty$, find an integer $l$ such that $Q=l\cdot P$.

This problem is written in logarithmic notation as $l= \log_P Q$. Unlike logarithms defined over $\mathbb{R}$ which “count” the number of times a number is multiplied with itself, in this context it means the number of times a point is added to itself over an elliptic curve.

Shor described an efficient quantum algorithm for the discrete logarithm problem along with his more famous factoring algorithm. This was achieved by reducing the discrete logarithm problem as a period finding problem and exploiting the quantum Fourier transform.

Subgroups, the Hidden Subgroup Problem, and Period Finding

To fully understand the period finding problem and the quantum algorithm to solve it we must go over some more group theory. We will temporarily switch notation to more commonly used notation for group theory. Those interested only in the algorithm for breaking ECC can simply skip this section.

As we have seen earlier, the points on the elliptic curve of prime order $n$ form a cyclic group. In group theory notation this is written as $G=\langle g \rangle$ and $\lvert G \rvert = n$ with a group operation $\circ$. As usual, the properties of associativity ($(x \circ y ) \circ z = x \circ (y \circ z)$), identity elements ($x \circ e = e \circ x$), and inverse elements ($x \circ x^{-1} = x^{-1} \circ x = e$) are defined on this group along with commutativity (since we are working with Abelian groups).

Every group will have a generating set, i.e., a set of elements using which all the elements of $G$ can be obtained using the group operation. For elliptic curves with prime $n$ we have already seen that any point on the curve generates the entire set of points cyclically.

We can also define a subgroup $H \le G$. A subgroup will also follow the usual properties of a group along with closure on the subgroup, i.e., $\forall \; x,y \in H, \; x \circ y \in H$.

> Example

The group $\mathbb{Z}_N = \{0,1,2,\dots,N-1 \}$ under group operation addition is a group with a generating set $\{ 1\}$. For any $s$ that divides $N$, we can describe a subgroup $H = \{ 0,s,2s,\dots,N-s \}$ with a generating set $\{ s \}$.

For any subgroup one may define a coset of the subgroup by performing a group operation $H_g=\{ g\circ h\in H \}$, and these cosets can be defined for all $g\in G$. Note that cosets are not necessarily subgroups since they may not contain the identity element $e$.

> Example

Continuing with our previous example, $H_1 = \{ 1,s+1,2s+1,\dots,N-s+1 \}$ is a coset and does not include the identity element $0$.

Now consider a case where we are given a function $f(x)$ which has two important properties: $f(x)=c_g$ is constant for elements $x\in H_g$, and all $c_g$ are distinct values for every coset $H_g$.

We can use these ingredients to define an Abelian hidden subgroup problem, and for our case we will solve this problem using period finding. The Abelian hidden subgroup problem can be stated as follows:

Given a group $G$ that has an unknown subgroup $H$ and $f(x)=c_g$ where $c_g$ is constant for every element $x \in H_g$ and $c_g$ is distinct for every distinct coset $H_g$, find the subgroup $H$.

Note that “find $H$” is equivalent to “find a generating set for $H$“. It is known that the generating set has a size of at most $\log |H|$. A function $f(x)$ with properties as described above is typically referred to as “a function that hides $H$“.

Abelian hidden subgroup problems can be solved efficiently using quantum computers, whereas many known Abelian hidden subgroup problems can be exponentially expensive to solve using classical computers. The main idea behind the quantum approach is the fact that every finite Abelian group can be written as a direct product of cyclic groups $\mathbb{Z}_{N_1 } \times \mathbb{Z}_{N_2 } \times \cdots \times \mathbb{Z}_{N_m }$, and on these one may perform the quantum Fourier transform to learn the set that generates $H$.

> Example

For the above example $H = \{ 0,s,2s,\dots,N-s \}$ with the function $f(x) = x \; \mathrm{mod} \; s$, we get $f(h_g)=c_g \; \forall \; h_g\in H_g$. $f(x)$ is a periodic function with a period $s$. We can apply the Fourier transform on $f(x)$ to learn the period $s$, which generates $H$. The quantum Fourier transform is efficient over exponentially large spaces, unlike classical discrete Fourier transforms.

We can apply the same ideas to solve a discrete logarithm problem, which can be posed as an instance of a hidden subgroup problem. We first restate the general discrete logarithm problem:

Given a cyclic group $G=\langle g \rangle$ of order $N$ and an element $h \in G$, find the unique integer $k \in \{ 0,1, \dots , N-1 \}$ such that $h=g^k$ where $g^k=g \circ g \circ \cdots \circ g$ is the group generator composed with itself over the group operation $\circ$ $k$ times.

The equivalent hidden subgroup problem can be stated as:

Given the domain group $D= \mathbb{Z}_N \times \mathbb{Z}_N$, an image group $G=\langle g\rangle$, and a function $f: D \rightarrow G$ defined as $f(x,y) = g^x \circ h^y = g^x \circ g^{y \log_g h}=g^x \circ g^{y k}$, find the hidden subgroup $H \leq D$ generated by $H=\langle (N,0),(k,-1) \rangle$.

Note that for the discrete logarithm problem the cosets of $H$ partition $D$ such that $f$ is constant on each coset and distinct across cosets. This suggests that once again $f$ has a periodic nature, only this time it is 2-dimensional, and we can use the Fourier transform to learn $k$. Fourier transforms are known to be exponentially more efficient on quantum computers using the quantum Fourier Transform (QFT), which we will exploit.

Reduction to Period Finding

We will now go through some basic algebra to transform the discrete logarithm problem into a period finding problem. First let’s note that given $a,b,l\in \mathbb{Z}_n$ and $P,Q$ such that $Q=l\cdot P$, we can write

Writing this as a function $f(a,b)=(a+bl) \cdot P$, we see that this function is periodic in $a$ and $b$ as

Which tells us that

for some constant $c$. This implies that $f(a,b)$ has a $2D$ periodic structure with a period related to $l$.

This is exactly the same structure we have seen earlier for the general discrete logarithm problem, except with slightly different notation. The cyclic group is all the points on the chosen elliptic curve with prime order $n$. If we pick any point on the curve and keep adding it to itself, it will generate all the points on the curve (every point on the curve is a generator except $\infty$). The group operation is point addition, and the dot operation is “equivalent” to the exponentiation operation for integers as we saw earlier.

We can now proceed to describe the algorithm that uses period finding to solve the elliptic curve discrete logarithm problem.

As we see from the equation above, when $b,c$ are fixed, $a$ is periodic with order $n$. Correspondingly, when $a,c$ are fixed $b$ is periodic with order $n/l$.

The quantum Fourier transform can be used to find the period $l$. Let’s cover the steps of the quantum algorithm step-by-step.

Prepare a uniform superposition of $a,b$ such that $a,b\in [0,2^{m})$ where $2^m \geq n^2$.

Compute $f(a,b)=(a+bl) \cdot P$ into the final register. This can be implemented by converting classical Boolean circuits to quantum circuits. Note that the number of qubits in this final register depends on the chosen representation of $f(a,b)$ in bits.

Measure the final register. This will yield some arbitrary point on the curve $R= a’ \cdot P + b’ \cdot Q$. The first two registers will now be a superposition of all $K$ possible solutions $a’,b’\in [0,2^{m})$ that satisfy $R= a’ \cdot P + b’ \cdot Q$. We can drop the final register now as it is irrelevant.

As we have seen above, these $a’,b’$ satisfy

Now imagine that instead of $a,b\in[0,2^m)$ we restricted $a,b$ to $a,b\in[0,n)$. If we perform a 2-dimensional discrete Fourier transform with $n$ points per dimension, $DFT_n\otimes DFT_n$ (we are not referring to the quantum Fourier transform yet, which has $2^m$ points), on the two registers after some algebraic manipulation we can show that we now have the state

where $\omega_n^{\nu\delta}=\frac{2\pi i \nu \delta}{n}$ and $\delta=\log_P (a’\cdot P)$.

This basically tells us that subsequent measurements are independent of any particular $a’, b’, R$, and that if we measure the second register such that $\nu$ has a multiplicative inverse modulo $n$ (e.g., it will not for $\nu=0$), we can recover $l$ by simply solving

The success probability of this procedure is $\phi(n)/n$, which scales favorably for large prime $n$. The points $\nu l, \nu$ appear as perfect “peaks” in the lattice of points $(\nu l, \nu)$ after the Fourier transform. We will visualize these peaks in the next section for a small curve example.

While this postprocessing step is very straightforward for $DFT_n\otimes DFT_n$, in practice we will be using a quantum Fourier transform over $a,b\in[0,2^m)$. Since the discretized grid $2^m \times 2^m$ does not perfectly align with the $n \times n$ grid, the peaks will appear slightly “smeared”. But as $m$ is increased, they get sharper. There are several methods including continued fractions to recover $\nu l ,\nu$ from these imperfect measurements. In our toy example we will simply use integer rounding, which works remarkably well.

Now consider the more practical realistic scenario where we apply a 2-dimensional quantum Fourier transform $QFT_k\otimes QFT_k$ instead and get some state (for which it is unnecessary to derive the exact result for our purposes):

We can measure the registers and get integer bitstrings $s,t$ and to “project” them onto the $n\times n$ grid by rounding to the closest integers as:

If $m$ is large enough we will recover $s’=\nu l, t’=\nu$ with high probability! Note that this is slightly different from more rigorous approaches suggested in research literature with extensive proofs.

Shor’s Algorithm for Discrete Logarithms (simplified)

Now that we have all the elements required for breaking RSA, we will now summarize Shor’s algorithm to do so.

1. Pick the number of qubits for the input registers $m$. $2^m \geq n^2$ is recommended.
2. Prepares two registers $|a\rangle,|b\rangle$ with $m$ qubits each in superposition by applying Hadamard gates to each qubit.
3. Compute $f(a,b)$ into a third register $|f(a,b)\rangle$ with using an implementation of $U_{f(a,b)}|a\rangle,|b\rangle|0\rangle = |a\rangle,|b\rangle|f(a,b)\rangle$.
4. Measure the third register (optional)
5. Apply the QFT to registers $a$ and $b$ individually
6. Measure remaining registers $|a\rangle,|b\rangle$ to get integer bitstrings $s,t$
7. Project integer bitstrings to $n \times n$ grid as $s’= \lfloor \frac{s n}{2^m} \rceil, t’= \lfloor \frac{t n}{2^m} \rceil$ (use reduced fractions if $n$ is not known)
8. Attempt to solve modular equations, if solution exists
   • Solve $s’^{-1} s’ \equiv 1 \; \mathrm{mod} \; n$ for $s^{-1}$ if it exists and is nontrivial
   • $l_{est} = s’^{-1} t’ \; \mathrm{mod} \; n$
     • If $Q==l_{est} \cdot P$, $l = l_{est}$, terminate the algorithm
     • Else restart

Example: Discrete Logarithms in Qiskit

As we have seen, a basic algorithmic implementation to solve the discrete logarithm problem is even more straightforward than factoring, although the classical postprocessing steps can be somewhat involved if implemented rigorously. The same caveats as factoring apply: qubit counts, circuit depths, fault tolerant quantum computers, and efficient implementation of classical circuits as quantum circuits are factors relevant for cracking realistic elliptic curve discrete logarithm problems. In the following example, we solve it for a toy curve $y^2= x^3 + 3x +2 \; \mathrm{mod} \; 5$ and subsequently demonstrate visually the performance and scaling of the quantum algorithm.

We use the fact that for prime $n$ any $x$ coordinate has two unique solutions $\pm y$ modulo $n$ which are even and odd. Therefore, instead of encoding both coordinates as bitstrings, we can compress the coordinates as the $x$ coordinate bits and one bit to differentiate between the even/odd $y$ coordinates.

#!/usr/bin/env python3
# pip install numpy==1.26.0 qiskit==1.4.2

import numpy as np
from qiskit import QuantumCircuit, QuantumRegister, ClassicalRegister
from qiskit.circuit.library import QFT
from qiskit.primitives import StatevectorSampler

def scalar_mult(k, P, p, a, b):
    """Compute k*P using the double-and-add algorithm."""
    if k == 0 or P[0] is None:
        return (None, None)
    R = (None, None)
    Q = P
    while k > 0:
        if k & 1:
            R = point_add(R, Q, p, a, b)
        Q = point_add(Q, Q, p, a, b)
        k >>= 1
    return R

def point_add(P, Q, p, a, b):
    """Adds two points on the elliptic curve."""
    if P[0] is None:
        return Q
    if Q[0] is None:
        return P
    if P[0] == Q[0] and P[1] != Q[1]:
        return (None, None)
    if P == Q:
        lam = (3 * P[0]**2 + a) * pow(2 * P[1], p - 2, p) % p
    else:
        lam = (Q[1] - P[1]) * pow(Q[0] - P[0], p - 2, p) % p
    x3 = (lam**2 - P[0] - Q[0]) % p
    y3 = (lam * (P[0] - x3) - P[1]) % p
    return (x3, y3)

def compress_coord(P, bits):
    """Converts x,y coordinates into x-coord + even/odd bitstring encoding."""
    (x, y) = P
    if x is None or y is None:
        return "0" * bits
    return str(y % 2) + f"{x:0{bits-1}b}"

if __name__ == "__main__":
    p, a, b = 5, 3, 2 # Curve parameters
    n = 5   # Order of chosen curve
    P = (2, 1) # Base Point
    l = np.random.randint(1, n) # The private secret
    Q = scalar_mult(l, P, p, a, b)
    print(f"Solving ECDLP: Q = {l}P mod {n}")
    print(f"Secret l = {l}")

    m = 5   # Size of a,b registers for QFT
    out_bits = 4    # Number of bits to encode curve points in compressed format
    
    print("Preparing modular addition unitary")
    N_total = 2 * m + out_bits
    U_f = np.eye(2**N_total, dtype=bool)
    for _a in range(2**m):
        for _b in range(2**m):
            _a_bistring = f"{_a:0{m}b}"
            _b_bistring = f"{_b:0{m}b}"
            aP = scalar_mult(_a, P, p, a, b)
            bQ = scalar_mult(_b, Q, p, a, b)
            R = point_add(aP, bQ, p, a, b)
            R_bitstring = compress_coord(R, out_bits)
            
            basis_state_col = int("0" * out_bits + _b_bistring + _a_bistring, 2)
            basis_state_row = int(R_bitstring + _b_bistring + _a_bistring, 2)
            
            if basis_state_col == basis_state_row:
                continue
            U_f[basis_state_col, basis_state_row] = 1
            U_f[basis_state_row, basis_state_col] = 1
            U_f[basis_state_col, basis_state_col] = 0
            U_f[basis_state_row, basis_state_row] = 0

    print("Preparing quantum circuit")
    a_qreg = QuantumRegister(m, name='a')
    b_qreg = QuantumRegister(m, name='b')
    R_qreg = QuantumRegister(out_bits, name='R')
    a_creg = ClassicalRegister(m, name='s')
    b_creg = ClassicalRegister(m, name='t')
    R_creg = ClassicalRegister(out_bits, name='c')
    
    circ = QuantumCircuit(a_qreg, b_qreg, R_qreg, a_creg, b_creg, R_creg)
    circ.h(a_qreg)
    circ.h(b_qreg)
    circ.unitary(U_f, a_qreg[:] + b_qreg[:] + R_qreg[:], label="f(a,b)=aP+bQ")
    circ.measure(R_qreg, R_creg)
    circ.append(QFT(num_qubits=m), a_qreg)
    circ.append(QFT(num_qubits=m), b_qreg)
    circ.measure(a_qreg, a_creg)
    circ.measure(b_qreg, b_creg)

    print("Sampling quantum circuit")
    sampler = StatevectorSampler()
    job = sampler.run([circ], shots=1024)
    pub_result = job.result()[0]
    bitstrings_s = pub_result.data['s'].get_bitstrings()
    bitstrings_t = pub_result.data['t'].get_bitstrings()
    
    print("Classical post-processing")
    # Map each sample to the n×n grid using linear scaling
    s_proj = [round(int(_s, 2) * n / 2**m) % n for _s in bitstrings_s]
    t_proj = [round(int(_t, 2) * n / 2**m) % n for _t in bitstrings_t]
    # Try to recover l
    candidates = []
    for sp, tp in zip(s_proj, t_proj):
        if sp == 0:
            continue
        try:
            l_est = (tp * pow(sp, -1, n)) % n
            candidates.append(l_est)
        except ValueError:
            pass
    # Pick most commonly recovered l
    l_recovered = max(set(candidates), key=candidates.count) if candidates else None
    if candidates:
        print(f"Recovered l = {l_recovered} | Success: {l_recovered == l}")
    else:
        print("Did not find any valid candidate solutions.")

This code generates and samples a quantum circuit of the following form:

Running this code a few times outputs the following:

Solving ECDLP: Q = 4P mod 5
Secret l = 4
Recovered l = 4 | Success: True

Solving ECDLP: Q = 1P mod 5
Secret l = 1
Recovered l = 1 | Success: True

Solving ECDLP: Q = 2P mod 5
Secret l = 2
Recovered l = 2 | Success: True

We can try to visualize the algorithm via heatmaps of the raw sampled bitstrings and the projected values. In the following plots, the “slope” at which the peaks lie is $1/l$.

As we increase the number of qubits $m$, we see that the success probability of the algorithm increases. Note that while samples at $(0,0)$ are valid, they are trivial and useless for discovering $l$ . However, they are inevitable as seen on the plot, but are less likely for large $n$ (the probability of measuring $(0,0)$ in the ideal case is $1/n$).

Post-Quantum Cryptography: Fortifying against Quantum Computers

Cryptography Primitives

We have gone over core cryptographic primitives and shown that asymmetric cryptography can easily be decrypted using quantum computers, while modern symmetric cryptography and hashing are more resilient. We have also observed that quantum computers are highly capable at extracting periodicity and finding hidden subgroups.

New cryptographic protocols have been proposed which are as of yet publicly known to be quantum resistant. In 2024 NIST announced the first three post-quantum cryptography (PQC) standards. While the cryptographic community remains skeptical about the quantum resistance of these standards and the possibility of backdoor channels, they are expected to be safer than RSA and ECC in the post-quantum era.

Between RSA and ECC, resource estimates for ECC quantum attacks are lower ($<1200$ logical qubits,$<90$ million Toffoli gates or$<1450$ logical qubits,$<70$ million Toffoli gates) than RSA quantum attacks ($<100,000$ physical qubits). These estimates have steadily been decreasing over the past decades.

For AES and SHA, while they are practically unbreakable using quantum computers due to the sheer number of operations required, it is still advisable to double key lengths for good measure for high security applications.

Quantum Random Number Generation

Random number generation is another important subject central to cryptography. Safe usage of cryptography requires generating random numbers, a task which classical computers perform relatively poorly. Classical random number generators are deterministic algorithms that are fed a “seed”, e.g., the date and time, to mimic randomness. However, they can be predictable and are ultimately periodic. This makes them vulnerable to both classical and quantum attacks.

A simple solution is to draw random samples from a truly random source, e.g., a quantum resource. Quantum random number generator chips are available on the market and can be used to protect against classical predictability.

Quantum Key Distribution: A Quantum-Networked Future

Similar to how physical principles ensure that quantum random number generators are truly random, one may use other quantum mechanical principles to secure key distribution to create quantum key distribution (QKD). Well-known protocols are the BB84 protocol and the E91 protocol among many others. These protocols are protected by the laws of physics and can also detect eavesdroppers.

Unfortunately, they require deployment of (currently unavailable) public infrastructure like a quantum internet, and even then QKD is vulnerable to side-channel attacks like detector blinding or optical injection attacks to deduce secret keys.

QKD will offer an additional layer of security over PQC when it is available. Regardless of PQC and QKD, safe public infrastructure is necessary since neither of these can protect from man-in-the-middle attacks.

Outlook

In summary a recommended course of action for security in a post-quantum world is:

1. Transition to PQC public key cryptography immediately
2. Double key lengths for AES and SHA for high-security applications
3. Integrate quantum random number generators into protocols relying on random numbers
4. Appropriate resources for QKD and transition when infrastructure is available

Our Executive Summary provides a detailed plan of action.

DISCLAIMER: This 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. Please consult HiDi Corporation directly for professional advice on your cryptographic security needs.

© 2026 HiDi Corporation. All rights reserved.