Abstract Algebra in Modern Cryptography

, ,

When I first took Algebra, I had no idea why we spent weeks on groups, rings, and fields. I kept asking myself “when will I actually use this?” I found out later that it shows up everywhere in cryptography.

The Basics

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.

Things get interesting when you map between groups while keeping their structure intact. That’s 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

Homomorphic encryption lets you do math on encrypted data without decrypting it, which still blows my mind a little. The math 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.

Looking back

After too many late nights in the NTNU library, I started noticing these patterns everywhere. What started as “just another required math course” turned out to be useful for understanding how cryptography actually works.

The part I didn’t expect: you learn about groups and homomorphisms in a pure math context, then six months later you’re using the exact same concepts to encrypt data or build secure protocols. Same toolkit, different application. I kind of wish someone had told me that earlier.