6 ms·

Intro to Cryptography [pdf] (2011)

174 points by seamac3 3y ago

IceHegel 3y ago
Is the latex code on github? The margins are a bit off.
- dredmorbius 3y ago
  Possiibly here: <https://nigelsmart.github.io/Crypto_Book/ https://nigelsmart.github.io/Crypto_Book/> Though that doesn't appear to be a code repo.
  - gurjeet 3y ago
    I think this is what you're looking for: https://github.com/NigelSmart/nigelsmart.github.io/tree/master/Crypto_Book https://github.com/NigelSmart/nigelsmart.github.io/tree/mast...
    - dredmorbius 3y ago
      Thanks!
grog454 3y ago
> 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.
- 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.
ChrisArchitect 3y ago
(2011)
- dredmorbius 3y ago
  Based on what? I find Internet Archive's first capture in 2013: <https://web.archive.org/web/20230000000000*/https://www.cs.umd.edu/~waa/414-F11/IntroToCrypto.pdf https://web.archive.org/web/20230000000000*/https://www.cs.u...>
  - NhanH 3y ago
    https://www.cs.umd.edu/~waa/UMD/CMSC414-F11.html https://www.cs.umd.edu/~waa/UMD/CMSC414-F11.html This is the class that links to the book. Fall 2011
    - dredmorbius 3y ago
      Thanks!
  - _kst_ 3y ago
    $ 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 GMT
  - Jtsummers 3y ago
    https://nigelsmart.github.io/Crypto_Book/ https://nigelsmart.github.io/Crypto_Book/ 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.
deleted 3y ago
[deleted]
obnauticus 3y ago
Tbh Cryptography Engineering by Niels Ferguson is a very good and practical intro to this topic.
- a--n--b 3y ago
  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.
xavdid 3y ago
Another good resource on intro crypto is @lvh's Crypto101 book: https://www.crypto101.io/ https://www.crypto101.io/ There are also some basic practical exercises (I don't believe the projects are technically related, but are in similar veins): https://cryptopals.com/ https://cryptopals.com/
- cpach 3y ago
  Cryptopals is a great resource! But if you come up to set five or so, then I’m not sure it could be called basic.
vient 3y ago
One more nice crypto book https://joyofcryptography.com https://joyofcryptography.com It goes more in depth of understanding mathematics behind but less in scope — there are no elliptic curves, for example.
mtreis86 3y ago
I learn best by breaking things. Here are a couple good books on cryptanalysis https://www.goodreads.com/book/show/56242724-codebreaking https://www.goodreads.com/book/show/56242724-codebreaking https://www.goodreads.com/book/show/17994.The_Code_Book https://www.goodreads.com/book/show/17994.The_Code_Book https://www.goodreads.com/book/show/98610.Colossus https://www.goodreads.com/book/show/98610.Colossus
- Eddy_Viscosity2 3y ago
  The code book was great, also recommend.
- dev_0 3y ago
  [dead]
- trotro 3y ago
  I also recommend https://cryptohack.org https://cryptohack.org to practice exploiting common cryptographic vulnerabilities.

174 points by seamac3 3y ago

IceHegel 3y ago

Is the latex code on github? The margins are a bit off.

dredmorbius 3y ago
Possiibly here: <https://nigelsmart.github.io/Crypto_Book/ https://nigelsmart.github.io/Crypto_Book/> Though that doesn't appear to be a code repo.
- gurjeet 3y ago
  I think this is what you're looking for: https://github.com/NigelSmart/nigelsmart.github.io/tree/master/Crypto_Book https://github.com/NigelSmart/nigelsmart.github.io/tree/mast...
  - dredmorbius 3y ago
    Thanks!

grog454 3y ago

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

ChrisArchitect 3y ago

(2011)

dredmorbius 3y ago
Based on what? I find Internet Archive's first capture in 2013: <https://web.archive.org/web/20230000000000*/https://www.cs.umd.edu/~waa/414-F11/IntroToCrypto.pdf https://web.archive.org/web/20230000000000*/https://www.cs.u...>
- NhanH 3y ago
  https://www.cs.umd.edu/~waa/UMD/CMSC414-F11.html https://www.cs.umd.edu/~waa/UMD/CMSC414-F11.html This is the class that links to the book. Fall 2011
  - dredmorbius 3y ago
    Thanks!
- _kst_ 3y ago
  $ 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 GMT
- Jtsummers 3y ago
  https://nigelsmart.github.io/Crypto_Book/ https://nigelsmart.github.io/Crypto_Book/ 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.

deleted 3y ago

[deleted]

obnauticus 3y ago

Tbh Cryptography Engineering by Niels Ferguson is a very good and practical intro to this topic.

a--n--b 3y ago
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.

xavdid 3y ago

Another good resource on intro crypto is @lvh's Crypto101 book: https://www.crypto101.io/ https://www.crypto101.io/ There are also some basic practical exercises (I don't believe the projects are technically related, but are in similar veins): https://cryptopals.com/ https://cryptopals.com/

cpach 3y ago
Cryptopals is a great resource! But if you come up to set five or so, then I’m not sure it could be called basic.

vient 3y ago

One more nice crypto book https://joyofcryptography.com https://joyofcryptography.com It goes more in depth of understanding mathematics behind but less in scope — there are no elliptic curves, for example.

mtreis86 3y ago

I learn best by breaking things. Here are a couple good books on cryptanalysis https://www.goodreads.com/book/show/56242724-codebreaking https://www.goodreads.com/book/show/56242724-codebreaking https://www.goodreads.com/book/show/17994.The_Code_Book https://www.goodreads.com/book/show/17994.The_Code_Book https://www.goodreads.com/book/show/98610.Colossus https://www.goodreads.com/book/show/98610.Colossus

Eddy_Viscosity2 3y ago
The code book was great, also recommend.
dev_0 3y ago
[dead]
trotro 3y ago
I also recommend https://cryptohack.org https://cryptohack.org to practice exploiting common cryptographic vulnerabilities.