This competition is part of the
Bradford Quantum Hackathon 2025. Please join the event on Aqora and ensure to follow the rules specified there.
Form your teams using the Team Settings Tab!
Classical and Quantum Cryptography
Overview
In cryptography, integer factorization entails finding the prime factors that multiply to produce a number ( n ), called the modulus. For small numbers, this is easy to do by hand. However, as the modulus grows bitwise, the number of possible prime pairs ( p ) and ( q ) increases astonishingly quick, making the problem of breaking encryption computationally difficult, or even infeasible.
In practical cryptographic applications, ( n ) is extremely large for security. Many systems use public and private keys:
- Public key: Used to encrypt or verify information.
- Private key: Used to decrypt or sign information.
Below are examples of classical cryptographic systems and their mathematical underpinnings.
RSA (Rivest–Shamir–Adleman)
Mathematical Foundation
RSA is based on the integer factorization problem: given ( n = p \times q ), it is computationally hard to find ( p ) and ( q ) when ( n ) is large.
n=p×q,φ(n)=(p−1)(q−1)
Encryption:
c=memodn
Decryption:
m=cdmodn
where
e×d≡1(modφ(n)).
# RSA Encryption/Decryption Example
def egcd(a, b):
if b == 0:
return a, 1, 0
g, x1, y1 = egcd(b, a % b)
return g, y1, x1 - (a // b) * y1
def modinv(a, m):
g, x, _ = egcd(a, m)
if g != 1:
raise Exception("No modular inverse")
return x % m
# Step 1: Choose primes and compute modulus
p, q = 61, 53
n = p * q
phi = (p - 1) * (q - 1)
# Step 2: Choose e and compute d
e = 17
d = modinv(e, phi)
# Step 3: Encrypt and decrypt
m = 123
c = pow(m, e, n)
decrypted = pow(c, d, n)
print(f"Public key: (n={n}, e={e})")
print(f"Private key: d={d}")
print(f"Ciphertext: {c}")
print(f"Decrypted: {decrypted}")
Public key: (n=3233, e=17)
Private key: d=2753
Ciphertext: 855
Decrypted: 123
Strengths
- Well-understood and easily implementable.
- Foundation for many encryption and signature schemes.
Weaknesses
- Security depends on the hardness of factoring ( n ).
- Requires large key sizes (2048+ bits) to be secure.
- Vulnerable to Shor’s algorithm on quantum computers.
Discrete Logarithm Problem (DLP)
Mathematical Foundation
Given a large prime ( p ), a generator ( g ), and a public value ( h = g^x \bmod p ), the challenge is to find ( x ):
gx≡h(modp)
This is computationally difficult for large ( p ) and forms the basis of Diffie–Hellman and ElGamal systems.
# DLP Brute Force Example
def discrete_log(g, h, p):
for x in range(p):
if pow(g, x, p) == h:
return x
return None
p = 23
g = 5
h = 8 # find x such that 5^x ≡ 8 mod 23
x = discrete_log(g, h, p)
print(f"p = {p}, g = {g}, h = {h}")
print(f"Solution: x = {x}")
p = 23, g = 5, h = 8
Solution: x = 6
Pollard’s Rho (Factoring Algorithm)
Mathematical Foundation
Pollard’s Rho is a probabilistic algorithm that finds nontrivial factors of a composite number ( n ) using pseudorandom sequences and the birthday paradox:
f(x)=x2+1(modn)
Iterate values and compute:
gcd(∣xi−x2i∣,n)
until a nontrivial factor is found.
# Pollard's Rho Example
import math
import random
def pollards_rho(n):
if n % 2 == 0:
return 2
f = lambda x: (x**2 + 1) % n
x, y, d = 2, 2, 1
while d == 1:
x = f(x)
y = f(f(y))
d = math.gcd(abs(x - y), n)
return None if d == n else d
n = 8051
factor = pollards_rho(n)
print(f"Found factor: {factor}")
print(f"Other factor: {n // factor}")
Found factor: 97
Other factor: 83
Elliptic Curve Cryptography (ECC)
Mathematical Foundation
ECC is based on the Elliptic Curve Discrete Logarithm Problem (ECDLP):
Given a point ( P ) on an elliptic curve and another point ( Q = kP ), it is hard to determine ( k ).
An elliptic curve over a finite field has the general form:
E:y2=x3+ax+b(modp)
# Simple ECC Example
def point_add(P, Q, a, p):
if P is None:
return Q
if Q is None:
return P
# If x-coordinates are equal and y are negatives → point at infinity
if P[0] == Q[0] and (P[1] + Q[1]) % p == 0:
return None
# Compute slope
if P == Q:
s = (3 * P[0]**2 + a) * pow(2 * P[1], -1, p) % p
else:
denom = (Q[0] - P[0]) % p
inv = pow(denom, -1, p) # Will raise ValueError if not invertible
s = ((Q[1] - P[1]) * inv) % p
# Compute resulting point
x_r = (s**2 - P[0] - Q[0]) % p
y_r = (s * (P[0] - x_r) - P[1]) % p
return (x_r, y_r)
def scalar_mult(k, P, a, p):
R = None
for bit in bin(k)[2:]:
R = point_add(R, R, a, p)
if bit == "1":
R = point_add(R, P, a, p)
return R
# Example curve: y^2 = x^3 + 2x + 3 mod 97
p = 97
a, b = 2, 3
P = (3, 6)
k = 5
Q = scalar_mult(k, P, a, p)
print(f"Base point P = {P}")
print(f"Private key k = {k}")
print(f"Public key Q = {Q}")
Base point P = (3, 6)
Private key k = 5
Public key Q = None
Quantum Computing and Shor’s Algorithm
Background
Quantum computing leverages superposition, interference, and entanglement to perform certain computations exponentially faster than classical methods.
Shor’s Algorithm (1994) efficiently factors large integers by finding the period of modular exponentiation—undermining RSA and ECC.
Mathematical Foundation
Let ( N = p \times q ). Choose ( a ) such that ( \gcd(a, N) = 1 ).
Define:
f(x)=axmodN
The period ( r ) satisfies:
ar≡1(modN)
Once ( r ) is known:
p=gcd(ar/2−1,N),q=gcd(ar/2+1,N)
# Manual Derivation Example: N = 15
import math
N = 15
a = 7
# Compute sequence
seq = [pow(a, i, N) for i in range(1, 5)]
r = 4
p = math.gcd(pow(a, r//2, N) - 1, N)
q = math.gcd(pow(a, r//2, N) + 1, N)
print("Sequence:", seq)
print(f"r = {r}, p = {p}, q = {q}")
Sequence: [7, 4, 13, 1]
r = 4, p = 3, q = 5
from qiskit_aer import Aer
from qiskit import QuantumCircuit, transpile
import math
from math import gcd
# Simple period finding for N=15
def simple_factor(N):
"""Simplified factoring for demonstration"""
for a in range(2, N):
if gcd(a, N) != 1:
factor = gcd(a, N)
return [factor, N // factor]
return None
result = simple_factor(15)
print("Factors found:", result)
# Output: [3, 5]
Factors found: [3, 5]
Summary
| Method | Core Problem | Example Task | Main Weakness |
|---|
| RSA | Integer Factorization | Find (p,q) from (n) | Quantum factoring (Shor) |
| DLP | Discrete Logarithm | Find (x) from (g^x) | Quantum attacks (Shor) |
| ECC | Elliptic Curve Log | Find (k) from (P,Q=kP) | Quantum attacks (Shor) |
| Pollard’s Rho | Factoring (probabilistic) | Find divisor of (n) | Random runtime |
| Shor’s | Quantum Period Finding | Factor (N) via QFT | Needs large-scale qubits |
This extended section introduces the quantum advantage in cryptography. Classical encryption relies on problems that are easy to compute but hard to reverse. Quantum algorithms such as Shor’s transform these systems to be vulnerable and motivating the rise of post-quantum cryptography.
The Use-Case Challenge
The challenge has four N, with unknown identity, it is your task to factor or otherwise provide a solution to find relevant criteria.
Classical, N1 and N2
The classical component of the use-case challenge is intended to give a brief introduction to the mathematical underpinnings of cryptography. N1 is a more trivial problem while N2 is intended to be harder, requiring some algorithmic speedups that may have been mentioned previously.
Quantum, N3 and N4
Then, for the quantum component, there is N3, which is using Aqora's simulator. For N4, this will leverage hardware and may not be addressable until the in-person event, if selected to attend. Please note that solutions for N3 and N4 should be QASM strings that represent the quantum circuit. The reason for this is that simulators may be more idealistic and available than hardware when it comes to handling noise, error, and other relevant mechanisms. Additionally, utilizing real quantum computers can be difficult and limited.
Good Luck!
The team at Project Eleven look forward to all participants interested in approaching these use-case challenges. A member of our team will be monitoring the discussion section to address any concerns or questions. If you are interested in further application of post-quantum cryptography, we have an open challenge called the Q-Day Prize Challenge:
https://www.qdayprize.org/
