There are also some basic practical exercises (I don't believe the projects are technically related, but are in similar veins): https://cryptopals.com/
My graduate Applied Cryptography class used Katz and Lindell's "Introduction to Modern Cryptography." It's widely used at top institutions. While it definitely can be intimidating at time, the authors provides a classical approach to the topic.
I found it had a nice balance of theory and application.
That's the author's page for the book. The 3rd edition was originally published in 2008 and last updated in 2013. He has another book (linked from that page) which, from browsing the TOC, appears to cover the same or similar material but was published in 2015.
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).
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.
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.
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.
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.
All encryption, hashing, ECC, etc. etc. is about taking advantage of invertible operations.
Encryption needs to be inverted. So that's easy enough to understand. Hashing (and cryptographic hashes) need to be inverted because of the pigeon-hole principle. If we have a space of 1000 numbers, we want 1000 unique hashes to 'maximize the space'.
Turns out that the easiest way to accomplish this is through invertible functions, because if there's 1000 numbers that hash into 1000 other numbers, that's called a 1-to-1 and onto function, which is also the requirement for invertibility.
Any other setup, say 1000 numbers that turn into 500 numbers, weakens the hash obviously (two numbers collide for no reason), while the reverse 1000 numbers into 1500 numbers, is impossible.
---------
Once you realize that invertibility is the key to all of these algorithms, then its very straightforward. Its just a bunch of math that most simply accomplishes the goal.
The reason why crypto-math "looks" hard is because no one teaches the motivation behind the primitives. Its not like Galois Fiels are randomly used you know, mathematicians liked the properties of Galois Fields... and how easy it is to invert those operations.
> Hashing (and cryptographic hashes) need to be inverted because of the pigeon-hole principle. If we have a space of 1000 numbers, we want 1000 unique hashes to 'maximize the space'.
This is non-sensical and false.
Hash functions are not invertible. They are not injective functions. The domain is much larger than their range. You can hash multi gb files and get a small fixed size result. Furthermore, the entire point of a hash function is to not be invertible
To be clear invertibility (and especially trap door invertibility) is quite important in crypto. After all - it is mostly the study of secret messages - no point to that if you cant unscramble the message.
However understanding the goal is not the same as understanding how it works and how it fails. There is a long journey going from invertible functions are cool to wtf is an eliptic curve. The point of a course in cryptography isn't to teach people just what a cipher does as a black box, but to teach them how it works under the hood.
> Its not like Galois Fiels are randomly used you know, mathematicians liked the properties of Galois Fields... and how easy it is to invert those operations.
If you mean in the context of aes s-boxes, Other block ciphers do not do that. The important aspect was their non linearity not invertibility. Any valid sbox is going to be invertible.
> Once you realize that invertibility is the key to all of these algorithms, then its very straightforward.
I'd be curious how you connect this to zero knowledge proofs
No, it is what you say that is false. Please examine the inner structure of any widespread secure hash algorithm.
It is not possible to construct a complex-enough hash function with predictable properties (like being surjective and having equiprobable output values) from simpler non-invertible functions.
All good hash functions are made from a combination of invertible functions, over which some trick is used to make the resulting hash function non-invertible.
For instance, a non-invertible hash function (for a fixed input length) can be obtained as the sum of two invertible functions. For simplicity, one of the two invertible functions may be the identity function, as it is done in SHA-1, SHA-2 and a very large number of other frequently used hash functions.
Using such a hash function with fixed input length, there are many methods to extend it to work with a variable input length.
You went from hash functions are invertible to hash functions contain subroutines that are invertible. Which is true of pretty much everything.
> For instance, a non-invertible hash function can be obtained as the sum of two invertible functions. For simplicity, one of the two invertible functions may be the identity function, as it is done in SHA-1, SHA-2 and a very large number of other frequently used hash functions.
I dont understand what you are trying to reference here? Are you trying to claim that the compression function in a Merkle–Damgård hash function is invertible? Because it isn't (or at the very least usually designed in such a way that we do not know how to)
> You went from hash functions are invertible to hash functions contain subroutines that are invertible.
No. You misunderstood from the start because you apparently didn't recognize that SHA256 is built from an invertible block cipher named Davies–Meyer, and have probably googled the structure afterwards and then double-downed on the Merkle–Damgård compression function.
SHA256 is built up from an invertible block cipher for a reason. Invertibility has many important properties, one of which is the maximization of entropy while mixing the 256-bits of state into 256-bits of new-state.
Anyone who knows the internal structure of modern hashes knows what I'm talking about. Modern encryption is hugely built from one-to-one and onto functions. Its just the easiest way to prove various features.
Yes, even hash functions.
---------
BTW: Please pay attention to usernames as well. You're yelling at a fellow poster who is... erm... not me.
I have already written how most compression functions used in a Merkle–Damgård hash function are made to be non-invertible, by taking an invertible function and summing the input with the output (using the input means using the identity function of the input, which is the simplest invertible function).
Only with such methods it is possible to guarantee adequate mathematical properties for the compression function. Otherwise, if non-invertible functions are composed, the properties of the compound function are unpredictable, especially after the very large number of rounds (i.e. of function compositions) that are used in a practical hash function.
For anyone who might want to design a custom hash function it is critical to understand the importance of invertible functions, which is based on the fact that if you compose two invertible functions you get a function that is also invertible. Only this property allows predictions about the statistical characteristics of the result that is obtained after tens or hundreds of function compositions.
You can take the compression function of e.g. SHA-256, remove the final step that converts the invertible function into a non-invertible function, and you get a decent (invertible) block cipher function.
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.
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.
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).
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.
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.
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.
https://www.goodreads.com/book/show/56242724-codebreaking
https://www.goodreads.com/book/show/17994.The_Code_Book
https://www.goodreads.com/book/show/98610.Colossus