Intro to Cryptography [pdf] (2011)
cs.umd.edu
cs.umd.edu
https://www.goodreads.com/book/show/56242724-codebreaking
There are also some basic practical exercises (I don't believe the projects are technically related, but are in similar veins): https://cryptopals.com/
It goes more in depth of understanding mathematics behind but less in scope — there are no elliptic curves, for example.
I found it had a nice balance of theory and application.
I find Internet Archive's first capture in 2013: <https://web.archive.org/web/20230000000000*/https://www.cs.u...>
This is the class that links to the book. Fall 2011
$ curl -s --head https://www.cs.umd.edu/~waa/414-F11/IntroToCrypto.pdf | grep last-modified
last-modified: Wed, 07 Sep 2011 17:07:09 GMTThat'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.
Though that doesn't appear to be a code repo.
https://github.com/NigelSmart/nigelsmart.github.io/tree/mast...
> 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.
It’s my understanding that every cryptographic algorithm is based on math, much of it not so simple.
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).
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 dont see how aes use of gf(2^8) based sboxes have any implication for speed, but maybe i am out of my depth.
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.
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).
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.
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.
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
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)
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.
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.
Here's a discussion of cryptography that has 0 occurrences of "ring" (for example): https://en.wikipedia.org/wiki/Cryptography
And how do you explain elliptic curves without using fields?
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.
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)
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.
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).