Abstract Algebra in Modern Cryptography

, ,

I’ll be honest: when I first took Algebra, I had no idea why we were spending weeks on groups, rings, and fields. As a CS student, I kept thinking “when am I ever going to use this stuff?” Turns out, the answer was everywhere in cryptography.

The Basics

Let’s start simple. A group $(G,\cdot)$ is just a set with an operation that plays nicely. It needs to be closed (stay within the set), associative (grouping doesn’t matter), have an identity element, and every element needs an inverse.

The interesting part is when you map between groups while preserving their structure. This is called a homomorphism:

$$\phi : G \rightarrow H \text{ such that } \phi(a \cdot b) = \phi(a) \star \phi(b)$$

This structure preservation is actually the backbone of many cryptographic systems. Here’s how you might implement this:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
from typing import TypeVar, Generic, Callable

T = TypeVar('T')
S = TypeVar('S')

class Homomorphism(Generic[T, S]):
    """
    A class representing a group homomorphism between two sets.
    
    Attributes:
        mapping_func: The function that defines the homomorphism
    """
    def __init__(self, mapping_func: Callable[[T], S]):
        self.mapping_func = mapping_func
        
    def map(self, element: T) -> S:
        return self.mapping_func(element)

Computing on Encrypted Data

Here’s where things get really cool. Homomorphic encryption lets you do math on encrypted data without ever decrypting it. The math behind it uses ring homomorphisms where both addition and multiplication are preserved:

$$E(x + y) = E(x) \oplus E(y) \text{ and } E(x \cdot y) = E(x) \otimes E(y)$$

Here’s a basic version of how this might work:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
from dataclasses import dataclass

@dataclass
class HomomorphicCipher:
    """
    A basic implementation of partially homomorphic encryption.
    
    Attributes:
        modulus: The modulus for the encryption scheme
        key: The encryption key
    """
    modulus: int
    key: int
    
    def encrypt(self, message: int) -> int:
        return (message * self.key) % self.modulus
    
    def bulk_add(self, ciphertexts: list[int]) -> int:
        """Homomorphically add multiple encrypted values."""
        return sum(ciphertexts) % self.modulus

Why Public Key Crypto Actually Works

Most public key cryptography relies on problems that are easy to compute one way but hard to reverse. Take the discrete logarithm problem:

$$\text{Given } g^x \equiv h \pmod{p}, \text{ find }x$$

Computing $g^x \bmod p$ is straightforward, but finding $x$ when you only know $g$, $h$, and $p$ is computationally brutal for large primes. This difficulty gap is what keeps your encrypted messages safe.

Connecting the Dots

The thing that finally clicked for me was realizing that the same mathematical patterns show up everywhere. Group theory helps us understand molecular structures and also builds secure communication systems. It’s not a coincidence.

After spending way too many late nights in the NTNU library, I started seeing these connections everywhere. What began as “just another required math course” turned into understanding how the same fundamental patterns work across completely different fields. The abstract becomes practical when you see how these mathematical structures actually solve real problems.

That’s what I find most interesting about this stuff. It’s not just theory for theory’s sake. These mathematical tools give us a way to spot the underlying patterns that connect seemingly unrelated problems, whether that’s in cryptography, physics, or computer science.