Quantum Computing and Cryptography: Riding Into the Future of Security

Well, howdy there, tech cowboys and cowgirls! As we ride out into the frontier of the digital age get your lasso ready and saddle up coz there’s a quantum storm brewing on the horizon. Beneath the untamed wilds of binary code and cryptographic charms there is a force gathering strength and threatening to upend the age-old peace we’ve fought so hard to protect.

In this digital technical rodeo showdown, the outlaw in question is none other than Shor’s Algorithm, a quantum foe that packs a punch potent enough to topple RSA encryption which is the the foundation of most of our online security today. Just as the gunslingers of yore wielded their six-shooters, we have armed ourselves with cryptography to safeguard our secrets and treasures. But hold onto your hats, folks! The quantum horses are coming, and if we don’t take heed they’ll trample right through our encryption defenses.

I am writing this article to traverse the rugged terrain of quantum computing from cryptographic lenses, dissect the formidable RSA encryption, and uncover the nitty-gritty of Shor’s Algorithm.

BACKGROUND: RSA ENCRYPTION

RSA encryption is like you and your best mate decide to communicate secretly but instead of dusty old letter-writing, you choose numbers to send messages. Here’s how to get this cattle drive moving.

The first step is akin to picking out the perfect steeds for your rodeo by picking two prime numbers let’s say p and q.These primes should to be big for any would-be rustlers to replicate. Foe explaination and simple example we will choose (p = 5) and (q = 11).

Another real world analogy of the assymetric key encryption is think a Public key similar to mailbox slot which belongs to let’s say Alice and Private key like the mailbox key where anyone can drop a letter (even Bob) but only Alice can open the box. Let’s say Bob wants to send a message to Alice. Following is step by step description on how RSA encryption helps Alica and Bob to communicate securely:

At first, Alice prepares the keys: RSA Key Creation

Choose two primes
             p = 5     q = 11
                 │
                 ▼
        Multiply them together
             n = p × q
             n = 55
                 │
                 ▼
       Compute Euler Totient
      φ(n) = (p-1)(q-1)
      φ(n) = 4 × 10 = 40
                 │
                 ▼
     Choose public exponent e
      e = 7  (coprime with 40)
                 │
                 ▼
     Compute private key d
      d × e ≡ 1 mod 40
      d = 23

Result

Public Key  →  (e, n) = (7, 55)
Private Key →  (d) = 23

Alice sends Public Key: Public Key Distribution

Alice (Receiver)
      ┌─────────────────┐
      │ Public Key      │
      │ (7 , 55)        │
      └────────┬────────┘
               │
               │  shares publicly
               ▼
           Bob (Sender)

Anyone can use the public key which is like a mailbox slot but only Alice knows d which is private key.

