Why Abstract Algebra in Cryptography?

Question

I come from an engineering background, but not from computer science or anything to do with pure math. I studied applied math in college--never abstract algebra, number theory, or discrete math, formally. I have been a programmer most of my career.

Having developed a keen interest in cryptography, I learned number theory and abstract algebra on my own, and I get the role of number theory: in factoring prime numbers and the discrete logarithm problem for PKI. These are both hard problems.

However, why discrete log over a group? What is the significance of a group here? Why do we need a group?

Why use abstract algebra? I know AES uses Galois fields. I understand how, but I cannot figure out why.

I mean, why use finite field arithmetic?

Why should the arithmetic be done in a group? Why an Abelian group? Why a polynomial? Why are the closure, inverses, and identities necessary to AES?

Likewise, what other advantages do groups, rings, and fields have for cryptography? How exactly are the characteristics of finite fields indispensable for AES and cryptography in general? Why couldn't this be achieved without finite fields? Likewise, for other uses of abstract algebra in cryptography...

Answer 1

• Abstract algebra basically comprises Groups, Rings, Fields, Vector Spaces, Modules, and many other algebraic structures. It is not only useful in Cryptography but in Channel Coding, in the branch of Chemistry and Physics too. It is a tool like Groups where you can do arithmetic and algebraic operation under a closed set. One can compare two algebraic structures and find similarities between them and use these properties further.

• Now your question about AES and Galois Field. if you do arithmetic operation on the matrix of AES, say multiplying two bytes $\texttt{0xEF}$ and $\texttt{0xDC}$, without finite field your many arithmetic operations go beyond 1 byte of length. Finite field make sure that it will remain within the closed set by reducing to modulo.

• for example; if you take the finite field created by the prime number 11 ($\mathbf{Z}^*_{11}$) the set only contains $\{1,2,\ldots,10\}$ elements. All operations are done within this set. Then only you can substitute bytes find inverses when you decrypt AES encrypted ciphertext.

  if you don't use them, strictly speaking without irreducible polynomial (like in AES it is $x^8+x^4+x^3+x+1$) or prime number, where it makes sure that all length of all operations ends up in byte and hence easy to find their unique inverses while decryption.

Answer 2

Here is a more general perspective - I see the role of abstract algebra in cryptography to be two-fold - 1) Efficient implementation of algorithms, 2) To be able to prove that the design is secure against attacks. These two points are different sides of the same coin - they give us control over the apparent randomness of a cipher. To elaborate and give examples from AES:

1. Imagine a cipher which encrypts 128-bit messages to 128 bits of ciphertext. What would you do if you wanted to avoid any form of algebra altogether? A straightforward way would be to create key dependent lookup tables of sizes $2^128$ bits to translate the messages to ciphertexts. But this would take up an inordinate amount of memory. Instead, what we do in practice is to perform algebraic manipulations on plaintexts and hope to get what looks like random looking ciphertexts. Case in point from AES: Look at how the Rijndael Sbox is instantiated - this is given in the form of an affine transformation, which allows a designer to generate the Sbox on chip (Ignore security issues for now) to save memory instead of storing the whole table.

Public-key cryptography is also largely based on the above principle - the intended recipient of a message has access to a key, which gives access to knowledge about some algebraic structure behind the encryption algorithm which allows him to efficiently decrypt the cipher text. Look at code-based cryptosystems based on error correcting codes, for example.

2. Cryptographers would like to design ciphers for which they can prove has certain security properties, rather than having a cipher do 'random things' to a message and hope that a cryptanalysis does not find any patterns. For instance, one well-known attack is the interpolation attack, which tries to find algebraic relations between plaintext and ciphertext. Using techniques from algebra one can design ciphers that a provably resistant to such attacks.

Example from AES: The mixcolumns step tries to spread 'randomness' from one byte in the input to several bytes in the output. Instead of doing it 'randomly', this is done using a matrix multiplication with a matrix called an MDS matrix. One consequence of using this matrix is that one can prove that AES has 128-bit security against differential cryptanalysis. See the design rationale behind AES for more information.

I hope this gives a broad high-level idea of why abstract algebra is used in cryptography.