Studying Cryptography

What maths / books do I need to refresh / learn / read to get into studying applied cryptography?

Dicrete Mathematics/Number Theory. The MIT has free lectures online. For studying cryptography I recommend the book Introduction to Modern Cryptography by Jonathan Katz and Yehuda Lindell.

E7 Lie-Groups Hodge Conjecture Surreal Number Theory Tesseract Packing Hairy Ball Theorem Zeeman Knot Theory but most importantly: the lainchan.org catalog, you stupid dickhead

>>21393 These aren't relevant to cryptography. >exceptional Lie groups >hodge conjecture >hairy ball theorem >surreal number theory all objects used in cryptography are discrete, these concepts are about smooth or at the very least uncountable objects

>>21394 Yes, obviously. Did you expect me to give OP a serious answer after he makes a stupid thread for a question that can be googled and that has been asked multiple times in the existing cryptography thread? And even if I would have wanted to help, how can I know what OPs current level of knowledge is? If he has never heard a math course in university, then of course the next steps are different from someone with a math degree but no experience in crypto. Ask stupid, effortless questions in the wrong place, get stupid answers.

>>21395 Well by OP's stupid thread you can infer his math is probably at the high school level, and that he probably won't care to read anything, or he will give up after chapter 1 when he's expected to do some mental work. You can also tell that he is impulsive and makes threads on a whim.

>>21425 In my defense I was pretty good at entry level linear algebra, david c lay's book was neat

https://cryptohack.org/ is a pretty good place to start. other than that, find a good linear algebra textbook and grind all of the exercises

>>21384 Well you need VERY good math for this.

Unless you go to stanford or israel and get a mentor there's really no point. Cryptography is for the jews only

>>21437 If it doesn’t teach definitions, then you’ll need something else. Modern crypto is 50-60% definitions. Pick up a simple book like Joy of Cryptography and work through all the exercises. If any math concept doesn’t make sense, read the relevant chapter from linear algebra done wrong or D&F and do all the exercises there.

>>21437 this site looks neat, thanks!

Handbook of Applied Cryptography https://cacr.uwaterloo.ca/hac/

>>21516 Would not recommend for solo work unless already familiar with crypto. Definitions are hidden when they are even there, little to no formalization, security guarantees for many schemes are not listed but rather adhoc arguments for protection against specific attacks are provided. Where can I use RSA PKE for instance? What guarantees do I get? All of this is missing, so I can't recommend as more than a reference guide for someone already familiar with these schemes.

I tried crypto hack and got filtered after the chinese remainder theorem problem do I need pre-req reading or is it over for me

>>21658 CRT at its simplest can be taught to anyone with some CS experience. I'd teach it as "Given a series of modulo equivalences for a single number you can use the extended euclidian (EE) to solve when the modulus are all pairwise coprime." Then all it is is applying the EE. The basic idea is that given any two coprime integers m and n there exists two coefficients a and b such that an + bm = 1 and this is found using the EE (take my word for this). Now let's see how we apply that to a simple congruence x =_n c x =_m d with m and n coprime again Well using the above equation for 1, we have c = c(1) = c(an + bm) so x =_n c(an + bm) =_n can + cbm =_n 0 + cbm =_n cbm Similarly, x =_m d(an + mb) =_m dan + dbm =_m dan + 0 =_m dan so x = dan + cbm is a solution as we see above! --- Test it for yourself. We can extend this to any number of equations by recursing by replacing the first two equations above with x =_{mn} dan + cbm Which is a smaller version of the original system as we replaced 2 equations with 1 and the next equation's modulus is still coprime to mn (take my word for this right now, but it's easy to see by looking at prime decomposition). But the full CRT may require group theory as a prereq.

>>21384 I only know theoretical stuffs. So this is my recommendation to study theoretical cryptography. For applied cryptography, I think it would still work omitting some steps. Elementary Number Theory -> Linear Algebra + Analysis -> Algebra + General Topology -> Commutative Algebra -> Algebraic Topology + Category Theory -> Algebraic Geometry + Algebraic Number Theory Logically, you don't actually need everything in these steps. For example, you won't use much analysis. But I highly doubt that anyone could understand open sets without studying episilon-delta. Thus although you won't use all of them, you still need the core facts of these subjects.