After Public Key Transmission Alice’s public key ( (e, n) = (7, 55) is in Bob’s hands where he can send secret messages by creating a ciphertext using the public key. This is the part which can be evesdropped by let’s say Eve.

Bob sends a secret: Encryption

Let’s say Bob wants to send a digit 3:

Message m = 3

He encrypts using Alice’s public key.

Bob
         │
         │  Encrypt
         ▼

c = m^e mod n
    c = 3^7 mod 55
    c = 42

After encryption Bob actually sends over the network:

Encrypted Message
c = 42

Bob ───────────────► Alice
      ciphertext

Alice reads the ciphertext: Decryption

Alice uses her private key.

Alice
             │
             │ Decrypt
             ▼
        m = c^d mod n
        m = 42^23 mod 55
        m = 3

The original message appears again after decyption:

Ciphertext 42
      │
      ▼
Original Message = 3

Later, Alice retrieves the message with the secret sauce ( m = c^d mod n ).

Full RSA Flow (Simple Diagram)

Alice creates keys
     ┌──────────────────────┐
     │ p=5 , q=11           │
     │ n=55 , φ(n)=40       │
     │ e=7 , d=23           │
     └──────────┬───────────┘
                │
        Public Key (7,55)
                │
                ▼
              Bob
      Message m = 3
                │
       Encrypt using e
                │
        c = 3^7 mod 55
           c = 42
                │
                ▼
         Send ciphertext
                │
                ▼
              Alice
        Decrypt using d
        m = 42^23 mod 55
                │
                ▼
           Message = 3

Why It’s Mathematically Hard to deduce

The beauty of RSA lies in its reliance on the math that underpins prime factorization. While computing N from (p) and (q) is a stroll in the park but reversing that process by determining p and q from n is akin to finding a needle in a stack of hay which has a lot of needles. It requires immense brute-force computational firepower, which current classical algorithms struggle to muster.

Current Key Lengths and Their Security Levels

Most modern implementations use RSA keys lengthened to 2048 bits or even longer. A 2048-bit key is grizzled with security, being painstakingly difficult to crack, while the likes of 4096-bit keys take traditional methods into a dusty sunset that might last centuries. This makes RSA a stalwart ally in protecting emails, transactions, and SSH security in our digital saloons.

Here comes Quantum Computers which can Break RSA

Shor’s algorithm is a quantum gunslinger. This algorithm tasks quantum computers with exploiting the tremendous “superposition” , “entanglement” and “interference” that arise in quantum mechanics. Specifically, Shor’s Algorithm leverages the quantum Fourier transform (QFT) to find the period of a function, helping to crack the code behind RSA by turning the complexity of factorization into a polynomial-time problem.

Simply put, where classical computers might take centuries to crack RSA, a quantum computer can do it in the blink of an eye broadly threatening the financial and personal security sectors.

I saw this term few days ago: “Harvest Now, Decrypt Later” Attacks

A notable strategy is the “harvest now, decrypt later” tactic. In this scenario, attackers gather encrypted data now, confident that a quantum computer will soon allow them to decrypt it. Organizations need to realize that the encryption they rely on could become wide open in the not-so-distant future it’s high noon in the digital wild west.

CLASSICAL FACTORIZATION APPROACHES

Trial Division and Pollard’s Rho Algorithm and General Number Field Sieve (GNFS)

Well AI wrote this part but I would like to include this in this article. Before quantum computing burst onto the scene, the classical methods for tackling factorization were a mix of old guns and upstarts. The trial division method is as straightforward as it sounds which is trial and error, repeating the process until the prime factors pop up. With large numbers, this method meanders at a snail’s pace.

Another contender is Pollard’s rho algorithm, which employs clever probabilistic tricks but still falls short when up against the massive numbers that modern encryption techniques rely on.

The heavyweight champion of classical factorization is undoubtedly the General Number Field Sieve (GNFS). Despite being the fastest classical algorithm for large numbers, this method still stands to benefit from the quantum leap that Shor’s Algorithm offers. To give you a sense of the timescale: GNFS can take years to factor a 2048-bit RSA key, while a quantum computer equipped with Shor’s Algorithm may breeze through it in mere moments.

Why Classical Methods Are Too Slow

In practical terms, as we seek to multiply and divide larger numbers, these classical methods begin to flounder, akin to a cowboy losing his hat in a dust storm. With a real-world example, while a GNFS run for 2048-bit RSA might churn for several years, Shor’s will one day complete the same task in a blip — leaving classical methods in the dust.

QUANTUM FOURIER TRANSFORM: THE KEY INNOVATION

What is Quantum Superposition and Entanglement?

Now, let’s tip our hats to the quantum mechanics that elevate Shor’s Algorithm to legendary status. At the core, we find two powerful phenomena: superposition, the ability of quantum bits (qubits) to exist in multiple states simultaneously and entanglement**, a bizarre connection where the state of one qubit instantly influences another, no matter the distance.

How QFT Exploits Quantum Mechanics

The Quantum Fourier Transform is the central trick up Shor’s sleeve. Just as a cowboy uses his lasso to catch and control two wild mustangs, QFT takes the mixed states of qubits and arranges them in a way that allows us to extract valuable information about the periodicity of the function we’re analyzing.

Why It’s Exponentially Faster

In the quantum realm, the processing speed is squaring the old conventions we’re familiar with. QFT operates exponentially faster than the classical Fourier transform, making Shor’s bonanza a real game-changer. It can distill vast amounts of information into manageable pieces swiftly and effectively.

SHOR’S ALGORITHM

“Hide the period in a quantum superposition → reveal it with interference.”

A 1000 ft high level Algorithm Walkthrough

Buckle in, cowpokes — we’re about to go through the wild bucking bronco that is Shor’s Algorithm step by step.

Problem Statement: Given a number N (let’s take 15), we need to basically find the nontrivial factors (here, p=3 and q=5).

Random Integer: Pick a random integer a such that ( 1 < a < N ). Let’s say ( a = 2 ).

GCD: Compute gcd(a, N). If it’s not equal to 1 or N, then this is a nontrivial factor.

Order Finding with QFT: The trick half of the algorithm spirals into QFT territory. We define the function f(x) = a^x mod N and find its order r, where the first r such that f(x) = f(x + r). Too much math ha! That’s what I thought but I will go in detail next after this pointwise description.

Periodicity: Using the QFT we extract the periodicity from our quantum states, allowing us to bypass much of the classical labor and then we can apply the formula Period = Total Samples / Frequency to find the period.

Factors: Finally, if r is even, we compute (a^{r/2}-1)and (a^{r/2}+1). The GCD of these with N should yield the nontrivial factors we were after.

And voilà! You’ve just factored 15 into 3 and 5, proving how expedient this quantum approach is when contrasted with classical methods. Though, this may be not very good explanation. I will try to start with how I learnt this. It started from basics where I had to understand roots of unity. It looks very simple but it has its own significance.

Roots of unity OR Building blocks of QFT

Roots of unity are evenly spaced points on the unit circle.

Fourth roots of unity

z⁴ = 1
z = [1, i, -1, -i]

Each step rotates by 90°

Eighth roots of unity

z⁸ = 1

Think of roots of unity like fence posts around a circular ranch. With 4 roots, you’ve got posts every 90°, which is fine if you’re herding slow-moving cattle — you can tell roughly where things repeat, but the details are fuzzy. When you move to 8 roots, the posts show up every 45°, giving you a much sharper eye for the trail. The more posts you hammer into the ground, the better you can spot subtle rhythms galloping around the circle. In Fourier terms, 4 roots give you coarse resolution, 8 roots give you finer resolution, and more roots give you pinpoint frequency precision. This in Fourier analysis called the resolution knob: turn it up, and hidden patterns stop slipping through the cracks of the prairie.

You must be saying “super simple!” That’s what I want readers of this article to think since I thought the same when I was learning Shor’s algorithm. Now, lets look at how frequency and period works with each other with some good real life stories. Lets bring up the concept of QFT here as well.

Ah! One more small thing I forgot to bring up about Discrete Fourier Transform. No worries, its basically classical way of representing QFT but have to atleast touchbase or mention this:

Discrete Fourier Transform (DFT)

Well! I just want to touchbase on mathematical format of a DFT and how it looks like. Given a vector:

DFT produces:

Where:

Must be feelign like too much notations, formulas and math but hold on to your hats! this will be as easy to comprehend as to comprehend the fact why is sky blue! Simple right! Well! Why is it blue??

🔹QFT matrix

The QFT matrix (same math as DFT, just unitary-scaled):

QFT matrix

where each row **i**:

• Tests one frequency
• Uses powers of roots of unity

This matrix is literally: “All frequency detectors stacked together”

Picture yourself at a dusty open-air concert out on the prairie, where eight speakers are lined up like hitching posts. Each speaker, labeled by (j), is doing its honest day’s work by pushing out sound into the crowd. Now the music itself is a mix of different tones, and those tones such as bass, low-mid, high-mid, treble, and the rest are labeled by (k). The QFT matrix (F) is the seasoned sound engineer in a cowboy hat, calmly asking one sharp question: “How much does speaker (j) contribute to frequency (k)?” Every entry (F[j,k]) answers exactly that. With eight speakers, (F) is an 8×8 ledger, where each row belongs to one speaker and each column corresponds to one possible musical frequency. So in the row for speaker 1, you’ll find how much that speaker feeds the bass, the low-mid, the mid, the high, and everything in between — no guesswork, no trial runs. When you multiply your data by this matrix, you’re essentially letting that engineer check all frequencies across all speakers at once, instead of walking the line one speaker at a time. That’s the magic of the QFT: in a single, well-aimed operation, it rounds up every hidden frequency in your signal and brings them all into the open, like a clean cattle drive at sunset.

I will write this speaker analogy description pointwise:

• You’re at a concert with 8 speakers in a line
• j = which speaker (1st speaker, 2nd speaker, …, 8th speaker)
• k = which musical frequency (bass, low-mid, high-mid, treble, etc.)
• F[j, k] = “how much does speaker j contribute to frequency k?”

The QFT matrix F contains all those contributions, which is why multiplying your data by F reveals all the hidden frequencies in your signal! It contains all possible frequencies for each speaker.

Talking about the exact structure:

F is an 8×8 matrix (if you have 8 speakers). So for speaker 1:

F[1, bass] = how much speaker 1 contributes to bass
F[1, low-mid] = how much speaker 1 contributes to low-mid
F[1, mid] = how much speaker 1 contributes to mid
F[1, high] = how much speaker 1 contributes to high
similarly for all 8 frequencies

I wrote up this to experiment and dig deeper on this: https://github.com/sagacioussid02/quantumb6/blob/main/shors.ipynb

So F simultaneously reveals all frequencies hidden across all speakers in one matrix operation! Let’s looks at some more analogies and how QFT can help us understand and deduce QFT:

🕰️ Clock Chime:

Consider a clock ticks 8 times in one minute. It makes a loud DING every 4 ticks.

Tick #:   0 1 2 3 4 5 6 7
Sound:    . . . . D . . . D

Interpretation

• Total ticks = 8
• Repetition every = 4 ticks
• Period = 4
• Frequency = 2 dings per minute

What is QFT’s job in this case:

“Which clock rhythm is the loudest?”

🎶 Drum Beat / Music Loop

QFT finds the rhythm hidden inside a pattern.

A drummer plays 8 beats and a strong beat happens every 4 beats.

Beat #:   1 2 3 4 5 6 7 8
Volume:   L L L H L L L H

Interpretation

• Loop length = 8 beats
• Pattern repeats every 4 beats
• Frequency = 2 cycles per loop

Quantum Fourier Transform will answer:

“Which rhythm dominates this song?” => Wrong rhythms will cancel and only correct rhythm resonates.

Just picture each beat whispering: “This is my position.” For all Wrong pattern the whispers clash and cancel each other whereas for all the right pattern the whispers sing in harmony 🎶

Let’s continue to look at some more analogies:

🌊 Lighthouse Flash

A lighthouse rotates once and emits 8 flashes per full turn which shines brightly every 4 flashes.

Angle:    0° 45° 90° 135° 180° 225° 270° 315°
Flash:     .   .    .     ★     .     .      .     ★

Interpretation

• Full rotation = 8 samples
• Pattern interval = 4
• Frequency = 2 flashes per rotation

Roots of unity:

These are angles on the lighthouse rotation.

🏁 Road Milestone

A car drives 8 km and every 4 km, you see the same roadside restaurant.

Km:      0 1 2 3 4 5 6 7
View:    🌲 🌲 🌲 🍔 🌲 🌲 🌲 🍔

Interpretation

• Total distance = 8 km
• Restaurant repeat = every 4 km
• Frequency = 2 restaurants per trip

QFT basically figures out all possible spacings at once and listens for which spacing resonates. Want to note here that QFT does not Walk back and measure distances or Compare every possible spacing one by one. These were few misconceptions I had .

Imagine instead of measuring manually you shout different rhythms into the road and listen for an echo. The wrong rhythms cancels out echo and for the Right rhythm the echo comes back loud. That’s QFT. Let’s see one more:

🌈 Wallpaper Pattern

A wall has 8 tiles in a row. The wallpaper pattern repeats every 4 tiles.

Tile #:  1 2 3 4 5 6 7 8
Color:   🔵 🟡 🟢 🔴 🔵 🟡 🟢 🔴

Interpretation

• Total tiles = 8
• Pattern width = 4
• Frequency = 2 pattern blocks

QFT asks which repeating pattern can explain the whole wall without conflict and lets quantum interference answer.

You clearly see repetition but imagine You are NOT told how wide the repeating pattern is. The hard question is not if there is a repetition! since it can be seen. but the hard question is:

“What is the smallest pattern that can explain the entire wall?”

That smallest block is the period. QFT tests every possible pattern width at the same time and checks which one fits perfectly without leftovers. It doesn’t slide a ruler across the wall Or compare tile blocks one by one. Let’s explain this a bit further to get a grasp on this qiantum concept:

Imagine trying all pattern widths This is how manual tests looklike:

QFT does this in parallel and not sequentially. For each possible pattern width, rotate a pointer a little bit for every tile. If the pattern is wrong then pointers point everywhere and cancel each other. If the pattern is correct then pointers align to add up. Only the correct pattern survives.

So, after QFT, the result looks like:

Pattern width: 1 2 3 4 5 6 7 8
Confidence:    0 0 0 █ 0 0 0 0

The wall itself tells you:

“I am built from 4-tile blocks.”

The question now everybody will be asking that why Frequency appears instead of Width. QFT matrix naturally describes in form of frequency instead of size.

• Pattern width = 4 tiles
• Total tiles = 8
• Frequency = 2

Meaning:

“This pattern repeats twice across the wall.”

QFT detects how many times the pattern repeats, not how wide it is.

🧠 Each story/analogies I went through above has the following things:

• Repetition => period
• Resolution => number of samples
• Alignment => constructive interference
• Misalignment => cancellation

That is exactly what QFT exploits.

Too much talking now! Let’s come back to our subject. I will now see how these things like roots of unity or QFT connected to Shor’s Algorithm. If we replace:

Tiles replace with values of ( a^x mod N )
Wall replace with full superposition or QFT

Pattern width = period ( r )

QFT finds: “How many times does the hidden pattern repeat?”

That’s all Shor needs for the next step which is multiplying the pattern by QFT matrix. I touchbased on this during analogies in QFT matrices. This is just a fast follow of that. When pattern is multiplied by QFT matrix most rows cancel out (destructive interference). Only, rows matching the correct frequency add up (constructive interference)

An example result looks like:

y = [0, 0, 0, 4, 0, 0, 0, 0]

Smallest non-zero entry tells the frequency of vector sequence.

🔹 Why Multiplying QFT × Periodic Sequence Creates Mostly Zeros

Wrong frequency rows:

• Roots of unity point in all directions
• Vector sum cancels to zero

Correct frequency row:

• Phases align
• Magnitudes add

This is not magic but constructive and desctructive quantum interference.

Imagine if a traditional method took centuries to crack a 2048-bit key, while Shor’s Algorithm swept through it in mere milliseconds. All that hard work we put into crafting secure systems might just be for naught against a burgeoning quantum frontier. The power of quantum bits can carry a massive load, allowing multiple calculations to occur simultaneously. Where classical methods make heavy weather, our quantum equivalent blitzes through the process as if riding a stallion compared to a plodding mule.

PRACTICAL IMPLICATIONS

1. Qubit Requirements for Different RSA Key Sizes

Now, let’s dive into the nitty-gritty of what it takes to get quantum computers working against RSA encryption. Here’s the breakdown for key sizes:

2048-bit RSA: Mind your saddle! This monster needs around 4,000–6,000 logical qubits.

4096-bit RSA: That bruiser jumps to a staggering 8,000–12,000 logical qubits.

2. Error Correction Overhead Needed

Quantum computing isn’t all sunshine and rainbows. Error correction remains a hurdle taller than a mountain. Achieving reliable quantum computation requires hefty overhead due to the delicate nature of qubit states. However, this cowboy hat ain’t all glitz and glam. The technical challenges loom large: coherence times, error rates, and scaling up physically capable systems without losing integrity.

As we ride into this uncertain frontier of quantum computing, be vigilant and proactive. It’s our collective duty to ensure that the wild west of digital security stays within our control. So tighten those saddles, folks! The future’s not just coming — it’s barreling down the trail, and we need to be ready to embrace it.

There you have it, partner — a comprehensive guide to the shifting winds of quantum computing and its blossoming relationship with cryptography. As we saddle up for new adventures, keep your head sharp and your circuits ready; we’re just getting warmed up.

I would also like to add some useful notes based on my experiments and observations:

1. “Divide frequency by matrix width to get period”

This is exactly what Shor uses.

2. In Shor’s algorithm:

• This sequence is periodic
• QFT extracts the frequency
• Frequency → period (r)
• Period → factors using:

QFT does NOT give public and private keys directly It gives the period, which allows factoring (N)

Once (N) is factored → RSA private key falls.

References:

1. Quantum COmputing Algorithms by Barry Burd
2. Step by Step Shor’s algorithm