Attacking a congruential public key cryptosystem using Gaussian lattice reduction in 2 dimension¶
In this example we use our library to first construct a Congruential Public Key Cryptosystem and then attack it and retrieve private key using Gaussian lattice reduction.
Congruential Public Key cryptosystem¶
Key creation¶
We start by choosing a large integer modulus $q$ which will be a public parameter of the cryptosystem.
Then we need to choose two secret integers $f$ and $g$ that will form private key such that:
$$
\begin{aligned}
0 < &f < \sqrt{q/2} \\
\sqrt{q/4} < &g < \sqrt{q/2}
\end{aligned}
$$
We will be calculating multiplicative modular inverses so we need to make sure that they exists:
$$
\begin{aligned}
\gcd(f,q) &= 1 \\
\gcd(f,g) &= 1
\end{aligned}
$$
we then calculate
$$
h \equiv f^{-1} g \mod{q}
$$
that value will serve as our public key.
Let's see this in code
from lbpqc.primitives.integer import integer_ring
import math
q = 122430513841
f = 231241
g = 195698
assert 0 < f < (q/2) ** 0.5
assert (q/4) ** 0.5 < g < (q/2) ** 0.5
assert math.gcd(f, q * g) == 1
h = (integer_ring.modinv(f,q) * g) % q
public_key = h
private_key = (f,g)
print("private key:", private_key)
print("public key:", public_key)
private key: (231241, 195698) public key: 79751031608
Encryption¶
In order to perform encryption we have to chose plaintext integer $m$ that we want to encrypt and random integer $r$ that will serve as noise.
$m$ must satisfy $ 0 < m < \sqrt{q/4} $ and $r$ must satisfy $ 0 < r < \sqrt{q/2} $.
We can then use public key $h$ to compute ciphertext $e$ with the following formula:
$$
e \equiv rh + m \mod{q}
$$
m = 123456
r = 101010
assert 0 < m < (q/4) ** 0.5
assert 0 < r < (q/2) ** 0.5
h = public_key
e = (r * public_key + m) % q
plaintext = m
ciphertext = e
print("plaintext:", plaintext)
print("ciphertext:", ciphertext)
plaintext: 123456 ciphertext: 91183651259
Decryption¶
We will use private key to decrypt the message. First we compute the intermidiate value
$$
a \equiv fe \mod{q}
$$
and then retrieve the plaintext
$$
b \equiv f^{-1}a \mod{g}
$$
it's important to notice that we calculate multiplicative inverse of $f$ modulo $g$ this time and not modulo $q$ as we did when creating the key.
The $b$ should be equal plaintext $m$.
f,g = private_key
e = ciphertext
a = (f * e) % q
b = (integer_ring.modinv(f, g) * a) % g
print("decrypted message:", b)
assert b == plaintext
decrypted message: 123456
Attacking the cryptosystem¶
Unfortunetly this cryptosystem isn't very secure. In order to break it, all the attacker needs is to find two positive integers $F$ and $G$ that will satisfy the following equation
$$
Fh \equiv G \mod{q}
$$
and this integers have to be sufficiently small
$$
F = \mathcal{O}(\sqrt{q}) \quad \textrm{and} \quad G = \mathcal{O}(\sqrt{q})
$$
We can rewrite this congruence as
$$
Fh = G + qR
$$
It's then quite easy to reformulate this problem into finding shortest vector in lattice.
Let's define two vectors
$$
\begin{aligned}
v_1 &= (1,h)\\
v_2 &= (0,q)
\end{aligned}
$$
To break the cryptosystem we have to find a linear combination
$$
\boldsymbol{w} = a_1 \boldsymbol{v_1} + a_2 \boldsymbol{v_2}; \quad a_1, a_2 \in \mathbb{Z}
$$
such that $\boldsymbol{w}$ has length $\mathcal{O}(\sqrt{q})$.
To put it in a lattice's terms. We need to find a short nonzero vector in the set of two-dimensional lattice
$$
L = \{a_1 \boldsymbol{v_1} + a_2 \boldsymbol{v_2} \; : \; a_1, a_2 \in \mathbb{Z} \}
$$
It turns out that for two dimensional lattices this problem is quite trivial
Gaussian Lattice Reduction in Dimension 2¶
from lbpqc.primitives.lattice import reductions
import numpy as np
v1 = np.array([1,h])
v2 = np.array([0,q])
V = np.array([v1, v2])
W = reductions.GLR_2dim(V)
w1 = W[0]
w2 = W[1]
print("w1:", w1, "||w1||:", np.linalg.norm(w1))
print("w2:", w1, "||w2||:", np.linalg.norm(w2))
F, G = np.rint(w1).astype(int)
print()
print("F:", F)
print("G:", G)
print("secret f:", f)
print("secret g:", g)
w1: [-231241. -195698.] ||w1||: 302935.8138038486 w2: [-231241. -195698.] ||w2||: 410253.69316192635 F: -231241 G: -195698 secret f: 231241 secret g: 195698
As we can see using only public parameters of the cryptosystem, we managed to retrieve secret key by interpreting the underlying problem as SVP in dimension 2 Lattice.