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?” Turns out, it’s 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 is pretty wild - you can do math on encrypted data without decrypting it. 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.

Connecting the Dots

Group theory shows up in molecular structures, cryptographic systems, and a bunch of other places. After too many late nights in the NTNU library, I started noticing these patterns everywhere. What started as “just another required math course” became useful for understanding how cryptography actually works.

The cool part is seeing how abstract math solves real problems. You learn about groups and homomorphisms in a pure math context, then suddenly you’re using the exact same concepts to encrypt data or build secure protocols. It’s the same toolkit, just applied differently.