5
$\begingroup$

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...

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ What exactly are the alternative structures that you would want to use? $\endgroup$
    – Maeher
    Nov 26, 2020 at 9:56

1 Answer 1

Reset to default
6
$\begingroup$

  • 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.

Improve this answer
$\endgroup$
1
  • 3
    $\begingroup$ Addition: we need a field in AES (rather than some other finite set with some internal laws) so that $a*(b+c)=(a*b)+(a*c)$ holds, and elements except $0$ have an inverse, so that we can multiply by a matrix in MixColumns and that can be undone my multiplying by the inverse of the matrix, because that's the principle of inverting MixColumns on decryption. And then, because we want the set to be bytes, and there are $2^8$ of these, we demonstrably have no other field than $\text{GF}(2^8)$ to choose from. $\endgroup$
    – fgrieu ♦
    Nov 26, 2020 at 16:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.