9 ms·

> Part 1 > Mathematical Background > Before we tackle cryptography we need to cover some basic facts from mathematics. Nit: we really don't. This reminds me

> Part 1 > Mathematical Background > Before we tackle cryptography we need to cover some basic facts from mathematics. Nit: we really don't. This reminds me of how dry and uninspired the cryptography and cryptology (less so) classes I took almost 20 years ago were.

l33t233372 3y ago
Can you explain why? It’s my understanding that every cryptographic algorithm is based on math, much of it not so simple.
- dragontamer 3y ago
  The opposite IMO, we're just bad at explaining it. There's two strategies: substitution and permutations. Substitutions is when you replace a set of bits with another set of bits (ex: ABCD might become IAQN). Permutations is when you move bits around (ex: ABCD might become CADB). When you mix substitutions with permutations, and then loop like 10+ times, it becomes really hard to follow. Bam, cryptography algorithms. ---------- How do you build substitutions and permutations that are hard to follow? Well, it seems like substitutions are the hard one, permutations seem relatively straight forward to me in most block ciphers (AES is really easy: a rotation to the right, and then a column-wide rotation. All of the bytes are in a 4x4 matrix, for the 16-bytes. Its actually super easy to follow AES's permutation steps). Substitutions need to be done in such a way that is resistant to pattern-matching / cryptoanalysis. Choosing random numbers is not sufficient. For this, we enter "math", such as galois fields. Galois Fields looks complex, but that's only because you haven't learned them yet. All a Galois Field is... is a set of numbers (such as 0, 1, 2, 3, 4, in the GF(5) field) that have addition, addition-inverse, multiplication, and multiplication-inverse. Note: Galois Fields manage to accomplish this by reinventing the definition of addition and multiplication. Ignoring this... weirdness... its rather straight forward. Every operation can be inverted (not just addition and multiplication... but also complex algorithms like exponents, logarithms, square roots and more). Once we're assured that both addition and multiplication can be perfectly inverted, we can build substitutions that are perfect... and then use math to prove that it should be hard to invert (though always possible to invert, due to both addition and multiplication having inverting-steps). Proving that these things are "hard to reverse" with cryptoanalysis is beyond the scope of most student's study. So Cryptography courses go into Galois fields but forget to tell you why the hell you're studying it in the first place. -------- In practice, we just show off AES's S-box (substitution box), that says which bytes get replaced with new bytes. And vice versa (https://en.wikipedia.org/wiki/Rijndael_S-box https://en.wikipedia.org/wiki/Rijndael_S-box). The GF(2^8) extension field just is a complex way of saying 8-bit numbers using this weird "addition-changed / multiplication-changed" math system that has guarantees of reversal / invertions.
  - AlotOfReading 3y ago
    It's hinted at in your post, but to make it more explicit we use GF(2^n) mainly because using it means arithmetic can be efficiently implemented with bitwise operations on digital computers. The whole mathematical machinery of modern crytography is a weird hybrid between the kinds of math computers can do quickly and the kinds of math that are easy to analyze for humans.
    - bawolff 3y ago
      I always thought that aes to prove to the world that the NSA didnt bribe people to choose bad random s-boxes. People used to worry about that with DES (turned out they actually changed the numbers of des to fix a not publicly known attack) I dont see how aes use of gf(2^8) based sboxes have any implication for speed, but maybe i am out of my depth.
    - dragontamer 3y ago
      GF(2^n) Galois Field numbers are actually somewhat inefficient at multiplication. At least, in the 90s when AES was invented (today we have pmull and carryless-multiplication that speeds things up, but its still overall slow compared to normal multiplication). Because of this, modern ciphers prefer Add-Xor-Rotate ciphers instead of Galois Field operations. As it turns out, Add-Xor-Rotate groups are provably invertible too, and are far, far more efficient to run than Galois Field operations.
      - adrian_b 3y ago
        Fast Galois Field operations are significantly cheaper to implement in hardware. The only reason why they may be slower in software is because the Intel and AMD CPUs already had fast integer operations, but neither Intel nor AMD have bothered to also provide a fast implementation of carry-less multiplication on most of their CPU models (though on most recent models the speed is adequate for polynomial authentication done concurrently with AES encryption).
  - bawolff 3y ago
    I'm confused, how is this not explaining math? That all sounds like math. Not to mention this is basically an eli5 for what is a block ciphers (or aes specificly). If you are actually studying block ciphers you'll need to learn much more than that. Additionally, Block ciphers are just one part of cryptography - i think this thread was more about ECC.
- grog454 3y ago
  My claim as that we don't need to cover math before we tackle cryptography, and my reasoning is that there is more than one way to approach a topic. Here's a discussion of cryptography that has 0 occurrences of "ring" (for example): https://en.wikipedia.org/wiki/Cryptography https://en.wikipedia.org/wiki/Cryptography
  - charlieyu1 3y ago
    There are plenty of books about practical side of cryptography. This one goes much deeper than that. And how do you explain elliptic curves without using fields?
  - Forgeties79 3y ago
    > My claim as that we don't need to cover math before we tackle cryptography I’ll just be blunt here. This is incredibly nitpicky to the point where I’m not even sure what you’re trying to accomplish or add here.
  - a--n--b 3y ago
    The page you link gives a surface-level description on the area and common techniques. Any remotely detailed explanations on specific topics demand mathematical foundations to be established, which is the approach most respectable cryptography _books_ adopt. If you allow me to substitute “ring” with “field,” the phrase immediately appears in technique-specific pages (see elliptic curve cryptography: https://en.m.wikipedia.org/wiki/Elliptic-curve_cryptography https://en.m.wikipedia.org/wiki/Elliptic-curve_cryptography) Undergraduate/graduate cryptography courses don’t teach from Wikipedia articles for a reason. It would be a disservice to those learning cryptography to discount the pivotal role of mathematics in the field.
Vervious 3y ago
I agree that they shouldn't dump it all into chapter 1. But, when learning any cryptographic scheme, in order to understand what is going on, it is certainly necessary to learn the corresponding mathematical tools. Even to define what it means for a scheme to be secure requires a good grasp of probability (and negligible functions in the asymptotic regime).
dperrin 3y ago
I’m curious why you think mathematics doesn’t need to be covered here. Immediately after covering the maths background, the author jumps into elliptic curves and I can’t think of how to understand that without understanding a little bit finite fields and groups. The maths covered seems essential for almost the entire last third of the book.
sanderjd 3y ago
Maybe cryptography isn't for you? It's one of those things where, yes, the math is important.
computerfriend 3y ago
Aside from totally disagreeing, I also don't see what's dry or uninspired about mathematics.

l33t233372 3y ago

Can you explain why? It’s my understanding that every cryptographic algorithm is based on math, much of it not so simple.

dragontamer 3y ago
The opposite IMO, we're just bad at explaining it. There's two strategies: substitution and permutations. Substitutions is when you replace a set of bits with another set of bits (ex: ABCD might become IAQN). Permutations is when you move bits around (ex: ABCD might become CADB). When you mix substitutions with permutations, and then loop like 10+ times, it becomes really hard to follow. Bam, cryptography algorithms. ---------- How do you build substitutions and permutations that are hard to follow? Well, it seems like substitutions are the hard one, permutations seem relatively straight forward to me in most block ciphers (AES is really easy: a rotation to the right, and then a column-wide rotation. All of the bytes are in a 4x4 matrix, for the 16-bytes. Its actually super easy to follow AES's permutation steps). Substitutions need to be done in such a way that is resistant to pattern-matching / cryptoanalysis. Choosing random numbers is not sufficient. For this, we enter "math", such as galois fields. Galois Fields looks complex, but that's only because you haven't learned them yet. All a Galois Field is... is a set of numbers (such as 0, 1, 2, 3, 4, in the GF(5) field) that have addition, addition-inverse, multiplication, and multiplication-inverse. Note: Galois Fields manage to accomplish this by reinventing the definition of addition and multiplication. Ignoring this... weirdness... its rather straight forward. Every operation can be inverted (not just addition and multiplication... but also complex algorithms like exponents, logarithms, square roots and more). Once we're assured that both addition and multiplication can be perfectly inverted, we can build substitutions that are perfect... and then use math to prove that it should be hard to invert (though always possible to invert, due to both addition and multiplication having inverting-steps). Proving that these things are "hard to reverse" with cryptoanalysis is beyond the scope of most student's study. So Cryptography courses go into Galois fields but forget to tell you why the hell you're studying it in the first place. -------- In practice, we just show off AES's S-box (substitution box), that says which bytes get replaced with new bytes. And vice versa (https://en.wikipedia.org/wiki/Rijndael_S-box https://en.wikipedia.org/wiki/Rijndael_S-box). The GF(2^8) extension field just is a complex way of saying 8-bit numbers using this weird "addition-changed / multiplication-changed" math system that has guarantees of reversal / invertions.
- AlotOfReading 3y ago
  It's hinted at in your post, but to make it more explicit we use GF(2^n) mainly because using it means arithmetic can be efficiently implemented with bitwise operations on digital computers. The whole mathematical machinery of modern crytography is a weird hybrid between the kinds of math computers can do quickly and the kinds of math that are easy to analyze for humans.
  - bawolff 3y ago
    I always thought that aes to prove to the world that the NSA didnt bribe people to choose bad random s-boxes. People used to worry about that with DES (turned out they actually changed the numbers of des to fix a not publicly known attack) I dont see how aes use of gf(2^8) based sboxes have any implication for speed, but maybe i am out of my depth.
  - dragontamer 3y ago
    GF(2^n) Galois Field numbers are actually somewhat inefficient at multiplication. At least, in the 90s when AES was invented (today we have pmull and carryless-multiplication that speeds things up, but its still overall slow compared to normal multiplication). Because of this, modern ciphers prefer Add-Xor-Rotate ciphers instead of Galois Field operations. As it turns out, Add-Xor-Rotate groups are provably invertible too, and are far, far more efficient to run than Galois Field operations.
    - adrian_b 3y ago
      Fast Galois Field operations are significantly cheaper to implement in hardware. The only reason why they may be slower in software is because the Intel and AMD CPUs already had fast integer operations, but neither Intel nor AMD have bothered to also provide a fast implementation of carry-less multiplication on most of their CPU models (though on most recent models the speed is adequate for polynomial authentication done concurrently with AES encryption).
- bawolff 3y ago
  I'm confused, how is this not explaining math? That all sounds like math. Not to mention this is basically an eli5 for what is a block ciphers (or aes specificly). If you are actually studying block ciphers you'll need to learn much more than that. Additionally, Block ciphers are just one part of cryptography - i think this thread was more about ECC.
grog454 3y ago
My claim as that we don't need to cover math before we tackle cryptography, and my reasoning is that there is more than one way to approach a topic. Here's a discussion of cryptography that has 0 occurrences of "ring" (for example): https://en.wikipedia.org/wiki/Cryptography https://en.wikipedia.org/wiki/Cryptography
- charlieyu1 3y ago
  There are plenty of books about practical side of cryptography. This one goes much deeper than that. And how do you explain elliptic curves without using fields?
- Forgeties79 3y ago
  > My claim as that we don't need to cover math before we tackle cryptography I’ll just be blunt here. This is incredibly nitpicky to the point where I’m not even sure what you’re trying to accomplish or add here.
- a--n--b 3y ago
  The page you link gives a surface-level description on the area and common techniques. Any remotely detailed explanations on specific topics demand mathematical foundations to be established, which is the approach most respectable cryptography _books_ adopt. If you allow me to substitute “ring” with “field,” the phrase immediately appears in technique-specific pages (see elliptic curve cryptography: https://en.m.wikipedia.org/wiki/Elliptic-curve_cryptography https://en.m.wikipedia.org/wiki/Elliptic-curve_cryptography) Undergraduate/graduate cryptography courses don’t teach from Wikipedia articles for a reason. It would be a disservice to those learning cryptography to discount the pivotal role of mathematics in the field.

Vervious 3y ago

I agree that they shouldn't dump it all into chapter 1. But, when learning any cryptographic scheme, in order to understand what is going on, it is certainly necessary to learn the corresponding mathematical tools. Even to define what it means for a scheme to be secure requires a good grasp of probability (and negligible functions in the asymptotic regime).

dperrin 3y ago

I’m curious why you think mathematics doesn’t need to be covered here. Immediately after covering the maths background, the author jumps into elliptic curves and I can’t think of how to understand that without understanding a little bit finite fields and groups. The maths covered seems essential for almost the entire last third of the book.

sanderjd 3y ago

Maybe cryptography isn't for you? It's one of those things where, yes, the math is important.

computerfriend 3y ago

Aside from totally disagreeing, I also don't see what's dry or uninspired about mathematics.