>>21662 I omitted Complex Analysis. You couldn't understand tons of algebraic geometry and elliptic curve stuffs without it. You can study it while studying algebra and general topology.

>>21662 This is only necessary if you want to intimately understand the constructions. In reality you need 1. Probability / basic combinatorics 2. Group/field/ring theory 3. Linear Algebra The rest is learned on the job and it abstracted away most of the time. If you ask people in crypto when the last time they used a sheaf, 99% of them will say "not that I realized". I guess I use algebraic varieties, but none of my lab-mates do.

>>21666 oops, and number theory duh...

>>21666 I guess it depends on the fields. For example, for cryptocurrencies I remember that Confidential Transaction is just a group homomorphism and at the end zk-SNARK just compare two conditional probabilities (the algorithm itself is fuarrrking complex though). However, it's true that some fields actually require higher number theory. I don't deny that those fields seem to be just number theory people doing number theory stuffs. But those fields make the foundations. So you can't totally dismiss them especially if you want to study more deeply. Anyway, so just studying for own's interest might be the best answer. Just do what you want. That's all.

>>21666 >>21662 How much lin alg do i need? a full book ala "David Lay, Steven Lay, Judi McDonald - Linear Algebra and Its Applications, Global Edition-Pearson (2021)" or a short introduction like in gilbert strang's calculus book?

>>21666 >>21667 Is "A Classical Introduction to Modern Number Theory" a good enough choice? What are some short and simple books on combinatorics and group theory aswell?

>>21677 Just use Hoffman & Kunze. Personally, for linear algebra I really like Finite-Dimensional Vector Spaces by Halmos, but you don't need that level. Also the book is more focused on functional analysis.

>>21677 >>21678 One book is never enough, but here are the books I'll suggest for (linear) algebra: Hefferon, Friedberg and Insel and Spence, Axler, Treil, Hoffman and Kunze, Dummit and Foote, Lang, Rotman, Hungerford. The first five are linear algebra focused. I suggest finding which of those five's presentation your brain groks and use that as your primary source. You'll do fine with any of them, but I don't like Axler personally (although people I know do). Then use the others as references and when you're done skim them to see if there's anything you missed. Don't start with Ireland and Kenneth for number theory as it assumes you already know basic group-field-ring theory. Use something like Silverman's "A Friendly Introduction to Number Theory" unless you tackle number theory after algebra, then Ireland and Kenneth is a fine choice. For combinatorics, I don't have a "formal" background in combinatorics like I do in the other topics. You just need to understand basic counting.

>>21680 Actually. Now that I'm thinking about it. I'd just stick with Dummit and Foote for group-field-ring theory. The other books are focused on the more mature mathematician.

>>21681 For algebra, Artin is also awesome. You can't use only his books though. For number theory, I recommend to read Disquisitiones Arithmeticae by Gauss after reading Silverman. That book is absolutely a classic. It still gives inspirations for mathematicians, like Barghava for example.

>>21679 >>21680 >>21681 >>21683 I'm on a time limit so if you had one book a CS midwit fool like me could understand for each topic which ones would you recommend

>>21384 I have a few PDFs to share.

>>21685 >Serious Cryptography Good. >Real-World Cryptography Terrible. >Cryptography Engineering Didn't read.

>>21686 Thanks for your input. Here's more

>>21687 Katz and Lindell is fine. I also suggest Boneh and Shoup. The other books aren't nearly rigorous enough for my tastes.

>>21770 also, to add on to my question, is there a book that's easier than nigel smarts entries?

>>21770 I'm going to ignore your question and tell you what the image is saying. This way we won't be confused about terminology. All integers can be decomposed into a collection of primes through "prime factorization". For instance, 15 can be decomposed as the collection {3,5} because 3 * 5 = 15 and furthermore, this decomposition is unique for all integers. Certain numbers form multisets where a number shows up multiple times in their decomposition like 45 = 3 * 3 * 5 giving a decomposition of {3,3,5}. We can then write any integer as a product of all the numbers in the decomposition as follows: N decomposes into n distinct primes p_1, p_2, p_3, ... and furthermore, each prime p_i shows up in the decomposition e_i times. For example, if we decompose 45, we get p_1 = 3, p_2 = 5, e_1 = 2, e_2 = 1. This is because 45 = 3 * 3 * 5 = 3^2 * 5^1 = (p_1)^(e_1) * (p_2) ^ (e_2). Now euler's totient function \phi(n) simply counts how many numbers between 0 and n are coprime to n (their only shared factor is 1). For instance, take 6. \phi(6) = 2 because 1 is coprime to every number (besides 0), 2 and 6 share a factor of 2, 3 and 6 share a factor of 3, 4 and 6 share a factor of 2, and 5 is coprime to 6. So the set of coprime numbers is {1,5} and the total number of them is 2. There is a shortcut to computing euler's totient function \phi(N) which uses the prime decomposition of a number N. Namely, if we want to compute \phi(N) where N is prime, we find that by definition of primality, there are no numbers sharing a divisor! That means that the set of coprime numbers (between 0 and N) to N is just {1,2,3,4,5,...,N-1} which means the set has size N-1 and \phi(N) = N-1. Now let N be a product of primes (i.e., N = p^e for some prime p and some positive exponent e). Then let's see what numbers are NOT relatively prime to it. Well, once again by the definition of primality, it's just all multiples of p. (take 9 for example = 3^2. The NON-coprime numbers are 3 and 6 which are exactly the multiples of 3) So it suffices to count how many of these exist. Well... Since N = p^e, then we have {p, 2p, 3p, ..., (p^{e-1})p} as all multiples of p less than p^e = N. There are also exactly p^{e-1} of them! This means that all the rest are coprime to N and there must be N - p^{e-1} = p^e - p^{e-1} number coprime to N implying that \phi(N) = p^e - p^{e-1} where N = p^e. Then there's one last piece of the puzzle. As it turns out, euler's totient function is multiplicative! That means that \phi(N) * \phi(M) = \phi(N * M) when M and N are coprime! (this goes in both directions. So we can start with \phi(M * N) and compute it as \phi(N) * \phi(M) or can start with \phi(N) and \phi(M) and infer the value of \phi(N * M)). The proof I know of this is pretty quick, but requires some number theory or ring theory, so just take my word for it. This means we now have all the tools we need to compute \phi(N) for any integer N! We first use our decomposition to split N into primes p_1, p_2, p_3, ... and their exponents e_1, e_2, e_3, ... Such that we can write N = (p_1)^(e_1) * (p_2)^(e_2) * (p_3)^(e_3) * ... Well... Prime numbers and their powers are coprime to other primes and their powers by the definition of primality (27 and 49 are coprime since 27 = 3^3 and 49 = 7^2), so each (p_i)^(e_i) are pairwise coprime. But we know how to compute \phi(p_i^e_i) and we know how to compute \phi(p_i^e_i * p_j^e_j) = \phi(p_i^e_i) * \phi(p_j^e_j), so we can simply recurse to compute \phi(N)! \phi(N) = \phi((p_1)^(e_1) * (p_2)^(e_2) * (p_3)^(e_3) * ...) = \phi((p_1)^(e_1)) * \phi((p_2)^(e_2)) * \phi((p_3)^(e_3)) * ... = (p_1^e_1 - p_1^{e_1-1}) * (p_2^e_2 - p_2^{e_2-1}) * (p_3^e_3 - p_3^{e_3-1}) * ... With some small manipulation, you arrive at the bottom equation in your image.

>>21772 > Since N = p^e, then we have {p, 2p, 3p, ..., (p^{e-1})p} as all multiples of p less than p^e = N. There are also exactly p^{e-1} of them! Oops, my brain was moving faster than my hands. The statement I meant to make was Since N = p^e, then we have that {p, 2p, 3p, ..., (p^{e-1})p} are all multiples of p up to and including N. Specifically, this means that there are p^{e-1} - 1 total multiples of p between 1 and N. Then we have a total of N-1 numbers between 0 and N and we are missing p^{e-1} - 1 of them as NON-coprimes, so we get (N-1)-(p^{e-1} - 1) = N - p^{e-1}.

But... why a u want learn crypt?